]>
Commit | Line | Data |
---|---|---|
7c673cae | 1 | //======================================================================= |
f67539c2 | 2 | // Copyright 2002 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee, |
7c673cae FG |
3 | // |
4 | // Distributed under the Boost Software License, Version 1.0. (See | |
5 | // accompanying file LICENSE_1_0.txt or copy at | |
6 | // http://www.boost.org/LICENSE_1_0.txt) | |
7 | //======================================================================= | |
8 | ||
9 | #include <string> | |
10 | #include <boost/graph/adjacency_list.hpp> | |
11 | #include <boost/graph/undirected_dfs.hpp> | |
12 | #include <boost/cstdlib.hpp> | |
13 | #include <iostream> | |
14 | ||
15 | /* | |
16 | Example graph from Tarjei Knapstad. | |
17 | ||
18 | H15 | |
19 | | | |
20 | H8 C2 | |
21 | \ / \ | |
22 | H9-C0-C1 C3-O7-H14 | |
23 | / | | | |
24 | H10 C6 C4 | |
25 | / \ / \ | |
26 | H11 C5 H13 | |
27 | | | |
28 | H12 | |
29 | */ | |
30 | ||
f67539c2 TL |
31 | std::string name[] = { "C0", "C1", "C2", "C3", "C4", "C5", "C6", "O7", "H8", |
32 | "H9", "H10", "H11", "H12", "H13", "H14", "H15" }; | |
7c673cae FG |
33 | |
34 | struct detect_loops : public boost::dfs_visitor<> | |
35 | { | |
f67539c2 TL |
36 | template < class Edge, class Graph > void back_edge(Edge e, const Graph& g) |
37 | { | |
38 | std::cout << name[source(e, g)] << " -- " << name[target(e, g)] << "\n"; | |
39 | } | |
7c673cae FG |
40 | }; |
41 | ||
42 | int main(int, char*[]) | |
43 | { | |
f67539c2 TL |
44 | using namespace boost; |
45 | typedef adjacency_list< vecS, vecS, undirectedS, no_property, | |
46 | property< edge_color_t, default_color_type > > | |
47 | graph_t; | |
48 | typedef graph_traits< graph_t >::vertex_descriptor vertex_t; | |
49 | ||
50 | const std::size_t N = sizeof(name) / sizeof(std::string); | |
51 | graph_t g(N); | |
52 | ||
53 | add_edge(0, 1, g); | |
54 | add_edge(0, 8, g); | |
55 | add_edge(0, 9, g); | |
56 | add_edge(0, 10, g); | |
57 | add_edge(1, 2, g); | |
58 | add_edge(1, 6, g); | |
59 | add_edge(2, 15, g); | |
60 | add_edge(2, 3, g); | |
61 | add_edge(3, 7, g); | |
62 | add_edge(3, 4, g); | |
63 | add_edge(4, 13, g); | |
64 | add_edge(4, 5, g); | |
65 | add_edge(5, 12, g); | |
66 | add_edge(5, 6, g); | |
67 | add_edge(6, 11, g); | |
68 | add_edge(7, 14, g); | |
69 | ||
70 | std::cout << "back edges:\n"; | |
71 | detect_loops vis; | |
72 | undirected_dfs(g, | |
73 | root_vertex(vertex_t(0)) | |
74 | .visitor(vis) | |
75 | .edge_color_map(get(edge_color, g))); | |
76 | std::cout << std::endl; | |
77 | ||
78 | return boost::exit_success; | |
7c673cae | 79 | } |