1 | // Copyright 2004 The Trustees of Indiana University. |
2 | |
3 | // Use, modification and distribution is subject to the Boost Software |
4 | // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at |
5 | // http://www.boost.org/LICENSE_1_0.txt) |
6 | |
7 | // Authors: Douglas Gregor |
8 | // Andrew Lumsdaine |
9 | #include <boost/graph/biconnected_components.hpp> |
10 | #include <boost/graph/adjacency_list.hpp> |
11 | #include <boost/core/lightweight_test.hpp> |
12 | #include <boost/lexical_cast.hpp> |
13 | #include <vector> |
14 | #include <iterator> |
15 | #include <iostream> |
16 | #include <algorithm> |
17 | #include <boost/graph/connected_components.hpp> |
18 | #include <boost/graph/random.hpp> |
19 | #include <boost/random/linear_congruential.hpp> |
20 | #include <fstream> |
21 | |
22 | using namespace boost; |
23 | |
24 | struct EdgeProperty |
25 | { |
26 | std::size_t component; |
27 | }; |
28 | |
29 | static bool any_errors = false; |
30 | |
31 | template < typename Graph, typename Vertex > |
32 | void check_articulation_points(const Graph& g, std::vector< Vertex > art_points) |
33 | { |
34 | std::vector< int > components(num_vertices(g)); |
35 | int basic_comps = connected_components(g, |
36 | make_iterator_property_map( |
37 | components.begin(), get(vertex_index, g), int())); |
38 | |
39 | std::vector< Vertex > art_points_check; |
40 | |
41 | typename graph_traits< Graph >::vertex_iterator vi, vi_end; |
42 | for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) |
43 | { |
44 | Graph g_copy(g); |
45 | Vertex victim = vertex(get(vertex_index, g, *vi), g_copy); |
46 | clear_vertex(victim, g_copy); |
47 | remove_vertex(victim, g_copy); |
48 | |
49 | int copy_comps = connected_components(g_copy, |
50 | make_iterator_property_map( |
51 | components.begin(), get(vertex_index, g_copy), int())); |
52 | |
53 | if (copy_comps > basic_comps) |
54 | art_points_check.push_back(*vi); |
55 | } |
56 | |
57 | std::sort(art_points.begin(), art_points.end()); |
58 | std::sort(art_points_check.begin(), art_points_check.end()); |
59 | |
60 | BOOST_TEST(art_points == art_points_check); |
61 | if (art_points != art_points_check) |
62 | { |
63 | std::cerr << "ERROR!" << std::endl; |
64 | std::cerr << "\tComputed: " ; |
65 | std::size_t i; |
66 | for (i = 0; i < art_points.size(); ++i) |
67 | std::cout << art_points[i] << ' '; |
68 | std::cout << std::endl << "\tExpected: " ; |
69 | for (i = 0; i < art_points_check.size(); ++i) |
70 | std::cout << art_points_check[i] << ' '; |
71 | std::cout << std::endl; |
72 | any_errors = true; |
73 | } |
74 | else |
75 | std::cout << "OK." << std::endl; |
76 | } |
77 | |
78 | typedef adjacency_list< listS, vecS, undirectedS, no_property, EdgeProperty > |
79 | Graph; |
80 | typedef graph_traits< Graph >::vertex_descriptor Vertex; |
81 | |
82 | bool test_graph(Graph& g) |
83 | { // Returns false on failure |
84 | std::vector< Vertex > art_points; |
85 | |
86 | std::cout << "Computing biconnected components & articulation points... " ; |
87 | std::cout.flush(); |
88 | |
89 | std::size_t num_comps = biconnected_components( |
90 | g, comp: get(p: &EdgeProperty::component, g), out: std::back_inserter(x&: art_points)) |
91 | .first; |
92 | |
93 | std::cout << "done.\n\t" << num_comps << " biconnected components.\n" |
94 | << "\t" << art_points.size() << " articulation points.\n" |
95 | << "\tTesting articulation points..." ; |
96 | std::cout.flush(); |
97 | |
98 | check_articulation_points(g, art_points); |
99 | |
100 | if (any_errors) |
101 | { |
102 | std::ofstream out("biconnected_components_test_failed.dot" ); |
103 | |
104 | out << "graph A {\n" |
105 | << " node[shape=\"circle\"]\n" ; |
106 | |
107 | for (std::size_t i = 0; i < art_points.size(); ++i) |
108 | { |
109 | out << art_points[i] << " [ style=\"filled\" ];" << std::endl; |
110 | } |
111 | |
112 | graph_traits< Graph >::edge_iterator ei, ei_end; |
113 | for (boost::tie(t0&: ei, t1&: ei_end) = edges(g_: g); ei != ei_end; ++ei) |
114 | out << source(e: *ei, g) << " -- " << target(e: *ei, g) << "[label=\"" |
115 | << g[*ei].component << "\"]\n" ; |
116 | out << "}\n" ; |
117 | } |
118 | |
119 | return any_errors; |
120 | } |
121 | |
122 | int main(int argc, char* argv[]) |
123 | { |
124 | std::size_t n = 100; |
125 | std::size_t m = 500; |
126 | std::size_t seed = 1; |
127 | |
128 | if (argc > 1) |
129 | n = lexical_cast< std::size_t >(arg: argv[1]); |
130 | if (argc > 2) |
131 | m = lexical_cast< std::size_t >(arg: argv[2]); |
132 | if (argc > 3) |
133 | seed = lexical_cast< std::size_t >(arg: argv[3]); |
134 | |
135 | { |
136 | Graph g(n); |
137 | minstd_rand gen(seed); |
138 | generate_random_graph(g, V: n, E: m, gen); |
139 | if (test_graph(g)) |
140 | return 1; |
141 | } |
142 | |
143 | { |
144 | Graph g(4); |
145 | add_edge(u: 2, v: 3, g_&: g); |
146 | add_edge(u: 0, v: 3, g_&: g); |
147 | add_edge(u: 0, v: 2, g_&: g); |
148 | add_edge(u: 1, v: 0, g_&: g); |
149 | if (test_graph(g)) |
150 | return 1; |
151 | } |
152 | |
153 | return boost::report_errors(); |
154 | } |
155 | |