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