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