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