Changeset - r618:b95898314e09
« 615:e3d9bf
« 617:4137ef
625:029a48 »
622:28f587 »
gravatar
alpar (Alpar Juttner)
alpar@cs.elte.hu
Merge
0 3 0
merge default
1 file changed with 32 insertions and 18 deletions:
lemon/network_simplex.h
7
6
test/min_cost_flow_test.cc
1
6
tools/dimacs-solver.cc
24
6
↑ Collapse diff ↑
lemon/network_simplex.h
Ignore white space 4 line context
... ... 
@@ -1148,4 +1148,5 @@
1148 1148 
      // Run Circulation to check if a feasible solution exists
1149 1149 
      typedef ConstMap<Arc, Flow> ConstArcMap;
1150 
      ConstArcMap zero_arc_map(0), inf_arc_map(inf_cap);
1150 1151 
      FlowNodeMap *csup = NULL;
1151 1152 
      bool local_csup = false;
... ... 
@@ -1168,5 +1169,5 @@
1168 1169 
          } else {
1169 1170 
            Circulation<GR, FlowArcMap, ConstArcMap, FlowNodeMap>
1170 
              circ(_graph, *_plower, ConstArcMap(inf_cap), *csup);
1171 
              circ(_graph, *_plower, inf_arc_map, *csup);
1171 1172 
            circ_result = circ.run();
1172 1173 
          }
... ... 
@@ -1174,9 +1175,9 @@
1174 1175 
          if (_pupper) {
1175 1176 
            Circulation<GR, ConstArcMap, FlowArcMap, FlowNodeMap>
1176 
              circ(_graph, ConstArcMap(0), *_pupper, *csup);
1177 
              circ(_graph, zero_arc_map, *_pupper, *csup);
1177 1178 
            circ_result = circ.run();
1178 1179 
          } else {
1179 1180 
            Circulation<GR, ConstArcMap, ConstArcMap, FlowNodeMap>
1180 
              circ(_graph, ConstArcMap(0), ConstArcMap(inf_cap), *csup);
1181 
              circ(_graph, zero_arc_map, inf_arc_map, *csup);
1181 1182 
            circ_result = circ.run();
1182 1183 
          }
... ... 
@@ -1195,5 +1196,5 @@
1195 1196 
          } else {
1196 1197 
            Circulation<RevGraph, FlowArcMap, ConstArcMap, NegNodeMap>
1197 
              circ(rgraph, *_plower, ConstArcMap(inf_cap), neg_csup);
1198 
              circ(rgraph, *_plower, inf_arc_map, neg_csup);
1198 1199 
            circ_result = circ.run();
1199 1200 
          }
... ... 
@@ -1201,9 +1202,9 @@
1201 1202 
          if (_pupper) {
1202 1203 
            Circulation<RevGraph, ConstArcMap, FlowArcMap, NegNodeMap>
1203 
              circ(rgraph, ConstArcMap(0), *_pupper, neg_csup);
1204 
              circ(rgraph, zero_arc_map, *_pupper, neg_csup);
1204 1205 
            circ_result = circ.run();
1205 1206 
          } else {
1206 1207 
            Circulation<RevGraph, ConstArcMap, ConstArcMap, NegNodeMap>
1207 
              circ(rgraph, ConstArcMap(0), ConstArcMap(inf_cap), neg_csup);
1208 
              circ(rgraph, zero_arc_map, inf_arc_map, neg_csup);
1208 1209 
            circ_result = circ.run();
1209 1210 
          }
test/min_cost_flow_test.cc
Ignore white space 6 line context
... ... 
@@ -234,10 +234,5 @@
234 234 
    typedef int Flow;
235 235 
    typedef int Cost;
236 
    // TODO: This typedef should be enabled if the standard maps are
237 
    // reference maps in the graph concepts (See #190).
238 
/**/
239 
    //typedef concepts::Digraph GR;
240 
    typedef ListDigraph GR;
241 
/**/
236 
    typedef concepts::Digraph GR;
242 237 
    checkConcept< McfClassConcept<GR, Flow, Cost>,
243 238 
                  NetworkSimplex<GR, Flow, Cost> >();
tools/dimacs-solver.cc
Ignore white space 6 line context
... ... 
@@ -94,5 +94,5 @@
94 94 
template<class Value>
95 95 
void solve_min(ArgParser &ap, std::istream &is, std::ostream &,
96 
               DimacsDescriptor &desc)
96 
               Value infty, DimacsDescriptor &desc)
97 97 
{
98 98 
  bool report = !ap.given("q");
... ... 
@@ -101,15 +101,33 @@
101 101 
  Digraph::NodeMap<Value> sup(g);
102 102 
  Timer ti;
103 

			




	103
	104
	
		
  ti.restart();


			




	104
	
	
		
  readDimacsMin(is, g, lower, cap, cost, sup, 0, desc);


			




	
	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
	118
	
		
  if (report) std::cerr << "Read the file: " << ti << '\n';


			




	
	119
	
		

			




	106
	120
	
		
  ti.restart();


			




	107
	121
	
		
  NetworkSimplex<Digraph, Value> ns(g);


			




	108
	122
	
		
  ns.lowerMap(lower).capacityMap(cap).costMap(cost).supplyMap(sup);


			




	
	123
	
		
  if (sum_sup > 0) ns.problemType(ns.LEQ);


			




	109
	124
	
		
  if (report) std::cerr << "Setup NetworkSimplex class: " << ti << '\n';


			




	110
	125
	
		
  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';


			




	
	126
	
		
  bool res = ns.run();


			




	
	127
	
		
  if (report) {


			




	
	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
	
		

			




	...
	...
	
		
@@ -152,5 +170,5 @@


			




	152
	170
	
		
    {


			




	153
	171
	
		
    case DimacsDescriptor::MIN:


			




	154
	
	
		
      solve_min<Value>(ap,is,os,desc);


			




	
	172
	
		
      solve_min<Value>(ap,is,os,infty,desc);


			




	155
	173
	
		
      break;


			




	156
	174
	
		
    case DimacsDescriptor::MAX:


			




        

    






    
    



    


    

     
    
0 comments (0 inline)