The graph_factory branch (@ 1321) has been merged to trunk.
2 * src/lemon/dimacs.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, EGRES).
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
17 #ifndef LEMON_DIMACS_H
18 #define LEMON_DIMACS_H
23 #include <lemon/maps.h>
27 /// \brief Dimacs file format reader.
35 /// Dimacs min cost flow reader function.
37 /// This function reads a min cost flow instance from dimacs format,
38 /// i.e. from dimacs files having a line starting with \c p \c "min".
39 /// At the beginning \c g is cleared by \c g.clear(). The edge
40 /// capacities are written to \c capacity, \c s and \c t are set to
41 /// the source and the target nodes resp. and the cost of the edges
42 /// are written to \c cost.
44 /// \author Marton Makai
45 template<typename Graph, typename CapacityMap, typename CostMap>
46 void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
47 typename Graph::Node &s, typename Graph::Node &t,
50 typename CapacityMap::ValueType _cap;
51 typename CostMap::ValueType _cost;
58 typename Graph::Edge e;
59 std::vector<typename Graph::Node> nodes;
65 case 'p': //problem definition
66 is >> problem >> n >> m;
69 for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
71 case 'n': //node definition
72 if (problem=="sp") { //shortest path problem
77 if (problem=="max" || problem=="min") { //((max) or (min cost)) flow problem
80 if (d=='s') s=nodes[i];
81 if (d=='t') t=nodes[i];
85 if ( problem == "max" || problem == "sp") {
88 e=g.addEdge(nodes[i], nodes[j]);
90 capacity.set(e, _cap);
92 if ( problem == "min" ) {
93 is >> i >> j >> _cap >> _cost;
95 e=g.addEdge(nodes[i], nodes[j]);
97 capacity.set(e, _cap);
103 g.addEdge(nodes[i], nodes[j]);
112 /// Dimacs max flow reader function.
114 /// This function reads a max flow instance from dimacs format,
115 /// i.e. from dimacs files having a line starting with \c p \c
116 /// "max". At the beginning \c g is cleared by \c g.clear(). The
117 /// edge capacities are written to \c capacity and \c s and \c t are
118 /// set to the source and the target nodes.
120 /// \author Marton Makai
121 template<typename Graph, typename CapacityMap>
122 void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
123 typename Graph::Node &s, typename Graph::Node &t) {
124 NullMap<typename Graph::Edge, int> n;
125 readDimacs(is, g, capacity, s, t, n);
129 /// Dimacs shortest path reader function.
131 /// This function reads a shortest path instance from dimacs format,
132 /// i.e. from dimacs files having a line starting with \c p \c "sp".
133 /// At the beginning \c g is cleared by \c g.clear(). The edge
134 /// capacities are written to \c capacity and \c s is set to the
137 /// \author Marton Makai
138 template<typename Graph, typename CapacityMap>
139 void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
140 typename Graph::Node &s) {
141 NullMap<typename Graph::Edge, int> n;
142 readDimacs(is, g, capacity, s, s, n);
146 /// Dimacs capacitated graph reader function.
148 /// This function reads an edge capacitated graph instance from
149 /// dimacs format. At the beginning \c g is cleared by \c g.clear()
150 /// and the edge capacities are written to \c capacity.
152 /// \author Marton Makai
153 template<typename Graph, typename CapacityMap>
154 void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity) {
155 typename Graph::Node u;
156 NullMap<typename Graph::Edge, int> n;
157 readDimacs(is, g, capacity, u, u, n);
161 /// Dimacs plain graph reader function.
163 /// This function reads a graph without any designated nodes and
164 /// maps from dimacs format, i.e. from dimacs files having a line
165 /// starting with \c p \c "mat". At the beginning \c g is cleared
168 /// \author Marton Makai
169 template<typename Graph>
170 void readDimacs(std::istream& is, Graph &g) {
171 typename Graph::Node u;
172 NullMap<typename Graph::Edge, int> n;
173 readDimacs(is, g, n, u, u, n);
179 /// write matching problem
180 template<typename Graph>
181 void writeDimacs(std::ostream& os, const Graph &g) {
182 typedef typename Graph::NodeIt NodeIt;
183 typedef typename Graph::EdgeIt EdgeIt;
185 typename Graph::template NodeMap<int> nodes(g);
187 os << "c matching problem" << std::endl;
190 for(NodeIt v(g); v!=INVALID; ++v) {
195 os << "p mat " << g.nodeNum() << " " << g.edgeNum() << std::endl;
197 for(EdgeIt e(g); e!=INVALID; ++e) {
198 os << "a " << nodes[g.tail(e)] << " " << nodes[g.head(e)] << std::endl;
207 #endif //LEMON_DIMACS_H