41 #include <lemon/error.h> |
41 #include <lemon/error.h> |
42 |
42 |
43 #include <lemon/dijkstra.h> |
43 #include <lemon/dijkstra.h> |
44 #include <lemon/preflow.h> |
44 #include <lemon/preflow.h> |
45 #include <lemon/matching.h> |
45 #include <lemon/matching.h> |
|
46 #include <lemon/network_simplex.h> |
46 |
47 |
47 using namespace lemon; |
48 using namespace lemon; |
48 typedef SmartDigraph Digraph; |
49 typedef SmartDigraph Digraph; |
49 DIGRAPH_TYPEDEFS(Digraph); |
50 DIGRAPH_TYPEDEFS(Digraph); |
50 typedef SmartGraph Graph; |
51 typedef SmartGraph Graph; |
88 pre.run(); |
89 pre.run(); |
89 if(report) std::cerr << "Run Preflow: " << ti << '\n'; |
90 if(report) std::cerr << "Run Preflow: " << ti << '\n'; |
90 if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n'; |
91 if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n'; |
91 } |
92 } |
92 |
93 |
|
94 template<class Value> |
|
95 void solve_min(ArgParser &ap, std::istream &is, std::ostream &, |
|
96 DimacsDescriptor &desc) |
|
97 { |
|
98 bool report = !ap.given("q"); |
|
99 Digraph g; |
|
100 Digraph::ArcMap<Value> lower(g), cap(g), cost(g); |
|
101 Digraph::NodeMap<Value> sup(g); |
|
102 Timer ti; |
|
103 ti.restart(); |
|
104 readDimacsMin(is, g, lower, cap, cost, sup, 0, desc); |
|
105 if (report) std::cerr << "Read the file: " << ti << '\n'; |
|
106 ti.restart(); |
|
107 NetworkSimplex<Digraph, Value> ns(g); |
|
108 ns.lowerMap(lower).capacityMap(cap).costMap(cost).supplyMap(sup); |
|
109 if (report) std::cerr << "Setup NetworkSimplex class: " << ti << '\n'; |
|
110 ti.restart(); |
|
111 ns.run(); |
|
112 if (report) std::cerr << "Run NetworkSimplex: " << ti << '\n'; |
|
113 if (report) std::cerr << "\nMin flow cost: " << ns.totalCost() << '\n'; |
|
114 } |
|
115 |
93 void solve_mat(ArgParser &ap, std::istream &is, std::ostream &, |
116 void solve_mat(ArgParser &ap, std::istream &is, std::ostream &, |
94 DimacsDescriptor &desc) |
117 DimacsDescriptor &desc) |
95 { |
118 { |
96 bool report = !ap.given("q"); |
119 bool report = !ap.given("q"); |
97 Graph g; |
120 Graph g; |
126 } |
149 } |
127 |
150 |
128 switch(desc.type) |
151 switch(desc.type) |
129 { |
152 { |
130 case DimacsDescriptor::MIN: |
153 case DimacsDescriptor::MIN: |
131 std::cerr << |
154 solve_min<Value>(ap,is,os,desc); |
132 "\n\n Sorry, the min. cost flow solver is not yet available.\n"; |
|
133 break; |
155 break; |
134 case DimacsDescriptor::MAX: |
156 case DimacsDescriptor::MAX: |
135 solve_max<Value>(ap,is,os,infty,desc); |
157 solve_max<Value>(ap,is,os,infty,desc); |
136 break; |
158 break; |
137 case DimacsDescriptor::SP: |
159 case DimacsDescriptor::SP: |