35 #include <cstring> |
35 #include <cstring> |
36 |
36 |
37 #include <lemon/smart_graph.h> |
37 #include <lemon/smart_graph.h> |
38 #include <lemon/dimacs.h> |
38 #include <lemon/dimacs.h> |
39 #include <lemon/lgf_writer.h> |
39 #include <lemon/lgf_writer.h> |
|
40 #include <lemon/time_measure.h> |
40 |
41 |
41 #include <lemon/arg_parser.h> |
42 #include <lemon/arg_parser.h> |
42 #include <lemon/error.h> |
43 #include <lemon/error.h> |
43 |
44 |
44 using namespace std; |
45 #include <lemon/dijkstra.h> |
|
46 #include <lemon/preflow.h> |
|
47 #include <lemon/max_matching.h> |
|
48 |
45 using namespace lemon; |
49 using namespace lemon; |
46 |
50 typedef SmartDigraph Digraph; |
|
51 DIGRAPH_TYPEDEFS(Digraph); |
|
52 typedef SmartGraph Graph; |
|
53 |
|
54 template<class Value> |
|
55 void solve_sp(ArgParser &ap, std::istream &is, std::ostream &, |
|
56 DimacsDescriptor &desc) |
|
57 { |
|
58 bool report = !ap.given("q"); |
|
59 Digraph g; |
|
60 Node s; |
|
61 Digraph::ArcMap<Value> len(g); |
|
62 Timer t; |
|
63 t.restart(); |
|
64 readDimacsSp(is, g, len, s, desc); |
|
65 if(report) std::cerr << "Read the file: " << t << '\n'; |
|
66 t.restart(); |
|
67 Dijkstra<Digraph, Digraph::ArcMap<Value> > dij(g,len); |
|
68 if(report) std::cerr << "Setup Dijkstra class: " << t << '\n'; |
|
69 t.restart(); |
|
70 dij.run(s); |
|
71 if(report) std::cerr << "Run Dijkstra: " << t << '\n'; |
|
72 } |
|
73 |
|
74 template<class Value> |
|
75 void solve_max(ArgParser &ap, std::istream &is, std::ostream &, |
|
76 DimacsDescriptor &desc) |
|
77 { |
|
78 bool report = !ap.given("q"); |
|
79 Digraph g; |
|
80 Node s,t; |
|
81 Digraph::ArcMap<Value> cap(g); |
|
82 Timer ti; |
|
83 ti.restart(); |
|
84 readDimacsMax(is, g, cap, s, t, desc); |
|
85 if(report) std::cerr << "Read the file: " << ti << '\n'; |
|
86 ti.restart(); |
|
87 Preflow<Digraph, Digraph::ArcMap<Value> > pre(g,cap,s,t); |
|
88 if(report) std::cerr << "Setup Preflow class: " << ti << '\n'; |
|
89 ti.restart(); |
|
90 pre.run(); |
|
91 if(report) std::cerr << "Run Preflow: " << ti << '\n'; |
|
92 if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n'; |
|
93 } |
|
94 |
|
95 void solve_mat(ArgParser &ap, std::istream &is, std::ostream &, |
|
96 DimacsDescriptor &desc) |
|
97 { |
|
98 bool report = !ap.given("q"); |
|
99 Graph g; |
|
100 Timer ti; |
|
101 ti.restart(); |
|
102 readDimacsMat(is, g, desc); |
|
103 if(report) std::cerr << "Read the file: " << ti << '\n'; |
|
104 ti.restart(); |
|
105 MaxMatching<Graph> mat(g); |
|
106 if(report) std::cerr << "Setup MaxMatching class: " << ti << '\n'; |
|
107 ti.restart(); |
|
108 mat.run(); |
|
109 if(report) std::cerr << "Run MaxMatching: " << ti << '\n'; |
|
110 if(report) std::cerr << "\nCardinality of max matching: " |
|
111 << mat.matchingSize() << '\n'; |
|
112 } |
|
113 |
|
114 |
|
115 template<class Value> |
|
116 void solve(ArgParser &ap, std::istream &is, std::ostream &os, |
|
117 DimacsDescriptor &desc) |
|
118 { |
|
119 switch(desc.type) |
|
120 { |
|
121 case DimacsDescriptor::MIN: |
|
122 std::cerr << |
|
123 "\n\n Sorry, the min. cost flow solver is not yet available.\n" |
|
124 << std::endl; |
|
125 break; |
|
126 case DimacsDescriptor::MAX: |
|
127 solve_max<Value>(ap,is,os,desc); |
|
128 break; |
|
129 case DimacsDescriptor::SP: |
|
130 solve_sp<Value>(ap,is,os,desc); |
|
131 break; |
|
132 case DimacsDescriptor::MAT: |
|
133 solve_mat(ap,is,os,desc); |
|
134 break; |
|
135 default: |
|
136 break; |
|
137 } |
|
138 } |
47 |
139 |
48 int main(int argc, const char *argv[]) { |
140 int main(int argc, const char *argv[]) { |
49 typedef SmartDigraph Digraph; |
141 typedef SmartDigraph Digraph; |
50 |
142 |
51 typedef Digraph::Arc Arc; |
143 typedef Digraph::Arc Arc; |
60 |
152 |
61 ArgParser ap(argc, argv); |
153 ArgParser ap(argc, argv); |
62 ap.other("[INFILE [OUTFILE]]", |
154 ap.other("[INFILE [OUTFILE]]", |
63 "If either the INFILE or OUTFILE file is missing the standard\n" |
155 "If either the INFILE or OUTFILE file is missing the standard\n" |
64 " input/output will be used instead.") |
156 " input/output will be used instead.") |
|
157 .boolOption("q", "Do not print any report") |
|
158 .boolOption("int","Use 'int' for capacities, costs etc. (default)") |
|
159 .optionGroup("datatype","int") |
|
160 #ifdef HAVE_LONG_LONG |
|
161 .boolOption("long","Use 'long long' for capacities, costs etc.") |
|
162 .optionGroup("datatype","long") |
|
163 #endif |
|
164 .boolOption("double","Use 'double' for capacities, costs etc.") |
|
165 .optionGroup("datatype","double") |
|
166 .boolOption("ldouble","Use 'long double' for capacities, costs etc.") |
|
167 .optionGroup("datatype","ldouble") |
|
168 .onlyOneGroup("datatype") |
65 .run(); |
169 .run(); |
66 |
170 |
67 ifstream input; |
171 std::ifstream input; |
68 ofstream output; |
172 std::ofstream output; |
69 |
173 |
70 switch(ap.files().size()) |
174 switch(ap.files().size()) |
71 { |
175 { |
72 case 2: |
176 case 2: |
73 output.open(ap.files()[1].c_str()); |
177 output.open(ap.files()[1].c_str()); |
80 throw IoError("File cannot be found", ap.files()[0]); |
184 throw IoError("File cannot be found", ap.files()[0]); |
81 } |
185 } |
82 case 0: |
186 case 0: |
83 break; |
187 break; |
84 default: |
188 default: |
85 cerr << ap.commandName() << ": too many arguments\n"; |
189 std::cerr << ap.commandName() << ": too many arguments\n"; |
86 return 1; |
190 return 1; |
87 } |
191 } |
88 istream& is = (ap.files().size()<1 ? cin : input); |
192 std::istream& is = (ap.files().size()<1 ? std::cin : input); |
89 ostream& os = (ap.files().size()<2 ? cout : output); |
193 std::ostream& os = (ap.files().size()<2 ? std::cout : output); |
90 |
194 |
91 DimacsDescriptor desc = dimacsType(is); |
195 DimacsDescriptor desc = dimacsType(is); |
92 switch(desc.type) |
196 |
|
197 if(!ap.given("q")) |
93 { |
198 { |
94 case DimacsDescriptor::MIN: |
199 std::cout << "Problem type: "; |
95 { |
200 switch(desc.type) |
96 Digraph digraph; |
201 { |
97 DoubleArcMap lower(digraph), capacity(digraph), cost(digraph); |
202 case DimacsDescriptor::MIN: |
98 DoubleNodeMap supply(digraph); |
203 std::cout << "min"; |
99 readDimacsMin(is, digraph, lower, capacity, cost, supply, desc); |
204 break; |
100 DigraphWriter<Digraph>(digraph, os). |
205 case DimacsDescriptor::MAX: |
101 nodeMap("supply", supply). |
206 std::cout << "max"; |
102 arcMap("lower", lower). |
207 break; |
103 arcMap("capacity", capacity). |
208 case DimacsDescriptor::SP: |
104 arcMap("cost", cost). |
209 std::cout << "sp"; |
105 attribute("problem","min"). |
210 case DimacsDescriptor::MAT: |
106 run(); |
211 std::cout << "mat"; |
107 } |
212 break; |
108 break; |
213 default: |
109 case DimacsDescriptor::MAX: |
214 exit(1); |
110 { |
215 break; |
111 Digraph digraph; |
216 } |
112 Node s, t; |
217 std::cout << "\nNum of nodes: " << desc.nodeNum; |
113 DoubleArcMap capacity(digraph); |
218 std::cout << "\nNum of arcs: " << desc.edgeNum; |
114 readDimacsMax(is, digraph, capacity, s, t, desc); |
219 std::cout << '\n' << std::endl; |
115 DigraphWriter<Digraph>(digraph, os). |
|
116 arcMap("capacity", capacity). |
|
117 node("source", s). |
|
118 node("target", t). |
|
119 attribute("problem","max"). |
|
120 run(); |
|
121 } |
|
122 break; |
|
123 case DimacsDescriptor::SP: |
|
124 { |
|
125 Digraph digraph; |
|
126 Node s; |
|
127 DoubleArcMap capacity(digraph); |
|
128 readDimacsSp(is, digraph, capacity, s, desc); |
|
129 DigraphWriter<Digraph>(digraph, os). |
|
130 arcMap("capacity", capacity). |
|
131 node("source", s). |
|
132 attribute("problem","sp"). |
|
133 run(); |
|
134 } |
|
135 break; |
|
136 case DimacsDescriptor::MAT: |
|
137 { |
|
138 Digraph digraph; |
|
139 readDimacsMat(is, digraph,desc); |
|
140 DigraphWriter<Digraph>(digraph, os). |
|
141 attribute("problem","mat"). |
|
142 run(); |
|
143 } |
|
144 break; |
|
145 default: |
|
146 break; |
|
147 } |
220 } |
|
221 |
|
222 if(ap.given("double")) |
|
223 solve<double>(ap,is,os,desc); |
|
224 else if(ap.given("ldouble")) |
|
225 solve<long double>(ap,is,os,desc); |
|
226 #ifdef HAVE_LONG_LONG |
|
227 else if(ap.given("long")) |
|
228 solve<long long>(ap,is,os,desc); |
|
229 #endif |
|
230 else solve<int>(ap,is,os,desc); |
|
231 |
148 return 0; |
232 return 0; |
149 } |
233 } |