forked from smaniu/treewidth
-
Notifications
You must be signed in to change notification settings - Fork 0
/
main.cpp
160 lines (151 loc) · 5.28 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
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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include <iostream>
#include <fstream>
#include <sstream>
#include <memory>
#include "common.h"
#include "Graph.h"
//Strategies and decompositions
#include "PermutationStrategy.h"
#include "DegreePermutationStrategy.h"
#include "FillInPermutationStrategy.h"
#include "DegreeFillInPermutationStrategy.h"
#include "MCSPermutationStrategy.h"
#include "TreeDecomposition.h"
//Lower Bounds
#include "LowerBound.h"
#include "LowerBoundMMD.h"
#include "Delta2D.h"
#include "CE.h"
//Meta lower bounds
#include "MetaLowerBoundHeuristic.h"
#include "LBN.h"
#include "LBNPlus.h"
void lower(int argc, const char * argv[]){
std::string file_name_graph(argv[2]);
std::stringstream ss, ss_stat;
timestamp_t t0, t1;
double time_sec;
int meta = 0;
int lb = 0;
if(argc>3)
lb = atoi(argv[3]);
if(argc>4)
meta = atoi(argv[4]);
ss << file_name_graph << "." << meta << "." << lb << "." << ".lb";
Graph graph;
//strategy
std::unique_ptr<PermutationStrategy> strategy(new DegreePermutationStrategy());
//lower bounds estimators
std::vector<std::unique_ptr<LowerBound>> bounds;
bounds.push_back(std::unique_ptr<LowerBound>\
(new LowerBoundMMD(graph, *strategy)));
bounds.push_back(std::unique_ptr<LowerBound>\
(new LowerBoundMMDPlus(graph, *strategy)));
bounds.push_back(std::unique_ptr<LowerBound>\
(new Delta2D(graph, *strategy)));
//meta lower bound estimators
std::vector<std::unique_ptr<MetaLowerBoundHeuristic>> metas;
metas.push_back(std::unique_ptr<MetaLowerBoundHeuristic>\
(new LBN(graph, *bounds[lb])));
metas.push_back(std::unique_ptr<MetaLowerBoundHeuristic>\
(new LBNPlus(graph, *bounds[lb])));
unsigned long src, tgt;
std::cout << "loading graph..." << std::flush;
t0 = get_timestamp();
std::ifstream file(file_name_graph);
while(file >> src >> tgt){
if(src!=tgt) graph.add_edge(src, tgt);
}
file.close();
std::ofstream filestat(ss.str());
t1 = get_timestamp();
time_sec = (t1-t0)/(1000.0L*1000.0L);
std::cout << " done in " << time_sec << " sec."<< std::endl;
std::cout << "graph: " << graph.number_nodes() << " nodes " <<\
graph.number_edges() << " edges" << std::endl;
std::cout << "lower bound..." << std::flush;
t0 = get_timestamp();
unsigned long lower = 0;
if(meta==0){
lower = bounds[lb]->estimate();
}
else{
lower = metas[meta-1]->estimate();
}
t1 = get_timestamp();
time_sec = (t1-t0)/(1000.0L*1000.0L);
std::cout << " done in " << time_sec << " sec."<< std::endl;
std::cout << "lower bound " << lower << std::endl;
filestat << lower << "\t" << time_sec << std::endl;
filestat.close();
}
void upper(int argc, const char * argv[]){
std::string file_name_graph(argv[2]);
std::stringstream ss, ss_stat;
timestamp_t t0, t1;
double time_sec;
int str = 0;
int part = 0;
if(argc>3)
str = atoi(argv[3]);
if(argc>4)
part = atoi(argv[4]);
ss << file_name_graph << "." << str << "." << part << ".dec";
ss_stat << file_name_graph << "." << str << "." << part << ".stat";
Graph graph;
std::vector<std::unique_ptr<PermutationStrategy>> strategies;
strategies.push_back(std::unique_ptr<PermutationStrategy>
(new DegreePermutationStrategy()));
strategies.push_back(std::unique_ptr<PermutationStrategy>
(new FillInPermutationStrategy()));
strategies.push_back(std::unique_ptr<PermutationStrategy>
(new DegreeFillInPermutationStrategy()));
strategies.push_back(std::unique_ptr<PermutationStrategy>
(new MCSPermutationStrategy()));
unsigned long src, tgt;
std::ofstream filestat(ss_stat.str());
std::cout << "loading graph..." << std::flush;
t0 = get_timestamp();
std::ifstream file1(file_name_graph);
while(file1 >> src >> tgt){
if(src!=tgt) graph.add_edge(src, tgt);
}
file1.close();
t1 = get_timestamp();
time_sec = (t1-t0)/(1000.0L*1000.0L);
std::cout << " done in " << time_sec << " sec."<< std::endl;
std::cout << "graph: " << graph.number_nodes() << " nodes " <<\
graph.number_edges() << " edges" << std::endl;
TreeDecomposition decomposition(graph, *strategies[str]);
std::cout << "upper bound..." << std::flush;
t0 = get_timestamp();
unsigned long upper = decomposition.decompose(part);
t1 = get_timestamp();
time_sec = (t1-t0)/(1000.0L*1000.0L);
std::cout << " done in " << time_sec << " sec."<< std::endl;
std::cout << "upper bound " << upper << std::endl;
filestat << upper << "\t";
filestat << time_sec << "\t";
std::cout << "building tree..." << std::flush;
t0 = get_timestamp();
decomposition.build_tree();
t1 = get_timestamp();
time_sec = (t1-t0)/(1000.0L*1000.0L);
std::cout << " done in " << time_sec << " sec."<< std::endl;
filestat << time_sec << std::endl;
std::cout << "writing decomposition..." << std::flush;
t0 = get_timestamp();
std::ofstream filedec(ss.str());
filedec << decomposition;
filedec.close();
filestat << decomposition.get_stat();
filestat.close();
t1 = get_timestamp();
time_sec = (t1-t0)/(1000.0L*1000.0L);
std::cout << " done in " << time_sec << " sec."<< std::endl;
}
int main(int argc, const char * argv[]) {
std::string first_arg(argv[1]);
if(first_arg=="--upper") upper(argc, argv);
else if(first_arg=="--lower") lower(argc, argv);
}