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