text: // 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;
  }
  