forked from jeffythedragonslayer/lipton-tarjan
-
Notifications
You must be signed in to change notification settings - Fork 1
/
chrobak.cpp
123 lines (99 loc) · 4.74 KB
/
chrobak.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/planar_canonical_ordering.hpp>
#include <boost/graph/is_straight_line_drawing.hpp>
#include <boost/graph/make_connected.hpp>
#include <boost/graph/make_biconnected_planar.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/graph/planar_face_traversal.hpp>
#include <boost/graph/chrobak_payne_drawing.hpp>
#include <boost/graph/make_maximal_planar.hpp>
#include <boost/graph/boyer_myrvold_planar_test.hpp>
#include <boost/algorithm/string.hpp>
#include <boost/lexical_cast.hpp>
#include <vector>
#include <fstream>
#include <iostream>
using namespace std;
using namespace boost;
typedef adjacency_list<vecS, vecS, undirectedS, property<vertex_index_t, int>, property<edge_index_t, int>> Graph;
typedef vector<vector<graph_traits<Graph>::edge_descriptor>> embedding_storage_t;
typedef iterator_property_map<embedding_storage_t::iterator, property_map<Graph, vertex_index_t>::type> embedding_t;
struct face_counter : public planar_face_traversal_visitor
{
face_counter() : count(0) {}
void begin_face() { ++count; }
int count;
};
struct coord_t
{
size_t x;
size_t y;
};
void makemaxplanar(Graph& g)
{
auto e_index = get(edge_index, g);
graph_traits<Graph>::edges_size_type edge_count = 0;
graph_traits<Graph>::edge_iterator ei, ei_end;
for(tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) put(e_index, *ei, edge_count++);
typedef vector< graph_traits<Graph>::edge_descriptor > vec_t;
vector<vec_t> embedding(num_vertices(g));
boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, boyer_myrvold_params::embedding = &embedding[0]);
make_biconnected_planar(g, &embedding[0]);
edge_count = 0;
for(tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) put(e_index, *ei, edge_count++);
boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, boyer_myrvold_params::embedding = &embedding[0]);
make_maximal_planar(g, &embedding[0]);
edge_count = 0;
for(tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) put(e_index, *ei, edge_count++);
boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, boyer_myrvold_params::embedding = &embedding[0]);
face_counter count_visitor;
planar_face_traversal(g, &embedding[0], count_visitor);
}
int main(int argc, char** argv)
{
if( argc < 2 ){
cerr << "Usage: chrobak [filename]\n";
return 1;
}
string fname(argv[1]);
ifstream f(fname);
if( !f ){
cerr << "file " << fname << " not found!\n";
return 1;
}
string str;
vector<pair<uint, uint>> edges;
uint n = 0;
while( getline(f, str) ){
uint colon = str.find(",");
string stra = str.substr(0, colon); trim(stra);
string strb = str.substr(colon+1 ); trim(strb);
uint a = lexical_cast<uint>(stra);
uint b = lexical_cast<uint>(strb);
n = max(max(n, a), b);
edges.push_back(make_pair(a, b));
}
Graph g(n);
for( auto& e : edges ) add_edge(e.first, e.second, g);
makemaxplanar(g);
embedding_storage_t embedding_storage(num_vertices(g));
embedding_t embedding (embedding_storage.begin(), get(vertex_index,g));
boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, boyer_myrvold_params::embedding = embedding);
vector<graph_traits<Graph>::vertex_descriptor> ordering;
planar_canonical_ordering(g, embedding, back_inserter(ordering));
typedef vector<coord_t> straight_line_drawing_storage_t;
typedef iterator_property_map < straight_line_drawing_storage_t::iterator, property_map<Graph, vertex_index_t>::type> straight_line_drawing_t;
straight_line_drawing_storage_t straight_line_drawing_storage (num_vertices(g));
straight_line_drawing_t straight_line_drawing (straight_line_drawing_storage.begin(), get(vertex_index,g));
chrobak_payne_straight_line_drawing(g, embedding, ordering.begin(), ordering.end(), straight_line_drawing);
graph_traits<Graph>::vertex_iterator vi, vi_end;
cout << "graph G {\n";
for(tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi) {
coord_t coord(get(straight_line_drawing,*vi));
cout << *vi << "[pos=\"" << coord.x << ',' << coord.y << "!\"];\n";
}
for( auto& e : edges ) cout << e.first << "--" << e.second << " ;\n";
cout << "}\n";
}