marci@423: // -*- c++ -*- marci@423: #ifndef HUGO_DIMACS_H marci@423: #define HUGO_DIMACS_H marci@423: marci@423: #include marci@423: #include marci@423: #include ladanyi@542: #include marci@423: jacint@575: /// \ingroup misc klao@442: /// \file klao@442: /// \brief Dimacs file format reader. klao@427: marci@423: namespace hugo { marci@423: marci@423: jacint@575: /// \addtogroup misc jacint@575: /// @{ jacint@575: jacint@575: /// Dimacs min cost flow reader function. jacint@575: jacint@575: /// This function reads a min cost flow instance from dimacs format, jacint@575: /// i.e. from dimacs files having a line starting with \c p \c "min". jacint@575: /// At the beginning \c g is cleared by \c g.clear(). The edge jacint@575: /// capacities are written to \c capacity, \c s and \c t are set to jacint@575: /// the source and the target nodes resp. and the cost of the edges jacint@575: /// are written to \c cost. marci@465: /// jacint@575: /// \author Marton Makai jacint@528: template jacint@528: void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, jacint@528: typename Graph::Node &s, typename Graph::Node &t, jacint@528: CostMap& cost) { jacint@528: g.clear(); jacint@528: typename CapacityMap::ValueType _cap; jacint@528: typename CostMap::ValueType _cost; jacint@528: char d; jacint@528: std::string problem; jacint@528: char c; jacint@528: int i, j; jacint@528: std::string str; jacint@528: int n, m; jacint@528: typename Graph::Edge e; jacint@528: std::vector nodes; jacint@528: while (is>>c) { jacint@528: switch (c) { jacint@528: case 'c': //comment jacint@528: getline(is, str); jacint@528: break; jacint@528: case 'p': //problem definition jacint@528: is >> problem >> n >> m; jacint@528: getline(is, str); jacint@528: nodes.resize(n+1); jacint@528: for (int k=1; k<=n; ++k) nodes[k]=g.addNode(); jacint@528: break; jacint@528: case 'n': //node definition jacint@528: if (problem=="sp") { //shortest path problem jacint@528: is >> i; jacint@528: getline(is, str); jacint@528: s=nodes[i]; jacint@528: } jacint@528: if (problem=="max" || problem=="min") { //((max) or (min cost)) flow problem jacint@528: is >> i >> d; jacint@528: getline(is, str); jacint@528: if (d=='s') s=nodes[i]; jacint@528: if (d=='t') t=nodes[i]; jacint@528: } jacint@528: break; jacint@528: case 'a': jacint@528: if ( problem == "max" || problem == "sp") { jacint@528: is >> i >> j >> _cap; jacint@528: getline(is, str); jacint@528: e=g.addEdge(nodes[i], nodes[j]); jacint@528: capacity.update(); jacint@528: capacity.set(e, _cap); jacint@575: } else { jacint@575: if ( problem == "min" ) { jacint@575: is >> i >> j >> _cap >> _cost; jacint@575: getline(is, str); jacint@575: e=g.addEdge(nodes[i], nodes[j]); jacint@575: capacity.update(); jacint@575: capacity.set(e, _cap); jacint@575: cost.update(); jacint@575: cost.set(e, _cost); jacint@575: } else { jacint@575: is >> i >> j; jacint@575: getline(is, str); jacint@575: g.addEdge(nodes[i], nodes[j]); jacint@575: } jacint@528: } jacint@528: break; jacint@528: } jacint@528: } jacint@528: } jacint@528: jacint@528: jacint@575: /// Dimacs max flow reader function. jacint@575: jacint@575: /// This function reads a max flow instance from dimacs format, jacint@575: /// i.e. from dimacs files having a line starting with \c p \c jacint@575: /// "max". At the beginning \c g is cleared by \c g.clear(). The jacint@575: /// edge capacities are written to \c capacity and \c s and \c t are jacint@575: /// set to the source and the target nodes. jacint@575: /// jacint@575: /// \author Marton Makai jacint@575: template jacint@575: void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, jacint@575: typename Graph::Node &s, typename Graph::Node &t) { jacint@575: NullMap n; jacint@575: readDimacs(is, g, capacity, s, t, n); jacint@575: } jacint@575: jacint@575: jacint@575: /// Dimacs shortest path reader function. jacint@575: jacint@575: /// This function reads a shortest path instance from dimacs format, jacint@575: /// i.e. from dimacs files having a line starting with \c p \c "sp". jacint@575: /// At the beginning \c g is cleared by \c g.clear(). The edge jacint@575: /// capacities are written to \c capacity and \c s is set to the jacint@575: /// source node. jacint@575: /// jacint@575: /// \author Marton Makai jacint@575: template jacint@575: void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, jacint@575: typename Graph::Node &s) { jacint@575: NullMap n; jacint@575: readDimacs(is, g, capacity, s, s, n); jacint@575: } jacint@575: jacint@575: jacint@575: /// Dimacs capacitated graph reader function. jacint@575: jacint@575: /// This function reads an edge capacitated graph instance from jacint@575: /// dimacs format. At the beginning \c g is cleared by \c g.clear() jacint@575: /// and the edge capacities are written to \c capacity. jacint@575: /// jacint@575: /// \author Marton Makai jacint@575: template jacint@575: void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity) { jacint@575: typename Graph::Node u; jacint@575: NullMap n; jacint@575: readDimacs(is, g, capacity, u, u, n); jacint@575: } jacint@575: jacint@575: jacint@575: /// Dimacs plain graph reader function. jacint@575: jacint@575: /// This function reads a graph without any designated nodes and jacint@575: /// maps from dimacs format, i.e. from dimacs files having a line jacint@575: /// starting with \c p \c "mat". At the beginning \c g is cleared jacint@575: /// by \c g.clear(). jacint@575: /// jacint@575: /// \author Marton Makai jacint@575: template jacint@575: void readDimacs(std::istream& is, Graph &g) { jacint@575: typename Graph::Node u; jacint@575: NullMap n; jacint@575: readDimacs(is, g, n, u, u, n); jacint@575: } jacint@575: jacint@575: jacint@575: marci@423: jacint@528: /// write matching problem jacint@528: template jacint@528: void writeDimacs(std::ostream& os, const Graph &g) { jacint@528: typedef typename Graph::NodeIt NodeIt; jacint@528: typedef typename Graph::EdgeIt EdgeIt; jacint@528: jacint@528: typename Graph::template NodeMap nodes(g); jacint@528: jacint@528: os << "c matching problem" << std::endl; jacint@528: jacint@528: int i=1; jacint@528: NodeIt v; jacint@528: for(g.first(v); g.valid(v); g.next(v)) { jacint@528: nodes.set(v, i); jacint@528: ++i; jacint@528: } jacint@528: jacint@528: os << "p mat " << g.nodeNum() << " " << g.edgeNum() << std::endl; jacint@528: jacint@528: EdgeIt e; jacint@528: for(g.first(e); g.valid(e); g.next(e)) { jacint@528: os << "a " << nodes[g.tail(e)] << " " << nodes[g.head(e)] << std::endl; jacint@528: } jacint@528: jacint@528: } jacint@528: jacint@528: jacint@575: /// @} jacint@528: marci@423: } //namespace hugo marci@423: marci@423: #endif //HUGO_DIMACS_H jacint@575: jacint@575: // template jacint@575: // void readDimacsMaxFlow(std::istream& is, Graph &g, jacint@575: // typename Graph::Node &s, typename Graph::Node &t, CapacityMap& capacity) { jacint@575: // g.clear(); jacint@575: // int cap; jacint@575: // char d; jacint@575: // std::string problem; jacint@575: // char c; jacint@575: // int i, j; jacint@575: // std::string str; jacint@575: // int n, m; jacint@575: // typename Graph::Edge e; jacint@575: // std::vector nodes; jacint@575: // while (is>>c) { jacint@575: // switch (c) { jacint@575: // case 'c': //comment jacint@575: // getline(is, str); jacint@575: // break; jacint@575: // case 'p': //problem definition jacint@575: // is >> problem >> n >> m; jacint@575: // getline(is, str); jacint@575: // nodes.resize(n+1); jacint@575: // for (int k=1; k<=n; ++k) nodes[k]=g.addNode(); jacint@575: // break; jacint@575: // case 'n': //node definition jacint@575: // if (problem=="sp") { //shortest path problem jacint@575: // is >> i; jacint@575: // getline(is, str); jacint@575: // s=nodes[i]; jacint@575: // } jacint@575: // if (problem=="max") { //max flow problem jacint@575: // is >> i >> d; jacint@575: // getline(is, str); jacint@575: // if (d=='s') s=nodes[i]; jacint@575: // if (d=='t') t=nodes[i]; jacint@575: // } jacint@575: // break; jacint@575: // case 'a': jacint@575: // is >> i >> j >> cap; jacint@575: // getline(is, str); jacint@575: // e=g.addEdge(nodes[i], nodes[j]); jacint@575: // capacity.update(); jacint@575: // capacity.set(e, cap); jacint@575: // break; jacint@575: // } jacint@575: // } jacint@575: // }