42 #include <lemon/error.h> |
42 #include <lemon/error.h> |
43 |
43 |
44 #include <lemon/dijkstra.h> |
44 #include <lemon/dijkstra.h> |
45 #include <lemon/preflow.h> |
45 #include <lemon/preflow.h> |
46 #include <lemon/max_matching.h> |
46 #include <lemon/max_matching.h> |
|
47 #include <lemon/network_simplex.h> |
47 |
48 |
48 using namespace lemon; |
49 using namespace lemon; |
49 typedef SmartDigraph Digraph; |
50 typedef SmartDigraph Digraph; |
50 DIGRAPH_TYPEDEFS(Digraph); |
51 DIGRAPH_TYPEDEFS(Digraph); |
51 typedef SmartGraph Graph; |
52 typedef SmartGraph Graph; |
89 pre.run(); |
90 pre.run(); |
90 if(report) std::cerr << "Run Preflow: " << ti << '\n'; |
91 if(report) std::cerr << "Run Preflow: " << ti << '\n'; |
91 if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n'; |
92 if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n'; |
92 } |
93 } |
93 |
94 |
|
95 template<class Value> |
|
96 void solve_min(ArgParser &ap, std::istream &is, std::ostream &, |
|
97 DimacsDescriptor &desc) |
|
98 { |
|
99 bool report = !ap.given("q"); |
|
100 Digraph g; |
|
101 Digraph::ArcMap<Value> lower(g), cap(g), cost(g); |
|
102 Digraph::NodeMap<Value> sup(g); |
|
103 Timer ti; |
|
104 ti.restart(); |
|
105 readDimacsMin(is, g, lower, cap, cost, sup, desc); |
|
106 if (report) std::cerr << "Read the file: " << ti << '\n'; |
|
107 ti.restart(); |
|
108 NetworkSimplex< Digraph, Digraph::ArcMap<Value>, Digraph::ArcMap<Value>, |
|
109 Digraph::ArcMap<Value>, Digraph::NodeMap<Value> > |
|
110 ns(g, lower, cap, cost, sup); |
|
111 if (report) std::cerr << "Setup NetworkSimplex class: " << ti << '\n'; |
|
112 ti.restart(); |
|
113 ns.run(); |
|
114 if (report) std::cerr << "Run NetworkSimplex: " << ti << '\n'; |
|
115 if (report) std::cerr << "\nMin flow cost: " << ns.totalCost() << '\n'; |
|
116 } |
|
117 |
94 void solve_mat(ArgParser &ap, std::istream &is, std::ostream &, |
118 void solve_mat(ArgParser &ap, std::istream &is, std::ostream &, |
95 DimacsDescriptor &desc) |
119 DimacsDescriptor &desc) |
96 { |
120 { |
97 bool report = !ap.given("q"); |
121 bool report = !ap.given("q"); |
98 Graph g; |
122 Graph g; |
116 DimacsDescriptor &desc) |
140 DimacsDescriptor &desc) |
117 { |
141 { |
118 switch(desc.type) |
142 switch(desc.type) |
119 { |
143 { |
120 case DimacsDescriptor::MIN: |
144 case DimacsDescriptor::MIN: |
121 std::cerr << |
145 solve_min<Value>(ap,is,os,desc); |
122 "\n\n Sorry, the min. cost flow solver is not yet available.\n"; |
|
123 break; |
146 break; |
124 case DimacsDescriptor::MAX: |
147 case DimacsDescriptor::MAX: |
125 solve_max<Value>(ap,is,os,desc); |
148 solve_max<Value>(ap,is,os,desc); |
126 break; |
149 break; |
127 case DimacsDescriptor::SP: |
150 case DimacsDescriptor::SP: |