21 /// If the data is a shortest path problem instance then \c s will be the |
22 /// If the data is a shortest path problem instance then \c s will be the |
22 /// source node and \c capacity will contain the edge lengths. |
23 /// source node and \c capacity will contain the edge lengths. |
23 /// |
24 /// |
24 ///\author Marton Makai |
25 ///\author Marton Makai |
25 template<typename Graph, typename CapacityMap> |
26 template<typename Graph, typename CapacityMap> |
26 void readDimacsMaxFlow(std::istream& is, Graph &g, typename Graph::Node &s, typename Graph::Node &t, CapacityMap& capacity) { |
27 void readDimacsMaxFlow(std::istream& is, Graph &g, |
|
28 typename Graph::Node &s, typename Graph::Node &t, CapacityMap& capacity) { |
27 g.clear(); |
29 g.clear(); |
28 int cap; |
30 int cap; |
29 char d; |
31 char d; |
30 std::string problem; |
32 std::string problem; |
31 char c; |
33 char c; |
66 capacity.set(e, cap); |
68 capacity.set(e, cap); |
67 break; |
69 break; |
68 } |
70 } |
69 } |
71 } |
70 } |
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, cap, 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 |
71 |
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 |
72 } //namespace hugo |
204 } //namespace hugo |
73 |
205 |
74 #endif //HUGO_DIMACS_H |
206 #endif //HUGO_DIMACS_H |