LEMON/LEMON-main Changeset - r618:b95898314e09

Repositories » LEMON » LEMON-main

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r618:b95898314e09

« 615:e3d9bf
« 617:4137ef

625:029a48 »
622:28f587 »

r618:b95898314e09

Fri, 24 Apr 2009 13:12:14

[Not Reviewed]

0 comments (0 inline)

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

test/min_cost_flow_test.cc

tools/dimacs-solver.cc

↑ Collapse diff ↑

lemon/network_simplex.h

Show inline comments

@@ -1144,12 +1144,13 @@
+		        }
 		        art_cost = (art_cost + 1) * _node_num;
+		      }
 		      // Run Circulation to check if a feasible solution exists
 		      typedef ConstMap<Arc, Flow> ConstArcMap;
 		      ConstArcMap zero_arc_map(0), inf_arc_map(inf_cap);
 		      FlowNodeMap *csup = NULL;
 		      bool local_csup = false;
 		      if (_psupply) {
 		        csup = _psupply;
 		      } else {
 		        csup = new FlowNodeMap(_graph, 0);
@@ -1164,23 +1165,23 @@
 		          if (_pupper) {
 		            Circulation<GR, FlowArcMap, FlowArcMap, FlowNodeMap>
 		              circ(_graph, *_plower, *_pupper, *csup);
 		            circ_result = circ.run();
 		          } else {
 		            Circulation<GR, FlowArcMap, ConstArcMap, FlowNodeMap>
-		              circ(_graph, *_plower, ConstArcMap(inf_cap), *csup);
+		              circ(_graph, *_plower, inf_arc_map, *csup);
 		            circ_result = circ.run();
+		          }
 		        } else {
 		          if (_pupper) {
 		            Circulation<GR, ConstArcMap, FlowArcMap, FlowNodeMap>
-		              circ(_graph, ConstArcMap(0), *_pupper, *csup);
+		              circ(_graph, zero_arc_map, *_pupper, *csup);
 		            circ_result = circ.run();
 		          } else {
 		            Circulation<GR, ConstArcMap, ConstArcMap, FlowNodeMap>
-		              circ(_graph, ConstArcMap(0), ConstArcMap(inf_cap), *csup);
+		              circ(_graph, zero_arc_map, inf_arc_map, *csup);
 		            circ_result = circ.run();
+		          }
+		        }
 		      } else {
 		        // LEQ problem type
 		        typedef ReverseDigraph<const GR> RevGraph;
@@ -1191,23 +1192,23 @@
 		          if (_pupper) {
 		            Circulation<RevGraph, FlowArcMap, FlowArcMap, NegNodeMap>
 		              circ(rgraph, *_plower, *_pupper, neg_csup);
 		            circ_result = circ.run();
 		          } else {
 		            Circulation<RevGraph, FlowArcMap, ConstArcMap, NegNodeMap>
-		              circ(rgraph, *_plower, ConstArcMap(inf_cap), neg_csup);
+		              circ(rgraph, *_plower, inf_arc_map, neg_csup);
 		            circ_result = circ.run();
+		          }
 		        } else {
 		          if (_pupper) {
 		            Circulation<RevGraph, ConstArcMap, FlowArcMap, NegNodeMap>
-		              circ(rgraph, ConstArcMap(0), *_pupper, neg_csup);
+		              circ(rgraph, zero_arc_map, *_pupper, neg_csup);
 		            circ_result = circ.run();
 		          } else {
 		            Circulation<RevGraph, ConstArcMap, ConstArcMap, NegNodeMap>
-		              circ(rgraph, ConstArcMap(0), ConstArcMap(inf_cap), neg_csup);
+		              circ(rgraph, zero_arc_map, inf_arc_map, neg_csup);
 		            circ_result = circ.run();
+		          }
+		        }
+		      }
 		      if (local_csup) delete csup;
 		      if (!circ_result) return false;

