]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | #include <iostream> | |
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> | |
14 | #include <vector> | |
15 | ||
16 | #include <boost/graph/boyer_myrvold_planar_test.hpp> | |
17 | #include <boost/graph/is_kuratowski_subgraph.hpp> | |
18 | ||
19 | using namespace boost; | |
20 | ||
7c673cae FG |
21 | int main(int argc, char** argv) |
22 | { | |
23 | ||
f67539c2 TL |
24 | typedef adjacency_list< vecS, vecS, undirectedS, |
25 | property< vertex_index_t, int >, property< edge_index_t, int > > | |
26 | graph; | |
7c673cae | 27 | |
f67539c2 TL |
28 | // Create a K_6 (complete graph on 6 vertices), which |
29 | // contains both Kuratowski subgraphs as minors. | |
30 | graph g(6); | |
31 | add_edge(0, 1, g); | |
32 | add_edge(0, 2, g); | |
33 | add_edge(0, 3, g); | |
34 | add_edge(0, 4, g); | |
35 | add_edge(0, 5, g); | |
36 | add_edge(1, 2, g); | |
37 | add_edge(1, 3, g); | |
38 | add_edge(1, 4, g); | |
39 | add_edge(1, 5, g); | |
40 | add_edge(2, 3, g); | |
41 | add_edge(2, 4, g); | |
42 | add_edge(2, 5, g); | |
43 | add_edge(3, 4, g); | |
44 | add_edge(3, 5, g); | |
45 | add_edge(4, 5, g); | |
7c673cae | 46 | |
f67539c2 TL |
47 | // Initialize the interior edge index |
48 | property_map< graph, edge_index_t >::type e_index = get(edge_index, g); | |
49 | graph_traits< graph >::edges_size_type edge_count = 0; | |
50 | graph_traits< graph >::edge_iterator ei, ei_end; | |
51 | for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) | |
52 | put(e_index, *ei, edge_count++); | |
7c673cae | 53 | |
f67539c2 TL |
54 | // Test for planarity - we know it is not planar, we just want to |
55 | // compute the kuratowski subgraph as a side-effect | |
56 | typedef std::vector< graph_traits< graph >::edge_descriptor > | |
57 | kuratowski_edges_t; | |
58 | kuratowski_edges_t kuratowski_edges; | |
59 | if (boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, | |
60 | boyer_myrvold_params::kuratowski_subgraph | |
61 | = std::back_inserter(kuratowski_edges))) | |
62 | std::cout << "Input graph is planar" << std::endl; | |
63 | else | |
7c673cae | 64 | { |
f67539c2 | 65 | std::cout << "Input graph is not planar" << std::endl; |
7c673cae | 66 | |
f67539c2 TL |
67 | std::cout << "Edges in the Kuratowski subgraph: "; |
68 | kuratowski_edges_t::iterator ki, ki_end; | |
69 | ki_end = kuratowski_edges.end(); | |
70 | for (ki = kuratowski_edges.begin(); ki != ki_end; ++ki) | |
7c673cae | 71 | { |
f67539c2 | 72 | std::cout << *ki << " "; |
7c673cae | 73 | } |
f67539c2 | 74 | std::cout << std::endl; |
7c673cae | 75 | |
f67539c2 TL |
76 | std::cout << "Is a kuratowski subgraph? "; |
77 | if (is_kuratowski_subgraph( | |
78 | g, kuratowski_edges.begin(), kuratowski_edges.end())) | |
79 | std::cout << "Yes." << std::endl; | |
80 | else | |
81 | std::cout << "No." << std::endl; | |
7c673cae FG |
82 | } |
83 | ||
f67539c2 | 84 | return 0; |
7c673cae | 85 | } |