-
Notifications
You must be signed in to change notification settings - Fork 0
/
BFS.hpp
82 lines (73 loc) · 2.47 KB
/
BFS.hpp
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
#pragma once
#include <set>
#include <memory>
namespace graph_tools {
class BFS {
public:
BFS(Graph* g = nullptr) :
_g(g),
_traversed(0)
{}
Graph*& graph() { return _g; }
void run(Graph::NodeID root, int iter, bool forward = true) {
_visited.clear();
_active.clear();
_visited.insert(root);
_active.insert(root);
_traversed = 0;
if (forward) {
run_forward(root, iter);
} else {
run_back(root, iter);
}
}
void run_forward(Graph::NodeID root, int iter) {
int i = 0;
while (!_active.empty() && i++ < iter) {
std::set<Graph::NodeID> _next;
for (auto src : _active) {
for (auto dst : _g->neighbors(src)) {
// skip visited
_traversed += 1;
if (_visited.find(dst) != _visited.end())
continue;
// update
_visited.insert(dst);
_next.insert(dst);
}
}
_active = _next;
}
}
void run_back(Graph::NodeID root, int iter) {
int i = 0;
Graph _r = _g->transpose();
while (!_active.empty() && i++ < iter) {
std::set<Graph::NodeID> _next;
for (Graph::NodeID dst = 0; dst < _g->num_nodes(); dst++) {
// skip visited
if (_visited.find(dst) != _visited.end()) continue;
for (auto src : _r.neighbors(dst)) {
_traversed += 1;
// skip inactive
if (_active.find(src) == _active.end()) continue;
// update
_visited.insert(dst);
_next.insert(dst);
break;
}
}
_active = _next;
}
}
public:
std::set<Graph::NodeID> & visited() { return _visited; }
std::set<Graph::NodeID> & active() { return _active; }
Graph::NodeID traversed() const { return _traversed; }
private:
Graph* _g;
std::set<Graph::NodeID> _visited;
std::set<Graph::NodeID> _active;
Graph::NodeID _traversed;
};
}