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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
|
#ifndef CONSTRAINED_BFS_VISITOR_H
#define CONSTRAINED_BFS_VISITOR_H
#include "Common/UnorderedMap.h"
#include "Common/IOUtil.h"
#include "Graph/BreadthFirstSearch.h"
#include "Graph/DefaultColorMap.h"
#include "Graph/Path.h"
#include "Graph/HashGraph.h"
#include "Graph/AllPathsSearch.h"
#include <boost/graph/graph_traits.hpp>
#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
template <typename G>
class ConstrainedBFSVisitor : public DefaultBFSVisitor<G>
{
public:
typedef typename boost::graph_traits<G>::vertex_descriptor V;
typedef typename boost::graph_traits<G>::edge_descriptor E;
typedef unsigned short depth_t;
private:
typedef std::vector<V> Predecessors;
typedef unordered_map<V, unsigned, hash<V> > OutDegreeMap;
typedef unordered_map<V, depth_t, hash<V> > DepthMap;
HashGraph<V> m_traversalGraph;
OutDegreeMap m_outDegree;
DepthMap m_depthMap;
V m_start;
V m_goal;
depth_t m_minDepth;
depth_t m_maxDepth;
unsigned m_maxBranches;
DefaultColorMap<G>& m_colorMap;
bool m_bFoundGoal;
depth_t m_maxDepthVisited;
unsigned m_branches;
bool m_tooManyBranches;
public:
ConstrainedBFSVisitor(
const V& start,
const V& goal,
depth_t minDepth,
depth_t maxDepth,
unsigned maxBranches,
DefaultColorMap<G>& colorMap) :
m_start(start),
m_goal(goal),
m_minDepth(minDepth),
m_maxDepth(maxDepth),
m_maxBranches(maxBranches),
m_colorMap(colorMap),
m_bFoundGoal(false),
m_maxDepthVisited(0),
m_branches(1),
m_tooManyBranches(false) {}
#if 0
// for debugging
BFSVisitorResult examine_vertex(const V& v, const G& g)
{
std::cout << "visiting vertex: " << v << "\n";
return BFS_SUCCESS;
}
#endif
BFSVisitorResult examine_edge(const E& e, const G& g)
{
V u = source(e, g);
V v = target(e, g);
#if 0
// for debugging
std::cout << "visiting edge: (" << u << ", " << v << ")\n";
#endif
if (m_tooManyBranches) {
put(m_colorMap, v, boost::black_color);
return BFS_ABORT_SEARCH;
}
if (v == m_goal)
m_bFoundGoal = true;
// record history of traversal, so that we can trace
// backwards from goal to start in pathsToGoal()
add_edge(v, u, m_traversalGraph);
// track depth of nodes and go no deeper than m_maxDepth
if (get(m_colorMap, v) == boost::white_color) // tree edge
m_depthMap[v] = m_depthMap[u] + 1;
if (m_depthMap[v] >= m_maxDepth)
put(m_colorMap, v, boost::black_color);
if (m_depthMap[v] > m_maxDepthVisited)
m_maxDepthVisited = m_depthMap[v];
// track number of branches and abort if we exceed m_maxBranches
if (m_maxBranches != NO_LIMIT && ++m_outDegree[u] > 1)
m_branches++;
if (m_maxBranches != NO_LIMIT && m_branches > m_maxBranches) {
m_tooManyBranches = true;
put(m_colorMap, v, boost::black_color);
}
return BFS_SUCCESS;
}
AllPathsSearchResult<V> uniquePathToGoal()
{
AllPathsSearchResult<V> result = pathsToGoal(1);
return result;
}
AllPathsSearchResult<V> pathsToGoal(unsigned maxPaths)
{
AllPathsSearchResult<V> result;
if (m_tooManyBranches) {
result.resultCode = TOO_MANY_BRANCHES;
return result;
}
else if (!m_bFoundGoal) {
result.resultCode = NO_PATH;
return result;
}
result = allPathsSearch(m_traversalGraph, m_goal, m_start,
maxPaths, m_minDepth, m_maxDepth, NO_LIMIT);
if (result.resultCode == FOUND_PATH) {
for (unsigned i = 0; i < result.paths.size(); i++)
reverse(result.paths[i].begin(), result.paths[i].end());
}
return result;
}
depth_t getMaxDepthVisited()
{
return m_maxDepthVisited;
}
};
#endif /* CONSTRAINED_BFS_VISITOR_H */
|
