1 | #include <boost/graph/adjacency_list.hpp>
|
---|
2 | #include <boost/graph/graph_traits.hpp>
|
---|
3 | #include <boost/property_map/property_map.hpp>
|
---|
4 |
|
---|
5 | #include <boost/graph/boyer_myrvold_planar_test.hpp>
|
---|
6 | #include <boost/graph/make_biconnected_planar.hpp>
|
---|
7 |
|
---|
8 | using namespace boost;
|
---|
9 |
|
---|
10 | #include <utility>
|
---|
11 | #include <vector>
|
---|
12 | #include <cstdio>
|
---|
13 |
|
---|
14 | using std::pair;
|
---|
15 | using std::vector;
|
---|
16 | using std::printf;
|
---|
17 |
|
---|
18 | typedef adjacency_list< vecS, vecS, undirectedS, property<vertex_index_t, int>, property<edge_index_t, int> >
|
---|
19 | graph_t;
|
---|
20 | typedef graph_traits<graph_t>::edge_descriptor
|
---|
21 | edge_descriptor_t;
|
---|
22 | typedef graph_traits<graph_t>::edge_iterator
|
---|
23 | edge_iterator_t;
|
---|
24 | typedef vector< vector< edge_descriptor_t > >
|
---|
25 | embedding_storage_t;
|
---|
26 | typedef boost::iterator_property_map< embedding_storage_t::iterator, property_map<graph_t, vertex_index_t>::type >
|
---|
27 | embedding_t;
|
---|
28 |
|
---|
29 |
|
---|
30 | int main() {
|
---|
31 | vector< pair< edge_descriptor_t, bool > > eds;
|
---|
32 |
|
---|
33 | graph_t g(11);
|
---|
34 | eds.push_back(add_edge(0,1,0,g));
|
---|
35 | eds.push_back(add_edge(1,3,1,g));
|
---|
36 | eds.push_back(add_edge(1,2,2,g));
|
---|
37 | eds.push_back(add_edge(4,1,3,g));
|
---|
38 | eds.push_back(add_edge(2,4,4,g));
|
---|
39 | eds.push_back(add_edge(2,3,5,g));
|
---|
40 | eds.push_back(add_edge(3,4,6,g));
|
---|
41 | eds.push_back(add_edge(5,6,7,g));
|
---|
42 | eds.push_back(add_edge(7,5,8,g));
|
---|
43 | eds.push_back(add_edge(5,8,9,g));
|
---|
44 | eds.push_back(add_edge(6,7,10,g));
|
---|
45 | eds.push_back(add_edge(8,6,11,g));
|
---|
46 | eds.push_back(add_edge(6,9,12,g));
|
---|
47 | eds.push_back(add_edge(7,8,13,g));
|
---|
48 | eds.push_back(add_edge(9,7,14,g));
|
---|
49 | eds.push_back(add_edge(0,8,15,g));
|
---|
50 | eds.push_back(add_edge(8,9,16,g));
|
---|
51 | eds.push_back(add_edge(9,10,17,g));
|
---|
52 |
|
---|
53 | embedding_storage_t embedding_storage(num_vertices(g));
|
---|
54 | embedding_t embedding(embedding_storage.begin(), get(vertex_index, g));
|
---|
55 |
|
---|
56 | for (int i=0; i<(int)eds.size(); ++i) {
|
---|
57 | if (!eds[i].second) {
|
---|
58 | printf("Incorrect input\n");
|
---|
59 | return 0;
|
---|
60 | }
|
---|
61 | }
|
---|
62 |
|
---|
63 | embedding[0].push_back(eds[0].first);
|
---|
64 | embedding[0].push_back(eds[15].first);
|
---|
65 | embedding[1].push_back(eds[0].first);
|
---|
66 | embedding[1].push_back(eds[2].first);
|
---|
67 | embedding[1].push_back(eds[3].first);
|
---|
68 | embedding[1].push_back(eds[1].first);
|
---|
69 | embedding[2].push_back(eds[2].first);
|
---|
70 | embedding[2].push_back(eds[5].first);
|
---|
71 | embedding[2].push_back(eds[4].first);
|
---|
72 | embedding[3].push_back(eds[1].first);
|
---|
73 | embedding[3].push_back(eds[6].first);
|
---|
74 | embedding[3].push_back(eds[5].first);
|
---|
75 | embedding[4].push_back(eds[3].first);
|
---|
76 | embedding[4].push_back(eds[4].first);
|
---|
77 | embedding[4].push_back(eds[6].first);
|
---|
78 | embedding[5].push_back(eds[7].first);
|
---|
79 | embedding[5].push_back(eds[9].first);
|
---|
80 | embedding[5].push_back(eds[8].first);
|
---|
81 | embedding[6].push_back(eds[7].first);
|
---|
82 | embedding[6].push_back(eds[10].first);
|
---|
83 | embedding[6].push_back(eds[12].first);
|
---|
84 | embedding[6].push_back(eds[11].first);
|
---|
85 | embedding[7].push_back(eds[8].first);
|
---|
86 | embedding[7].push_back(eds[13].first);
|
---|
87 | embedding[7].push_back(eds[14].first);
|
---|
88 | embedding[7].push_back(eds[10].first);
|
---|
89 | embedding[8].push_back(eds[9].first);
|
---|
90 | embedding[8].push_back(eds[11].first);
|
---|
91 | embedding[8].push_back(eds[16].first);
|
---|
92 | embedding[8].push_back(eds[15].first);
|
---|
93 | embedding[8].push_back(eds[13].first);
|
---|
94 | embedding[9].push_back(eds[12].first);
|
---|
95 | embedding[9].push_back(eds[14].first);
|
---|
96 | embedding[9].push_back(eds[17].first);
|
---|
97 | embedding[9].push_back(eds[16].first);
|
---|
98 | embedding[10].push_back(eds[17].first);
|
---|
99 | /*
|
---|
100 | if (boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g,
|
---|
101 | boyer_myrvold_params::embedding = embedding)) {
|
---|
102 | printf("OK!\n");
|
---|
103 | } else {
|
---|
104 | printf("ERROR!\n");
|
---|
105 | }
|
---|
106 | */
|
---|
107 | make_biconnected_planar(g, embedding);
|
---|
108 | {
|
---|
109 | edge_iterator_t ei, ei_end;
|
---|
110 | int edge_count = 0;
|
---|
111 | for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
|
---|
112 | put(get(edge_index, g), *ei, edge_count++);
|
---|
113 | }
|
---|
114 | }
|
---|
115 |
|
---|
116 | if (boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g,
|
---|
117 | boyer_myrvold_params::embedding = embedding)) {
|
---|
118 | printf("OK!\n");
|
---|
119 | } else {
|
---|
120 | printf("ERROR!\n");
|
---|
121 | }
|
---|
122 |
|
---|
123 | return 0;
|
---|
124 | }
|
---|