vmap.h: Enables one to create maps with a virtual base class.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
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>
26 #include <lemon/invalid.h>
28 /// \ingroup dimacs_group
30 /// \brief Dimacs file format reader.
35 ///@defgroup dimacs_group DIMACS format
36 ///\brief Read and write files in DIMACS format
38 ///Tools to read a graph from or write it to a file in DIMACS format
42 /// \addtogroup dimacs_group
45 /// Dimacs min cost flow reader function.
47 /// This function reads a min cost flow instance from dimacs format,
48 /// i.e. from dimacs files having a line starting with
52 /// At the beginning \c g is cleared by \c g.clear(). The edge
53 /// capacities are written to \c capacity, \c s and \c t are set to
54 /// the source and the target nodes resp. and the cost of the edges
55 /// are written to \c cost.
57 /// \author Marton Makai
58 template<typename Graph, typename CapacityMap, typename CostMap>
59 void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
60 typename Graph::Node &s, typename Graph::Node &t,
63 typename CapacityMap::Value _cap;
64 typename CostMap::Value _cost;
71 typename Graph::Edge e;
72 std::vector<typename Graph::Node> nodes;
78 case 'p': //problem definition
79 is >> problem >> n >> m;
82 for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
84 case 'n': //node definition
85 if (problem=="sp") { //shortest path problem
90 if (problem=="max" || problem=="min") { //((max) or (min cost)) flow problem
93 if (d=='s') s=nodes[i];
94 if (d=='t') t=nodes[i];
98 if ( problem == "max" || problem == "sp") {
101 e=g.addEdge(nodes[i], nodes[j]);
103 capacity.set(e, _cap);
105 if ( problem == "min" ) {
106 is >> i >> j >> _cap >> _cost;
108 e=g.addEdge(nodes[i], nodes[j]);
110 capacity.set(e, _cap);
116 g.addEdge(nodes[i], nodes[j]);
125 /// Dimacs max flow reader function.
127 /// This function reads a max flow instance from dimacs format,
128 /// i.e. from dimacs files having a line starting with
132 ///At the beginning \c g is cleared by \c g.clear(). The
133 /// edge capacities are written to \c capacity and \c s and \c t are
134 /// set to the source and the target nodes.
136 /// \author Marton Makai
137 template<typename Graph, typename CapacityMap>
138 void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
139 typename Graph::Node &s, typename Graph::Node &t) {
140 NullMap<typename Graph::Edge, int> n;
141 readDimacs(is, g, capacity, s, t, n);
145 /// Dimacs shortest path reader function.
147 /// This function reads a shortest path instance from dimacs format,
148 /// i.e. from dimacs files having a line starting with
152 /// At the beginning \c g is cleared by \c g.clear(). The edge
153 /// capacities are written to \c capacity and \c s is set to the
156 /// \author Marton Makai
157 template<typename Graph, typename CapacityMap>
158 void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
159 typename Graph::Node &s) {
160 NullMap<typename Graph::Edge, int> n;
161 readDimacs(is, g, capacity, s, s, n);
165 /// Dimacs capacitated graph reader function.
167 /// This function reads an edge capacitated graph instance from
168 /// dimacs format. At the beginning \c g is cleared by \c g.clear()
169 /// and the edge capacities are written to \c capacity.
171 /// \author Marton Makai
172 template<typename Graph, typename CapacityMap>
173 void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity) {
174 typename Graph::Node u;
175 NullMap<typename Graph::Edge, int> n;
176 readDimacs(is, g, capacity, u, u, n);
180 /// Dimacs plain graph reader function.
182 /// This function reads a graph without any designated nodes and
183 /// maps from dimacs format, i.e. from dimacs files having a line
188 /// At the beginning \c g is cleared
191 /// \author Marton Makai
192 template<typename Graph>
193 void readDimacs(std::istream& is, Graph &g) {
194 typename Graph::Node u;
195 NullMap<typename Graph::Edge, int> n;
196 readDimacs(is, g, n, u, u, n);
202 /// write matching problem
203 template<typename Graph>
204 void writeDimacs(std::ostream& os, const Graph &g) {
205 typedef typename Graph::NodeIt NodeIt;
206 typedef typename Graph::EdgeIt EdgeIt;
208 typename Graph::template NodeMap<int> nodes(g);
210 os << "c matching problem" << std::endl;
213 for(NodeIt v(g); v!=INVALID; ++v) {
218 os << "p mat " << g.nodeNum() << " " << g.edgeNum() << std::endl;
220 for(EdgeIt e(g); e!=INVALID; ++e) {
221 os << "a " << nodes[g.source(e)] << " " << nodes[g.target(e)] << std::endl;
230 #endif //LEMON_DIMACS_H