25 #include <lemon/maps.h> |
25 #include <lemon/maps.h> |
26 #include <lemon/bits/invalid.h> |
26 #include <lemon/bits/invalid.h> |
27 |
27 |
28 /// \ingroup dimacs_group |
28 /// \ingroup dimacs_group |
29 /// \file |
29 /// \file |
30 /// \brief Dimacs file format reader. |
30 /// \brief DIMACS file format reader. |
31 |
31 |
32 namespace lemon { |
32 namespace lemon { |
33 |
33 |
34 /// |
|
35 ///@defgroup dimacs_group DIMACS format |
34 ///@defgroup dimacs_group DIMACS format |
36 ///\brief Read and write files in DIMACS format |
35 ///\brief Read and write files in DIMACS format |
37 /// |
36 /// |
38 ///Tools to read a graph from or write it to a file in DIMACS format |
37 ///Tools to read a graph from or write it to a file in DIMACS format |
39 ///data |
38 ///data |
40 ///\ingroup io_group |
39 ///\ingroup io_group |
41 |
40 |
42 /// \addtogroup dimacs_group |
41 /// \addtogroup dimacs_group |
43 /// @{ |
42 /// @{ |
44 |
43 |
45 /// Dimacs min cost flow reader function. |
44 /// DIMACS min cost flow reader function. |
46 |
45 /// |
47 /// This function reads a min cost flow instance from dimacs format, |
46 /// This function reads a min cost flow instance from DIMACS format, |
48 /// i.e. from dimacs files having a line starting with |
47 /// i.e. from DIMACS files having a line starting with |
49 ///\code |
48 /// \code |
50 /// p "min" |
49 /// p min |
51 ///\endcode |
50 /// \endcode |
52 /// At the beginning \c g is cleared by \c g.clear(). The edge |
51 /// At the beginning \c g is cleared by \c g.clear(). The supply |
53 /// capacities are written to \c capacity, \c s and \c t are set to |
52 /// amount of the nodes are written to \c supply (signed). The |
54 /// the source and the target nodes resp. and the cost of the edges |
53 /// lower bounds, capacities and costs of the edges are written to |
55 /// are written to \c cost. |
54 /// \c lower, \c capacity and \c cost. |
56 /// |
55 /// |
57 /// \author Marton Makai |
56 /// \author Marton Makai and Peter Kovacs |
58 template<typename Graph, typename CapacityMap, typename CostMap> |
57 template <typename Graph, typename SupplyMap, |
59 void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, |
58 typename CapacityMap, typename CostMap> |
60 typename Graph::Node &s, typename Graph::Node &t, |
59 void readDimacs( std::istream& is, |
61 CostMap& cost) { |
60 Graph &g, |
|
61 SupplyMap& supply, |
|
62 CapacityMap& lower, |
|
63 CapacityMap& capacity, |
|
64 CostMap& cost ) |
|
65 { |
62 g.clear(); |
66 g.clear(); |
63 typename CapacityMap::Value _cap; |
67 std::vector<typename Graph::Node> nodes; |
64 typename CostMap::Value _cost; |
68 typename Graph::Edge e; |
65 char d; |
69 std::string problem, str; |
66 std::string problem; |
|
67 char c; |
70 char c; |
|
71 int n, m; |
68 int i, j; |
72 int i, j; |
69 std::string str; |
73 typename SupplyMap::Value sup; |
70 int n, m; |
74 typename CapacityMap::Value low; |
71 typename Graph::Edge e; |
75 typename CapacityMap::Value cap; |
72 std::vector<typename Graph::Node> nodes; |
76 typename CostMap::Value co; |
73 while (is>>c) { |
77 while (is >> c) { |
74 switch (c) { |
78 switch (c) { |
75 case 'c': //comment |
79 case 'c': // comment line |
76 getline(is, str); |
80 getline(is, str); |
77 break; |
81 break; |
78 case 'p': //problem definition |
82 case 'p': // problem definition line |
79 is >> problem >> n >> m; |
83 is >> problem >> n >> m; |
80 getline(is, str); |
84 getline(is, str); |
81 nodes.resize(n+1); |
85 if (problem != "min") return; |
82 for (int k=1; k<=n; ++k) nodes[k]=g.addNode(); |
86 nodes.resize(n + 1); |
83 break; |
87 for (int k = 1; k <= n; ++k) { |
84 case 'n': //node definition |
88 nodes[k] = g.addNode(); |
85 if (problem=="sp") { //shortest path problem |
89 supply[nodes[k]] = 0; |
86 is >> i; |
90 } |
87 getline(is, str); |
91 break; |
88 s=nodes[i]; |
92 case 'n': // node definition line |
89 } |
93 is >> i >> sup; |
90 if (problem=="max" || problem=="min") { //((max) or (min cost)) flow problem |
94 getline(is, str); |
91 is >> i >> d; |
95 supply.set(nodes[i], sup); |
92 getline(is, str); |
96 break; |
93 if (d=='s') s=nodes[i]; |
97 case 'a': // edge (arc) definition line |
94 if (d=='t') t=nodes[i]; |
98 is >> i >> j >> low >> cap >> co; |
95 } |
99 getline(is, str); |
96 break; |
100 e = g.addEdge(nodes[i], nodes[j]); |
97 case 'a': |
101 lower.set(e, low); |
98 if ( problem == "max" || problem == "sp") { |
102 if (cap >= 0) |
99 is >> i >> j >> _cap; |
103 capacity.set(e, cap); |
100 getline(is, str); |
104 else |
101 e=g.addEdge(nodes[i], nodes[j]); |
105 capacity.set(e, -1); |
102 //capacity.update(); |
106 cost.set(e, co); |
103 capacity.set(e, _cap); |
|
104 } else { |
|
105 if ( problem == "min" ) { |
|
106 is >> i >> j >> _cap >> _cost; |
|
107 getline(is, str); |
|
108 e=g.addEdge(nodes[i], nodes[j]); |
|
109 //capacity.update(); |
|
110 capacity.set(e, _cap); |
|
111 //cost.update(); |
|
112 cost.set(e, _cost); |
|
113 } else { |
|
114 is >> i >> j; |
|
115 getline(is, str); |
|
116 g.addEdge(nodes[i], nodes[j]); |
|
117 } |
|
118 } |
|
119 break; |
107 break; |
120 } |
108 } |
121 } |
109 } |
122 } |
110 } |
123 |
111 |
124 |
112 /// DIMACS max flow reader function. |
125 /// Dimacs max flow reader function. |
113 /// |
126 |
114 /// This function reads a max flow instance from DIMACS format, |
127 /// This function reads a max flow instance from dimacs format, |
115 /// i.e. from DIMACS files having a line starting with |
128 /// i.e. from dimacs files having a line starting with |
116 /// \code |
129 ///\code |
117 /// p max |
130 /// p "max" |
118 /// \endcode |
131 ///\endcode |
119 /// At the beginning \c g is cleared by \c g.clear(). The edge |
132 ///At the beginning \c g is cleared by \c g.clear(). The |
120 /// capacities are written to \c capacity and \c s and \c t are |
133 /// edge capacities are written to \c capacity and \c s and \c t are |
|
134 /// set to the source and the target nodes. |
121 /// set to the source and the target nodes. |
135 /// |
122 /// |
136 /// \author Marton Makai |
123 /// \author Marton Makai |
137 template<typename Graph, typename CapacityMap> |
124 template<typename Graph, typename CapacityMap> |
138 void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, |
125 void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, |
139 typename Graph::Node &s, typename Graph::Node &t) { |
126 typename Graph::Node &s, typename Graph::Node &t) { |
140 NullMap<typename Graph::Edge, int> n; |
127 g.clear(); |
141 readDimacs(is, g, capacity, s, t, n); |
128 std::vector<typename Graph::Node> nodes; |
142 } |
129 typename Graph::Edge e; |
143 |
130 std::string problem; |
144 |
131 char c, d; |
145 /// Dimacs shortest path reader function. |
132 int n, m; |
146 |
133 int i, j; |
147 /// This function reads a shortest path instance from dimacs format, |
134 typename CapacityMap::Value _cap; |
148 /// i.e. from dimacs files having a line starting with |
135 std::string str; |
149 ///\code |
136 while (is >> c) { |
150 /// p "sp" |
137 switch (c) { |
151 ///\endcode |
138 case 'c': // comment line |
|
139 getline(is, str); |
|
140 break; |
|
141 case 'p': // problem definition line |
|
142 is >> problem >> n >> m; |
|
143 getline(is, str); |
|
144 nodes.resize(n + 1); |
|
145 for (int k = 1; k <= n; ++k) |
|
146 nodes[k] = g.addNode(); |
|
147 break; |
|
148 case 'n': // node definition line |
|
149 if (problem == "sp") { // shortest path problem |
|
150 is >> i; |
|
151 getline(is, str); |
|
152 s = nodes[i]; |
|
153 } |
|
154 if (problem == "max") { // max flow problem |
|
155 is >> i >> d; |
|
156 getline(is, str); |
|
157 if (d == 's') s = nodes[i]; |
|
158 if (d == 't') t = nodes[i]; |
|
159 } |
|
160 break; |
|
161 case 'a': // edge (arc) definition line |
|
162 if (problem == "max" || problem == "sp") { |
|
163 is >> i >> j >> _cap; |
|
164 getline(is, str); |
|
165 e = g.addEdge(nodes[i], nodes[j]); |
|
166 capacity.set(e, _cap); |
|
167 } else { |
|
168 is >> i >> j; |
|
169 getline(is, str); |
|
170 g.addEdge(nodes[i], nodes[j]); |
|
171 } |
|
172 break; |
|
173 } |
|
174 } |
|
175 } |
|
176 |
|
177 /// DIMACS shortest path reader function. |
|
178 /// |
|
179 /// This function reads a shortest path instance from DIMACS format, |
|
180 /// i.e. from DIMACS files having a line starting with |
|
181 /// \code |
|
182 /// p sp |
|
183 /// \endcode |
152 /// At the beginning \c g is cleared by \c g.clear(). The edge |
184 /// 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 |
185 /// capacities are written to \c capacity and \c s is set to the |
154 /// source node. |
186 /// source node. |
155 /// |
187 /// |
156 /// \author Marton Makai |
188 /// \author Marton Makai |
157 template<typename Graph, typename CapacityMap> |
189 template<typename Graph, typename CapacityMap> |
158 void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, |
190 void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, |
159 typename Graph::Node &s) { |
191 typename Graph::Node &s) { |
160 NullMap<typename Graph::Edge, int> n; |
192 readDimacs(is, g, capacity, s, s); |
161 readDimacs(is, g, capacity, s, s, n); |
193 } |
162 } |
194 |
163 |
195 /// DIMACS capacitated graph reader function. |
164 |
196 /// |
165 /// Dimacs capacitated graph reader function. |
|
166 |
|
167 /// This function reads an edge capacitated graph instance from |
197 /// This function reads an edge capacitated graph instance from |
168 /// dimacs format. At the beginning \c g is cleared by \c g.clear() |
198 /// DIMACS format. At the beginning \c g is cleared by \c g.clear() |
169 /// and the edge capacities are written to \c capacity. |
199 /// and the edge capacities are written to \c capacity. |
170 /// |
200 /// |
171 /// \author Marton Makai |
201 /// \author Marton Makai |
172 template<typename Graph, typename CapacityMap> |
202 template<typename Graph, typename CapacityMap> |
173 void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity) { |
203 void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity) { |
174 typename Graph::Node u; |
204 typename Graph::Node u; |
175 NullMap<typename Graph::Edge, int> n; |
205 readDimacs(is, g, capacity, u, u); |
176 readDimacs(is, g, capacity, u, u, n); |
206 } |
177 } |
207 |
178 |
208 /// DIMACS plain graph reader function. |
179 |
209 /// |
180 /// Dimacs plain graph reader function. |
|
181 |
|
182 /// This function reads a graph without any designated nodes and |
210 /// This function reads a graph without any designated nodes and |
183 /// maps from dimacs format, i.e. from dimacs files having a line |
211 /// maps from DIMACS format, i.e. from DIMACS files having a line |
184 /// starting with |
212 /// starting with |
185 ///\code |
213 /// \code |
186 /// p "mat" |
214 /// p mat |
187 ///\endcode |
215 /// \endcode |
188 /// At the beginning \c g is cleared |
216 /// At the beginning \c g is cleared by \c g.clear(). |
189 /// by \c g.clear(). |
|
190 /// |
217 /// |
191 /// \author Marton Makai |
218 /// \author Marton Makai |
192 template<typename Graph> |
219 template<typename Graph> |
193 void readDimacs(std::istream& is, Graph &g) { |
220 void readDimacs(std::istream& is, Graph &g) { |
194 typename Graph::Node u; |
221 typename Graph::Node u; |
195 NullMap<typename Graph::Edge, int> n; |
222 NullMap<typename Graph::Edge, int> n; |
196 readDimacs(is, g, n, u, u, n); |
223 readDimacs(is, g, n, u, u); |
197 } |
224 } |
198 |
225 |
199 |
226 /// DIMACS plain graph writer function. |
200 |
227 /// |
201 |
228 /// This function writes a graph without any designated nodes and |
202 /// write matching problem |
229 /// maps into DIMACS format, i.e. into DIMACS file having a line |
|
230 /// starting with |
|
231 /// \code |
|
232 /// p mat |
|
233 /// \endcode |
|
234 /// |
|
235 /// \author Marton Makai |
203 template<typename Graph> |
236 template<typename Graph> |
204 void writeDimacs(std::ostream& os, const Graph &g) { |
237 void writeDimacs(std::ostream& os, const Graph &g) { |
205 typedef typename Graph::NodeIt NodeIt; |
238 typedef typename Graph::NodeIt NodeIt; |
206 typedef typename Graph::EdgeIt EdgeIt; |
239 typedef typename Graph::EdgeIt EdgeIt; |
207 |
240 |
|
241 os << "c matching problem" << std::endl; |
|
242 os << "p mat " << g.nodeNum() << " " << g.edgeNum() << std::endl; |
|
243 |
208 typename Graph::template NodeMap<int> nodes(g); |
244 typename Graph::template NodeMap<int> nodes(g); |
209 |
245 int i = 1; |
210 os << "c matching problem" << std::endl; |
246 for(NodeIt v(g); v != INVALID; ++v) { |
211 |
|
212 int i=1; |
|
213 for(NodeIt v(g); v!=INVALID; ++v) { |
|
214 nodes.set(v, i); |
247 nodes.set(v, i); |
215 ++i; |
248 ++i; |
216 } |
249 } |
217 |
250 for(EdgeIt e(g); e != INVALID; ++e) { |
218 os << "p mat " << g.nodeNum() << " " << g.edgeNum() << std::endl; |
|
219 |
|
220 for(EdgeIt e(g); e!=INVALID; ++e) { |
|
221 os << "a " << nodes[g.source(e)] << " " << nodes[g.target(e)] << std::endl; |
251 os << "a " << nodes[g.source(e)] << " " << nodes[g.target(e)] << std::endl; |
222 } |
252 } |
223 |
|
224 } |
253 } |
225 |
254 |
226 /// @} |
255 /// @} |
227 |
256 |
228 } //namespace lemon |
257 } //namespace lemon |