1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
19 #ifndef LEMON_DIMACS_H
20 #define LEMON_DIMACS_H
25 #include <lemon/maps.h>
27 /// \ingroup dimacs_group
29 /// \brief DIMACS file format reader.
33 ///@defgroup dimacs_group DIMACS format
34 ///\brief Read and write files in DIMACS format
36 ///Tools to read a digraph from or write it to a file in DIMACS format
40 /// \addtogroup dimacs_group
43 /// DIMACS min cost flow reader function.
45 /// This function reads a min cost flow instance from DIMACS format,
46 /// i.e. from DIMACS files having a line starting with
50 /// At the beginning \c g is cleared by \c g.clear(). The supply
51 /// amount of the nodes are written to \c supply (signed). The
52 /// lower bounds, capacities and costs of the arcs are written to
53 /// \c lower, \c capacity and \c cost.
54 template <typename Digraph, typename LowerMap,
55 typename CapacityMap, typename CostMap,
57 void readDimacs( std::istream& is,
60 CapacityMap& capacity,
65 std::vector<typename Digraph::Node> nodes;
66 typename Digraph::Arc e;
67 std::string problem, str;
71 typename SupplyMap::Value sup;
72 typename CapacityMap::Value low;
73 typename CapacityMap::Value cap;
74 typename CostMap::Value co;
77 case 'c': // comment line
80 case 'p': // problem definition line
81 is >> problem >> n >> m;
83 if (problem != "min") return;
85 for (int k = 1; k <= n; ++k) {
86 nodes[k] = g.addNode();
87 supply.set(nodes[k], 0);
90 case 'n': // node definition line
93 supply.set(nodes[i], sup);
95 case 'a': // arc (arc) definition line
96 is >> i >> j >> low >> cap >> co;
98 e = g.addArc(nodes[i], nodes[j]);
101 capacity.set(e, cap);
110 /// DIMACS max flow reader function.
112 /// This function reads a max flow instance from DIMACS format,
113 /// i.e. from DIMACS files having a line starting with
117 /// At the beginning \c g is cleared by \c g.clear(). The arc
118 /// capacities are written to \c capacity and \c s and \c t are
119 /// set to the source and the target nodes.
120 template<typename Digraph, typename CapacityMap>
121 void readDimacs(std::istream& is, Digraph &g, CapacityMap& capacity,
122 typename Digraph::Node &s, typename Digraph::Node &t) {
124 std::vector<typename Digraph::Node> nodes;
125 typename Digraph::Arc e;
130 typename CapacityMap::Value _cap;
134 case 'c': // comment line
137 case 'p': // problem definition line
138 is >> problem >> n >> m;
141 for (int k = 1; k <= n; ++k)
142 nodes[k] = g.addNode();
144 case 'n': // node definition line
145 if (problem == "sp") { // shortest path problem
150 if (problem == "max") { // max flow problem
153 if (d == 's') s = nodes[i];
154 if (d == 't') t = nodes[i];
157 case 'a': // arc (arc) definition line
158 if (problem == "max" || problem == "sp") {
159 is >> i >> j >> _cap;
161 e = g.addArc(nodes[i], nodes[j]);
162 capacity.set(e, _cap);
166 g.addArc(nodes[i], nodes[j]);
173 /// DIMACS shortest path reader function.
175 /// This function reads a shortest path instance from DIMACS format,
176 /// i.e. from DIMACS files having a line starting with
180 /// At the beginning \c g is cleared by \c g.clear(). The arc
181 /// capacities are written to \c capacity and \c s is set to the
183 template<typename Digraph, typename CapacityMap>
184 void readDimacs(std::istream& is, Digraph &g, CapacityMap& capacity,
185 typename Digraph::Node &s) {
186 readDimacs(is, g, capacity, s, s);
189 /// DIMACS capacitated digraph reader function.
191 /// This function reads an arc capacitated digraph instance from
192 /// DIMACS format. At the beginning \c g is cleared by \c g.clear()
193 /// and the arc capacities are written to \c capacity.
194 template<typename Digraph, typename CapacityMap>
195 void readDimacs(std::istream& is, Digraph &g, CapacityMap& capacity) {
196 typename Digraph::Node u;
197 readDimacs(is, g, capacity, u, u);
200 /// DIMACS plain digraph reader function.
202 /// This function reads a digraph without any designated nodes and
203 /// maps from DIMACS format, i.e. from DIMACS files having a line
208 /// At the beginning \c g is cleared by \c g.clear().
209 template<typename Digraph>
210 void readDimacs(std::istream& is, Digraph &g) {
211 typename Digraph::Node u;
212 NullMap<typename Digraph::Arc, int> n;
213 readDimacs(is, g, n, u, u);
216 /// DIMACS plain digraph writer function.
218 /// This function writes a digraph without any designated nodes and
219 /// maps into DIMACS format, i.e. into DIMACS file having a line
224 template<typename Digraph>
225 void writeDimacs(std::ostream& os, const Digraph &g) {
226 typedef typename Digraph::NodeIt NodeIt;
227 typedef typename Digraph::ArcIt ArcIt;
229 os << "c matching problem" << std::endl;
230 os << "p mat " << g.nodeNum() << " " << g.arcNum() << std::endl;
232 typename Digraph::template NodeMap<int> nodes(g);
234 for(NodeIt v(g); v != INVALID; ++v) {
238 for(ArcIt e(g); e != INVALID; ++e) {
239 os << "a " << nodes[g.source(e)] << " " << nodes[g.target(e)]
248 #endif //LEMON_DIMACS_H