1 /* -*- C++ -*- |
|
2 * src/lemon/dimacs.h - Part of LEMON, a generic C++ optimization library |
|
3 * |
|
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
5 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
6 * |
|
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. |
|
10 * |
|
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 |
|
13 * purpose. |
|
14 * |
|
15 */ |
|
16 |
|
17 #ifndef LEMON_DIMACS_H |
|
18 #define LEMON_DIMACS_H |
|
19 |
|
20 #include <iostream> |
|
21 #include <string> |
|
22 #include <vector> |
|
23 #include <lemon/maps.h> |
|
24 #include <lemon/invalid.h> |
|
25 |
|
26 /// \ingroup dimacs_group |
|
27 /// \file |
|
28 /// \brief Dimacs file format reader. |
|
29 |
|
30 namespace lemon { |
|
31 |
|
32 /// |
|
33 ///@defgroup dimacs_group DIMACS format |
|
34 ///\brief Read and write files in DIMACS format |
|
35 /// |
|
36 ///Tools to read a graph from or write it to a file in DIMACS format |
|
37 ///data |
|
38 ///\ingroup io_group |
|
39 |
|
40 /// \addtogroup dimacs_group |
|
41 /// @{ |
|
42 |
|
43 /// Dimacs min cost flow reader function. |
|
44 |
|
45 /// This function reads a min cost flow instance from dimacs format, |
|
46 /// i.e. from dimacs files having a line starting with |
|
47 /// \code |
|
48 /// p "min" |
|
49 /// \endcode |
|
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. |
|
54 /// |
|
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, |
|
59 CostMap& cost) { |
|
60 g.clear(); |
|
61 typename CapacityMap::Value _cap; |
|
62 typename CostMap::Value _cost; |
|
63 char d; |
|
64 std::string problem; |
|
65 char c; |
|
66 int i, j; |
|
67 std::string str; |
|
68 int n, m; |
|
69 typename Graph::Edge e; |
|
70 std::vector<typename Graph::Node> nodes; |
|
71 while (is>>c) { |
|
72 switch (c) { |
|
73 case 'c': //comment |
|
74 getline(is, str); |
|
75 break; |
|
76 case 'p': //problem definition |
|
77 is >> problem >> n >> m; |
|
78 getline(is, str); |
|
79 nodes.resize(n+1); |
|
80 for (int k=1; k<=n; ++k) nodes[k]=g.addNode(); |
|
81 break; |
|
82 case 'n': //node definition |
|
83 if (problem=="sp") { //shortest path problem |
|
84 is >> i; |
|
85 getline(is, str); |
|
86 s=nodes[i]; |
|
87 } |
|
88 if (problem=="max" || problem=="min") { //((max) or (min cost)) flow problem |
|
89 is >> i >> d; |
|
90 getline(is, str); |
|
91 if (d=='s') s=nodes[i]; |
|
92 if (d=='t') t=nodes[i]; |
|
93 } |
|
94 break; |
|
95 case 'a': |
|
96 if ( problem == "max" || problem == "sp") { |
|
97 is >> i >> j >> _cap; |
|
98 getline(is, str); |
|
99 e=g.addEdge(nodes[i], nodes[j]); |
|
100 //capacity.update(); |
|
101 capacity.set(e, _cap); |
|
102 } else { |
|
103 if ( problem == "min" ) { |
|
104 is >> i >> j >> _cap >> _cost; |
|
105 getline(is, str); |
|
106 e=g.addEdge(nodes[i], nodes[j]); |
|
107 //capacity.update(); |
|
108 capacity.set(e, _cap); |
|
109 //cost.update(); |
|
110 cost.set(e, _cost); |
|
111 } else { |
|
112 is >> i >> j; |
|
113 getline(is, str); |
|
114 g.addEdge(nodes[i], nodes[j]); |
|
115 } |
|
116 } |
|
117 break; |
|
118 } |
|
119 } |
|
120 } |
|
121 |
|
122 |
|
123 /// Dimacs max flow reader function. |
|
124 |
|
125 /// This function reads a max flow instance from dimacs format, |
|
126 /// i.e. from dimacs files having a line starting with |
|
127 /// \code |
|
128 /// p "max" |
|
129 /// \endcode |
|
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. |
|
133 /// |
|
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); |
|
140 } |
|
141 |
|
142 |
|
143 /// Dimacs shortest path reader function. |
|
144 |
|
145 /// This function reads a shortest path instance from dimacs format, |
|
146 /// i.e. from dimacs files having a line starting with |
|
147 /// \code |
|
148 /// p "sp" |
|
149 /// \endcode |
|
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 |
|
152 /// source node. |
|
153 /// |
|
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); |
|
160 } |
|
161 |
|
162 |
|
163 /// Dimacs capacitated graph reader function. |
|
164 |
|
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. |
|
168 /// |
|
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); |
|
175 } |
|
176 |
|
177 |
|
178 /// Dimacs plain graph reader function. |
|
179 |
|
180 /// This function reads a graph without any designated nodes and |
|
181 /// maps from dimacs format, i.e. from dimacs files having a line |
|
182 /// starting with |
|
183 /// \code |
|
184 /// p "mat" |
|
185 /// \endcode |
|
186 /// At the beginning \c g is cleared |
|
187 /// by \c g.clear(). |
|
188 /// |
|
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); |
|
195 } |
|
196 |
|
197 |
|
198 |
|
199 |
|
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; |
|
205 |
|
206 typename Graph::template NodeMap<int> nodes(g); |
|
207 |
|
208 os << "c matching problem" << std::endl; |
|
209 |
|
210 int i=1; |
|
211 for(NodeIt v(g); v!=INVALID; ++v) { |
|
212 nodes.set(v, i); |
|
213 ++i; |
|
214 } |
|
215 |
|
216 os << "p mat " << g.nodeNum() << " " << g.edgeNum() << std::endl; |
|
217 |
|
218 for(EdgeIt e(g); e!=INVALID; ++e) { |
|
219 os << "a " << nodes[g.source(e)] << " " << nodes[g.target(e)] << std::endl; |
|
220 } |
|
221 |
|
222 } |
|
223 |
|
224 /// @} |
|
225 |
|
226 } //namespace lemon |
|
227 |
|
228 #endif //LEMON_DIMACS_H |
|