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>
make_graph(Graph & g)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>
test(Graph & g,Iterator i,Descriptor d,string const & str)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>
invalidate_edges()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>
invalidate_vertices()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>
invalidate_out_edges()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>
invalidate_adj_verts()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
main()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
150