# Changeset 528:c00f6ebbe1e6 in lemon-0.x

Ignore:
Timestamp:
05/04/04 18:16:49 (20 years ago)
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@694
Message:

Able to read min cost flow, max flow, shortest path, matching testgraphs

File:
1 edited

Unmodified
Added
Removed
• ## src/include/dimacs.h

 r465 #include #include #include /// \file ///\author Marton Makai template void readDimacsMaxFlow(std::istream& is, Graph &g, typename Graph::Node &s, typename Graph::Node &t, CapacityMap& capacity) { void readDimacsMaxFlow(std::istream& is, Graph &g, typename Graph::Node &s, typename Graph::Node &t, CapacityMap& capacity) { g.clear(); int cap; } } /// matching problem template void readDimacs(std::istream& is, Graph &g) { typename Graph::Node u; NullMap n; readDimacs(is, g, n, u, u, n); std::cout<<"igen en."; } /// sg problem template void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity) { typename Graph::Node u; NullMap n; readDimacs(is, g, cap, u, u, n); } /// shortest path problem template void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, typename Graph::Node &s) { NullMap n; readDimacs(is, g, capacity, s, s, n); } /// max flow problem template void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, typename Graph::Node &s, typename Graph::Node &t) { NullMap n; readDimacs(is, g, capacity, s, t, n); } /// min cost flow problem template void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, typename Graph::Node &s, typename Graph::Node &t, CostMap& cost) { g.clear(); typename CapacityMap::ValueType _cap; typename CostMap::ValueType _cost; char d; std::string problem; char c; int i, j; std::string str; int n, m; typename Graph::Edge e; std::vector nodes; while (is>>c) { switch (c) { case 'c': //comment getline(is, str); break; case 'p': //problem definition 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 if (problem=="sp") { //shortest path problem is >> i; getline(is, str); s=nodes[i]; } if (problem=="max" || problem=="min") { //((max) or (min cost)) flow problem is >> i >> d; getline(is, str); if (d=='s') s=nodes[i]; if (d=='t') t=nodes[i]; } break; case 'a': if ( problem == "mat" ) { is >> i >> j; getline(is, str); g.addEdge(nodes[i], nodes[j]); } if ( problem == "max" || problem == "sp") { is >> i >> j >> _cap; getline(is, str); e=g.addEdge(nodes[i], nodes[j]); capacity.update(); capacity.set(e, _cap); } if ( problem == "min" ) { is >> i >> j >> _cap >> _cost; getline(is, str); e=g.addEdge(nodes[i], nodes[j]); capacity.update(); capacity.set(e, _cap); cost.update(); cost.set(e, _cost); } break; } } } /// write matching problem template void writeDimacs(std::ostream& os, const Graph &g) { typedef typename Graph::NodeIt NodeIt; typedef typename Graph::EdgeIt EdgeIt; typename Graph::template NodeMap nodes(g); os << "c matching problem" << std::endl; int i=1; NodeIt v; for(g.first(v); g.valid(v); g.next(v)) { nodes.set(v, i); ++i; } os << "p mat " << g.nodeNum() << " " << g.edgeNum() << std::endl; EdgeIt e; for(g.first(e); g.valid(e); g.next(e)) { os << "a " << nodes[g.tail(e)] << " " << nodes[g.head(e)] << std::endl; } } } //namespace hugo
Note: See TracChangeset for help on using the changeset viewer.