260 lines
7.3 KiB
C++
260 lines
7.3 KiB
C++
//=======================================================================
|
|
// 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/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;
|
|
|
|
|
|
struct VertexIndexUpdater
|
|
{
|
|
template <typename Graph>
|
|
void reset(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 reset(Graph&) {}
|
|
};
|
|
|
|
|
|
|
|
template <typename Graph, typename VertexIndexUpdater>
|
|
void test_K_5(VertexIndexUpdater vertex_index)
|
|
{
|
|
typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
|
|
|
|
Graph g;
|
|
vertex_t v1 = add_vertex(g);
|
|
vertex_t v2 = add_vertex(g);
|
|
vertex_t v3 = add_vertex(g);
|
|
vertex_t v4 = add_vertex(g);
|
|
vertex_t v5 = add_vertex(g);
|
|
vertex_index.reset(g);
|
|
|
|
BOOST_CHECK(boyer_myrvold_planarity_test(g));
|
|
add_edge(v1, v2, g);
|
|
BOOST_CHECK(boyer_myrvold_planarity_test(g));
|
|
add_edge(v1, v3, g);
|
|
BOOST_CHECK(boyer_myrvold_planarity_test(g));
|
|
add_edge(v1, v4, g);
|
|
BOOST_CHECK(boyer_myrvold_planarity_test(g));
|
|
add_edge(v1, v5, g);
|
|
BOOST_CHECK(boyer_myrvold_planarity_test(g));
|
|
add_edge(v2, v3, g);
|
|
BOOST_CHECK(boyer_myrvold_planarity_test(g));
|
|
add_edge(v2, v4, g);
|
|
BOOST_CHECK(boyer_myrvold_planarity_test(g));
|
|
add_edge(v2, v5, g);
|
|
BOOST_CHECK(boyer_myrvold_planarity_test(g));
|
|
add_edge(v3, v4, g);
|
|
BOOST_CHECK(boyer_myrvold_planarity_test(g));
|
|
add_edge(v3, v5, g);
|
|
BOOST_CHECK(boyer_myrvold_planarity_test(g));
|
|
|
|
//This edge should make the graph non-planar
|
|
add_edge(v4, v5, g);
|
|
BOOST_CHECK(!boyer_myrvold_planarity_test(g));
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
template <typename Graph, typename VertexIndexUpdater>
|
|
void test_K_3_3(VertexIndexUpdater vertex_index)
|
|
{
|
|
typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
|
|
|
|
Graph g;
|
|
vertex_t v1 = add_vertex(g);
|
|
vertex_t v2 = add_vertex(g);
|
|
vertex_t v3 = add_vertex(g);
|
|
vertex_t v4 = add_vertex(g);
|
|
vertex_t v5 = add_vertex(g);
|
|
vertex_t v6 = add_vertex(g);
|
|
vertex_index.reset(g);
|
|
|
|
BOOST_CHECK(boyer_myrvold_planarity_test(g));
|
|
add_edge(v1, v4, g);
|
|
BOOST_CHECK(boyer_myrvold_planarity_test(g));
|
|
add_edge(v1, v5, g);
|
|
BOOST_CHECK(boyer_myrvold_planarity_test(g));
|
|
add_edge(v1, v6, g);
|
|
BOOST_CHECK(boyer_myrvold_planarity_test(g));
|
|
add_edge(v2, v4, g);
|
|
BOOST_CHECK(boyer_myrvold_planarity_test(g));
|
|
add_edge(v2, v5, g);
|
|
BOOST_CHECK(boyer_myrvold_planarity_test(g));
|
|
add_edge(v2, v6, g);
|
|
BOOST_CHECK(boyer_myrvold_planarity_test(g));
|
|
add_edge(v3, v4, g);
|
|
BOOST_CHECK(boyer_myrvold_planarity_test(g));
|
|
add_edge(v3, v5, g);
|
|
BOOST_CHECK(boyer_myrvold_planarity_test(g));
|
|
|
|
//This edge should make the graph non-planar
|
|
add_edge(v3, v6, g);
|
|
BOOST_CHECK(!boyer_myrvold_planarity_test(g));
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
// This test creates a maximal planar graph on num_vertices vertices,
|
|
// then, if num_vertices is at least 5, adds an additional edge to
|
|
// create a non-planar graph.
|
|
|
|
template <typename Graph, typename VertexIndexUpdater>
|
|
void test_maximal_planar(VertexIndexUpdater vertex_index, std::size_t num_vertices)
|
|
{
|
|
typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
|
|
|
|
Graph g;
|
|
std::vector<vertex_t> vmap;
|
|
for(std::size_t i = 0; i < num_vertices; ++i)
|
|
vmap.push_back(add_vertex(g));
|
|
|
|
vertex_index.reset(g);
|
|
|
|
BOOST_CHECK(boyer_myrvold_planarity_test(g));
|
|
//create a cycle
|
|
for(std::size_t i = 0; i < num_vertices; ++i)
|
|
{
|
|
add_edge(vmap[i], vmap[(i+1) % num_vertices], g);
|
|
BOOST_CHECK(boyer_myrvold_planarity_test(g));
|
|
}
|
|
|
|
//triangulate the interior of the cycle.
|
|
for(std::size_t i = 2; i < num_vertices - 1; ++i)
|
|
{
|
|
add_edge(vmap[0], vmap[i], g);
|
|
BOOST_CHECK(boyer_myrvold_planarity_test(g));
|
|
}
|
|
|
|
//triangulate the exterior of the cycle.
|
|
for(std::size_t i = 3; i < num_vertices; ++i)
|
|
{
|
|
add_edge(vmap[1], vmap[i], g);
|
|
BOOST_CHECK(boyer_myrvold_planarity_test(g));
|
|
}
|
|
|
|
//Now add an additional edge, forcing the graph to be non-planar.
|
|
if (num_vertices > 4)
|
|
{
|
|
add_edge(vmap[2], vmap[4], g);
|
|
BOOST_CHECK(!boyer_myrvold_planarity_test(g));
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
int test_main(int, char* [])
|
|
{
|
|
typedef adjacency_list
|
|
<vecS,
|
|
vecS,
|
|
undirectedS,
|
|
property<vertex_index_t, int>
|
|
>
|
|
VVgraph_t;
|
|
|
|
typedef adjacency_list
|
|
<vecS,
|
|
listS,
|
|
undirectedS,
|
|
property<vertex_index_t, int>
|
|
>
|
|
VLgraph_t;
|
|
|
|
typedef adjacency_list
|
|
<listS,
|
|
vecS,
|
|
undirectedS,
|
|
property<vertex_index_t, int>
|
|
>
|
|
LVgraph_t;
|
|
|
|
typedef adjacency_list
|
|
<listS,
|
|
listS,
|
|
undirectedS,
|
|
property<vertex_index_t, int>
|
|
>
|
|
LLgraph_t;
|
|
|
|
typedef adjacency_list
|
|
<setS,
|
|
setS,
|
|
undirectedS,
|
|
property<vertex_index_t, int>
|
|
>
|
|
SSgraph_t;
|
|
|
|
test_K_5<VVgraph_t>(NoVertexIndexUpdater());
|
|
test_K_3_3<VVgraph_t>(NoVertexIndexUpdater());
|
|
test_maximal_planar<VVgraph_t>(NoVertexIndexUpdater(), 3);
|
|
test_maximal_planar<VVgraph_t>(NoVertexIndexUpdater(), 6);
|
|
test_maximal_planar<VVgraph_t>(NoVertexIndexUpdater(), 10);
|
|
test_maximal_planar<VVgraph_t>(NoVertexIndexUpdater(), 20);
|
|
test_maximal_planar<VVgraph_t>(NoVertexIndexUpdater(), 50);
|
|
|
|
test_K_5<VLgraph_t>(VertexIndexUpdater());
|
|
test_K_3_3<VLgraph_t>(VertexIndexUpdater());
|
|
test_maximal_planar<VLgraph_t>(VertexIndexUpdater(), 3);
|
|
test_maximal_planar<VLgraph_t>(VertexIndexUpdater(), 6);
|
|
test_maximal_planar<VLgraph_t>(VertexIndexUpdater(), 10);
|
|
test_maximal_planar<VLgraph_t>(VertexIndexUpdater(), 20);
|
|
test_maximal_planar<VLgraph_t>(VertexIndexUpdater(), 50);
|
|
|
|
test_K_5<LVgraph_t>(NoVertexIndexUpdater());
|
|
test_K_3_3<LVgraph_t>(NoVertexIndexUpdater());
|
|
test_maximal_planar<LVgraph_t>(NoVertexIndexUpdater(), 3);
|
|
test_maximal_planar<LVgraph_t>(NoVertexIndexUpdater(), 6);
|
|
test_maximal_planar<LVgraph_t>(NoVertexIndexUpdater(), 10);
|
|
test_maximal_planar<LVgraph_t>(NoVertexIndexUpdater(), 20);
|
|
test_maximal_planar<LVgraph_t>(NoVertexIndexUpdater(), 50);
|
|
|
|
test_K_5<LLgraph_t>(VertexIndexUpdater());
|
|
test_K_3_3<LLgraph_t>(VertexIndexUpdater());
|
|
test_maximal_planar<LLgraph_t>(VertexIndexUpdater(), 3);
|
|
test_maximal_planar<LLgraph_t>(VertexIndexUpdater(), 6);
|
|
test_maximal_planar<LLgraph_t>(VertexIndexUpdater(), 10);
|
|
test_maximal_planar<LLgraph_t>(VertexIndexUpdater(), 20);
|
|
test_maximal_planar<LLgraph_t>(VertexIndexUpdater(), 50);
|
|
|
|
test_K_5<SSgraph_t>(VertexIndexUpdater());
|
|
test_K_3_3<SSgraph_t>(VertexIndexUpdater());
|
|
test_maximal_planar<SSgraph_t>(VertexIndexUpdater(), 3);
|
|
test_maximal_planar<SSgraph_t>(VertexIndexUpdater(), 6);
|
|
test_maximal_planar<SSgraph_t>(VertexIndexUpdater(), 10);
|
|
test_maximal_planar<SSgraph_t>(VertexIndexUpdater(), 20);
|
|
test_maximal_planar<SSgraph_t>(VertexIndexUpdater(), 50);
|
|
|
|
return 0;
|
|
}
|