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
18using namespace boost;
19
20template < 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
30template < 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
44struct 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
57struct NoVertexIndexUpdater
58{
59 template < typename Graph > void update(Graph&) {}
60};
61
62template < typename Graph, typename VertexIndexUpdater >
63void 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
98int 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

source code of boost/libs/graph/test/make_bicon_planar_test.cpp