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

   1 // (C) Copyright Andrew Sutton 2009
   2 //
   3 // Use, modification and distribution are subject to the
   4 // Boost Software License, Version 1.0 (See accompanying file
   5 // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
   6
   7 #include <iostream>
   8 #include <string>
   9 #include <boost/graph/adjacency_list.hpp>
  10
  11 #include "../../../../../gpld/common/typestr.hpp"
  12
  13 using namespace std;
  14 using namespace boost;
  15
  16 // The purpose of this test is simply to provide a testing ground for the
  17 // invalidation of iterators and descriptors.
  18
  19 template <typename Graph>
  20 void make_graph(Graph& g)
  21 {
  22     // Build a simple (barbell) graph.
  23     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
  24     Vertex u = add_vertex(10, g);
  25     Vertex v = add_vertex(20, g);
  26     add_edge(u, v, 100, g);
  27 }
  28
  29 // Invalid iterators and descriptors will cause a segfault.
  30 template <typename Graph, typename Iterator, typename Descriptor>
  31 void test(Graph& g, Iterator i, Descriptor d, string const& str)
  32 {
  33     int x;
  34     cout << "... " << str << " iter" << endl;
  35     x = g[*i];
  36 //     cout << "... " << x << endl;
  37     cout << "... " << str << " desc" << endl;
  38     x = g[d];
  39 //     cout << "... " << x << endl;
  40 }
  41
  42 template <typename Graph>
  43 void invalidate_edges()
  44 {
  45     typedef typename graph_traits<Graph>::edge_descriptor Edge;
  46     typedef typename graph_traits<Graph>::edge_iterator EdgeIterator;
  47
  48     Graph g;
  49     make_graph(g);
  50
  51     // The actual test. These are valid here.
  52     EdgeIterator i = edges(g).first;
  53     Edge e = *i;
  54
  55     // Add a vertex, see what breaks.
  56     add_vertex(g);
  57     test(g, i, e, "edges");
  58 };
  59
  60 template <typename Graph>
  61 void invalidate_vertices()
  62 {
  63     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
  64     typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
  65
  66     Graph g;
  67     make_graph(g);
  68
  69     // The actual test. These are valid here.
  70     VertexIterator i = vertices(g).first;
  71     Vertex v = *i;
  72
  73     // Add a vertex, see what breaks.
  74     add_vertex(g);
  75     test(g, i, v, "vertices");
  76 }
  77
  78 template <typename Graph>
  79 void invalidate_out_edges()
  80 {
  81     typedef typename graph_traits<Graph>::edge_descriptor Edge;
  82     typedef typename graph_traits<Graph>::out_edge_iterator OutIterator;
  83
  84     Graph g;
  85     make_graph(g);
  86
  87     // The actual test. These are valid here.
  88     OutIterator i = out_edges(*vertices(g).first, g).first;
  89     Edge e = *i;
  90
  91     // Add a vertex, see what breaks.
  92     add_vertex(g);
  93     test(g, i, e, "out edges");
  94 }
  95
  96 template <typename Graph>
  97 void invalidate_adj_verts()
  98 {
  99     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
 100     typedef typename graph_traits<Graph>::adjacency_iterator AdjIterator;
 101
 102     Graph g;
 103     make_graph(g);
 104
 105     // The actual test. These are valid here.
 106     AdjIterator i = adjacent_vertices(*vertices(g).first, g).first;
 107     Vertex v = *i;
 108
 109     // Add a vertex, see what breaks.
 110     add_vertex(g);
 111     test(g, i, v, "adjacent vertices");
 112 }
 113
 114
 115 int main()
 116 {
 117     typedef adjacency_list<vecS, vecS, undirectedS, int, int> VVU;
 118     cout << "vecS vecS undirectedS" << endl;
 119     invalidate_vertices<VVU>();
 120     invalidate_edges<VVU>();
 121     invalidate_out_edges<VVU>();
 122     invalidate_adj_verts<VVU>();
 123
 124     typedef adjacency_list<vecS, vecS, bidirectionalS, int, int> VVB;
 125     cout << "vecS vecS bidirectionals" << endl;
 126     invalidate_vertices<VVB>();
 127     invalidate_edges<VVB>();
 128     invalidate_out_edges<VVB>();
 129     invalidate_adj_verts<VVB>();
 130
 131     // If you comment out the tests before this, then adj_verts test will
 132     // run without segfaulting - at least under gcc-4.3. Not really sure why,
 133     // but I'm guessing it's still not generating valid results, and shouldn't
 134     // be taken as an indicator of stability.
 135     typedef adjacency_list<vecS, vecS, directedS, int, int> VVD;
 136     cout << "vecS vecS directedS" << endl;
 137     invalidate_vertices<VVD>();
 138 //     invalidate_edges<VVD>();
 139 //     invalidate_out_edges<VVD>();
 140 //     invalidate_adj_verts<VVD>();
 141
 142     typedef adjacency_list<listS, vecS, directedS, int, int> LVD;
 143     cout << "listS vecS directedS" << endl;
 144     invalidate_vertices<LVD>();
 145 //     invalidate_edges<LVD>();
 146 //     invalidate_out_edges<LVD>();
 147 //     invalidate_adj_verts<LVD>();
 148 }
 149