mirror of
https://github.com/boostorg/graph.git
synced 2025-05-09 23:14:00 +00:00
105 lines
3.2 KiB
C++
105 lines
3.2 KiB
C++
//=======================================================================
|
|
// 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();
|
|
}
|