ceph/src/boost/libs/graph/test/biconnected_components_test.cpp

   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
  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
  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
 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 }