| 1 | #include <boost/graph/graph_traits.hpp>
|
|---|
| 2 | #include <boost/graph/adjacency_list.hpp>
|
|---|
| 3 | #include <boost/graph/boyer_myrvold_planar_test.hpp>
|
|---|
| 4 | #include <boost/graph/planar_face_traversal.hpp>
|
|---|
| 5 | #include <iostream>
|
|---|
| 6 |
|
|---|
| 7 | using namespace boost;
|
|---|
| 8 | using namespace std;
|
|---|
| 9 |
|
|---|
| 10 | typedef adjacency_list<vecS,
|
|---|
| 11 | vecS,
|
|---|
| 12 | undirectedS,
|
|---|
| 13 | property<vertex_index_t, int>,
|
|---|
| 14 | property<edge_index_t, int>
|
|---|
| 15 | > Graph;
|
|---|
| 16 |
|
|---|
| 17 | typedef std::vector< std::vector< graph_traits<Graph>::edge_descriptor > >
|
|---|
| 18 | embedding_storage_t;
|
|---|
| 19 | typedef boost::iterator_property_map
|
|---|
| 20 | < embedding_storage_t::iterator,
|
|---|
| 21 | property_map<Graph, vertex_index_t>::type
|
|---|
| 22 | >
|
|---|
| 23 | embedding_t;
|
|---|
| 24 |
|
|---|
| 25 | struct face_output_visitor: public planar_face_traversal_visitor
|
|---|
| 26 | {
|
|---|
| 27 | void begin_face() {
|
|---|
| 28 | std::cout << "New face: ";
|
|---|
| 29 | }
|
|---|
| 30 |
|
|---|
| 31 | template <typename Vertex> void next_vertex(Vertex v) {
|
|---|
| 32 | std::cout << v << " ";
|
|---|
| 33 | }
|
|---|
| 34 |
|
|---|
| 35 | void end_face() {
|
|---|
| 36 | std::cout << "visitor done. " << std::endl;
|
|---|
| 37 | }
|
|---|
| 38 | };
|
|---|
| 39 |
|
|---|
| 40 | int main(void)
|
|---|
| 41 | {
|
|---|
| 42 | typedef pair<int,int> Edge;
|
|---|
| 43 | Edge edge_array[] = {
|
|---|
| 44 | Edge(1,0),
|
|---|
| 45 | Edge(3,2),
|
|---|
| 46 | Edge(4,2),
|
|---|
| 47 | Edge(4,3),
|
|---|
| 48 | Edge(5,2),
|
|---|
| 49 | Edge(6,0),
|
|---|
| 50 | Edge(6,3),
|
|---|
| 51 | Edge(6,5),
|
|---|
| 52 | Edge(7,1),
|
|---|
| 53 | Edge(7,4),
|
|---|
| 54 | Edge(7,5),
|
|---|
| 55 | Edge(7,6),
|
|---|
| 56 | Edge(8,0),
|
|---|
| 57 | Edge(8,3),
|
|---|
| 58 | Edge(9,1),
|
|---|
| 59 | Edge(9,4),
|
|---|
| 60 | Edge(9,8)
|
|---|
| 61 | };
|
|---|
| 62 |
|
|---|
| 63 | Graph G(10);
|
|---|
| 64 |
|
|---|
| 65 | const int num_edges = sizeof(edge_array)/sizeof(edge_array[0]);
|
|---|
| 66 | graph_traits<Graph>::edge_descriptor e;
|
|---|
| 67 | bool b;
|
|---|
| 68 | int e_index = 0;
|
|---|
| 69 |
|
|---|
| 70 | for (int i = 0; i < num_edges; ++i) {
|
|---|
| 71 | tie(e, b) = add_edge(edge_array[i].first, edge_array[i].second, G);
|
|---|
| 72 | if (b) {
|
|---|
| 73 | put(get(edge_index, G), e, e_index++);
|
|---|
| 74 | }
|
|---|
| 75 | }
|
|---|
| 76 |
|
|---|
| 77 | embedding_storage_t embedding_storage(num_vertices(G));
|
|---|
| 78 | embedding_t embedding(embedding_storage.begin(), get(vertex_index, G));
|
|---|
| 79 |
|
|---|
| 80 | if (!boyer_myrvold_planarity_test(boyer_myrvold_params::graph = G, boyer_myrvold_params::embedding = embedding)) {
|
|---|
| 81 | cerr << "not planar" << endl;
|
|---|
| 82 | }
|
|---|
| 83 |
|
|---|
| 84 | face_output_visitor f_vis;
|
|---|
| 85 |
|
|---|
| 86 | cerr << "Bug: the graph is planar and 3-connected, \n"
|
|---|
| 87 | << " (in fact, it's a cube with a triangular prism attached to one face),\n"
|
|---|
| 88 | << "but the faces of a planar embedding are not detected."
|
|---|
| 89 | << "\n\n"
|
|---|
| 90 | << "Output that caused the bug report:\n"
|
|---|
| 91 | << "New face: 1 0 visitor done. \n"
|
|---|
| 92 | << "New face: 3 2 5 6 visitor done. \n"
|
|---|
| 93 | << "New face: 4 visitor done. \n"
|
|---|
| 94 | << "New face: 7 visitor done. \n"
|
|---|
| 95 | << "New face: 8 visitor done. \n"
|
|---|
| 96 | << "New face: 9 visitor done.\n"
|
|---|
| 97 | << "\n\n"
|
|---|
| 98 | << "Output calculated now:"
|
|---|
| 99 | << endl;
|
|---|
| 100 |
|
|---|
| 101 | planar_face_traversal(G, &embedding[0], f_vis);
|
|---|
| 102 |
|
|---|
| 103 | return 0;
|
|---|
| 104 | }
|
|---|
