1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
|
#ifndef ALLPATHS_SEARCH_H_
#define ALLPATHS_SEARCH_H_
#include "Common/UnorderedSet.h"
#include "Graph/Path.h"
#include <boost/tuple/tuple.hpp> // for boost::tie
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/graph_concepts.hpp>
#include <vector>
/** result of exhaustive path search from vertex A to vertex B */
template <class VertexT>
struct AllPathsSearchResult
{
public:
/** code indicating type of success/failure for search */
PathSearchResult resultCode;
/** number of edges traversed during search */
unsigned cost;
/** all paths from vertex A to vertex B (if successful) */
std::vector< Path<VertexT> > paths;
/** constructor */
AllPathsSearchResult() : resultCode(NO_PATH), cost(0) {}
};
template <class IncidenceGraph>
AllPathsSearchResult<typename boost::graph_traits<IncidenceGraph>::vertex_descriptor>
allPathsSearch(
const IncidenceGraph& g,
typename boost::graph_traits<IncidenceGraph>::vertex_descriptor start,
typename boost::graph_traits<IncidenceGraph>::vertex_descriptor goal,
unsigned maxPaths, unsigned minDepth, unsigned maxDepth, unsigned maxCost)
{
typedef typename boost::graph_traits<IncidenceGraph>::vertex_descriptor V;
typedef typename boost::graph_traits<IncidenceGraph>::out_edge_iterator EdgeIter;
typedef typename std::pair<EdgeIter,EdgeIter> EdgeIterPair;
unordered_set<V, hash<V> > visited;
Path<V> path;
std::vector<EdgeIterPair> eiStack;
unordered_set<V> cycleVertices;
path.push_back(start);
visited.insert(start);
eiStack.push_back(out_edges(start, g));
AllPathsSearchResult<V> result;
while(!path.empty() && result.cost <= maxCost) {
if (path.back() == goal &&
(minDepth == NO_LIMIT || (path.size() - 1) >= minDepth)) {
if (maxPaths != NO_LIMIT && result.paths.size() >= maxPaths) {
result.resultCode = TOO_MANY_PATHS;
return result;
}
if (!cycleVertices.empty()) {
result.resultCode = PATH_CONTAINS_CYCLE;
return result;
}
result.paths.push_back(path);
}
// find next unvisited node and append to path
while(!path.empty()) {
if ((maxDepth != NO_LIMIT && (path.size() - 1) >= maxDepth) ||
eiStack.back().first == eiStack.back().second)
{
visited.erase(path.back());
cycleVertices.erase(path.back());
path.pop_back();
eiStack.pop_back();
assert(path.empty() == eiStack.empty());
if (!path.empty())
eiStack.back().first++;
} else {
V v = target(*(eiStack.back().first), g);
if (visited.find(v) != visited.end()) {
cycleVertices.insert(v);
eiStack.back().first++;
} else {
path.push_back(v);
eiStack.push_back(out_edges(v, g));
visited.insert(v);
result.cost++;
break;
}
} // if ei != ei_end
} // while !path.empty()
} // while !path.empty()
if (result.cost > maxCost)
result.resultCode = MAX_COST_EXCEEDED;
else if (result.paths.empty())
result.resultCode = NO_PATH;
else
result.resultCode = FOUND_PATH;
return result;
}
template <class IncidenceGraph>
AllPathsSearchResult<typename boost::graph_traits<IncidenceGraph>::vertex_descriptor>
allPathsSearch(
const IncidenceGraph& g,
typename boost::graph_traits<IncidenceGraph>::vertex_descriptor start,
typename boost::graph_traits<IncidenceGraph>::vertex_descriptor goal)
{
return allPathsSearch(g, start, goal, NO_LIMIT, NO_LIMIT, NO_LIMIT, NO_LIMIT);
}
#endif
|
