Changeset 573:28b154307c0d in lemon
 Timestamp:
 02/23/09 12:49:57 (10 years ago)
 Branch:
 default
 Phase:
 public
 Location:
 tools
 Files:

 1 edited
 1 copied
Legend:
 Unmodified
 Added
 Removed

tools/Makefile.am
r570 r573 2 2 3 3 bin_PROGRAMS += \ 4 tools/dimacssolver \ 4 5 tools/dimacstolgf \ 5 6 tools/lgfgen … … 9 10 endif WANT_TOOLS 10 11 12 tools_dimacs_solver_SOURCES = tools/dimacssolver.cc 11 13 tools_dimacs_to_lgf_SOURCES = tools/dimacstolgf.cc 12 14 tools_lgf_gen_SOURCES = tools/lgfgen.cc 
tools/dimacssolver.cc
r463 r573 26 26 /// See 27 27 /// \verbatim 28 /// dimacs tolgfhelp28 /// dimacssolver help 29 29 /// \endverbatim 30 30 /// for more info on usage. … … 38 38 #include <lemon/dimacs.h> 39 39 #include <lemon/lgf_writer.h> 40 #include <lemon/time_measure.h> 40 41 41 42 #include <lemon/arg_parser.h> 42 43 #include <lemon/error.h> 43 44 44 using namespace std; 45 #include <lemon/dijkstra.h> 46 #include <lemon/preflow.h> 47 #include <lemon/max_matching.h> 48 45 49 using namespace lemon; 46 50 typedef SmartDigraph Digraph; 51 DIGRAPH_TYPEDEFS(Digraph); 52 typedef SmartGraph Graph; 53 54 template<class Value> 55 void solve_sp(ArgParser &ap, std::istream &is, std::ostream &, 56 DimacsDescriptor &desc) 57 { 58 bool report = !ap.given("q"); 59 Digraph g; 60 Node s; 61 Digraph::ArcMap<Value> len(g); 62 Timer t; 63 t.restart(); 64 readDimacsSp(is, g, len, s, desc); 65 if(report) std::cerr << "Read the file: " << t << '\n'; 66 t.restart(); 67 Dijkstra<Digraph, Digraph::ArcMap<Value> > dij(g,len); 68 if(report) std::cerr << "Setup Dijkstra class: " << t << '\n'; 69 t.restart(); 70 dij.run(s); 71 if(report) std::cerr << "Run Dijkstra: " << t << '\n'; 72 } 73 74 template<class Value> 75 void solve_max(ArgParser &ap, std::istream &is, std::ostream &, 76 DimacsDescriptor &desc) 77 { 78 bool report = !ap.given("q"); 79 Digraph g; 80 Node s,t; 81 Digraph::ArcMap<Value> cap(g); 82 Timer ti; 83 ti.restart(); 84 readDimacsMax(is, g, cap, s, t, desc); 85 if(report) std::cerr << "Read the file: " << ti << '\n'; 86 ti.restart(); 87 Preflow<Digraph, Digraph::ArcMap<Value> > pre(g,cap,s,t); 88 if(report) std::cerr << "Setup Preflow class: " << ti << '\n'; 89 ti.restart(); 90 pre.run(); 91 if(report) std::cerr << "Run Preflow: " << ti << '\n'; 92 if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n'; 93 } 94 95 void solve_mat(ArgParser &ap, std::istream &is, std::ostream &, 96 DimacsDescriptor &desc) 97 { 98 bool report = !ap.given("q"); 99 Graph g; 100 Timer ti; 101 ti.restart(); 102 readDimacsMat(is, g, desc); 103 if(report) std::cerr << "Read the file: " << ti << '\n'; 104 ti.restart(); 105 MaxMatching<Graph> mat(g); 106 if(report) std::cerr << "Setup MaxMatching class: " << ti << '\n'; 107 ti.restart(); 108 mat.run(); 109 if(report) std::cerr << "Run MaxMatching: " << ti << '\n'; 110 if(report) std::cerr << "\nCardinality of max matching: " 111 << mat.matchingSize() << '\n'; 112 } 113 114 115 template<class Value> 116 void solve(ArgParser &ap, std::istream &is, std::ostream &os, 117 DimacsDescriptor &desc) 118 { 119 switch(desc.type) 120 { 121 case DimacsDescriptor::MIN: 122 std::cerr << 123 "\n\n Sorry, the min. cost flow solver is not yet available.\n" 124 << std::endl; 125 break; 126 case DimacsDescriptor::MAX: 127 solve_max<Value>(ap,is,os,desc); 128 break; 129 case DimacsDescriptor::SP: 130 solve_sp<Value>(ap,is,os,desc); 131 break; 132 case DimacsDescriptor::MAT: 133 solve_mat(ap,is,os,desc); 134 break; 135 default: 136 break; 137 } 138 } 47 139 48 140 int main(int argc, const char *argv[]) { … … 63 155 "If either the INFILE or OUTFILE file is missing the standard\n" 64 156 " input/output will be used instead.") 157 .boolOption("q", "Do not print any report") 158 .boolOption("int","Use 'int' for capacities, costs etc. (default)") 159 .optionGroup("datatype","int") 160 #ifdef HAVE_LONG_LONG 161 .boolOption("long","Use 'long long' for capacities, costs etc.") 162 .optionGroup("datatype","long") 163 #endif 164 .boolOption("double","Use 'double' for capacities, costs etc.") 165 .optionGroup("datatype","double") 166 .boolOption("ldouble","Use 'long double' for capacities, costs etc.") 167 .optionGroup("datatype","ldouble") 168 .onlyOneGroup("datatype") 65 169 .run(); 66 170 67 ifstream input;68 ofstream output;171 std::ifstream input; 172 std::ofstream output; 69 173 70 174 switch(ap.files().size()) … … 83 187 break; 84 188 default: 85 cerr << ap.commandName() << ": too many arguments\n";189 std::cerr << ap.commandName() << ": too many arguments\n"; 86 190 return 1; 87 191 } 88 istream& is = (ap.files().size()<1 ?cin : input);89 ostream& os = (ap.files().size()<2 ?cout : output);192 std::istream& is = (ap.files().size()<1 ? std::cin : input); 193 std::ostream& os = (ap.files().size()<2 ? std::cout : output); 90 194 91 195 DimacsDescriptor desc = dimacsType(is); 92 switch(desc.type) 196 197 if(!ap.given("q")) 93 198 { 94 case DimacsDescriptor::MIN: 95 { 96 Digraph digraph; 97 DoubleArcMap lower(digraph), capacity(digraph), cost(digraph); 98 DoubleNodeMap supply(digraph); 99 readDimacsMin(is, digraph, lower, capacity, cost, supply, desc); 100 DigraphWriter<Digraph>(digraph, os). 101 nodeMap("supply", supply). 102 arcMap("lower", lower). 103 arcMap("capacity", capacity). 104 arcMap("cost", cost). 105 attribute("problem","min"). 106 run(); 107 } 108 break; 109 case DimacsDescriptor::MAX: 110 { 111 Digraph digraph; 112 Node s, t; 113 DoubleArcMap capacity(digraph); 114 readDimacsMax(is, digraph, capacity, s, t, desc); 115 DigraphWriter<Digraph>(digraph, os). 116 arcMap("capacity", capacity). 117 node("source", s). 118 node("target", t). 119 attribute("problem","max"). 120 run(); 121 } 122 break; 123 case DimacsDescriptor::SP: 124 { 125 Digraph digraph; 126 Node s; 127 DoubleArcMap capacity(digraph); 128 readDimacsSp(is, digraph, capacity, s, desc); 129 DigraphWriter<Digraph>(digraph, os). 130 arcMap("capacity", capacity). 131 node("source", s). 132 attribute("problem","sp"). 133 run(); 134 } 135 break; 136 case DimacsDescriptor::MAT: 137 { 138 Digraph digraph; 139 readDimacsMat(is, digraph,desc); 140 DigraphWriter<Digraph>(digraph, os). 141 attribute("problem","mat"). 142 run(); 143 } 144 break; 145 default: 146 break; 199 std::cout << "Problem type: "; 200 switch(desc.type) 201 { 202 case DimacsDescriptor::MIN: 203 std::cout << "min"; 204 break; 205 case DimacsDescriptor::MAX: 206 std::cout << "max"; 207 break; 208 case DimacsDescriptor::SP: 209 std::cout << "sp"; 210 case DimacsDescriptor::MAT: 211 std::cout << "mat"; 212 break; 213 default: 214 exit(1); 215 break; 216 } 217 std::cout << "\nNum of nodes: " << desc.nodeNum; 218 std::cout << "\nNum of arcs: " << desc.edgeNum; 219 std::cout << '\n' << std::endl; 147 220 } 221 222 if(ap.given("double")) 223 solve<double>(ap,is,os,desc); 224 else if(ap.given("ldouble")) 225 solve<long double>(ap,is,os,desc); 226 #ifdef HAVE_LONG_LONG 227 else if(ap.given("long")) 228 solve<long long>(ap,is,os,desc); 229 #endif 230 else solve<int>(ap,is,os,desc); 231 148 232 return 0; 149 233 }
Note: See TracChangeset
for help on using the changeset viewer.