MapSelector has become a standalone class.
2 * lemon/dimacs.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, 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>
24 #include <lemon/invalid.h>
26 /// \ingroup dimacs_group
28 /// \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 graph 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 edge
51 /// capacities are written to \c capacity, \c s and \c t are set to
52 /// the source and the target nodes resp. and the cost of the edges
53 /// are written to \c cost.
55 /// \author Marton Makai
56 template<typename Graph, typename CapacityMap, typename CostMap>
57 void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
58 typename Graph::Node &s, typename Graph::Node &t,
61 typename CapacityMap::Value _cap;
62 typename CostMap::Value _cost;
69 typename Graph::Edge e;
70 std::vector<typename Graph::Node> nodes;
76 case 'p': //problem definition
77 is >> problem >> n >> m;
80 for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
82 case 'n': //node definition
83 if (problem=="sp") { //shortest path problem
88 if (problem=="max" || problem=="min") { //((max) or (min cost)) flow problem
91 if (d=='s') s=nodes[i];
92 if (d=='t') t=nodes[i];
96 if ( problem == "max" || problem == "sp") {
99 e=g.addEdge(nodes[i], nodes[j]);
101 capacity.set(e, _cap);
103 if ( problem == "min" ) {
104 is >> i >> j >> _cap >> _cost;
106 e=g.addEdge(nodes[i], nodes[j]);
108 capacity.set(e, _cap);
114 g.addEdge(nodes[i], nodes[j]);
123 /// Dimacs max flow reader function.
125 /// This function reads a max flow instance from dimacs format,
126 /// i.e. from dimacs files having a line starting with
130 ///At the beginning \c g is cleared by \c g.clear(). The
131 /// edge capacities are written to \c capacity and \c s and \c t are
132 /// set to the source and the target nodes.
134 /// \author Marton Makai
135 template<typename Graph, typename CapacityMap>
136 void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
137 typename Graph::Node &s, typename Graph::Node &t) {
138 NullMap<typename Graph::Edge, int> n;
139 readDimacs(is, g, capacity, s, t, n);
143 /// Dimacs shortest path reader function.
145 /// This function reads a shortest path instance from dimacs format,
146 /// i.e. from dimacs files having a line starting with
150 /// At the beginning \c g is cleared by \c g.clear(). The edge
151 /// capacities are written to \c capacity and \c s is set to the
154 /// \author Marton Makai
155 template<typename Graph, typename CapacityMap>
156 void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
157 typename Graph::Node &s) {
158 NullMap<typename Graph::Edge, int> n;
159 readDimacs(is, g, capacity, s, s, n);
163 /// Dimacs capacitated graph reader function.
165 /// This function reads an edge capacitated graph instance from
166 /// dimacs format. At the beginning \c g is cleared by \c g.clear()
167 /// and the edge capacities are written to \c capacity.
169 /// \author Marton Makai
170 template<typename Graph, typename CapacityMap>
171 void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity) {
172 typename Graph::Node u;
173 NullMap<typename Graph::Edge, int> n;
174 readDimacs(is, g, capacity, u, u, n);
178 /// Dimacs plain graph reader function.
180 /// This function reads a graph without any designated nodes and
181 /// maps from dimacs format, i.e. from dimacs files having a line
186 /// At the beginning \c g is cleared
189 /// \author Marton Makai
190 template<typename Graph>
191 void readDimacs(std::istream& is, Graph &g) {
192 typename Graph::Node u;
193 NullMap<typename Graph::Edge, int> n;
194 readDimacs(is, g, n, u, u, n);
200 /// write matching problem
201 template<typename Graph>
202 void writeDimacs(std::ostream& os, const Graph &g) {
203 typedef typename Graph::NodeIt NodeIt;
204 typedef typename Graph::EdgeIt EdgeIt;
206 typename Graph::template NodeMap<int> nodes(g);
208 os << "c matching problem" << std::endl;
211 for(NodeIt v(g); v!=INVALID; ++v) {
216 os << "p mat " << g.nodeNum() << " " << g.edgeNum() << std::endl;
218 for(EdgeIt e(g); e!=INVALID; ++e) {
219 os << "a " << nodes[g.source(e)] << " " << nodes[g.target(e)] << std::endl;
228 #endif //LEMON_DIMACS_H