All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
AllSimplePaths.h
Go to the documentation of this file.
1 /*
2 * AllSimplePaths.h
3 *
4 * Created on: 23.06.2017
5 * Author: Eugenio Angriman
6 */
7 
8 #ifndef AllSimplePaths_H_
9 #define AllSimplePaths_H_
10 
11 #include "../graph/Graph.h"
12 #include "../base/Algorithm.h"
13 
14 
15 namespace NetworKit {
16 
22 
23  public:
24 
34 
35  ~AllSimplePaths() = default;
36 
40  void run();
41 
46 
47  /*
48  * This method returns a vector that contains all the simple paths from a source node to a target node repepresented by vectors. Each path contains the source node as the first element and the target node as the last element.
49  */
50  std::vector<std::vector<node>> getAllSimplePaths();
51 
52  /*
53  * This method iterates over all the simple paths and it is far more efficient than calling getAllSimplePaths().
54  */
55  template<typename L> void forAllSimplePaths(L handle);
56 
57  /*
58  * This method iterates in parallel over all the simple paths and it is far more efficient than calling getAllSimplePaths().
59  */
60  template<typename L> void parallelForAllSimplePaths(L handle);
61 
62 
63  protected:
64 
65  // This method computes all the paths after a reverse BFS from the target node and a normal BFS from the source node.
66  void computePaths();
67 
68  // This method returns a queue that contains all the nodes that could be part of a path from the source to the target that crosses @s.
69  std::vector<node>* getAvailableSources(node s, count pathLength = 0);
70 
71  // The graph
72  const Graph& G;
73  // The source node
75  // The target node
77  // The cutoff i.e. maximum length of paths from source to target. It is optional.
79 
80  // This vector contains the distance from each node to the target node.
81  std::vector<count> distanceToTarget;
82  // This vector contains the distance from the source node to each node.
83  std::vector<count> distanceFromSource;
84  // This vector contains all the possible paths from source to target.
85  std::vector<std::vector<node>> paths;
86 
87  // Whether the run method as been called or not.
88  bool hasRun = false;
89  };
90 
92  if (!hasRun) {
93  throw std::runtime_error("run method has not been called");
94  }
95  return paths.size();
96  }
97 
98  inline std::vector<std::vector<node>> AllSimplePaths::getAllSimplePaths() {
99  if (!hasRun) {
100  throw std::runtime_error("run method has not been called");
101  }
102  return paths;
103  }
104 
105  template<typename L>
107  if (!hasRun) {
108  throw std::runtime_error("run method has not been called");
109  }
110  for (std::vector<std::vector<node>>::iterator it = paths.begin() ; it != paths.end(); ++it) {
111  handle(*it);
112  }
113  }
114 
115  template<typename L>
117  if (!hasRun) {
118  throw std::runtime_error("run method has not been called");
119  }
120  #pragma omp parallel for schedule(guided)
121  for (count i = 0; i < paths.size(); ++i) {
122  handle(paths[i]);
123  }
124  }
125 
126 } /* namespace NetworKit */
127 
128 #endif /* AllSimplePaths_H_ */
std::vector< count > distanceFromSource
Definition: AllSimplePaths.h:83
AllSimplePaths(const Graph &G, node source, node target, count cutoff=none)
Creates the AllSimplePaths class for G, source s and target t.
Definition: AllSimplePaths.cpp:15
void run()
This method computes all possible paths from a given source node to a target node.
Definition: AllSimplePaths.cpp:40
void forAllSimplePaths(L handle)
Definition: AllSimplePaths.h:106
const Graph & G
Definition: AllSimplePaths.h:72
std::vector< node > * getAvailableSources(node s, count pathLength=0)
Definition: AllSimplePaths.cpp:207
Determines all the possible simple paths from a given source node to a target node of a directed unwe...
Definition: AllSimplePaths.h:21
void parallelForAllSimplePaths(L handle)
Definition: AllSimplePaths.h:116
void computePaths()
Definition: AllSimplePaths.cpp:113
node target
Definition: AllSimplePaths.h:76
count numberOfSimplePaths()
This method returns the number of simple paths from the source node to the target node...
Definition: AllSimplePaths.h:91
uint64_t count
Definition: Globals.h:21
std::vector< count > distanceToTarget
Definition: AllSimplePaths.h:81
constexpr index none
Constants.
Definition: Globals.h:28
std::vector< std::vector< node > > paths
Definition: AllSimplePaths.h:85
index node
Definition: Globals.h:23
std::vector< std::vector< node > > getAllSimplePaths()
Definition: AllSimplePaths.h:98
bool hasRun
Definition: AllSimplePaths.h:88
A graph (with optional weights) and parallel iterator methods.
Definition: Graph.h:79
node source
Definition: AllSimplePaths.h:74
count cutoff
Definition: AllSimplePaths.h:78