All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
APSP.h
Go to the documentation of this file.
1 /*
2  * APSP.h
3  *
4  * Created on: 07.07.2015
5  * Author: Arie Slobbe
6  */
7 
8 #ifndef APSP_H_
9 #define APSP_H_
10 
11 #include "../graph/Graph.h"
12 #include "../base/Algorithm.h"
13 
14 namespace NetworKit {
15 
20 class APSP: public Algorithm {
21 
22 public:
23 
29  APSP(const Graph& G);
30 
31  virtual ~APSP() = default;
32 
34  void run() override;
35 
39  virtual std::string toString() const override;
40 
46  std::vector<std::vector<edgeweight> > getDistances() const {if (!hasRun) throw std::runtime_error("Call run method first"); return distances;}
47 
48 
53  edgeweight getDistance(node u, node v) const {if (!hasRun) throw std::runtime_error("Call run method first"); return distances[u][v];}
54 
58  virtual bool isParallel() const override { return true; }
59 
60 
61 protected:
62 
63  const Graph& G;
64  std::vector<std::vector<edgeweight> > distances;
65 };
66 
67 } /* namespace NetworKit */
68 
69 #endif /* APSP_H_ */
virtual std::string toString() const override
Definition: APSP.cpp:36
std::vector< std::vector< edgeweight > > distances
Definition: APSP.h:64
edgeweight getDistance(node u, node v) const
Returns the distance from u to v or infinity if u and v are not connected.
Definition: APSP.h:53
virtual bool isParallel() const override
Definition: APSP.h:58
bool hasRun
A boolean variable indicating whether an algorithm has finished its computation or not...
Definition: Algorithm.h:14
virtual ~APSP()=default
index node
Definition: Globals.h:23
void run() override
Computes the shortest paths from each node to all other nodes.
Definition: APSP.cpp:17
const Graph & G
Definition: APSP.h:63
Class for all-pair shortest path algorithm.
Definition: APSP.h:20
std::vector< std::vector< edgeweight > > getDistances() const
Returns a vector of weighted distances between node pairs.
Definition: APSP.h:46
Definition: Algorithm.h:9
A graph (with optional weights) and parallel iterator methods.
Definition: Graph.h:79
APSP(const Graph &G)
Creates the APSP class for G.
Definition: APSP.cpp:15
double edgeweight
Definition: Globals.h:24