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
|
//=======================================================================
// Copyright 2024
// Author: Daniel Yang
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================
#include <vector>
#include <string>
#include <boost/config.hpp>
#include <boost/core/lightweight_test.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/undirected_dfs.hpp>
using Graph = boost::adjacency_list<
boost::vecS,
boost::vecS,
boost::undirectedS,
boost::no_property,
boost::property<boost::edge_color_t, boost::default_color_type>>;
using Vertex = boost::graph_traits<Graph>::vertex_descriptor;
using Edge = boost::graph_traits<Graph>::edge_descriptor;
struct DFSVisitorLogger : boost::default_dfs_visitor {
std::vector<std::string> &log;
DFSVisitorLogger(std::vector<std::string> &log) : log(log) {}
void log_vertex(const Vertex v, const std::string &event) {
log.push_back("vertex " + std::to_string(v) + " " + event);
}
void log_edge(const Edge e, const std::string &event, const Graph &g) {
log.push_back("edge (" + std::to_string(boost::source(e, g)) + "," + std::to_string(boost::target(e, g)) + ") " + event);
}
void discover_vertex(Vertex v, const Graph &g) {
log_vertex(v, "discovered");
}
void finish_vertex(Vertex v, const Graph &g) {
log_vertex(v, "finished");
}
void examine_edge(Edge e, const Graph &g) {
log_edge(e, "examined", g);
}
void tree_edge(Edge e, const Graph &g) {
log_edge(e, "tree", g);
}
void back_edge(Edge e, const Graph &g) {
log_edge(e, "back", g);
}
void forward_or_cross_edge(Edge e, const Graph &g) {
log_edge(e, "forward_cross", g);
}
void finish_edge(Edge e, const Graph &g) {
log_edge(e, "finished", g);
}
};
int main() {
Graph g(3);
boost::add_edge(0, 1, g);
boost::add_edge(1, 2, g);
std::vector<std::string> expected_answer = {
"vertex 0 discovered",
"edge (0,1) examined",
"edge (0,1) tree",
"vertex 1 discovered",
"edge (1,0) examined",
"edge (1,0) finished",
"edge (1,2) examined",
"edge (1,2) tree",
"vertex 2 discovered",
"edge (2,1) examined",
"edge (2,1) finished",
"vertex 2 finished",
"edge (1,2) finished",
"vertex 1 finished",
"edge (0,1) finished",
"vertex 0 finished",
};
std::vector<std::string> actual_answer;
// run undirected_dfs
DFSVisitorLogger dfs_visitor_logger(actual_answer);
boost::undirected_dfs(g,
boost::visitor(dfs_visitor_logger)
.edge_color_map(boost::get(boost::edge_color, g)));
// check if all vertices and edges have been visited in the correct order
BOOST_TEST(expected_answer.size() == actual_answer.size());
if (expected_answer.size() == actual_answer.size()) {
for (int i = 0; i < expected_answer.size(); ++i) {
BOOST_TEST(expected_answer[i] == actual_answer[i]);
}
}
return boost::report_errors();
}
|
