Changeset - r649:a79ef774fae1
« 648:e8349c
650:425cc8 »
gravatar
kpeter (Peter Kovacs)
kpeter@inf.elte.hu
Support min cost flow in dimacs-solver (#234)
0 1 0
default
1 file changed with 25 insertions and 2 deletions:
tools/dimacs-solver.cc
25
2
↑ Collapse diff ↑
tools/dimacs-solver.cc
Ignore white space 6 line context
... ... 
@@ -44,6 +44,7 @@
44 44 
#include <lemon/dijkstra.h>
45 45 
#include <lemon/preflow.h>
46 46 
#include <lemon/max_matching.h>
47 
#include <lemon/network_simplex.h>
47 48 

			




	48
	49
	
		
using namespace lemon;


			




	49
	50
	
		
typedef SmartDigraph Digraph;


			




	...
	...
	
		
@@ -91,6 +92,29 @@


			




	91
	92
	
		
  if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n';  


			




	92
	93
	
		
}


			




	93
	94
	
		

			




	
	95
	
		
template<class Value>


			




	
	96
	
		
void solve_min(ArgParser &ap, std::istream &is, std::ostream &,


			




	
	97
	
		
               DimacsDescriptor &desc)


			




	
	98
	
		
{


			




	
	99
	
		
  bool report = !ap.given("q");


			




	
	100
	
		
  Digraph g;


			




	
	101
	
		
  Digraph::ArcMap<Value> lower(g), cap(g), cost(g);


			




	
	102
	
		
  Digraph::NodeMap<Value> sup(g);


			




	
	103
	
		
  Timer ti;


			




	
	104
	
		
  ti.restart();


			




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


			




	
	106
	
		
  if (report) std::cerr << "Read the file: " << ti << '\n';


			




	
	107
	
		
  ti.restart();


			




	
	108
	
		
  NetworkSimplex< Digraph, Digraph::ArcMap<Value>, Digraph::ArcMap<Value>,


			




	
	109
	
		
                  Digraph::ArcMap<Value>, Digraph::NodeMap<Value> >


			




	
	110
	
		
    ns(g, lower, cap, cost, sup);


			




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


			




	
	112
	
		
  ti.restart();


			




	
	113
	
		
  ns.run();


			




	
	114
	
		
  if (report) std::cerr << "Run NetworkSimplex: " << ti << '\n';


			




	
	115
	
		
  if (report) std::cerr << "\nMin flow cost: " << ns.totalCost() << '\n';


			




	
	116
	
		
}


			




	
	117
	
		

			




	94
	118
	
		
void solve_mat(ArgParser &ap, std::istream &is, std::ostream &,


			




	95
	119
	
		
              DimacsDescriptor &desc)


			




	96
	120
	
		
{


			




	...
	...
	
		
@@ -118,8 +142,7 @@


			




	118
	142
	
		
  switch(desc.type)


			




	119
	143
	
		
    {


			




	120
	144
	
		
    case DimacsDescriptor::MIN:


			




	121
	
	
		
      std::cerr <<


			




	122
	
	
		
        "\n\n Sorry, the min. cost flow solver is not yet available.\n";


			




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


			




	123
	146
	
		
      break;


			




	124
	147
	
		
    case DimacsDescriptor::MAX:


			




	125
	148
	
		
      solve_max<Value>(ap,is,os,desc);


			




        

    






    
    



    


    

     
    
0 comments (0 inline)