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
22using namespace boost;
23
24struct EdgeProperty
25{
26 std::size_t component;
27};
28
29static bool any_errors = false;
30
31template < typename Graph, typename Vertex >
32void 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
78typedef adjacency_list< listS, vecS, undirectedS, no_property, EdgeProperty >
79 Graph;
80typedef graph_traits< Graph >::vertex_descriptor Vertex;
81
82bool 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
122int 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

source code of boost/libs/graph/test/biconnected_components_test.cpp