123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173 |
- //=======================================================================
- // Copyright 2007 Aaron Windsor
- //
- // Distributed under the Boost Software License, Version 1.0. (See
- // accompanying file LICENSE_1_0.txt or copy at
- // http://www.boost.org/LICENSE_1_0.txt)
- //=======================================================================
- #include <boost/graph/adjacency_list.hpp>
- #include <boost/graph/properties.hpp>
- #include <boost/graph/make_maximal_planar.hpp>
- #include <boost/graph/boyer_myrvold_planar_test.hpp>
- #include <boost/property_map/property_map.hpp>
- #include <boost/property_map/vector_property_map.hpp>
- #include <boost/test/minimal.hpp>
- using namespace boost;
- template <typename Graph>
- void reset_edge_index(Graph& g)
- {
- typename property_map<Graph, edge_index_t>::type index = get(edge_index, g);
- typename graph_traits<Graph>::edge_iterator ei, ei_end;
- typename graph_traits<Graph>::edges_size_type cnt = 0;
- for(boost::tie(ei,ei_end) = edges(g); ei != ei_end; ++ei)
- put(index, *ei, cnt++);
- }
- template <typename Graph>
- void make_cycle(Graph& g, int size)
- {
- typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
- vertex_t first_vertex = add_vertex(g);
- vertex_t prev_vertex = first_vertex;
- for(int i = 1; i < size; ++i)
- {
- vertex_t curr_vertex = add_vertex(g);
- add_edge(curr_vertex, prev_vertex, g);
- prev_vertex = curr_vertex;
- }
- add_edge(first_vertex, prev_vertex, g);
- }
- struct UpdateVertexIndex
- {
- template <typename Graph>
- void update(Graph& g)
- {
- typename property_map<Graph, vertex_index_t>::type index = get(vertex_index, g);
- typename graph_traits<Graph>::vertex_iterator vi, vi_end;
- typename graph_traits<Graph>::vertices_size_type cnt = 0;
- for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
- put(index, *vi, cnt++);
- }
- };
- struct NoVertexIndexUpdater
- {
- template <typename Graph> void update(Graph&) {}
- };
- template <typename Graph, typename VertexIndexUpdater>
- void test_cycle(VertexIndexUpdater vertex_index_updater, int size)
- {
- Graph g;
- make_cycle(g, size);
- vertex_index_updater.update(g);
- reset_edge_index(g);
-
- typedef std::vector< typename graph_traits<Graph>::edge_descriptor > edge_vector_t;
- typedef std::vector< edge_vector_t > embedding_storage_t;
- typedef iterator_property_map
- < typename embedding_storage_t::iterator,
- typename property_map<Graph, vertex_index_t>::type
- > embedding_t;
-
- embedding_storage_t embedding_storage(num_vertices(g));
- embedding_t embedding(embedding_storage.begin(), get(vertex_index, g));
- typename graph_traits<Graph>::vertex_iterator vi, vi_end;
- for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
- std::copy(out_edges(*vi,g).first, out_edges(*vi,g).second, std::back_inserter(embedding[*vi]));
- BOOST_CHECK(boyer_myrvold_planarity_test(g));
- make_maximal_planar(g, embedding);
- reset_edge_index(g);
- // A graph is maximal planar exactly when it's both
- // planar and has 3 * num_vertices(g) - 6 edges.
- BOOST_CHECK(num_edges(g) == 3 * num_vertices(g) - 6);
- BOOST_CHECK(boyer_myrvold_planarity_test(g));
- }
- int test_main(int, char* [])
- {
- typedef adjacency_list
- <vecS,
- vecS,
- undirectedS,
- property<vertex_index_t, int>,
- property<edge_index_t, int>
- >
- VVgraph_t;
-
- typedef adjacency_list
- <vecS,
- listS,
- undirectedS,
- property<vertex_index_t, int>,
- property<edge_index_t, int>
- >
- VLgraph_t;
- typedef adjacency_list
- <listS,
- vecS,
- undirectedS,
- property<vertex_index_t, int>,
- property<edge_index_t, int>
- >
- LVgraph_t;
- typedef adjacency_list
- <listS,
- listS,
- undirectedS,
- property<vertex_index_t, int>,
- property<edge_index_t, int>
- >
- LLgraph_t;
- typedef adjacency_list
- <setS,
- setS,
- undirectedS,
- property<vertex_index_t, int>,
- property<edge_index_t, int>
- >
- SSgraph_t;
- test_cycle<VVgraph_t>(NoVertexIndexUpdater(), 10);
- test_cycle<VVgraph_t>(NoVertexIndexUpdater(), 50);
- test_cycle<VLgraph_t>(UpdateVertexIndex(), 3);
- test_cycle<VLgraph_t>(UpdateVertexIndex(), 30);
- test_cycle<LVgraph_t>(NoVertexIndexUpdater(), 15);
- test_cycle<LVgraph_t>(NoVertexIndexUpdater(), 45);
- test_cycle<LLgraph_t>(UpdateVertexIndex(), 8);
- test_cycle<LLgraph_t>(UpdateVertexIndex(), 19);
- test_cycle<SSgraph_t>(UpdateVertexIndex(), 13);
- test_cycle<SSgraph_t>(UpdateVertexIndex(), 20);
- return 0;
- }
|