forked from jeffythedragonslayer/lipton-tarjan
-
Notifications
You must be signed in to change notification settings - Fork 1
/
main.cpp
90 lines (81 loc) · 2.61 KB
/
main.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
#include "lipton-tarjan.h"
#include <iostream>
#include <fstream>
#include <csignal>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/lexical_cast.hpp>
#include <boost/algorithm/string.hpp>
#include <boost/graph/copy.hpp>
#include "colors.h"
#include "strutil.h"
using namespace std;
using namespace boost;
map<VertDesc, uint> vert2uint;
map<uint, VertDesc> uint2vert;
Graph load_graph(string fname)
{
ifstream in(fname);
if( !in ){
cerr << "file \"in\" not found!\n";
exit(1);
}
string str;
vector<pair<uint, uint>> edges;
uint max_v = 0;
while( getline(in, 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);
max_v = max(max(max_v, a), b);
edges.push_back(make_pair(a, b));
}
Graph g(max_v+1);
VertIter vi, vi_end;
uint i = 0;
for( tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi ){
vert2uint[*vi] = i;
uint2vert[i] = *vi;
++i;
}
for( auto& e : edges ){
auto src = uint2vert[e.first];
auto tar = uint2vert[e.second];
add_edge(src, tar, g);
}
vert2uint[Graph::null_vertex()] = -1;
return g;
}
int main(int argc, char* argv[])
{
vector<string> fname;
if( argc < 2 ){
cout << "Usage: lt [filename]\n";
return 0;
}
for( uint i = 1; i < argc; ++i ) fname.push_back(argv[i]);
for( auto& f : fname ){
cout << "loading graph\n";
auto g = load_graph(f);
uint n = num_vertices(g);
auto m = get(vertex_index, g);
VertIter vi, vend;
uint i = 0;
for( tie(vi, vend) = vertices(g); vi != vend; ++vi ){
m[*vi] = i;
++i;
}
cout << "n: " << n << '\n';
uint e = num_edges(g);
cout << "starting lipton tarjan...\n";
Graph g_copy;
copy_graph(g, g_copy);
cout << "g\n";
print_graph(g);
cout << "g_copy\n";
print_graph(g_copy);
auto p = lipton_tarjan(g, g_copy);
}
}