1 // -*- c++ -*- |
|
2 #ifndef HUGO_DIMACS_H |
|
3 #define HUGO_DIMACS_H |
|
4 |
|
5 #include <iostream> |
|
6 #include <string> |
|
7 #include <vector> |
|
8 #include <maps.h> |
|
9 |
|
10 /// \file |
|
11 /// \brief Dimacs file format reader. |
|
12 |
|
13 namespace hugo { |
|
14 |
|
15 /// Dimacs flow file format reader function. |
|
16 |
|
17 /// This function reads a flow instance from dimacs flow format. |
|
18 /// At the beginning \c g is cleared by \c g.clear(). |
|
19 /// If the data coming from \c is is a max flow problem instance, then |
|
20 /// \c s and \c t will be respectively the source and target nodes |
|
21 /// and \c capacity will contain the edge capacities. |
|
22 /// If the data is a shortest path problem instance then \c s will be the |
|
23 /// source node and \c capacity will contain the edge lengths. |
|
24 /// |
|
25 ///\author Marton Makai |
|
26 template<typename Graph, typename CapacityMap> |
|
27 void readDimacsMaxFlow(std::istream& is, Graph &g, |
|
28 typename Graph::Node &s, typename Graph::Node &t, CapacityMap& capacity) { |
|
29 g.clear(); |
|
30 int cap; |
|
31 char d; |
|
32 std::string problem; |
|
33 char c; |
|
34 int i, j; |
|
35 std::string str; |
|
36 int n, m; |
|
37 typename Graph::Edge e; |
|
38 std::vector<typename Graph::Node> nodes; |
|
39 while (is>>c) { |
|
40 switch (c) { |
|
41 case 'c': //comment |
|
42 getline(is, str); |
|
43 break; |
|
44 case 'p': //problem definition |
|
45 is >> problem >> n >> m; |
|
46 getline(is, str); |
|
47 nodes.resize(n+1); |
|
48 for (int k=1; k<=n; ++k) nodes[k]=g.addNode(); |
|
49 break; |
|
50 case 'n': //node definition |
|
51 if (problem=="sp") { //shortest path problem |
|
52 is >> i; |
|
53 getline(is, str); |
|
54 s=nodes[i]; |
|
55 } |
|
56 if (problem=="max") { //max flow problem |
|
57 is >> i >> d; |
|
58 getline(is, str); |
|
59 if (d=='s') s=nodes[i]; |
|
60 if (d=='t') t=nodes[i]; |
|
61 } |
|
62 break; |
|
63 case 'a': |
|
64 is >> i >> j >> cap; |
|
65 getline(is, str); |
|
66 e=g.addEdge(nodes[i], nodes[j]); |
|
67 capacity.update(); |
|
68 capacity.set(e, cap); |
|
69 break; |
|
70 } |
|
71 } |
|
72 } |
|
73 |
|
74 /// matching problem |
|
75 template<typename Graph> |
|
76 void readDimacs(std::istream& is, Graph &g) { |
|
77 typename Graph::Node u; |
|
78 NullMap<typename Graph::Edge, int> n; |
|
79 readDimacs(is, g, n, u, u, n); |
|
80 std::cout<<"igen en."; |
|
81 } |
|
82 |
|
83 /// sg problem |
|
84 template<typename Graph, typename CapacityMap> |
|
85 void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity) { |
|
86 typename Graph::Node u; |
|
87 NullMap<typename Graph::Edge, int> n; |
|
88 readDimacs(is, g, capacity, u, u, n); |
|
89 } |
|
90 |
|
91 /// shortest path problem |
|
92 template<typename Graph, typename CapacityMap> |
|
93 void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, |
|
94 typename Graph::Node &s) { |
|
95 NullMap<typename Graph::Edge, int> n; |
|
96 readDimacs(is, g, capacity, s, s, n); |
|
97 } |
|
98 |
|
99 /// max flow problem |
|
100 template<typename Graph, typename CapacityMap> |
|
101 void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, |
|
102 typename Graph::Node &s, typename Graph::Node &t) { |
|
103 NullMap<typename Graph::Edge, int> n; |
|
104 readDimacs(is, g, capacity, s, t, n); |
|
105 } |
|
106 |
|
107 /// min cost flow problem |
|
108 template<typename Graph, typename CapacityMap, typename CostMap> |
|
109 void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, |
|
110 typename Graph::Node &s, typename Graph::Node &t, |
|
111 CostMap& cost) { |
|
112 g.clear(); |
|
113 typename CapacityMap::ValueType _cap; |
|
114 typename CostMap::ValueType _cost; |
|
115 char d; |
|
116 std::string problem; |
|
117 char c; |
|
118 int i, j; |
|
119 std::string str; |
|
120 int n, m; |
|
121 typename Graph::Edge e; |
|
122 std::vector<typename Graph::Node> nodes; |
|
123 while (is>>c) { |
|
124 switch (c) { |
|
125 case 'c': //comment |
|
126 getline(is, str); |
|
127 break; |
|
128 case 'p': //problem definition |
|
129 is >> problem >> n >> m; |
|
130 getline(is, str); |
|
131 nodes.resize(n+1); |
|
132 for (int k=1; k<=n; ++k) nodes[k]=g.addNode(); |
|
133 break; |
|
134 case 'n': //node definition |
|
135 if (problem=="sp") { //shortest path problem |
|
136 is >> i; |
|
137 getline(is, str); |
|
138 s=nodes[i]; |
|
139 } |
|
140 if (problem=="max" || problem=="min") { //((max) or (min cost)) flow problem |
|
141 is >> i >> d; |
|
142 getline(is, str); |
|
143 if (d=='s') s=nodes[i]; |
|
144 if (d=='t') t=nodes[i]; |
|
145 } |
|
146 break; |
|
147 case 'a': |
|
148 if ( problem == "mat" ) { |
|
149 is >> i >> j; |
|
150 getline(is, str); |
|
151 g.addEdge(nodes[i], nodes[j]); |
|
152 } |
|
153 if ( problem == "max" || problem == "sp") { |
|
154 is >> i >> j >> _cap; |
|
155 getline(is, str); |
|
156 e=g.addEdge(nodes[i], nodes[j]); |
|
157 capacity.update(); |
|
158 capacity.set(e, _cap); |
|
159 } |
|
160 if ( problem == "min" ) { |
|
161 is >> i >> j >> _cap >> _cost; |
|
162 getline(is, str); |
|
163 e=g.addEdge(nodes[i], nodes[j]); |
|
164 capacity.update(); |
|
165 capacity.set(e, _cap); |
|
166 cost.update(); |
|
167 cost.set(e, _cost); |
|
168 } |
|
169 break; |
|
170 } |
|
171 } |
|
172 } |
|
173 |
|
174 |
|
175 |
|
176 /// write matching problem |
|
177 template<typename Graph> |
|
178 void writeDimacs(std::ostream& os, const Graph &g) { |
|
179 typedef typename Graph::NodeIt NodeIt; |
|
180 typedef typename Graph::EdgeIt EdgeIt; |
|
181 |
|
182 typename Graph::template NodeMap<int> nodes(g); |
|
183 |
|
184 os << "c matching problem" << std::endl; |
|
185 |
|
186 int i=1; |
|
187 NodeIt v; |
|
188 for(g.first(v); g.valid(v); g.next(v)) { |
|
189 nodes.set(v, i); |
|
190 ++i; |
|
191 } |
|
192 |
|
193 os << "p mat " << g.nodeNum() << " " << g.edgeNum() << std::endl; |
|
194 |
|
195 EdgeIt e; |
|
196 for(g.first(e); g.valid(e); g.next(e)) { |
|
197 os << "a " << nodes[g.tail(e)] << " " << nodes[g.head(e)] << std::endl; |
|
198 } |
|
199 |
|
200 } |
|
201 |
|
202 |
|
203 |
|
204 } //namespace hugo |
|
205 |
|
206 #endif //HUGO_DIMACS_H |
|