123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148 |
- // 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 (boost::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;
- }
- typedef adjacency_list<listS, vecS, undirectedS,
- no_property, EdgeProperty> Graph;
- typedef graph_traits<Graph>::vertex_descriptor Vertex;
- bool test_graph(Graph& g) { // Returns false on failure
- 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 (boost::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 any_errors;
- }
-
- 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]);
- {
- Graph g(n);
- minstd_rand gen(seed);
- generate_random_graph(g, n, m, gen);
- if (test_graph(g)) return 1;
- }
- {
- Graph g(4);
- add_edge(2, 3, g);
- add_edge(0, 3, g);
- add_edge(0, 2, g);
- add_edge(1, 0, g);
- if (test_graph(g)) return 1;
- }
- return 0;
- }
|