Merge
authorAlpar Juttner <alpar@cs.elte.hu>
Fri, 24 Apr 2009 12:12:14 +0100
changeset 610b95898314e09
parent 609 4137ef9aacc6
parent 607 e3d9bff447ed
child 614 28f58740b6f8
child 617 029a48052c67
Merge
lemon/network_simplex.h
     1.1 --- a/lemon/network_simplex.h	Fri Apr 24 11:54:48 2009 +0200
     1.2 +++ b/lemon/network_simplex.h	Fri Apr 24 12:12:14 2009 +0100
     1.3 @@ -1147,6 +1147,7 @@
     1.4  
     1.5        // Run Circulation to check if a feasible solution exists
     1.6        typedef ConstMap<Arc, Flow> ConstArcMap;
     1.7 +      ConstArcMap zero_arc_map(0), inf_arc_map(inf_cap);
     1.8        FlowNodeMap *csup = NULL;
     1.9        bool local_csup = false;
    1.10        if (_psupply) {
    1.11 @@ -1167,17 +1168,17 @@
    1.12              circ_result = circ.run();
    1.13            } else {
    1.14              Circulation<GR, FlowArcMap, ConstArcMap, FlowNodeMap>
    1.15 -              circ(_graph, *_plower, ConstArcMap(inf_cap), *csup);
    1.16 +              circ(_graph, *_plower, inf_arc_map, *csup);
    1.17              circ_result = circ.run();
    1.18            }
    1.19          } else {
    1.20            if (_pupper) {
    1.21              Circulation<GR, ConstArcMap, FlowArcMap, FlowNodeMap>
    1.22 -              circ(_graph, ConstArcMap(0), *_pupper, *csup);
    1.23 +              circ(_graph, zero_arc_map, *_pupper, *csup);
    1.24              circ_result = circ.run();
    1.25            } else {
    1.26              Circulation<GR, ConstArcMap, ConstArcMap, FlowNodeMap>
    1.27 -              circ(_graph, ConstArcMap(0), ConstArcMap(inf_cap), *csup);
    1.28 +              circ(_graph, zero_arc_map, inf_arc_map, *csup);
    1.29              circ_result = circ.run();
    1.30            }
    1.31          }
    1.32 @@ -1194,17 +1195,17 @@
    1.33              circ_result = circ.run();
    1.34            } else {
    1.35              Circulation<RevGraph, FlowArcMap, ConstArcMap, NegNodeMap>
    1.36 -              circ(rgraph, *_plower, ConstArcMap(inf_cap), neg_csup);
    1.37 +              circ(rgraph, *_plower, inf_arc_map, neg_csup);
    1.38              circ_result = circ.run();
    1.39            }
    1.40          } else {
    1.41            if (_pupper) {
    1.42              Circulation<RevGraph, ConstArcMap, FlowArcMap, NegNodeMap>
    1.43 -              circ(rgraph, ConstArcMap(0), *_pupper, neg_csup);
    1.44 +              circ(rgraph, zero_arc_map, *_pupper, neg_csup);
    1.45              circ_result = circ.run();
    1.46            } else {
    1.47              Circulation<RevGraph, ConstArcMap, ConstArcMap, NegNodeMap>
    1.48 -              circ(rgraph, ConstArcMap(0), ConstArcMap(inf_cap), neg_csup);
    1.49 +              circ(rgraph, zero_arc_map, inf_arc_map, neg_csup);
    1.50              circ_result = circ.run();
    1.51            }
    1.52          }
     2.1 --- a/test/min_cost_flow_test.cc	Fri Apr 24 11:54:48 2009 +0200
     2.2 +++ b/test/min_cost_flow_test.cc	Fri Apr 24 12:12:14 2009 +0100
     2.3 @@ -233,12 +233,7 @@
     2.4    {
     2.5      typedef int Flow;
     2.6      typedef int Cost;
     2.7 -    // TODO: This typedef should be enabled if the standard maps are
     2.8 -    // reference maps in the graph concepts (See #190).
     2.9 -/**/
    2.10 -    //typedef concepts::Digraph GR;
    2.11 -    typedef ListDigraph GR;
    2.12 -/**/
    2.13 +    typedef concepts::Digraph GR;
    2.14      checkConcept< McfClassConcept<GR, Flow, Cost>,
    2.15                    NetworkSimplex<GR, Flow, Cost> >();
    2.16    }
     3.1 --- a/tools/dimacs-solver.cc	Fri Apr 24 11:54:48 2009 +0200
     3.2 +++ b/tools/dimacs-solver.cc	Fri Apr 24 12:12:14 2009 +0100
     3.3 @@ -93,24 +93,42 @@
     3.4  
     3.5  template<class Value>
     3.6  void solve_min(ArgParser &ap, std::istream &is, std::ostream &,
     3.7 -               DimacsDescriptor &desc)
     3.8 +               Value infty, DimacsDescriptor &desc)
     3.9  {
    3.10    bool report = !ap.given("q");
    3.11    Digraph g;
    3.12    Digraph::ArcMap<Value> lower(g), cap(g), cost(g);
    3.13    Digraph::NodeMap<Value> sup(g);
    3.14    Timer ti;
    3.15 +
    3.16    ti.restart();
    3.17 -  readDimacsMin(is, g, lower, cap, cost, sup, 0, desc);
    3.18 +  readDimacsMin(is, g, lower, cap, cost, sup, infty, desc);
    3.19 +  ti.stop();
    3.20 +  Value sum_sup = 0;
    3.21 +  for (Digraph::NodeIt n(g); n != INVALID; ++n) {
    3.22 +    sum_sup += sup[n];
    3.23 +  }
    3.24 +  if (report) {
    3.25 +    std::cerr << "Sum of supply values: " << sum_sup << "\n";
    3.26 +    if (sum_sup <= 0)
    3.27 +      std::cerr << "GEQ supply contraints are used for NetworkSimplex\n\n";
    3.28 +    else
    3.29 +      std::cerr << "LEQ supply contraints are used for NetworkSimplex\n\n";
    3.30 +  }
    3.31    if (report) std::cerr << "Read the file: " << ti << '\n';
    3.32 +
    3.33    ti.restart();
    3.34    NetworkSimplex<Digraph, Value> ns(g);
    3.35    ns.lowerMap(lower).capacityMap(cap).costMap(cost).supplyMap(sup);
    3.36 +  if (sum_sup > 0) ns.problemType(ns.LEQ);
    3.37    if (report) std::cerr << "Setup NetworkSimplex class: " << ti << '\n';
    3.38    ti.restart();
    3.39 -  ns.run();
    3.40 -  if (report) std::cerr << "Run NetworkSimplex: " << ti << '\n';
    3.41 -  if (report) std::cerr << "\nMin flow cost: " << ns.totalCost() << '\n';
    3.42 +  bool res = ns.run();
    3.43 +  if (report) {
    3.44 +    std::cerr << "Run NetworkSimplex: " << ti << "\n\n";
    3.45 +    std::cerr << "Feasible flow: " << (res ? "found" : "not found") << '\n';
    3.46 +    if (res) std::cerr << "Min flow cost: " << ns.totalCost() << '\n';
    3.47 +  }
    3.48  }
    3.49  
    3.50  void solve_mat(ArgParser &ap, std::istream &is, std::ostream &,
    3.51 @@ -151,7 +169,7 @@
    3.52    switch(desc.type)
    3.53      {
    3.54      case DimacsDescriptor::MIN:
    3.55 -      solve_min<Value>(ap,is,os,desc);
    3.56 +      solve_min<Value>(ap,is,os,infty,desc);
    3.57        break;
    3.58      case DimacsDescriptor::MAX:
    3.59        solve_max<Value>(ap,is,os,infty,desc);