test/min_cost_flow_test.cc

Show inline comments

@@ -230,18 +230,13 @@
 		int main()
+		{
 		  // Check the interfaces
+		  {
 		    typedef int Flow;
 		    typedef int Cost;
 		    // TODO: This typedef should be enabled if the standard maps are
 		    // reference maps in the graph concepts (See #190).
 		/**/
 		    //typedef concepts::Digraph GR;
 		    typedef ListDigraph GR;
 		/**/
 		    typedef concepts::Digraph GR;
 		    checkConcept< McfClassConcept<GR, Flow, Cost>,
 		                  NetworkSimplex<GR, Flow, Cost> >();
+		  }
 		  // Run various MCF tests
 		  typedef ListDigraph Digraph;

tools/dimacs-solver.cc

Show inline comments

@@ -90,30 +90,48 @@
 		  if(report) std::cerr << "Run Preflow: " << ti << '\n';
 		  if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n';
+		}
 		template<class Value>
 		void solve_min(ArgParser &ap, std::istream &is, std::ostream &,
 		               DimacsDescriptor &desc)
+		               Value infty, DimacsDescriptor &desc)
+		{
 		  bool report = !ap.given("q");
 		  Digraph g;
 		  Digraph::ArcMap<Value> lower(g), cap(g), cost(g);
 		  Digraph::NodeMap<Value> sup(g);
 		  Timer ti;
 		  ti.restart();
-		  readDimacsMin(is, g, lower, cap, cost, sup, 0, desc);
+		  readDimacsMin(is, g, lower, cap, cost, sup, infty, desc);
 		  ti.stop();
 		  Value sum_sup = 0;
 		  for (Digraph::NodeIt n(g); n != INVALID; ++n) {
 		    sum_sup += sup[n];
+		  }
 		  if (report) {
 		    std::cerr << "Sum of supply values: " << sum_sup << "\n";
 		    if (sum_sup <= 0)
 		      std::cerr << "GEQ supply contraints are used for NetworkSimplex\n\n";
 		    else
 		      std::cerr << "LEQ supply contraints are used for NetworkSimplex\n\n";
+		  }
 		  if (report) std::cerr << "Read the file: " << ti << '\n';
 		  ti.restart();
 		  NetworkSimplex<Digraph, Value> ns(g);
 		  ns.lowerMap(lower).capacityMap(cap).costMap(cost).supplyMap(sup);
 		  if (sum_sup > 0) ns.problemType(ns.LEQ);
 		  if (report) std::cerr << "Setup NetworkSimplex class: " << ti << '\n';
 		  ti.restart();
 		  ns.run();
 		  if (report) std::cerr << "Run NetworkSimplex: " << ti << '\n';
-		  if (report) std::cerr << "\nMin flow cost: " << ns.totalCost() << '\n';
+		  bool res = ns.run();
 		  if (report) {
 		    std::cerr << "Run NetworkSimplex: " << ti << "\n\n";
 		    std::cerr << "Feasible flow: " << (res ? "found" : "not found") << '\n';
 		    if (res) std::cerr << "Min flow cost: " << ns.totalCost() << '\n';
+		  }
+		}
 		void solve_mat(ArgParser &ap, std::istream &is, std::ostream &,
 		              DimacsDescriptor &desc)
+		{
 		  bool report = !ap.given("q");
@@ -148,13 +166,13 @@
 		      exit(1);
+		    }
 		  switch(desc.type)
+		    {
 		    case DimacsDescriptor::MIN:
 		      solve_min<Value>(ap,is,os,desc);
+		      solve_min<Value>(ap,is,os,infty,desc);
 		      break;
 		    case DimacsDescriptor::MAX:
 		      solve_max<Value>(ap,is,os,infty,desc);
 		      break;
 		    case DimacsDescriptor::SP:
 		      solve_sp<Value>(ap,is,os,desc);

0 comments (0 inline)

RhodeCode

Login to your account