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

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