|
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
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
|
#ifndef DATA_FORMATS_MATH_GRAPH_WALKER_H
#define DATA_FORMATS_MATH_GRAPH_WALKER_H
#include "DataFormats/Math/interface/Graph.h"
#include <queue>
#include <vector>
namespace math {
/** a walker for an acyclic directed multigraph */
template <class N, class E>
class GraphWalker {
public:
using index_type = typename math::Graph<N, E>::index_type;
using index_result = typename math::Graph<N, E>::index_result;
using edge_type = typename math::Graph<N, E>::edge_type;
using edge_list = typename math::Graph<N, E>::edge_list;
using edge_iterator = typename math::Graph<N, E>::edge_iterator;
using const_edge_iterator = typename math::Graph<N, E>::const_edge_iterator;
// only a const-edge_range!
using edge_range = std::pair<const_edge_iterator, const_edge_iterator>;
using stack_type = std::vector<edge_range>;
using bfs_type = std::queue<edge_type>;
using result_type = bool;
using value_type = typename math::Graph<N, E>::value_type;
public:
//! creates a walker rooted by the first candidate root found in the underlying Graph
GraphWalker(const Graph<N, E> &);
//! creates a walker rooted by the node given
GraphWalker(const Graph<N, E> &, const N &);
GraphWalker() = delete;
// operations
result_type firstChild();
result_type nextSibling();
result_type parent();
result_type next();
inline value_type current() const;
result_type next_bfs();
value_type current_bfs() const;
void reset();
const stack_type &stack() const { return stack_; }
protected:
// stack_.back().first corresponds to index of the current node!
stack_type stack_; // hierarchical stack used in navigation
bfs_type queue_; // breath first search queue
edge_list root_; // root of the walker
const Graph<N, E> &graph_;
};
template <class N, class E>
GraphWalker<N, E>::GraphWalker(const Graph<N, E> &g) : graph_(g) { // complexity = (no nodes) * (no edges)
graph_.findRoots(root_);
stack_.emplace_back(edge_range(root_.begin(), root_.end()));
if (!root_.empty()) {
queue_.push(root_[0]);
}
}
template <class N, class E>
GraphWalker<N, E>::GraphWalker(const Graph<N, E> &g, const N &root) : graph_(g) {
index_result rr = graph_.nodeIndex(root);
if (!rr.second) // no such root node, no walker can be created!
throw root;
root_.emplace_back(edge_type(rr.first, 0));
stack_.emplace_back(edge_range(root_.begin(), root_.end()));
queue_.push(root_[0]);
}
template <class N, class E>
typename GraphWalker<N, E>::value_type GraphWalker<N, E>::current() const {
const edge_range &er = stack_.back();
return value_type(graph_.nodeData(er.first->first), graph_.edgeData(er.first->second));
}
template <class N, class E>
typename GraphWalker<N, E>::value_type GraphWalker<N, E>::current_bfs() const {
const edge_type &e = queue_.front();
return value_type(graph_.nodeData(e.first), graph_.edgeData(e.second));
}
template <class N, class E>
void GraphWalker<N, E>::reset() {
stack_.clear();
stack_.emplace_back(edge_range(root_.begin(), root_.end()));
queue_.clear();
if (root_.size()) {
queue_.push(root_[0]);
}
}
template <class N, class E>
typename GraphWalker<N, E>::result_type GraphWalker<N, E>::firstChild() {
result_type result = false;
const edge_range &adjEdges = graph_.edges(stack_.back().first->first);
if (adjEdges.first != adjEdges.second) {
stack_.emplace_back(adjEdges);
result = true;
}
return result;
}
template <class N, class E>
typename GraphWalker<N, E>::result_type GraphWalker<N, E>::nextSibling() {
result_type result = false;
edge_range &siblings = stack_.back();
if (siblings.first != (siblings.second - 1)) {
++siblings.first;
result = true;
}
return result;
}
template <class N, class E>
typename GraphWalker<N, E>::result_type GraphWalker<N, E>::parent() {
result_type result = false;
if (stack_.size() > 1) {
stack_.pop_back();
result = true;
}
return result;
}
template <class N, class E>
typename GraphWalker<N, E>::result_type GraphWalker<N, E>::next() {
result_type result = false;
if (firstChild()) {
result = true;
} else if (stack_.size() > 1 && nextSibling()) {
result = true;
} else {
while (parent()) {
if (stack_.size() > 1 && nextSibling()) {
result = true;
break;
}
}
}
return result;
}
template <class N, class E>
typename GraphWalker<N, E>::result_type GraphWalker<N, E>::next_bfs() {
result_type result(false);
if (!queue_.empty()) {
const edge_type &e = queue_.front();
const edge_range &er = graph_.edges(e.first);
const_edge_iterator it(er.first), ed(er.second);
for (; it != ed; ++it) {
queue_.push(*it);
}
queue_.pop();
if (!queue_.empty()) {
result = true;
}
}
return result;
}
} // namespace math
#endif
|