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