1 //=======================================================================
2 // Copyright 2007 Aaron Windsor
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 //=======================================================================
9 #include <boost/graph/adjacency_list.hpp>
10 #include <boost/graph/properties.hpp>
11 #include <boost/graph/graph_traits.hpp>
12 #include <boost/property_map/property_map.hpp>
13 #include <boost/ref.hpp>
16 #include <boost/graph/boyer_myrvold_planar_test.hpp>
17 #include <boost/graph/is_kuratowski_subgraph.hpp>
19 using namespace boost
;
22 int main(int argc
, char** argv
)
25 typedef adjacency_list
29 property
<vertex_index_t
, int>,
30 property
<edge_index_t
, int>
34 // Create a K_6 (complete graph on 6 vertices), which
35 // contains both Kuratowski subgraphs as minors.
54 // Initialize the interior edge index
55 property_map
<graph
, edge_index_t
>::type e_index
= get(edge_index
, g
);
56 graph_traits
<graph
>::edges_size_type edge_count
= 0;
57 graph_traits
<graph
>::edge_iterator ei
, ei_end
;
58 for(boost::tie(ei
, ei_end
) = edges(g
); ei
!= ei_end
; ++ei
)
59 put(e_index
, *ei
, edge_count
++);
62 // Test for planarity - we know it is not planar, we just want to
63 // compute the kuratowski subgraph as a side-effect
64 typedef std::vector
< graph_traits
<graph
>::edge_descriptor
>
66 kuratowski_edges_t kuratowski_edges
;
67 if (boyer_myrvold_planarity_test(boyer_myrvold_params::graph
= g
,
68 boyer_myrvold_params::kuratowski_subgraph
=
69 std::back_inserter(kuratowski_edges
)
72 std::cout
<< "Input graph is planar" << std::endl
;
75 std::cout
<< "Input graph is not planar" << std::endl
;
77 std::cout
<< "Edges in the Kuratowski subgraph: ";
78 kuratowski_edges_t::iterator ki
, ki_end
;
79 ki_end
= kuratowski_edges
.end();
80 for(ki
= kuratowski_edges
.begin(); ki
!= ki_end
; ++ki
)
82 std::cout
<< *ki
<< " ";
84 std::cout
<< std::endl
;
86 std::cout
<< "Is a kuratowski subgraph? ";
87 if (is_kuratowski_subgraph
88 (g
, kuratowski_edges
.begin(), kuratowski_edges
.end())
90 std::cout
<< "Yes." << std::endl
;
92 std::cout
<< "No." << std::endl
;