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