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 >
check_articulation_points(const Graph & g,std::vector<Vertex> art_points)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
test_graph(Graph & g)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, get(&EdgeProperty::component, g), std::back_inserter(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(ei, ei_end) = edges(g); ei != ei_end; ++ei)
114 out << source(*ei, g) << " -- " << target(*ei, g) << "[label=\""
115 << g[*ei].component << "\"]\n";
116 out << "}\n";
117 }
118
119 return any_errors;
120 }
121
main(int argc,char * argv[])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 >(argv[1]);
130 if (argc > 2)
131 m = lexical_cast< std::size_t >(argv[2]);
132 if (argc > 3)
133 seed = lexical_cast< std::size_t >(argv[3]);
134
135 {
136 Graph g(n);
137 minstd_rand gen(seed);
138 generate_random_graph(g, n, m, gen);
139 if (test_graph(g))
140 return 1;
141 }
142
143 {
144 Graph g(4);
145 add_edge(2, 3, g);
146 add_edge(0, 3, g);
147 add_edge(0, 2, g);
148 add_edge(1, 0, g);
149 if (test_graph(g))
150 return 1;
151 }
152
153 return boost::report_errors();
154 }
155