diff --git a/lemon/dimacs.h b/lemon/dimacs.h --- a/lemon/dimacs.h +++ b/lemon/dimacs.h @@ -23,6 +23,7 @@ #include #include #include +#include /// \ingroup dimacs_group /// \file @@ -40,6 +41,70 @@ /// \addtogroup dimacs_group /// @{ + + /// DIMACS file type descriptor. + struct DimacsDescriptor + { + ///File type enum + enum Type + { + NONE, MIN, MAX, SP, MAT + }; + ///The file type + Type type; + ///The number of nodes on the graph + int nodeNum; + ///The number of edges on the graph + int edgeNum; + int lineShift; + /// Constructor. Sets the type to NONE. + DimacsDescriptor() : type(NONE) {} + }; + + ///Discover the type of a DIMACS file + + ///It starts seeking the begining of the file for the problem type + ///and size info. The found date is returned in a special struct + ///that can be evaluated and passed to the appropriate reader + ///function. + DimacsDescriptor dimacsType(std::istream& is) + { + DimacsDescriptor r; + std::string problem,str; + char c; + r.lineShift=0; + while (is >> c) + switch(c) + { + case 'p': + if(is >> problem >> r.nodeNum >> r.edgeNum) + { + getline(is, str); + r.lineShift++; + if(problem=="min") r.type=DimacsDescriptor::MIN; + else if(problem=="max") r.type=DimacsDescriptor::MAX; + else if(problem=="sp") r.type=DimacsDescriptor::SP; + else if(problem=="mat") r.type=DimacsDescriptor::MAT; + else throw FormatError("Unknown problem type"); + return r; + } + else + { + throw FormatError("Missing or wrong problem type declaration."); + } + break; + case 'c': + getline(is, str); + r.lineShift++; + break; + default: + throw FormatError("Unknown DIMACS declaration."); + } + throw FormatError("Missing problem type declaration."); + } + + + /// DIMACS min cost flow reader function. /// /// This function reads a min cost flow instance from DIMACS format, @@ -47,27 +112,40 @@ /// \code /// p min /// \endcode - /// At the beginning \c g is cleared by \c g.clear(). The supply + /// At the beginning, \c g is cleared by \c g.clear(). The supply /// amount of the nodes are written to \c supply (signed). The /// lower bounds, capacities and costs of the arcs are written to /// \c lower, \c capacity and \c cost. + /// + /// If the file type was previously evaluated by dimacsType(), then + /// the descriptor struct should be given by the \c dest parameter. template - void readDimacsMin( std::istream& is, - Digraph &g, - LowerMap& lower, - CapacityMap& capacity, - CostMap& cost, - SupplyMap& supply ) + typename CapacityMap, typename CostMap, + typename SupplyMap> + void readDimacsMin(std::istream& is, + Digraph &g, + LowerMap& lower, + CapacityMap& capacity, + CostMap& cost, + SupplyMap& supply, + DimacsDescriptor desc=DimacsDescriptor()) { g.clear(); std::vector nodes; typename Digraph::Arc e; std::string problem, str; char c; - int n, m; int i, j; + if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is); + if(desc.type!=DimacsDescriptor::MIN) + throw FormatError("Problem type mismatch"); + + nodes.resize(desc.nodeNum + 1); + for (int k = 1; k <= desc.nodeNum; ++k) { + nodes[k] = g.addNode(); + supply.set(nodes[k], 0); + } + typename SupplyMap::Value sup; typename CapacityMap::Value low; typename CapacityMap::Value cap; @@ -77,16 +155,6 @@ case 'c': // comment line getline(is, str); break; - case 'p': // problem definition line - is >> problem >> n >> m; - getline(is, str); - if (problem != "min") return; - nodes.resize(n + 1); - for (int k = 1; k <= n; ++k) { - nodes[k] = g.addNode(); - supply.set(nodes[k], 0); - } - break; case 'n': // node definition line is >> i >> sup; getline(is, str); @@ -107,47 +175,38 @@ } } - /// DIMACS max flow reader function. - /// - /// This function reads a max flow instance from DIMACS format, - /// i.e. from DIMACS files having a line starting with - /// \code - /// p max - /// \endcode - /// At the beginning \c g is cleared by \c g.clear(). The arc - /// capacities are written to \c capacity and \c s and \c t are - /// set to the source and the target nodes. template - void readDimacsMax(std::istream& is, Digraph &g, CapacityMap& capacity, - typename Digraph::Node &s, typename Digraph::Node &t) { + void _readDimacs(std::istream& is, + Digraph &g, + CapacityMap& capacity, + typename Digraph::Node &s, + typename Digraph::Node &t, + DimacsDescriptor desc=DimacsDescriptor()) { g.clear(); + s=t=INVALID; std::vector nodes; typename Digraph::Arc e; - std::string problem; char c, d; - int n, m; int i, j; typename CapacityMap::Value _cap; std::string str; + nodes.resize(desc.nodeNum + 1); + for (int k = 1; k <= desc.nodeNum; ++k) { + nodes[k] = g.addNode(); + } + while (is >> c) { switch (c) { case 'c': // comment line getline(is, str); break; - case 'p': // problem definition line - is >> problem >> n >> m; - getline(is, str); - nodes.resize(n + 1); - for (int k = 1; k <= n; ++k) - nodes[k] = g.addNode(); - break; case 'n': // node definition line - if (problem == "sp") { // shortest path problem + if (desc.type==DimacsDescriptor::SP) { // shortest path problem is >> i; getline(is, str); s = nodes[i]; } - if (problem == "max") { // max flow problem + if (desc.type==DimacsDescriptor::MAX) { // max flow problem is >> i >> d; getline(is, str); if (d == 's') s = nodes[i]; @@ -155,7 +214,8 @@ } break; case 'a': // arc (arc) definition line - if (problem == "max" || problem == "sp") { + if (desc.type==DimacsDescriptor::SP || + desc.type==DimacsDescriptor::MAX) { is >> i >> j >> _cap; getline(is, str); e = g.addArc(nodes[i], nodes[j]); @@ -170,6 +230,32 @@ } } + /// DIMACS max flow reader function. + /// + /// This function reads a max flow instance from DIMACS format, + /// i.e. from DIMACS files having a line starting with + /// \code + /// p max + /// \endcode + /// At the beginning, \c g is cleared by \c g.clear(). The arc + /// capacities are written to \c capacity and \c s and \c t are + /// set to the source and the target nodes. + /// + /// If the file type was previously evaluated by dimacsType(), then + /// the descriptor struct should be given by the \c dest parameter. + template + void readDimacsMax(std::istream& is, + Digraph &g, + CapacityMap& capacity, + typename Digraph::Node &s, + typename Digraph::Node &t, + DimacsDescriptor desc=DimacsDescriptor()) { + if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is); + if(desc.type!=DimacsDescriptor::MAX) + throw FormatError("Problem type mismatch"); + _readDimacs(is,g,capacity,s,t,desc); + } + /// DIMACS shortest path reader function. /// /// This function reads a shortest path instance from DIMACS format, @@ -177,25 +263,44 @@ /// \code /// p sp /// \endcode - /// At the beginning \c g is cleared by \c g.clear(). The arc - /// capacities are written to \c capacity and \c s is set to the + /// At the beginning, \c g is cleared by \c g.clear(). The arc + /// lengths are written to \c lenght and \c s is set to the /// source node. - template - void readDimacsSp(std::istream& is, Digraph &g, CapacityMap& capacity, - typename Digraph::Node &s) { + /// + /// If the file type was previously evaluated by dimacsType(), then + /// the descriptor struct should be given by the \c dest parameter. + template + void readDimacsSp(std::istream& is, + Digraph &g, + LengthMap& length, + typename Digraph::Node &s, + DimacsDescriptor desc=DimacsDescriptor()) { typename Digraph::Node t; - readDimacsMax(is, g, capacity, s, t); + if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is); + if(desc.type!=DimacsDescriptor::SP) + throw FormatError("Problem type mismatch"); + _readDimacs(is, g, length, s, t,desc); } /// DIMACS capacitated digraph reader function. /// /// This function reads an arc capacitated digraph instance from - /// DIMACS format. At the beginning \c g is cleared by \c g.clear() - /// and the arc capacities are written to \c capacity. + /// DIMACS 'mat' or 'sp' format. + /// At the beginning, \c g is cleared by \c g.clear() + /// and the arc capacities/lengths are written to \c capacity. + /// + /// If the file type was previously evaluated by dimacsType(), then + /// the descriptor struct should be given by the \c dest parameter. template - void readDimacsMax(std::istream& is, Digraph &g, CapacityMap& capacity) { + void readDimacsCap(std::istream& is, + Digraph &g, + CapacityMap& capacity, + DimacsDescriptor desc=DimacsDescriptor()) { typename Digraph::Node u,v; - readDimacsMax(is, g, capacity, u, v); + if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is); + if(desc.type!=DimacsDescriptor::MAX || desc.type!=DimacsDescriptor::SP) + throw FormatError("Problem type mismatch"); + _readDimacs(is, g, capacity, u, v, desc); } /// DIMACS plain digraph reader function. @@ -206,12 +311,19 @@ /// \code /// p mat /// \endcode - /// At the beginning \c g is cleared by \c g.clear(). + /// At the beginning, \c g is cleared by \c g.clear(). + /// + /// If the file type was previously evaluated by dimacsType(), then + /// the descriptor struct should be given by the \c dest parameter. template - void readDimacsMat(std::istream& is, Digraph &g) { + void readDimacsMat(std::istream& is, Digraph &g, + DimacsDescriptor desc=DimacsDescriptor()) { typename Digraph::Node u,v; NullMap n; - readDimacsMax(is, g, n, u, v); + if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is); + if(desc.type!=DimacsDescriptor::MAT) + throw FormatError("Problem type mismatch"); + _readDimacs(is, g, n, u, v, desc); } /// DIMACS plain digraph writer function. @@ -222,12 +334,16 @@ /// \code /// p mat /// \endcode + /// If \c comment is not empty, then it will be printed in the first line + /// prefixed by 'c'. template - void writeDimacsMat(std::ostream& os, const Digraph &g) { + void writeDimacsMat(std::ostream& os, const Digraph &g, + std::string comment="") { typedef typename Digraph::NodeIt NodeIt; typedef typename Digraph::ArcIt ArcIt; - os << "c matching problem" << std::endl; + if(!comment.empty()) + os << "c " << comment << std::endl; os << "p mat " << g.nodeNum() << " " << g.arcNum() << std::endl; typename Digraph::template NodeMap nodes(g); diff --git a/tools/dimacs-to-lgf.cc b/tools/dimacs-to-lgf.cc --- a/tools/dimacs-to-lgf.cc +++ b/tools/dimacs-to-lgf.cc @@ -39,6 +39,7 @@ #include #include +#include using namespace std; using namespace lemon; @@ -56,113 +57,93 @@ std::string inputName; std::string outputName; - std::string typeName; - - bool mincostflow; - bool maxflow; - bool shortestpath; - bool capacitated; - bool plain; - - bool version; ArgParser ap(argc, argv); - ap.refOption("-input", - "use FILE as input instead of standard input", - inputName).synonym("i", "-input") - .refOption("-output", - "use FILE as output instead of standard output", - outputName).synonym("o", "-output") - .refOption("-mincostflow", - "set the type of the digraph to \"mincostflow\" digraph", - mincostflow) - .optionGroup("type", "-mincostflow").synonym("mcf", "-mincostflow") - .refOption("-maxflow", - "set the type of the digraph to \"maxflow\" digraph", - maxflow) - .optionGroup("type", "-maxflow").synonym("mf", "-maxflow") - .refOption("-shortestpath", - "set the type of the digraph to \"shortestpath\" digraph", - shortestpath) - .optionGroup("type", "-shortestpath").synonym("sp", "-shortestpath") - .refOption("-capacitated", - "set the type of the digraph to \"capacitated\" digraph", - capacitated) - .optionGroup("type", "-capacitated").synonym("cap", "-capacitated") - .refOption("-plain", - "set the type of the digraph to \"plain\" digraph", - plain) - .optionGroup("type", "-plain").synonym("pl", "-plain") - .onlyOneGroup("type") - .mandatoryGroup("type") - .refOption("-version", "show version information", version) - .synonym("v", "-version") + ap.other("[INFILE [OUTFILE]]", + "If either the INFILE or OUTFILE file is missing the standard\n" + " input/output will be used instead.") .run(); ifstream input; - if (!inputName.empty()) { - input.open(inputName.c_str()); - if (!input) { - cerr << "File open error" << endl; - return -1; + ofstream output; + + switch(ap.files().size()) + { + case 2: + output.open(ap.files()[1].c_str()); + if (!output) { + throw IoError("Cannot open the file for writing", ap.files()[1]); + } + case 1: + input.open(ap.files()[0].c_str()); + if (!input) { + throw IoError("File cannot be found", ap.files()[0]); + } + case 0: + break; + default: + cerr << ap.commandName() << ": too many arguments\n"; + return 1; + } + istream& is = (ap.files().size()<1 ? cin : input); + ostream& os = (ap.files().size()<2 ? cout : output); + + DimacsDescriptor desc = dimacsType(is); + switch(desc.type) + { + case DimacsDescriptor::MIN: + { + Digraph digraph; + DoubleArcMap lower(digraph), capacity(digraph), cost(digraph); + DoubleNodeMap supply(digraph); + readDimacsMin(is, digraph, lower, capacity, cost, supply, desc); + DigraphWriter(digraph, os). + nodeMap("supply", supply). + arcMap("lower", lower). + arcMap("capacity", capacity). + arcMap("cost", cost). + attribute("problem","min"). + run(); + } + break; + case DimacsDescriptor::MAX: + { + Digraph digraph; + Node s, t; + DoubleArcMap capacity(digraph); + readDimacsMax(is, digraph, capacity, s, t, desc); + DigraphWriter(digraph, os). + arcMap("capacity", capacity). + node("source", s). + node("target", t). + attribute("problem","max"). + run(); + } + break; + case DimacsDescriptor::SP: + { + Digraph digraph; + Node s; + DoubleArcMap capacity(digraph); + readDimacsSp(is, digraph, capacity, s, desc); + DigraphWriter(digraph, os). + arcMap("capacity", capacity). + node("source", s). + attribute("problem","sp"). + run(); + } + break; + case DimacsDescriptor::MAT: + { + Digraph digraph; + readDimacsMat(is, digraph,desc); + DigraphWriter(digraph, os). + attribute("problem","mat"). + run(); + } + break; + default: + break; } - } - istream& is = (inputName.empty() ? cin : input); - - ofstream output; - if (!outputName.empty()) { - output.open(outputName.c_str()); - if (!output) { - cerr << "File open error" << endl; - return -1; - } - } - ostream& os = (outputName.empty() ? cout : output); - - if (mincostflow) { - Digraph digraph; - DoubleArcMap lower(digraph), capacity(digraph), cost(digraph); - DoubleNodeMap supply(digraph); - readDimacsMin(is, digraph, lower, capacity, cost, supply); - DigraphWriter(digraph, os). - nodeMap("supply", supply). - arcMap("lower", lower). - arcMap("capacity", capacity). - arcMap("cost", cost). - run(); - } else if (maxflow) { - Digraph digraph; - Node s, t; - DoubleArcMap capacity(digraph); - readDimacsMax(is, digraph, capacity, s, t); - DigraphWriter(digraph, os). - arcMap("capacity", capacity). - node("source", s). - node("target", t). - run(); - } else if (shortestpath) { - Digraph digraph; - Node s; - DoubleArcMap capacity(digraph); - readDimacsSp(is, digraph, capacity, s); - DigraphWriter(digraph, os). - arcMap("capacity", capacity). - node("source", s). - run(); - } else if (capacitated) { - Digraph digraph; - DoubleArcMap capacity(digraph); - readDimacsMax(is, digraph, capacity); - DigraphWriter(digraph, os). - arcMap("capacity", capacity). - run(); - } else if (plain) { - Digraph digraph; - readDimacsMat(is, digraph); - DigraphWriter(digraph, os).run(); - } else { - cerr << "Invalid type error" << endl; - return -1; - } return 0; }