11 #include <graph_wrapper.h> |
11 #include <graph_wrapper.h> |
12 #include <maps.h> |
12 #include <maps.h> |
13 |
13 |
14 namespace hugo { |
14 namespace hugo { |
15 |
15 |
16 template<typename Graph, typename Number, typename FlowMap, typename CapacityMap> |
16 // template<typename Graph, typename Number, typename CapacityMap, typename FlowMap> |
17 class ResGraph { |
17 // class ResGraph { |
18 public: |
18 // public: |
19 typedef typename Graph::Node Node; |
19 // typedef typename Graph::Node Node; |
20 typedef typename Graph::NodeIt NodeIt; |
20 // typedef typename Graph::NodeIt NodeIt; |
21 private: |
21 // private: |
22 typedef typename Graph::SymEdgeIt OldSymEdgeIt; |
22 // typedef typename Graph::SymEdgeIt OldSymEdgeIt; |
23 const Graph& G; |
23 // const Graph& G; |
24 FlowMap& flow; |
24 // const CapacityMap& capacity; |
25 const CapacityMap& capacity; |
25 // FlowMap& flow; |
26 public: |
26 // public: |
27 ResGraph(const Graph& _G, FlowMap& _flow, |
27 // ResGraph(const Graph& _G, const CapacityMap& _capacity, FlowMap& _flow) : |
28 const CapacityMap& _capacity) : |
28 // G(_G), capacity(_capacity), flow(_flow) { } |
29 G(_G), flow(_flow), capacity(_capacity) { } |
29 |
30 |
30 // class Edge; |
31 class Edge; |
31 // class OutEdgeIt; |
32 class OutEdgeIt; |
32 // friend class Edge; |
33 friend class Edge; |
33 // friend class OutEdgeIt; |
34 friend class OutEdgeIt; |
34 |
35 |
35 // class Edge { |
36 class Edge { |
36 // friend class ResGraph<Graph, Number, FlowMap, CapacityMap>; |
37 friend class ResGraph<Graph, Number, FlowMap, CapacityMap>; |
37 // protected: |
38 protected: |
38 // const ResGraph<Graph, Number, FlowMap, CapacityMap>* resG; |
39 const ResGraph<Graph, Number, FlowMap, CapacityMap>* resG; |
39 // OldSymEdgeIt sym; |
40 OldSymEdgeIt sym; |
40 // public: |
41 public: |
41 // Edge() { } |
42 Edge() { } |
42 // //Edge(const Edge& e) : resG(e.resG), sym(e.sym) { } |
43 //Edge(const Edge& e) : resG(e.resG), sym(e.sym) { } |
43 // Number free() const { |
44 Number free() const { |
44 // if (resG->G.aNode(sym)==resG->G.tail(sym)) { |
45 if (resG->G.aNode(sym)==resG->G.tail(sym)) { |
45 // return (resG->capacity.get(sym)-resG->flow.get(sym)); |
46 return (resG->capacity.get(sym)-resG->flow.get(sym)); |
46 // } else { |
47 } else { |
47 // return (resG->flow.get(sym)); |
48 return (resG->flow.get(sym)); |
48 // } |
49 } |
49 // } |
50 } |
50 // bool valid() const { return sym.valid(); } |
51 bool valid() const { return sym.valid(); } |
51 // void augment(Number a) const { |
52 void augment(Number a) const { |
52 // if (resG->G.aNode(sym)==resG->G.tail(sym)) { |
53 if (resG->G.aNode(sym)==resG->G.tail(sym)) { |
53 // resG->flow.set(sym, resG->flow.get(sym)+a); |
54 resG->flow.set(sym, resG->flow.get(sym)+a); |
54 // //resG->flow[sym]+=a; |
55 //resG->flow[sym]+=a; |
55 // } else { |
56 } else { |
56 // resG->flow.set(sym, resG->flow.get(sym)-a); |
57 resG->flow.set(sym, resG->flow.get(sym)-a); |
57 // //resG->flow[sym]-=a; |
58 //resG->flow[sym]-=a; |
58 // } |
59 } |
59 // } |
60 } |
60 // }; |
61 }; |
61 |
62 |
62 // class OutEdgeIt : public Edge { |
63 class OutEdgeIt : public Edge { |
63 // friend class ResGraph<Graph, Number, FlowMap, CapacityMap>; |
64 friend class ResGraph<Graph, Number, FlowMap, CapacityMap>; |
64 // public: |
65 public: |
65 // OutEdgeIt() { } |
66 OutEdgeIt() { } |
66 // //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; } |
67 //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; } |
67 // private: |
68 private: |
68 // OutEdgeIt(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) { |
69 OutEdgeIt(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) { |
69 // resG=&_resG; |
70 resG=&_resG; |
70 // sym=resG->G.template first<OldSymEdgeIt>(v); |
71 sym=resG->G.template first<OldSymEdgeIt>(v); |
71 // while( sym.valid() && !(free()>0) ) { ++sym; } |
72 while( sym.valid() && !(free()>0) ) { ++sym; } |
72 // } |
73 } |
73 // public: |
74 public: |
74 // OutEdgeIt& operator++() { |
75 OutEdgeIt& operator++() { |
75 // ++sym; |
76 ++sym; |
76 // while( sym.valid() && !(free()>0) ) { ++sym; } |
77 while( sym.valid() && !(free()>0) ) { ++sym; } |
77 // return *this; |
78 return *this; |
78 // } |
79 } |
79 // }; |
80 }; |
80 |
81 |
81 // void /*getF*/first(OutEdgeIt& e, Node v) const { |
82 void /*getF*/first(OutEdgeIt& e, Node v) const { |
82 // e=OutEdgeIt(*this, v); |
83 e=OutEdgeIt(*this, v); |
83 // } |
84 } |
84 // void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); } |
85 void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); } |
|
86 |
85 |
87 template< typename It > |
86 // template< typename It > |
88 It first() const { |
87 // It first() const { |
89 It e; |
88 // It e; |
90 /*getF*/first(e); |
89 // /*getF*/first(e); |
91 return e; |
90 // return e; |
92 } |
91 // } |
93 |
92 |
94 template< typename It > |
93 // template< typename It > |
95 It first(Node v) const { |
94 // It first(Node v) const { |
96 It e; |
95 // It e; |
97 /*getF*/first(e, v); |
96 // /*getF*/first(e, v); |
98 return e; |
97 // return e; |
99 } |
98 // } |
100 |
99 |
101 Node tail(Edge e) const { return G.aNode(e.sym); } |
100 // Node tail(Edge e) const { return G.aNode(e.sym); } |
102 Node head(Edge e) const { return G.bNode(e.sym); } |
101 // Node head(Edge e) const { return G.bNode(e.sym); } |
103 |
102 |
104 Node aNode(OutEdgeIt e) const { return G.aNode(e.sym); } |
103 // Node aNode(OutEdgeIt e) const { return G.aNode(e.sym); } |
105 Node bNode(OutEdgeIt e) const { return G.bNode(e.sym); } |
104 // Node bNode(OutEdgeIt e) const { return G.bNode(e.sym); } |
106 |
105 |
107 int id(Node v) const { return G.id(v); } |
106 // int id(Node v) const { return G.id(v); } |
108 |
107 |
109 template <typename S> |
108 // template <typename S> |
110 class NodeMap { |
109 // class NodeMap { |
111 typename Graph::NodeMap<S> node_map; |
110 // typename Graph::NodeMap<S> node_map; |
112 public: |
111 // public: |
113 NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { } |
112 // NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { } |
114 NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { } |
113 // NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { } |
115 void set(Node nit, S a) { node_map.set(nit, a); } |
114 // void set(Node nit, S a) { node_map.set(nit, a); } |
116 S get(Node nit) const { return node_map.get(nit); } |
115 // S get(Node nit) const { return node_map.get(nit); } |
117 S& operator[](Node nit) { return node_map[nit]; } |
116 // S& operator[](Node nit) { return node_map[nit]; } |
118 const S& operator[](Node nit) const { return node_map[nit]; } |
117 // const S& operator[](Node nit) const { return node_map[nit]; } |
119 }; |
118 // }; |
120 |
119 |
121 }; |
120 // }; |
122 |
121 |
123 |
122 |
124 template<typename Graph, typename Number, typename FlowMap, typename CapacityMap> |
123 // template<typename Graph, typename Number, typename FlowMap, typename CapacityMap> |
125 class ResGraph2 { |
124 // class ResGraph2 { |
126 public: |
125 // public: |
127 typedef typename Graph::Node Node; |
126 // typedef typename Graph::Node Node; |
128 typedef typename Graph::NodeIt NodeIt; |
127 // typedef typename Graph::NodeIt NodeIt; |
129 private: |
128 // private: |
130 //typedef typename Graph::SymEdgeIt OldSymEdgeIt; |
129 // //typedef typename Graph::SymEdgeIt OldSymEdgeIt; |
131 typedef typename Graph::OutEdgeIt OldOutEdgeIt; |
130 // typedef typename Graph::OutEdgeIt OldOutEdgeIt; |
132 typedef typename Graph::InEdgeIt OldInEdgeIt; |
131 // typedef typename Graph::InEdgeIt OldInEdgeIt; |
133 |
132 |
134 const Graph& G; |
133 // const Graph& G; |
135 FlowMap& flow; |
134 // FlowMap& flow; |
136 const CapacityMap& capacity; |
135 // const CapacityMap& capacity; |
137 public: |
136 // public: |
138 ResGraph2(const Graph& _G, FlowMap& _flow, |
137 // ResGraph2(const Graph& _G, FlowMap& _flow, |
139 const CapacityMap& _capacity) : |
138 // const CapacityMap& _capacity) : |
140 G(_G), flow(_flow), capacity(_capacity) { } |
139 // G(_G), flow(_flow), capacity(_capacity) { } |
141 |
140 |
142 class Edge; |
141 // class Edge; |
143 class OutEdgeIt; |
142 // class OutEdgeIt; |
144 friend class Edge; |
143 // friend class Edge; |
145 friend class OutEdgeIt; |
144 // friend class OutEdgeIt; |
146 |
145 |
147 class Edge { |
146 // class Edge { |
148 friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>; |
147 // friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>; |
149 protected: |
148 // protected: |
150 const ResGraph2<Graph, Number, FlowMap, CapacityMap>* resG; |
149 // const ResGraph2<Graph, Number, FlowMap, CapacityMap>* resG; |
151 //OldSymEdgeIt sym; |
150 // //OldSymEdgeIt sym; |
152 OldOutEdgeIt out; |
151 // OldOutEdgeIt out; |
153 OldInEdgeIt in; |
152 // OldInEdgeIt in; |
154 bool out_or_in; //true, iff out |
153 // bool out_or_in; //true, iff out |
155 public: |
154 // public: |
156 Edge() : out_or_in(true) { } |
155 // Edge() : out_or_in(true) { } |
157 Number free() const { |
156 // Number free() const { |
158 if (out_or_in) { |
157 // if (out_or_in) { |
159 return (resG->capacity.get(out)-resG->flow.get(out)); |
158 // return (resG->capacity.get(out)-resG->flow.get(out)); |
160 } else { |
159 // } else { |
161 return (resG->flow.get(in)); |
160 // return (resG->flow.get(in)); |
162 } |
161 // } |
163 } |
162 // } |
164 bool valid() const { |
163 // bool valid() const { |
165 return out_or_in && out.valid() || in.valid(); } |
164 // return out_or_in && out.valid() || in.valid(); } |
166 void augment(Number a) const { |
165 // void augment(Number a) const { |
167 if (out_or_in) { |
166 // if (out_or_in) { |
168 resG->flow.set(out, resG->flow.get(out)+a); |
167 // resG->flow.set(out, resG->flow.get(out)+a); |
169 } else { |
168 // } else { |
170 resG->flow.set(in, resG->flow.get(in)-a); |
169 // resG->flow.set(in, resG->flow.get(in)-a); |
171 } |
170 // } |
172 } |
171 // } |
173 }; |
172 // }; |
174 |
173 |
175 class OutEdgeIt : public Edge { |
174 // class OutEdgeIt : public Edge { |
176 friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>; |
175 // friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>; |
177 public: |
176 // public: |
178 OutEdgeIt() { } |
177 // OutEdgeIt() { } |
179 private: |
178 // private: |
180 OutEdgeIt(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) { |
179 // OutEdgeIt(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) { |
181 resG=&_resG; |
180 // resG=&_resG; |
182 out=resG->G.template first<OldOutEdgeIt>(v); |
181 // out=resG->G.template first<OldOutEdgeIt>(v); |
183 while( out.valid() && !(free()>0) ) { ++out; } |
182 // while( out.valid() && !(free()>0) ) { ++out; } |
184 if (!out.valid()) { |
183 // if (!out.valid()) { |
185 out_or_in=0; |
184 // out_or_in=0; |
186 in=resG->G.template first<OldInEdgeIt>(v); |
185 // in=resG->G.template first<OldInEdgeIt>(v); |
187 while( in.valid() && !(free()>0) ) { ++in; } |
186 // while( in.valid() && !(free()>0) ) { ++in; } |
188 } |
187 // } |
189 } |
188 // } |
190 public: |
189 // public: |
191 OutEdgeIt& operator++() { |
190 // OutEdgeIt& operator++() { |
192 if (out_or_in) { |
191 // if (out_or_in) { |
193 Node v=resG->G.aNode(out); |
192 // Node v=resG->G.aNode(out); |
194 ++out; |
193 // ++out; |
195 while( out.valid() && !(free()>0) ) { ++out; } |
194 // while( out.valid() && !(free()>0) ) { ++out; } |
196 if (!out.valid()) { |
195 // if (!out.valid()) { |
197 out_or_in=0; |
196 // out_or_in=0; |
198 in=resG->G.template first<OldInEdgeIt>(v); |
197 // in=resG->G.template first<OldInEdgeIt>(v); |
199 while( in.valid() && !(free()>0) ) { ++in; } |
198 // while( in.valid() && !(free()>0) ) { ++in; } |
200 } |
199 // } |
201 } else { |
200 // } else { |
202 ++in; |
201 // ++in; |
203 while( in.valid() && !(free()>0) ) { ++in; } |
202 // while( in.valid() && !(free()>0) ) { ++in; } |
204 } |
203 // } |
205 return *this; |
204 // return *this; |
206 } |
205 // } |
207 }; |
206 // }; |
208 |
207 |
209 void /*getF*/first(OutEdgeIt& e, Node v) const { |
208 // void /*getF*/first(OutEdgeIt& e, Node v) const { |
210 e=OutEdgeIt(*this, v); |
209 // e=OutEdgeIt(*this, v); |
211 } |
210 // } |
212 void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); } |
211 // void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); } |
213 |
212 |
214 template< typename It > |
213 // template< typename It > |
215 It first() const { |
214 // It first() const { |
216 It e; |
215 // It e; |
217 /*getF*/first(e); |
216 // /*getF*/first(e); |
218 return e; |
217 // return e; |
219 } |
218 // } |
220 |
219 |
221 template< typename It > |
220 // template< typename It > |
222 It first(Node v) const { |
221 // It first(Node v) const { |
223 It e; |
222 // It e; |
224 /*getF*/first(e, v); |
223 // /*getF*/first(e, v); |
225 return e; |
224 // return e; |
226 } |
225 // } |
227 |
226 |
228 Node tail(Edge e) const { |
227 // Node tail(Edge e) const { |
229 return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); } |
228 // return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); } |
230 Node head(Edge e) const { |
229 // Node head(Edge e) const { |
231 return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); } |
230 // return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); } |
232 |
231 |
233 Node aNode(OutEdgeIt e) const { |
232 // Node aNode(OutEdgeIt e) const { |
234 return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); } |
233 // return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); } |
235 Node bNode(OutEdgeIt e) const { |
234 // Node bNode(OutEdgeIt e) const { |
236 return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); } |
235 // return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); } |
237 |
236 |
238 int id(Node v) const { return G.id(v); } |
237 // int id(Node v) const { return G.id(v); } |
239 |
238 |
240 template <typename S> |
239 // template <typename S> |
241 class NodeMap { |
240 // class NodeMap { |
242 typename Graph::NodeMap<S> node_map; |
241 // typename Graph::NodeMap<S> node_map; |
243 public: |
242 // public: |
244 NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { } |
243 // NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { } |
245 NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { } |
244 // NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { } |
246 void set(Node nit, S a) { node_map.set(nit, a); } |
245 // void set(Node nit, S a) { node_map.set(nit, a); } |
247 S get(Node nit) const { return node_map.get(nit); } |
246 // S get(Node nit) const { return node_map.get(nit); } |
248 }; |
247 // }; |
249 }; |
248 // }; |
250 |
249 |
251 |
250 |
252 template <typename Graph, typename Number, typename FlowMap, typename CapacityMap> |
251 template <typename Graph, typename Number, |
|
252 typename CapacityMap, typename FlowMap> |
253 class MaxFlow { |
253 class MaxFlow { |
254 protected: |
254 protected: |
255 typedef typename Graph::Node Node; |
255 typedef typename Graph::Node Node; |
256 typedef typename Graph::Edge Edge; |
256 typedef typename Graph::Edge Edge; |
257 typedef typename Graph::EdgeIt EdgeIt; |
257 typedef typename Graph::EdgeIt EdgeIt; |
258 typedef typename Graph::OutEdgeIt OutEdgeIt; |
258 typedef typename Graph::OutEdgeIt OutEdgeIt; |
259 typedef typename Graph::InEdgeIt InEdgeIt; |
259 typedef typename Graph::InEdgeIt InEdgeIt; |
260 const Graph* g; |
260 const Graph* g; |
261 Node s; |
261 Node s; |
262 Node t; |
262 Node t; |
|
263 const CapacityMap* capacity; |
263 FlowMap* flow; |
264 FlowMap* flow; |
264 const CapacityMap* capacity; |
265 typedef ResGraphWrapper<const Graph, Number, CapacityMap, FlowMap> ResGW; |
265 typedef ResGraphWrapper<const Graph, Number, FlowMap, CapacityMap > ResGW; |
|
266 typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt; |
266 typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt; |
267 typedef typename ResGW::Edge ResGWEdge; |
267 typedef typename ResGW::Edge ResGWEdge; |
268 public: |
268 public: |
269 |
269 |
270 MaxFlow(const Graph& _g, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) : |
270 MaxFlow(const Graph& _g, Node _s, Node _t, const CapacityMap& _capacity, |
271 g(&_g), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { } |
271 FlowMap& _flow) : |
|
272 g(&_g), s(_s), t(_t), capacity(&_capacity), flow(&_flow) { } |
272 |
273 |
273 bool augmentOnShortestPath() { |
274 bool augmentOnShortestPath() { |
274 ResGW res_graph(*g, *flow, *capacity); |
275 ResGW res_graph(*g, *capacity, *flow); |
275 bool _augment=false; |
276 bool _augment=false; |
276 |
277 |
277 BfsIterator5< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph); |
278 BfsIterator5< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph); |
278 bfs.pushAndSetReached(s); |
279 bfs.pushAndSetReached(s); |
279 |
280 |