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 | |
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 > |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |