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

   1 // (C) Copyright Jeremy Siek 2004
   2 // (C) Copyright Andrew Sutton 2009
   3 // Distributed under the Boost Software License, Version 1.0. (See
   4 // accompanying file LICENSE_1_0.txt or copy at
   5 // http://www.boost.org/LICENSE_1_0.txt)
   6
   7 #include <set>
   8
   9 #include <boost/random/mersenne_twister.hpp>
  10
  11 #include <boost/graph/adjacency_list.hpp>
  12 #include <boost/graph/subgraph.hpp>
  13 #include <boost/graph/random.hpp>
  14 #include "graph_test.hpp"
  15 #include <boost/graph/iteration_macros.hpp>
  16
  17 using namespace boost;
  18
  19 struct node
  20 {
  21     int color;
  22 };
  23
  24 struct arc
  25 {
  26     int weight;
  27 };
  28 typedef property<edge_index_t, std::size_t, arc> arc_prop;
  29
  30 typedef adjacency_list<
  31     vecS, vecS, bidirectionalS,
  32     node, arc_prop
  33 > Graph;
  34
  35 typedef subgraph<Graph> Subgraph;
  36 typedef graph_traits<Subgraph>::vertex_descriptor Vertex;
  37 typedef graph_traits<Subgraph>::edge_descriptor Edge;
  38 typedef graph_traits<Subgraph>::vertex_iterator VertexIter;
  39 typedef graph_traits<Subgraph>::edge_iterator EdgeIter;
  40
  41 int test_main(int, char*[])
  42 {
  43   mt19937 gen;
  44   for (int t = 0; t < 100; t += 5) {
  45     Subgraph g;
  46     int N = t + 2;
  47     std::vector<Vertex> vertex_set;
  48     std::vector< std::pair<Vertex, Vertex> > edge_set;
  49
  50     generate_random_graph(g, N, N * 2, gen,
  51                           std::back_inserter(vertex_set),
  52                           std::back_inserter(edge_set));
  53     graph_test< Subgraph > gt;
  54
  55     gt.test_incidence_graph(vertex_set, edge_set, g);
  56     gt.test_bidirectional_graph(vertex_set, edge_set, g);
  57     gt.test_adjacency_graph(vertex_set, edge_set, g);
  58     gt.test_vertex_list_graph(vertex_set, g);
  59     gt.test_edge_list_graph(vertex_set, edge_set, g);
  60     gt.test_adjacency_matrix(vertex_set, edge_set, g);
  61
  62     std::vector<Vertex> sub_vertex_set;
  63     std::vector<Vertex> sub_global_map;
  64     std::vector<Vertex> global_sub_map(num_vertices(g));
  65     std::vector< std::pair<Vertex, Vertex> > sub_edge_set;
  66
  67     Subgraph& g_s = g.create_subgraph();
  68
  69     const std::set<Vertex>::size_type Nsub = N/2;
  70
  71     // Collect a set of random vertices to put in the subgraph
  72     std::set<Vertex> verts;
  73     while (verts.size() < Nsub)
  74       verts.insert(random_vertex(g, gen));
  75
  76     for (std::set<Vertex>::iterator it = verts.begin();
  77         it != verts.end(); ++it) {
  78       Vertex v_global = *it;
  79       Vertex v = add_vertex(v_global, g_s);
  80       sub_vertex_set.push_back(v);
  81       sub_global_map.push_back(v_global);
  82       global_sub_map[v_global] = v;
  83     }
  84
  85     // compute induced edges
  86     BGL_FORALL_EDGES(e, g, Subgraph)
  87       if (container_contains(sub_global_map, source(e, g))
  88           && container_contains(sub_global_map, target(e, g)))
  89         sub_edge_set.push_back(std::make_pair(global_sub_map[source(e, g)],
  90                                               global_sub_map[target(e, g)]));
  91
  92     gt.test_incidence_graph(sub_vertex_set, sub_edge_set, g_s);
  93     gt.test_bidirectional_graph(sub_vertex_set, sub_edge_set, g_s);
  94     gt.test_adjacency_graph(sub_vertex_set, sub_edge_set, g_s);
  95     gt.test_vertex_list_graph(sub_vertex_set, g_s);
  96     gt.test_edge_list_graph(sub_vertex_set, sub_edge_set, g_s);
  97     gt.test_adjacency_matrix(sub_vertex_set, sub_edge_set, g_s);
  98
  99     if (num_vertices(g_s) == 0)
 100       return 0;
 101
 102     // Test property maps for vertices.
 103     typedef property_map<Subgraph, int node::*>::type ColorMap;
 104     ColorMap colors = get(&node::color, g_s);
 105     for(std::pair<VertexIter, VertexIter> r = vertices(g_s); r.first != r.second; ++r.first)
 106         colors[*r.first] = 0;
 107
 108     // Test property maps for edges.
 109     typedef property_map<Subgraph, int arc::*>::type WeightMap;
 110     WeightMap weights = get(&arc::weight, g_s);
 111     for(std::pair<EdgeIter, EdgeIter> r = edges(g_s); r.first != r.second; ++r.first) {
 112         weights[*r.first] = 12;
 113     }
 114
 115     // A regression test: the copy constructor of subgraph did not
 116     // copy one of the members, so local_edge->global_edge mapping
 117     // was broken.
 118     {
 119         Subgraph g;
 120         graph_traits<Graph>::vertex_descriptor v1, v2;
 121         v1 = add_vertex(g);
 122         v2 = add_vertex(g);
 123         add_edge(v1, v2, g);
 124
 125         Subgraph sub = g.create_subgraph(vertices(g).first, vertices(g).second);
 126
 127         graph_traits<Graph>::edge_iterator ei, ee;
 128         for (boost::tie(ei, ee) = edges(sub); ei != ee; ++ei) {
 129             // This used to segfault.
 130             get(&arc::weight, sub, *ei);
 131         }
 132     }
 133
 134   }
 135   return 0;
 136 }