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
9IMPORTANT: this file should not be tested - it creates invalid graphs/sequences
10which *do* crash at runtime - this seems to be the intent, but it's not
11clear 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
21using namespace std;
22using 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
27template < 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.
37template < typename Graph, typename Iterator, typename Descriptor >
38void 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
49template < 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
66template < 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
83template < 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
100template < 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
117int 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

source code of boost/libs/graph/test/adj_list_invalidation.cpp