1 // (C) Copyright 2007-2009 Andrew Sutton
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 <boost/graph/undirected_graph.hpp>
9 #include <boost/graph/directed_graph.hpp>
10
11 using namespace std;
12 using namespace boost;
13
test()14 template < typename Graph > void test()
15 {
16 typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
17 typedef typename property_map< Graph, vertex_index_t >::type IndexMap;
18
19 static const size_t N = 5;
20
21 Graph g;
22 (void)(IndexMap) get(vertex_index, g);
23
24 // build up the graph
25 Vertex v[N];
26 for (size_t i = 0; i < N; ++i)
27 {
28 v[i] = add_vertex(g);
29 }
30
31 // after the first build, we should have these conditions
32 BOOST_ASSERT(max_vertex_index(g) == N);
33 for (size_t i = 0; i < N; ++i)
34 {
35 BOOST_ASSERT(get_vertex_index(v[i], g) == i);
36 }
37
38 // Remove all vertices and then re-add them.
39 for (size_t i = 0; i < N; ++i)
40 remove_vertex(v[i], g);
41 BOOST_ASSERT(num_vertices(g) == 0);
42 for (size_t i = 0; i < N; ++i)
43 {
44 v[i] = add_vertex(g);
45 }
46 BOOST_ASSERT(num_vertices(g) == N);
47
48 // Before renumbering, our vertices should be off by N. In other words,
49 // we're not in a good state.
50 BOOST_ASSERT(max_vertex_index(g) == 10);
51 for (size_t i = 0; i < N; ++i)
52 {
53 BOOST_ASSERT(get_vertex_index(v[i], g) == N + i);
54 }
55
56 // Renumber vertices
57 renumber_vertex_indices(g);
58
59 // And we should be back to the initial condition
60 BOOST_ASSERT(max_vertex_index(g) == N);
61 for (size_t i = 0; i < N; ++i)
62 {
63 BOOST_ASSERT(get_vertex_index(v[i], g) == i);
64 }
65 }
66
67 // Make sure that graphs constructed over n vertices will actually number
68 // their vertices correctly.
build()69 template < typename Graph > void build()
70 {
71 typedef typename graph_traits< Graph >::vertex_iterator Iterator;
72 typedef typename property_map< Graph, vertex_index_t >::type IndexMap;
73
74 static const size_t N = 5;
75
76 Graph g(N);
77 BOOST_ASSERT(max_vertex_index(g) == N);
78
79 (void)(IndexMap) get(vertex_index, g);
80
81 // Each vertex should be numbered correctly.
82 Iterator i, end;
83 boost::tie(i, end) = vertices(g);
84 for (size_t x = 0; i != end; ++i, ++x)
85 {
86 BOOST_ASSERT(get_vertex_index(*i, g) == x);
87 }
88 }
89
main(int,char * [])90 int main(int, char*[])
91 {
92 test< undirected_graph<> >();
93 test< directed_graph<> >();
94
95 build< undirected_graph<> >();
96
97 return 0;
98 }
99