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/test/minimal.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 check_articulation_points(const Graph& g, std::vector<Vertex> art_points)
34 {
35 std::vector<int> components(num_vertices(g));
36 int basic_comps =
37 connected_components(g,
38 make_iterator_property_map(components.begin(),
39 get(vertex_index, g),
40 int()));
41
42 std::vector<Vertex> art_points_check;
43
44 typename graph_traits<Graph>::vertex_iterator vi, vi_end;
45 for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
46 Graph g_copy(g);
47 Vertex victim = vertex(get(vertex_index, g, *vi), g_copy);
48 clear_vertex(victim, g_copy);
49 remove_vertex(victim, g_copy);
50
51 int copy_comps =
52 connected_components
53 (g_copy,
54 make_iterator_property_map(components.begin(),
55 get(vertex_index, g_copy),
56 int()));
57
58 if (copy_comps > basic_comps)
59 art_points_check.push_back(*vi);
60 }
61
62 std::sort(art_points.begin(), art_points.end());
63 std::sort(art_points_check.begin(), art_points_check.end());
64
65 BOOST_CHECK(art_points == art_points_check);
66 if (art_points != art_points_check) {
67 std::cerr << "ERROR!" << std::endl;
68 std::cerr << "\tComputed: ";
69 std::size_t i;
70 for (i = 0; i < art_points.size(); ++i)
71 std::cout << art_points[i] << ' ';
72 std::cout << std::endl << "\tExpected: ";
73 for (i = 0; i < art_points_check.size(); ++i)
74 std::cout << art_points_check[i] << ' ';
75 std::cout << std::endl;
76 any_errors = true;
77 } else std::cout << "OK." << std::endl;
78 }
79
80 typedef adjacency_list<listS, vecS, undirectedS,
81 no_property, EdgeProperty> Graph;
82 typedef graph_traits<Graph>::vertex_descriptor Vertex;
83
test_graph(Graph & g)84 bool test_graph(Graph& g) { // Returns false on failure
85 std::vector<Vertex> art_points;
86
87 std::cout << "Computing biconnected components & articulation points... ";
88 std::cout.flush();
89
90 std::size_t num_comps =
91 biconnected_components(g,
92 get(&EdgeProperty::component, g),
93 std::back_inserter(art_points)).first;
94
95 std::cout << "done.\n\t" << num_comps << " biconnected components.\n"
96 << "\t" << art_points.size() << " articulation points.\n"
97 << "\tTesting articulation points...";
98 std::cout.flush();
99
100 check_articulation_points(g, art_points);
101
102 if (any_errors) {
103 std::ofstream out("biconnected_components_test_failed.dot");
104
105 out << "graph A {\n" << " node[shape=\"circle\"]\n";
106
107 for (std::size_t i = 0; i < art_points.size(); ++i) {
108 out << art_points[i] << " [ style=\"filled\" ];" << std::endl;
109 }
110
111 graph_traits<Graph>::edge_iterator ei, ei_end;
112 for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
113 out << source(*ei, g) << " -- " << target(*ei, g)
114 << "[label=\"" << g[*ei].component << "\"]\n";
115 out << "}\n";
116 }
117
118 return any_errors;
119 }
120
test_main(int argc,char * argv[])121 int test_main(int argc, char* argv[])
122 {
123 std::size_t n = 100;
124 std::size_t m = 500;
125 std::size_t seed = 1;
126
127 if (argc > 1) n = lexical_cast<std::size_t>(argv[1]);
128 if (argc > 2) m = lexical_cast<std::size_t>(argv[2]);
129 if (argc > 3) seed = lexical_cast<std::size_t>(argv[3]);
130
131 {
132 Graph g(n);
133 minstd_rand gen(seed);
134 generate_random_graph(g, n, m, gen);
135 if (test_graph(g)) return 1;
136 }
137
138 {
139 Graph g(4);
140 add_edge(2, 3, g);
141 add_edge(0, 3, g);
142 add_edge(0, 2, g);
143 add_edge(1, 0, g);
144 if (test_graph(g)) return 1;
145 }
146
147 return 0;
148 }
149