1 | //======================================================================= |
2 | // Copyright 2007 Aaron Windsor |
3 | // |
4 | // Distributed under the Boost Software License, Version 1.0. (See |
5 | // accompanying file LICENSE_1_0.txt or copy at |
6 | // http://www.boost.org/LICENSE_1_0.txt) |
7 | //======================================================================= |
8 | |
9 | #include <boost/graph/adjacency_list.hpp> |
10 | #include <boost/graph/properties.hpp> |
11 | #include <boost/graph/make_biconnected_planar.hpp> |
12 | #include <boost/graph/biconnected_components.hpp> |
13 | #include <boost/graph/boyer_myrvold_planar_test.hpp> |
14 | #include <boost/property_map/property_map.hpp> |
15 | #include <boost/property_map/vector_property_map.hpp> |
16 | #include <boost/core/lightweight_test.hpp> |
17 | |
18 | using namespace boost; |
19 | |
20 | template < typename Graph > void reset_edge_index(Graph& g) |
21 | { |
22 | typename property_map< Graph, edge_index_t >::type index |
23 | = get(edge_index, g); |
24 | typename graph_traits< Graph >::edge_iterator ei, ei_end; |
25 | typename graph_traits< Graph >::edges_size_type cnt = 0; |
26 | for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) |
27 | put(index, *ei, cnt++); |
28 | } |
29 | |
30 | template < typename Graph > void make_line_graph(Graph& g, int size) |
31 | { |
32 | typedef typename graph_traits< Graph >::vertex_descriptor vertex_t; |
33 | |
34 | vertex_t prev_vertex = add_vertex(g); |
35 | |
36 | for (int i = 1; i < size; ++i) |
37 | { |
38 | vertex_t curr_vertex = add_vertex(g); |
39 | add_edge(curr_vertex, prev_vertex, g); |
40 | prev_vertex = curr_vertex; |
41 | } |
42 | } |
43 | |
44 | struct UpdateVertexIndex |
45 | { |
46 | template < typename Graph > void update(Graph& g) |
47 | { |
48 | typename property_map< Graph, vertex_index_t >::type index |
49 | = get(vertex_index, g); |
50 | typename graph_traits< Graph >::vertex_iterator vi, vi_end; |
51 | typename graph_traits< Graph >::vertices_size_type cnt = 0; |
52 | for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) |
53 | put(index, *vi, cnt++); |
54 | } |
55 | }; |
56 | |
57 | struct NoVertexIndexUpdater |
58 | { |
59 | template < typename Graph > void update(Graph&) {} |
60 | }; |
61 | |
62 | template < typename Graph, typename VertexIndexUpdater > |
63 | void test_line_graph(VertexIndexUpdater vertex_index_updater, int size) |
64 | { |
65 | |
66 | Graph g; |
67 | make_line_graph(g, size); |
68 | vertex_index_updater.update(g); |
69 | reset_edge_index(g); |
70 | |
71 | typedef std::vector< typename graph_traits< Graph >::edge_descriptor > |
72 | edge_vector_t; |
73 | typedef std::vector< edge_vector_t > embedding_storage_t; |
74 | typedef iterator_property_map< typename embedding_storage_t::iterator, |
75 | typename property_map< Graph, vertex_index_t >::type > |
76 | embedding_t; |
77 | |
78 | embedding_storage_t embedding_storage(num_vertices(g)); |
79 | embedding_t embedding(embedding_storage.begin(), get(vertex_index, g)); |
80 | |
81 | typename graph_traits< Graph >::vertex_iterator vi, vi_end; |
82 | for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) |
83 | std::copy(out_edges(*vi, g).first, out_edges(*vi, g).second, |
84 | std::back_inserter(embedding[*vi])); |
85 | |
86 | BOOST_TEST(biconnected_components( |
87 | g, make_vector_property_map< int >(get(edge_index, g))) |
88 | > 1); |
89 | BOOST_TEST(boyer_myrvold_planarity_test(g)); |
90 | make_biconnected_planar(g, embedding); |
91 | reset_edge_index(g); |
92 | BOOST_TEST(biconnected_components( |
93 | g, make_vector_property_map< int >(get(edge_index, g))) |
94 | == 1); |
95 | BOOST_TEST(boyer_myrvold_planarity_test(g)); |
96 | } |
97 | |
98 | int main(int, char*[]) |
99 | { |
100 | typedef adjacency_list< vecS, vecS, undirectedS, |
101 | property< vertex_index_t, int >, property< edge_index_t, int > > |
102 | VVgraph_t; |
103 | |
104 | typedef adjacency_list< vecS, listS, undirectedS, |
105 | property< vertex_index_t, int >, property< edge_index_t, int > > |
106 | VLgraph_t; |
107 | |
108 | typedef adjacency_list< listS, vecS, undirectedS, |
109 | property< vertex_index_t, int >, property< edge_index_t, int > > |
110 | LVgraph_t; |
111 | |
112 | typedef adjacency_list< listS, listS, undirectedS, |
113 | property< vertex_index_t, int >, property< edge_index_t, int > > |
114 | LLgraph_t; |
115 | |
116 | typedef adjacency_list< setS, setS, undirectedS, |
117 | property< vertex_index_t, int >, property< edge_index_t, int > > |
118 | SSgraph_t; |
119 | |
120 | test_line_graph< VVgraph_t >(vertex_index_updater: NoVertexIndexUpdater(), size: 10); |
121 | test_line_graph< VVgraph_t >(vertex_index_updater: NoVertexIndexUpdater(), size: 50); |
122 | |
123 | test_line_graph< VLgraph_t >(vertex_index_updater: UpdateVertexIndex(), size: 3); |
124 | test_line_graph< VLgraph_t >(vertex_index_updater: UpdateVertexIndex(), size: 30); |
125 | |
126 | test_line_graph< LVgraph_t >(vertex_index_updater: NoVertexIndexUpdater(), size: 15); |
127 | test_line_graph< LVgraph_t >(vertex_index_updater: NoVertexIndexUpdater(), size: 45); |
128 | |
129 | test_line_graph< LLgraph_t >(vertex_index_updater: UpdateVertexIndex(), size: 8); |
130 | test_line_graph< LLgraph_t >(vertex_index_updater: UpdateVertexIndex(), size: 19); |
131 | |
132 | test_line_graph< SSgraph_t >(vertex_index_updater: UpdateVertexIndex(), size: 13); |
133 | test_line_graph< SSgraph_t >(vertex_index_updater: UpdateVertexIndex(), size: 20); |
134 | |
135 | return boost::report_errors(); |
136 | } |
137 | |