91 if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n'; |
91 if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n'; |
92 } |
92 } |
93 |
93 |
94 template<class Value> |
94 template<class Value> |
95 void solve_min(ArgParser &ap, std::istream &is, std::ostream &, |
95 void solve_min(ArgParser &ap, std::istream &is, std::ostream &, |
96 DimacsDescriptor &desc) |
96 Value infty, DimacsDescriptor &desc) |
97 { |
97 { |
98 bool report = !ap.given("q"); |
98 bool report = !ap.given("q"); |
99 Digraph g; |
99 Digraph g; |
100 Digraph::ArcMap<Value> lower(g), cap(g), cost(g); |
100 Digraph::ArcMap<Value> lower(g), cap(g), cost(g); |
101 Digraph::NodeMap<Value> sup(g); |
101 Digraph::NodeMap<Value> sup(g); |
102 Timer ti; |
102 Timer ti; |
103 ti.restart(); |
103 |
104 readDimacsMin(is, g, lower, cap, cost, sup, 0, desc); |
104 ti.restart(); |
|
105 readDimacsMin(is, g, lower, cap, cost, sup, infty, desc); |
|
106 ti.stop(); |
|
107 Value sum_sup = 0; |
|
108 for (Digraph::NodeIt n(g); n != INVALID; ++n) { |
|
109 sum_sup += sup[n]; |
|
110 } |
|
111 if (report) { |
|
112 std::cerr << "Sum of supply values: " << sum_sup << "\n"; |
|
113 if (sum_sup <= 0) |
|
114 std::cerr << "GEQ supply contraints are used for NetworkSimplex\n\n"; |
|
115 else |
|
116 std::cerr << "LEQ supply contraints are used for NetworkSimplex\n\n"; |
|
117 } |
105 if (report) std::cerr << "Read the file: " << ti << '\n'; |
118 if (report) std::cerr << "Read the file: " << ti << '\n'; |
|
119 |
106 ti.restart(); |
120 ti.restart(); |
107 NetworkSimplex<Digraph, Value> ns(g); |
121 NetworkSimplex<Digraph, Value> ns(g); |
108 ns.lowerMap(lower).capacityMap(cap).costMap(cost).supplyMap(sup); |
122 ns.lowerMap(lower).capacityMap(cap).costMap(cost).supplyMap(sup); |
|
123 if (sum_sup > 0) ns.problemType(ns.LEQ); |
109 if (report) std::cerr << "Setup NetworkSimplex class: " << ti << '\n'; |
124 if (report) std::cerr << "Setup NetworkSimplex class: " << ti << '\n'; |
110 ti.restart(); |
125 ti.restart(); |
111 ns.run(); |
126 bool res = ns.run(); |
112 if (report) std::cerr << "Run NetworkSimplex: " << ti << '\n'; |
127 if (report) { |
113 if (report) std::cerr << "\nMin flow cost: " << ns.totalCost() << '\n'; |
128 std::cerr << "Run NetworkSimplex: " << ti << "\n\n"; |
|
129 std::cerr << "Feasible flow: " << (res ? "found" : "not found") << '\n'; |
|
130 if (res) std::cerr << "Min flow cost: " << ns.totalCost() << '\n'; |
|
131 } |
114 } |
132 } |
115 |
133 |
116 void solve_mat(ArgParser &ap, std::istream &is, std::ostream &, |
134 void solve_mat(ArgParser &ap, std::istream &is, std::ostream &, |
117 DimacsDescriptor &desc) |
135 DimacsDescriptor &desc) |
118 { |
136 { |
149 } |
167 } |
150 |
168 |
151 switch(desc.type) |
169 switch(desc.type) |
152 { |
170 { |
153 case DimacsDescriptor::MIN: |
171 case DimacsDescriptor::MIN: |
154 solve_min<Value>(ap,is,os,desc); |
172 solve_min<Value>(ap,is,os,infty,desc); |
155 break; |
173 break; |
156 case DimacsDescriptor::MAX: |
174 case DimacsDescriptor::MAX: |
157 solve_max<Value>(ap,is,os,infty,desc); |
175 solve_max<Value>(ap,is,os,infty,desc); |
158 break; |
176 break; |
159 case DimacsDescriptor::SP: |
177 case DimacsDescriptor::SP: |