SSSP.h
Go to the documentation of this file.
1 /*
2  * SSSP.h
3  *
4  * Created on: 15.04.2014
5  * Author: cls
6  */
7
8 #ifndef SSSP_H_
9 #define SSSP_H_
10
11 #include <set>
12
13 #include "../graph/Graph.h"
14 #include "../base/Algorithm.h"
15
16
17 namespace NetworKit {
18
23 class SSSP: public Algorithm {
24
25 public:
26
36  SSSP(const Graph& G, node source, bool storePaths=true, bool storeNodesSortedByDistance=false, node target = none);
37
38  virtual ~SSSP() = default;
39
41  virtual void run() = 0;
42
50  virtual std::vector<edgeweight> getDistances(bool moveOut=true);
51
57  edgeweight distance(node t) const;
58
64  bigfloat numberOfPaths(node t) const;
65
72  double _numberOfPaths(node t) const;
73
79  std::vector<node> getPredecessors(node t) const;
80
88  virtual std::vector<node> getPath(node t, bool forward=true) const;
89
97  virtual std::set<std::vector<node> > getPaths(node t, bool forward=true) const;
98
99  /* Returns the number of shortest paths to node t.*/
100  bigfloat getNumberOfPaths(node t) const;
101
112  virtual std::vector<node> getStack(bool moveOut=true);
113
123  virtual std::vector<node> getNodesSortedByDistance(bool moveOut=true);
124
125 protected:
126
127  const Graph& G;
128  const node source;
130  std::vector<edgeweight> distances;
131  std::vector<std::vector<node> > previous; // predecessors on shortest path
132  std::vector<bigfloat> npaths;
133
134  std::vector<node> nodesSortedByDistance;
135
136  bool storePaths;
138 };
139
140 inline edgeweight SSSP::distance(node t) const {
141  return distances[t];
142 }
143
145  if (! storePaths) {
146  throw std::runtime_error("number of paths have not been stored");
147  }
148  return npaths[t];
149 }
150
151 inline double SSSP::_numberOfPaths(node t) const {
152  if (! storePaths) {
153  throw std::runtime_error("number of paths have not been stored");
154  }
155  bigfloat limit = std::numeric_limits<double>::max();
156  if (npaths[t] > limit) {
157  throw std::overflow_error("number of paths do not fit into a double");
158  }
159  double res;
160  npaths[t].ToDouble(res);
161  return res;
162 }
163
164 inline std::vector<node> SSSP::getPredecessors(node t) const {
165  if (! storePaths) {
166  throw std::runtime_error("predecessors have not been stored");
167  }
168  return previous[t];
169 }
170
172  return npaths[t];
173 }
174
175 } /* namespace NetworKit */
176
177 #endif /* SSSP_H_ */
node target
Definition: SSSP.h:129
const node source
Definition: SSSP.h:128
bigfloat getNumberOfPaths(node t) const
Definition: SSSP.h:171
const Graph & G
Definition: SSSP.h:127
std::vector< bigfloat > npaths
Definition: SSSP.h:132
virtual std::vector< edgeweight > getDistances(bool moveOut=true)
Returns a vector of weighted distances from the source node, i.e.
Definition: SSSP.cpp:16
std::vector< node > getPredecessors(node t) const
Returns the predecessor nodes of t on all shortest paths from source to t.
Definition: SSSP.h:164
double _numberOfPaths(node t) const
Returns the number of shortest paths between the source node and t as a double value.
Definition: SSSP.h:151
Abstract base class for single-source shortest path algorithms.
Definition: SSSP.h:23
std::vector< node > nodesSortedByDistance
Definition: SSSP.h:134
virtual std::set< std::vector< node > > getPaths(node t, bool forward=true) const
Returns all shortest paths from source to t and an empty set if source and t are not connected...
Definition: SSSP.cpp:42
virtual std::vector< node > getStack(bool moveOut=true)
Returns a vector of nodes ordered in increasing distance from the source.
Definition: SSSP.cpp:92
bigfloat numberOfPaths(node t) const
Returns the number of shortest paths between the source node and t.
Definition: SSSP.h:144
std::vector< std::vector< node > > previous
Definition: SSSP.h:131
virtual ~SSSP()=default
Exact algorithm for computing the size of the largest clique in a graph.
Definition: MaxClique.h:24
virtual std::vector< node > getNodesSortedByDistance(bool moveOut=true)
Returns a vector of nodes ordered in increasing distance from the source.
Definition: SSSP.cpp:77
constexpr index none
Constants.
Definition: Globals.h:28
index node
Definition: Globals.h:23
edgeweight distance(node t) const
Returns the distance from the source node to t.
Definition: SSSP.h:140
std::vector< edgeweight > distances
Definition: SSSP.h:130
SSSP(const Graph &G, node source, bool storePaths=true, bool storeNodesSortedByDistance=false, node target=none)
Creates the SSSP class for G and source s.
Definition: SSSP.cpp:13
virtual void run()=0
Computes the shortest paths from the source to all other nodes.
bool storeNodesSortedByDistance
if true, store a vector of nodes ordered in increasing distance from the source
Definition: SSSP.h:137
Definition: Algorithm.h:9
virtual std::vector< node > getPath(node t, bool forward=true) const
Returns a shortest path from source to t and an empty path if source and t are not connected...
Definition: SSSP.cpp:20
A graph (with optional weights) and parallel iterator methods.
Definition: Graph.h:79
Big implements the floating point numbers.
Definition: ttmathbig.h:63
double edgeweight
Definition: Globals.h:24
bool storePaths
if true, paths are reconstructable and the number of paths is stored
Definition: SSSP.h:136