1 // -*- c++ -*- |
|
2 #ifndef LEMON_GRAPH_WRAPPER_H |
|
3 #define LEMON_GRAPH_WRAPPER_H |
|
4 |
|
5 #include <invalid.h> |
|
6 |
|
7 namespace lemon { |
|
8 |
|
9 template<typename Graph> |
|
10 class TrivGraphWrapper { |
|
11 protected: |
|
12 Graph* graph; |
|
13 |
|
14 public: |
|
15 typedef Graph BaseGraph; |
|
16 |
|
17 // TrivGraphWrapper() : graph(0) { } |
|
18 TrivGraphWrapper(Graph& _graph) : graph(&_graph) { } |
|
19 // void setGraph(Graph& _graph) { graph = &_graph; } |
|
20 // Graph& getGraph() const { return *graph; } |
|
21 |
|
22 typedef typename Graph::Node Node; |
|
23 class NodeIt : public Graph::NodeIt { |
|
24 public: |
|
25 NodeIt() { } |
|
26 NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { } |
|
27 NodeIt(const Invalid& i) : Graph::NodeIt(i) { } |
|
28 NodeIt(const TrivGraphWrapper<Graph>& _G) : |
|
29 Graph::NodeIt(*(_G.graph)) { } |
|
30 }; |
|
31 typedef typename Graph::Edge Edge; |
|
32 class OutEdgeIt : public Graph::OutEdgeIt { |
|
33 public: |
|
34 OutEdgeIt() { } |
|
35 OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { } |
|
36 OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { } |
|
37 OutEdgeIt(const TrivGraphWrapper<Graph>& _G, const Node& n) : |
|
38 Graph::OutEdgeIt(*(_G.graph), n) { } |
|
39 }; |
|
40 class InEdgeIt : public Graph::InEdgeIt { |
|
41 public: |
|
42 InEdgeIt() { } |
|
43 InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { } |
|
44 InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { } |
|
45 InEdgeIt(const TrivGraphWrapper<Graph>& _G, const Node& n) : |
|
46 Graph::InEdgeIt(*(_G.graph), n) { } |
|
47 }; |
|
48 //typedef typename Graph::SymEdgeIt SymEdgeIt; |
|
49 class EdgeIt : public Graph::EdgeIt { |
|
50 public: |
|
51 EdgeIt() { } |
|
52 EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { } |
|
53 EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { } |
|
54 EdgeIt(const TrivGraphWrapper<Graph>& _G) : |
|
55 Graph::EdgeIt(*(_G.graph)) { } |
|
56 }; |
|
57 |
|
58 NodeIt& first(NodeIt& i) const { |
|
59 i=NodeIt(*this); |
|
60 return i; |
|
61 } |
|
62 EdgeIt& first(EdgeIt& i) const { |
|
63 i=EdgeIt(*this); |
|
64 return i; |
|
65 } |
|
66 // template<typename I> I& first(I& i) const { |
|
67 // i=I(*this); |
|
68 // return i; |
|
69 // } |
|
70 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { |
|
71 i=OutEdgeIt(*this, p); |
|
72 return i; |
|
73 } |
|
74 InEdgeIt& first(InEdgeIt& i, const Node& p) const { |
|
75 i=InEdgeIt(*this, p); |
|
76 return i; |
|
77 } |
|
78 // template<typename I, typename P> I& first(I& i, const P& p) const { |
|
79 // i=I(*this, p); |
|
80 // return i; |
|
81 // } |
|
82 |
|
83 // template<typename I> I getNext(const I& i) const { |
|
84 // return graph->getNext(i); } |
|
85 template<typename I> I& next(I &i) const { graph->next(i); return i; } |
|
86 |
|
87 template< typename It > It first() const { |
|
88 It e; this->first(e); return e; } |
|
89 |
|
90 template< typename It > It first(const Node& v) const { |
|
91 It e; this->first(e, v); return e; } |
|
92 |
|
93 Node target(const Edge& e) const { return graph->target(e); } |
|
94 Node source(const Edge& e) const { return graph->source(e); } |
|
95 |
|
96 template<typename I> bool valid(const I& i) const { |
|
97 return graph->valid(i); } |
|
98 |
|
99 //template<typename I> void setInvalid(const I &i); |
|
100 //{ return graph->setInvalid(i); } |
|
101 |
|
102 int nodeNum() const { return graph->nodeNum(); } |
|
103 int edgeNum() const { return graph->edgeNum(); } |
|
104 |
|
105 template<typename I> Node aNode(const I& e) const { |
|
106 return graph->aNode(e); } |
|
107 template<typename I> Node bNode(const I& e) const { |
|
108 return graph->bNode(e); } |
|
109 |
|
110 Node addNode() const { return graph->addNode(); } |
|
111 Edge addEdge(const Node& source, const Node& target) const { |
|
112 return graph->addEdge(source, target); } |
|
113 |
|
114 template<typename I> void erase(const I& i) const { graph->erase(i); } |
|
115 |
|
116 void clear() const { graph->clear(); } |
|
117 |
|
118 template<typename T> class NodeMap : public Graph::NodeMap<T> { |
|
119 public: |
|
120 NodeMap(const TrivGraphWrapper<Graph>& _G) : |
|
121 Graph::NodeMap<T>(*(_G.graph)) { } |
|
122 NodeMap(const TrivGraphWrapper<Graph>& _G, T a) : |
|
123 Graph::NodeMap<T>(*(_G.graph), a) { } |
|
124 }; |
|
125 |
|
126 template<typename T> class EdgeMap : public Graph::EdgeMap<T> { |
|
127 public: |
|
128 EdgeMap(const TrivGraphWrapper<Graph>& _G) : |
|
129 Graph::EdgeMap<T>(*(_G.graph)) { } |
|
130 EdgeMap(const TrivGraphWrapper<Graph>& _G, T a) : |
|
131 Graph::EdgeMap<T>(*(_G.graph), a) { } |
|
132 }; |
|
133 |
|
134 template<typename Map, typename T> class NodeMapWrapper { |
|
135 protected: |
|
136 Map* map; |
|
137 public: |
|
138 NodeMapWrapper(Map& _map) : map(&_map) { } |
|
139 void set(Node n, T a) { map->set(n, a); } |
|
140 T get(Node n) const { return map->get(n); } |
|
141 }; |
|
142 |
|
143 template<typename Map, typename T> class EdgeMapWrapper { |
|
144 protected: |
|
145 Map* map; |
|
146 public: |
|
147 EdgeMapWrapper(Map& _map) : map(&_map) { } |
|
148 void set(Edge n, T a) { map->set(n, a); } |
|
149 T get(Edge n) const { return map->get(n); } |
|
150 }; |
|
151 }; |
|
152 |
|
153 |
|
154 template<typename Graph> |
|
155 class GraphWrapper { |
|
156 protected: |
|
157 Graph* graph; |
|
158 |
|
159 public: |
|
160 typedef Graph BaseGraph; |
|
161 |
|
162 // GraphWrapper() : graph(0) { } |
|
163 GraphWrapper(Graph& _graph) : graph(&_graph) { } |
|
164 // void setGraph(Graph& _graph) { graph=&_graph; } |
|
165 // Graph& getGraph() const { return *graph; } |
|
166 |
|
167 typedef typename Graph::Node Node; |
|
168 class NodeIt : public Graph::NodeIt { |
|
169 public: |
|
170 NodeIt() { } |
|
171 NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { } |
|
172 NodeIt(const Invalid& i) : Graph::NodeIt(i) { } |
|
173 NodeIt(const GraphWrapper<Graph>& _G) : |
|
174 Graph::NodeIt(*(_G.graph)) { } |
|
175 }; |
|
176 typedef typename Graph::Edge Edge; |
|
177 class OutEdgeIt : public Graph::OutEdgeIt { |
|
178 public: |
|
179 OutEdgeIt() { } |
|
180 OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { } |
|
181 OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { } |
|
182 OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& n) : |
|
183 Graph::OutEdgeIt(*(_G.graph), n) { } |
|
184 }; |
|
185 class InEdgeIt : public Graph::InEdgeIt { |
|
186 public: |
|
187 InEdgeIt() { } |
|
188 InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { } |
|
189 InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { } |
|
190 InEdgeIt(const GraphWrapper<Graph>& _G, const Node& n) : |
|
191 Graph::InEdgeIt(*(_G.graph), n) { } |
|
192 }; |
|
193 //typedef typename Graph::SymEdgeIt SymEdgeIt; |
|
194 class EdgeIt : public Graph::EdgeIt { |
|
195 public: |
|
196 EdgeIt() { } |
|
197 EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { } |
|
198 EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { } |
|
199 EdgeIt(const GraphWrapper<Graph>& _G) : |
|
200 Graph::EdgeIt(*(_G.graph)) { } |
|
201 }; |
|
202 |
|
203 NodeIt& first(NodeIt& i) const { |
|
204 i=NodeIt(*this); |
|
205 return i; |
|
206 } |
|
207 EdgeIt& first(EdgeIt& i) const { |
|
208 i=EdgeIt(*this); |
|
209 return i; |
|
210 } |
|
211 // template<typename I> I& first(I& i) const { |
|
212 // i=I(*this); |
|
213 // return i; |
|
214 // } |
|
215 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { |
|
216 i=OutEdgeIt(*this, p); |
|
217 return i; |
|
218 } |
|
219 InEdgeIt& first(InEdgeIt& i, const Node& p) const { |
|
220 i=InEdgeIt(*this, p); |
|
221 return i; |
|
222 } |
|
223 // template<typename I, typename P> I& first(I& i, const P& p) const { |
|
224 // i=I(*this, p); |
|
225 // return i; |
|
226 // } |
|
227 |
|
228 // template<typename I> I getNext(const I& i) const { |
|
229 // return gw.getNext(i); } |
|
230 template<typename I> I& next(I &i) const { graph->next(i); return i; } |
|
231 |
|
232 template< typename It > It first() const { |
|
233 It e; this->first(e); return e; } |
|
234 |
|
235 template< typename It > It first(const Node& v) const { |
|
236 It e; this->first(e, v); return e; } |
|
237 |
|
238 Node target(const Edge& e) const { return graph->target(e); } |
|
239 Node source(const Edge& e) const { return graph->source(e); } |
|
240 |
|
241 template<typename I> bool valid(const I& i) const { |
|
242 return graph->valid(i); } |
|
243 |
|
244 //template<typename I> void setInvalid(const I &i); |
|
245 //{ return graph->setInvalid(i); } |
|
246 |
|
247 int nodeNum() const { return graph->nodeNum(); } |
|
248 int edgeNum() const { return graph->edgeNum(); } |
|
249 |
|
250 template<typename I> Node aNode(const I& e) const { |
|
251 return graph->aNode(e); } |
|
252 template<typename I> Node bNode(const I& e) const { |
|
253 return graph->bNode(e); } |
|
254 |
|
255 Node addNode() const { return graph->addNode(); } |
|
256 Edge addEdge(const Node& source, const Node& target) const { |
|
257 return graph->addEdge(source, target); } |
|
258 |
|
259 template<typename I> void erase(const I& i) const { graph->erase(i); } |
|
260 |
|
261 void clear() const { graph->clear(); } |
|
262 |
|
263 template<typename T> class NodeMap : public Graph::NodeMap<T> { |
|
264 public: |
|
265 NodeMap(const GraphWrapper<Graph>& _G) : |
|
266 Graph::NodeMap<T>(*(_G.graph)) { } |
|
267 NodeMap(const GraphWrapper<Graph>& _G, T a) : |
|
268 Graph::NodeMap<T>(*(_G.graph), a) { } |
|
269 }; |
|
270 |
|
271 template<typename T> class EdgeMap : public Graph::EdgeMap<T> { |
|
272 public: |
|
273 EdgeMap(const GraphWrapper<Graph>& _G) : |
|
274 Graph::EdgeMap<T>(*(_G.graph)) { } |
|
275 EdgeMap(const GraphWrapper<Graph>& _G, T a) : |
|
276 Graph::EdgeMap<T>(*(_G.graph), a) { } |
|
277 }; |
|
278 }; |
|
279 |
|
280 |
|
281 // template<typename Graph> |
|
282 // class RevGraphWrapper |
|
283 // { |
|
284 // protected: |
|
285 // Graph* graph; |
|
286 |
|
287 // public: |
|
288 // typedef Graph BaseGraph; |
|
289 |
|
290 // typedef typename Graph::Node Node; |
|
291 // typedef typename Graph::NodeIt NodeIt; |
|
292 |
|
293 // typedef typename Graph::Edge Edge; |
|
294 // typedef typename Graph::OutEdgeIt InEdgeIt; |
|
295 // typedef typename Graph::InEdgeIt OutEdgeIt; |
|
296 // //typedef typename Graph::SymEdgeIt SymEdgeIt; |
|
297 // typedef typename Graph::EdgeIt EdgeIt; |
|
298 |
|
299 // //RevGraphWrapper() : graph(0) { } |
|
300 // RevGraphWrapper(Graph& _graph) : graph(&_graph) { } |
|
301 |
|
302 // void setGraph(Graph& _graph) { graph = &_graph; } |
|
303 // Graph& getGraph() const { return (*graph); } |
|
304 |
|
305 // template<typename I> I& first(I& i) const { return graph->first(i); } |
|
306 // template<typename I, typename P> I& first(I& i, const P& p) const { |
|
307 // return graph->first(i, p); } |
|
308 |
|
309 // template<typename I> I getNext(const I& i) const { |
|
310 // return graph->getNext(i); } |
|
311 // template<typename I> I& next(I &i) const { return graph->next(i); } |
|
312 |
|
313 // template< typename It > It first() const { |
|
314 // It e; first(e); return e; } |
|
315 |
|
316 // template< typename It > It first(const Node& v) const { |
|
317 // It e; first(e, v); return e; } |
|
318 |
|
319 // Node target(const Edge& e) const { return graph->source(e); } |
|
320 // Node source(const Edge& e) const { return graph->target(e); } |
|
321 |
|
322 // template<typename I> bool valid(const I& i) const |
|
323 // { return graph->valid(i); } |
|
324 |
|
325 // //template<typename I> void setInvalid(const I &i); |
|
326 // //{ return graph->setInvalid(i); } |
|
327 |
|
328 // template<typename I> Node aNode(const I& e) const { |
|
329 // return graph->aNode(e); } |
|
330 // template<typename I> Node bNode(const I& e) const { |
|
331 // return graph->bNode(e); } |
|
332 |
|
333 // Node addNode() const { return graph->addNode(); } |
|
334 // Edge addEdge(const Node& source, const Node& target) const { |
|
335 // return graph->addEdge(source, target); } |
|
336 |
|
337 // int nodeNum() const { return graph->nodeNum(); } |
|
338 // int edgeNum() const { return graph->edgeNum(); } |
|
339 |
|
340 // template<typename I> void erase(const I& i) const { graph->erase(i); } |
|
341 |
|
342 // void clear() const { graph->clear(); } |
|
343 |
|
344 // template<typename T> class NodeMap : public Graph::NodeMap<T> { |
|
345 // public: |
|
346 // NodeMap(const RevGraphWrapper<Graph>& _G) : |
|
347 // Graph::NodeMap<T>(_G.getGraph()) { } |
|
348 // NodeMap(const RevGraphWrapper<Graph>& _G, T a) : |
|
349 // Graph::NodeMap<T>(_G.getGraph(), a) { } |
|
350 // }; |
|
351 |
|
352 // template<typename T> class EdgeMap : public Graph::EdgeMap<T> { |
|
353 // public: |
|
354 // EdgeMap(const RevGraphWrapper<Graph>& _G) : |
|
355 // Graph::EdgeMap<T>(_G.getGraph()) { } |
|
356 // EdgeMap(const RevGraphWrapper<Graph>& _G, T a) : |
|
357 // Graph::EdgeMap<T>(_G.getGraph(), a) { } |
|
358 // }; |
|
359 // }; |
|
360 |
|
361 |
|
362 template<typename Graph> |
|
363 class RevGraphWrapper : public GraphWrapper<Graph> { |
|
364 public: |
|
365 typedef typename GraphWrapper<Graph>::Node Node; |
|
366 typedef typename GraphWrapper<Graph>::Edge Edge; |
|
367 //FIXME |
|
368 //If Graph::OutEdgeIt is not defined |
|
369 //and we do not want to use RevGraphWrapper::InEdgeIt, |
|
370 //this won't work, because of typedef |
|
371 //OR |
|
372 //graphs have to define their non-existing iterators to void |
|
373 //Unfortunately all the typedefs are instantiated in templates, |
|
374 //unlike other stuff |
|
375 typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt; |
|
376 typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt; |
|
377 |
|
378 // RevGraphWrapper() : GraphWrapper<Graph>() { } |
|
379 RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } |
|
380 |
|
381 Node target(const Edge& e) const |
|
382 { return GraphWrapper<Graph>::source(e); } |
|
383 Node source(const Edge& e) const |
|
384 { return GraphWrapper<Graph>::target(e); } |
|
385 }; |
|
386 |
|
387 //Subgraph on the same node-set and partial edge-set |
|
388 template<typename Graph, typename EdgeFilterMap> |
|
389 class SubGraphWrapper : public GraphWrapper<Graph> { |
|
390 protected: |
|
391 EdgeFilterMap* filter_map; |
|
392 public: |
|
393 typedef typename GraphWrapper<Graph>::Node Node; |
|
394 typedef typename GraphWrapper<Graph>::NodeIt NodeIt; |
|
395 typedef typename GraphWrapper<Graph>::Edge Edge; |
|
396 typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt; |
|
397 typedef typename GraphWrapper<Graph>::InEdgeIt InEdgeIt; |
|
398 typedef typename GraphWrapper<Graph>::OutEdgeIt OutEdgeIt; |
|
399 |
|
400 // SubGraphWrapper() : GraphWrapper<Graph>(), filter_map(0) { } |
|
401 SubGraphWrapper(Graph& _graph, EdgeFilterMap& _filter_map) : |
|
402 GraphWrapper<Graph>(_graph), filter_map(&_filter_map) { } |
|
403 |
|
404 template<typename I> I& first(I& i) const { |
|
405 graph->first(i); |
|
406 while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); } |
|
407 return i; |
|
408 } |
|
409 template<typename I, typename P> I& first(I& i, const P& p) const { |
|
410 graph->first(i, p); |
|
411 while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); } |
|
412 return i; |
|
413 } |
|
414 |
|
415 //template<typename I> I getNext(const I& i) const { |
|
416 // return gw.getNext(i); |
|
417 //} |
|
418 template<typename I> I& next(I &i) const { |
|
419 graph->next(i); |
|
420 while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); } |
|
421 return i; |
|
422 } |
|
423 |
|
424 template< typename It > It first() const { |
|
425 It e; this->first(e); return e; } |
|
426 |
|
427 template< typename It > It first(const Node& v) const { |
|
428 It e; this->first(e, v); return e; } |
|
429 }; |
|
430 |
|
431 // template<typename GraphWrapper> |
|
432 // class UndirGraphWrapper { |
|
433 // protected: |
|
434 // //Graph* graph; |
|
435 // GraphWrapper gw; |
|
436 |
|
437 // public: |
|
438 // typedef GraphWrapper BaseGraph; |
|
439 |
|
440 // typedef typename GraphWrapper::Node Node; |
|
441 // typedef typename GraphWrapper::NodeIt NodeIt; |
|
442 |
|
443 // //typedef typename Graph::Edge Edge; |
|
444 // //typedef typename Graph::OutEdgeIt OutEdgeIt; |
|
445 // //typedef typename Graph::InEdgeIt InEdgeIt; |
|
446 // //typedef typename Graph::SymEdgeIt SymEdgeIt; |
|
447 // //typedef typename Graph::EdgeIt EdgeIt; |
|
448 |
|
449 // //private: |
|
450 // typedef typename GraphWrapper::Edge GraphEdge; |
|
451 // typedef typename GraphWrapper::OutEdgeIt GraphOutEdgeIt; |
|
452 // typedef typename GraphWrapper::InEdgeIt GraphInEdgeIt; |
|
453 // //public: |
|
454 |
|
455 // //UndirGraphWrapper() : graph(0) { } |
|
456 // UndirGraphWrapper(GraphWrapper _gw) : gw(_gw) { } |
|
457 |
|
458 // //void setGraph(Graph& _graph) { graph = &_graph; } |
|
459 // //Graph& getGraph() const { return (*graph); } |
|
460 |
|
461 // class Edge { |
|
462 // friend class UndirGraphWrapper<GraphWrapper>; |
|
463 // bool out_or_in; //true iff out |
|
464 // GraphOutEdgeIt out; |
|
465 // GraphInEdgeIt in; |
|
466 // public: |
|
467 // Edge() : out_or_in(), out(), in() { } |
|
468 // Edge(const Invalid& i) : out_or_in(false), out(), in(i) { } |
|
469 // operator GraphEdge() const { |
|
470 // if (out_or_in) return(out); else return(in); |
|
471 // } |
|
472 // friend bool operator==(const Edge& u, const Edge& v) { |
|
473 // if (v.out_or_in) |
|
474 // return (u.out_or_in && u.out==v.out); |
|
475 // else |
|
476 // return (!u.out_or_in && u.in==v.in); |
|
477 // } |
|
478 // friend bool operator!=(const Edge& u, const Edge& v) { |
|
479 // if (v.out_or_in) |
|
480 // return (!u.out_or_in || u.out!=v.out); |
|
481 // else |
|
482 // return (u.out_or_in || u.in!=v.in); |
|
483 // } |
|
484 // }; |
|
485 |
|
486 // class OutEdgeIt : public Edge { |
|
487 // friend class UndirGraphWrapper<GraphWrapper>; |
|
488 // public: |
|
489 // OutEdgeIt() : Edge() { } |
|
490 // OutEdgeIt(const Invalid& i) : Edge(i) { } |
|
491 // OutEdgeIt(const UndirGraphWrapper<GraphWrapper>& _G, const Node& n) |
|
492 // : Edge() { |
|
493 // out_or_in=true; |
|
494 // _G.gw.first(out, n); |
|
495 // if (!(_G.gw.valid(out))) { |
|
496 // out_or_in=false; |
|
497 // _G.gw.first(in, n); |
|
498 // } |
|
499 // } |
|
500 // }; |
|
501 |
|
502 // OutEdgeIt& first(OutEdgeIt& e, const Node& n) const { |
|
503 // e.out_or_in=true; |
|
504 // gw.first(e.out, n); |
|
505 // if (!(gw.valid(e.out))) { |
|
506 // e.out_or_in=false; |
|
507 // gw.first(e.in, n); |
|
508 // } |
|
509 // return e; |
|
510 // } |
|
511 |
|
512 // OutEdgeIt& next(OutEdgeIt& e) const { |
|
513 // if (e.out_or_in) { |
|
514 // Node n=gw.source(e.out); |
|
515 // gw.next(e.out); |
|
516 // if (!gw.valid(e.out)) { |
|
517 // e.out_or_in=false; |
|
518 // gw.first(e.in, n); |
|
519 // } |
|
520 // } else { |
|
521 // gw.next(e.in); |
|
522 // } |
|
523 // return e; |
|
524 // } |
|
525 |
|
526 // Node aNode(const OutEdgeIt& e) const { |
|
527 // if (e.out_or_in) return gw.source(e); else return gw.target(e); } |
|
528 // Node bNode(const OutEdgeIt& e) const { |
|
529 // if (e.out_or_in) return gw.target(e); else return gw.source(e); } |
|
530 |
|
531 // typedef OutEdgeIt InEdgeIt; |
|
532 |
|
533 // template<typename I> I& first(I& i) const { return gw.first(i); } |
|
534 // // template<typename I, typename P> I& first(I& i, const P& p) const { |
|
535 // // return graph->first(i, p); } |
|
536 |
|
537 // template<typename I> I getNext(const I& i) const { |
|
538 // return gw.getNext(i); } |
|
539 // template<typename I> I& next(I &i) const { return gw.next(i); } |
|
540 |
|
541 // template< typename It > It first() const { |
|
542 // It e; first(e); return e; } |
|
543 |
|
544 // template< typename It > It first(const Node& v) const { |
|
545 // It e; first(e, v); return e; } |
|
546 |
|
547 // Node target(const Edge& e) const { return gw.target(e); } |
|
548 // Node source(const Edge& e) const { return gw.source(e); } |
|
549 |
|
550 // template<typename I> bool valid(const I& i) const |
|
551 // { return gw.valid(i); } |
|
552 |
|
553 // //template<typename I> void setInvalid(const I &i); |
|
554 // //{ return graph->setInvalid(i); } |
|
555 |
|
556 // int nodeNum() const { return gw.nodeNum(); } |
|
557 // int edgeNum() const { return gw.edgeNum(); } |
|
558 |
|
559 // // template<typename I> Node aNode(const I& e) const { |
|
560 // // return graph->aNode(e); } |
|
561 // // template<typename I> Node bNode(const I& e) const { |
|
562 // // return graph->bNode(e); } |
|
563 |
|
564 // Node addNode() const { return gw.addNode(); } |
|
565 // // FIXME: ez igy nem jo, mert nem |
|
566 // // Edge addEdge(const Node& source, const Node& target) const { |
|
567 // // return graph->addEdge(source, target); } |
|
568 |
|
569 // template<typename I> void erase(const I& i) const { gw.erase(i); } |
|
570 |
|
571 // void clear() const { gw.clear(); } |
|
572 |
|
573 // template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> { |
|
574 // public: |
|
575 // NodeMap(const UndirGraphWrapper<GraphWrapper>& _G) : |
|
576 // GraphWrapper::NodeMap<T>(_G.gw) { } |
|
577 // NodeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) : |
|
578 // GraphWrapper::NodeMap<T>(_G.gw, a) { } |
|
579 // }; |
|
580 |
|
581 // template<typename T> class EdgeMap : public GraphWrapper::EdgeMap<T> { |
|
582 // public: |
|
583 // EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G) : |
|
584 // GraphWrapper::EdgeMap<T>(_G.gw) { } |
|
585 // EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) : |
|
586 // GraphWrapper::EdgeMap<T>(_G.gw, a) { } |
|
587 // }; |
|
588 // }; |
|
589 |
|
590 |
|
591 template<typename Graph> |
|
592 class UndirGraphWrapper : public GraphWrapper<Graph> { |
|
593 protected: |
|
594 typedef typename Graph::Edge GraphEdge; |
|
595 typedef typename Graph::OutEdgeIt GraphOutEdgeIt; |
|
596 typedef typename Graph::InEdgeIt GraphInEdgeIt; |
|
597 public: |
|
598 typedef typename GraphWrapper<Graph>::Node Node; |
|
599 typedef typename GraphWrapper<Graph>::NodeIt NodeIt; |
|
600 |
|
601 // UndirGraphWrapper() : GraphWrapper<Graph>() { } |
|
602 UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } |
|
603 |
|
604 class Edge { |
|
605 friend class UndirGraphWrapper<Graph>; |
|
606 protected: |
|
607 bool out_or_in; //true iff out |
|
608 GraphOutEdgeIt out; |
|
609 GraphInEdgeIt in; |
|
610 public: |
|
611 Edge() : out_or_in(), out(), in() { } |
|
612 Edge(const Invalid& i) : out_or_in(false), out(), in(i) { } |
|
613 operator GraphEdge() const { |
|
614 if (out_or_in) return(out); else return(in); |
|
615 } |
|
616 //FIXME |
|
617 //2 edges are equal if they "refer" to the same physical edge |
|
618 //is it good? |
|
619 friend bool operator==(const Edge& u, const Edge& v) { |
|
620 if (v.out_or_in) |
|
621 if (u.out_or_in) return (u.out==v.out); else return (u.out==v.in); |
|
622 //return (u.out_or_in && u.out==v.out); |
|
623 else |
|
624 if (u.out_or_in) return (u.out==v.in); else return (u.in==v.in); |
|
625 //return (!u.out_or_in && u.in==v.in); |
|
626 } |
|
627 friend bool operator!=(const Edge& u, const Edge& v) { |
|
628 if (v.out_or_in) |
|
629 if (u.out_or_in) return (u.out!=v.out); else return (u.out!=v.in); |
|
630 //return (!u.out_or_in || u.out!=v.out); |
|
631 else |
|
632 if (u.out_or_in) return (u.out!=v.in); else return (u.in!=v.in); |
|
633 //return (u.out_or_in || u.in!=v.in); |
|
634 } |
|
635 }; |
|
636 |
|
637 class OutEdgeIt : public Edge { |
|
638 friend class UndirGraphWrapper<Graph>; |
|
639 public: |
|
640 OutEdgeIt() : Edge() { } |
|
641 OutEdgeIt(const Invalid& i) : Edge(i) { } |
|
642 OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& n) |
|
643 : Edge() { |
|
644 out_or_in=true; _G.graph->first(out, n); |
|
645 if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, n); } |
|
646 } |
|
647 }; |
|
648 |
|
649 typedef OutEdgeIt InEdgeIt; |
|
650 |
|
651 class EdgeIt : public Edge { |
|
652 friend class UndirGraphWrapper<Graph>; |
|
653 protected: |
|
654 NodeIt v; |
|
655 public: |
|
656 EdgeIt() : Edge() { } |
|
657 EdgeIt(const Invalid& i) : Edge(i) { } |
|
658 EdgeIt(const UndirGraphWrapper<Graph>& _G) |
|
659 : Edge() { |
|
660 out_or_in=true; |
|
661 //Node v; |
|
662 _G.first(v); |
|
663 if (_G.valid(v)) _G.graph->first(out); else out=INVALID; |
|
664 while (_G.valid(v) && !_G.graph->valid(out)) { |
|
665 _G.graph->next(v); |
|
666 if (_G.valid(v)) _G.graph->first(out); |
|
667 } |
|
668 } |
|
669 }; |
|
670 |
|
671 OutEdgeIt& first(OutEdgeIt& e, const Node& n) const { |
|
672 e.out_or_in=true; graph->first(e.out, n); |
|
673 if (!(graph->valid(e.out))) { e.out_or_in=false; graph->first(e.in, n); } |
|
674 return e; |
|
675 } |
|
676 |
|
677 EdgeIt& first(EdgeIt& e) const { |
|
678 e.out_or_in=true; |
|
679 //NodeIt v; |
|
680 first(e.v); |
|
681 if (valid(e.v)) graph->first(e.out, e.v); else e.out=INVALID; |
|
682 while (valid(e.v) && !graph->valid(e.out)) { |
|
683 graph->next(e.v); |
|
684 if (valid(e.v)) graph->first(e.out, e.v); |
|
685 } |
|
686 return e; |
|
687 } |
|
688 |
|
689 template<typename I> I& first(I& i) const { graph->first(i); return i; } |
|
690 template<typename I, typename P> I& first(I& i, const P& p) const { |
|
691 graph->first(i, p); return i; } |
|
692 |
|
693 OutEdgeIt& next(OutEdgeIt& e) const { |
|
694 if (e.out_or_in) { |
|
695 Node n=graph->source(e.out); |
|
696 graph->next(e.out); |
|
697 if (!graph->valid(e.out)) { e.out_or_in=false; graph->first(e.in, n); } |
|
698 } else { |
|
699 graph->next(e.in); |
|
700 } |
|
701 return e; |
|
702 } |
|
703 |
|
704 EdgeIt& next(EdgeIt& e) const { |
|
705 //NodeIt v=source(e); |
|
706 graph->next(e.out); |
|
707 while (valid(e.v) && !graph->valid(e.out)) { |
|
708 next(e.v); |
|
709 if (valid(e.v)) graph->first(e.out, e.v); |
|
710 } |
|
711 return e; |
|
712 } |
|
713 |
|
714 template<typename I> I& next(I &i) const { return graph->next(i); } |
|
715 // template<typename I> I getNext(const I& i) const { return gw.getNext(i); } |
|
716 |
|
717 template< typename It > It first() const { |
|
718 It e; this->first(e); return e; } |
|
719 |
|
720 template< typename It > It first(const Node& v) const { |
|
721 It e; this->first(e, v); return e; } |
|
722 |
|
723 // Node target(const Edge& e) const { return gw.target(e); } |
|
724 // Node source(const Edge& e) const { return gw.source(e); } |
|
725 |
|
726 // template<typename I> bool valid(const I& i) const |
|
727 // { return gw.valid(i); } |
|
728 |
|
729 // int nodeNum() const { return gw.nodeNum(); } |
|
730 // int edgeNum() const { return gw.edgeNum(); } |
|
731 |
|
732 // template<typename I> Node aNode(const I& e) const { |
|
733 // return graph->aNode(e); } |
|
734 // template<typename I> Node bNode(const I& e) const { |
|
735 // return graph->bNode(e); } |
|
736 |
|
737 Node aNode(const OutEdgeIt& e) const { |
|
738 if (e.out_or_in) return graph->source(e); else return graph->target(e); } |
|
739 Node bNode(const OutEdgeIt& e) const { |
|
740 if (e.out_or_in) return graph->target(e); else return graph->source(e); } |
|
741 |
|
742 // Node addNode() const { return gw.addNode(); } |
|
743 |
|
744 // FIXME: ez igy nem jo, mert nem |
|
745 // Edge addEdge(const Node& source, const Node& target) const { |
|
746 // return graph->addEdge(source, target); } |
|
747 |
|
748 // template<typename I> void erase(const I& i) const { gw.erase(i); } |
|
749 |
|
750 // void clear() const { gw.clear(); } |
|
751 |
|
752 // template<typename T> class NodeMap : public Graph::NodeMap<T> { |
|
753 // public: |
|
754 // NodeMap(const UndirGraphWrapper<Graph>& _G) : |
|
755 // Graph::NodeMap<T>(_G.gw) { } |
|
756 // NodeMap(const UndirGraphWrapper<Graph>& _G, T a) : |
|
757 // Graph::NodeMap<T>(_G.gw, a) { } |
|
758 // }; |
|
759 |
|
760 // template<typename T> class EdgeMap : |
|
761 // public GraphWrapper<Graph>::EdgeMap<T> { |
|
762 // public: |
|
763 // EdgeMap(const UndirGraphWrapper<Graph>& _G) : |
|
764 // GraphWrapper<Graph>::EdgeMap<T>(_G.gw) { } |
|
765 // EdgeMap(const UndirGraphWrapper<Graph>& _G, T a) : |
|
766 // Graph::EdgeMap<T>(_G.gw, a) { } |
|
767 // }; |
|
768 }; |
|
769 |
|
770 |
|
771 |
|
772 |
|
773 |
|
774 // template<typename Graph> |
|
775 // class SymGraphWrapper |
|
776 // { |
|
777 // Graph* graph; |
|
778 |
|
779 // public: |
|
780 // typedef Graph BaseGraph; |
|
781 |
|
782 // typedef typename Graph::Node Node; |
|
783 // typedef typename Graph::Edge Edge; |
|
784 |
|
785 // typedef typename Graph::NodeIt NodeIt; |
|
786 |
|
787 // //FIXME tag-ekkel megcsinalni, hogy abbol csinaljon |
|
788 // //iranyitatlant, ami van |
|
789 // //mert csak 1 dolgot lehet be typedef-elni |
|
790 // typedef typename Graph::OutEdgeIt SymEdgeIt; |
|
791 // //typedef typename Graph::InEdgeIt SymEdgeIt; |
|
792 // //typedef typename Graph::SymEdgeIt SymEdgeIt; |
|
793 // typedef typename Graph::EdgeIt EdgeIt; |
|
794 |
|
795 // int nodeNum() const { return graph->nodeNum(); } |
|
796 // int edgeNum() const { return graph->edgeNum(); } |
|
797 |
|
798 // template<typename I> I& first(I& i) const { return graph->first(i); } |
|
799 // template<typename I, typename P> I& first(I& i, const P& p) const { |
|
800 // return graph->first(i, p); } |
|
801 // //template<typename I> I next(const I i); { return graph->goNext(i); } |
|
802 // //template<typename I> I &goNext(I &i); { return graph->goNext(i); } |
|
803 |
|
804 // template< typename It > It first() const { |
|
805 // It e; first(e); return e; } |
|
806 |
|
807 // template< typename It > It first(Node v) const { |
|
808 // It e; first(e, v); return e; } |
|
809 |
|
810 // Node target(const Edge& e) const { return graph->target(e); } |
|
811 // Node source(const Edge& e) const { return graph->source(e); } |
|
812 |
|
813 // template<typename I> Node aNode(const I& e) const { |
|
814 // return graph->aNode(e); } |
|
815 // template<typename I> Node bNode(const I& e) const { |
|
816 // return graph->bNode(e); } |
|
817 |
|
818 // //template<typename I> bool valid(const I i); |
|
819 // //{ return graph->valid(i); } |
|
820 |
|
821 // //template<typename I> void setInvalid(const I &i); |
|
822 // //{ return graph->setInvalid(i); } |
|
823 |
|
824 // Node addNode() { return graph->addNode(); } |
|
825 // Edge addEdge(const Node& source, const Node& target) { |
|
826 // return graph->addEdge(source, target); } |
|
827 |
|
828 // template<typename I> void erase(const I& i) { graph->erase(i); } |
|
829 |
|
830 // void clear() { graph->clear(); } |
|
831 |
|
832 // template<typename T> class NodeMap : public Graph::NodeMap<T> { }; |
|
833 // template<typename T> class EdgeMap : public Graph::EdgeMap<T> { }; |
|
834 |
|
835 // void setGraph(Graph& _graph) { graph = &_graph; } |
|
836 // Graph& getGraph() { return (*graph); } |
|
837 |
|
838 // //SymGraphWrapper() : graph(0) { } |
|
839 // SymGraphWrapper(Graph& _graph) : graph(&_graph) { } |
|
840 // }; |
|
841 |
|
842 |
|
843 template<typename Graph, typename Number, typename FlowMap, typename CapacityMap> |
|
844 class ResGraphWrapper : public GraphWrapper<Graph>{ |
|
845 public: |
|
846 typedef typename GraphWrapper<Graph>::Node Node; |
|
847 typedef typename GraphWrapper<Graph>::NodeIt NodeIt; |
|
848 protected: |
|
849 typedef typename Graph::OutEdgeIt OldOutEdgeIt; |
|
850 typedef typename Graph::InEdgeIt OldInEdgeIt; |
|
851 FlowMap* flow; |
|
852 const CapacityMap* capacity; |
|
853 public: |
|
854 |
|
855 ResGraphWrapper(Graph& _graph, FlowMap& _flow, |
|
856 const CapacityMap& _capacity) : |
|
857 GraphWrapper<Graph>(_graph), flow(&_flow), capacity(&_capacity) { } |
|
858 |
|
859 class Edge; |
|
860 class OutEdgeIt; |
|
861 friend class Edge; |
|
862 friend class OutEdgeIt; |
|
863 |
|
864 class Edge { |
|
865 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; |
|
866 protected: |
|
867 bool out_or_in; //true, iff out |
|
868 OldOutEdgeIt out; |
|
869 OldInEdgeIt in; |
|
870 public: |
|
871 Edge() : out_or_in(true) { } |
|
872 Edge(const Invalid& i) : out_or_in(false), out(), in(i) { } |
|
873 // bool valid() const { |
|
874 // return out_or_in && out.valid() || in.valid(); } |
|
875 friend bool operator==(const Edge& u, const Edge& v) { |
|
876 if (v.out_or_in) |
|
877 return (u.out_or_in && u.out==v.out); |
|
878 else |
|
879 return (!u.out_or_in && u.in==v.in); |
|
880 } |
|
881 friend bool operator!=(const Edge& u, const Edge& v) { |
|
882 if (v.out_or_in) |
|
883 return (!u.out_or_in || u.out!=v.out); |
|
884 else |
|
885 return (u.out_or_in || u.in!=v.in); |
|
886 } |
|
887 }; |
|
888 |
|
889 |
|
890 class OutEdgeIt : public Edge { |
|
891 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; |
|
892 public: |
|
893 OutEdgeIt() { } |
|
894 //FIXME |
|
895 OutEdgeIt(const Edge& e) : Edge(e) { } |
|
896 OutEdgeIt(const Invalid& i) : Edge(i) { } |
|
897 protected: |
|
898 OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() { |
|
899 resG.graph->first(out, v); |
|
900 while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } |
|
901 if (!resG.graph->valid(out)) { |
|
902 out_or_in=0; |
|
903 resG.graph->first(in, v); |
|
904 while( resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); } |
|
905 } |
|
906 } |
|
907 // public: |
|
908 // OutEdgeIt& operator++() { |
|
909 // if (out_or_in) { |
|
910 // Node v=/*resG->*/G->aNode(out); |
|
911 // ++out; |
|
912 // while( out.valid() && !(Edge::resCap()>0) ) { ++out; } |
|
913 // if (!out.valid()) { |
|
914 // out_or_in=0; |
|
915 // G->first(in, v); |
|
916 // while( in.valid() && !(Edge::resCap()>0) ) { ++in; } |
|
917 // } |
|
918 // } else { |
|
919 // ++in; |
|
920 // while( in.valid() && !(Edge::resCap()>0) ) { ++in; } |
|
921 // } |
|
922 // return *this; |
|
923 // } |
|
924 }; |
|
925 |
|
926 //FIXME This is just for having InEdgeIt |
|
927 typedef void InEdgeIt; |
|
928 |
|
929 class EdgeIt : public Edge { |
|
930 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; |
|
931 NodeIt v; |
|
932 public: |
|
933 EdgeIt() { } |
|
934 //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { } |
|
935 EdgeIt(const Invalid& i) : Edge(i) { } |
|
936 EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() { |
|
937 resG.graph->first(v); |
|
938 if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID; |
|
939 while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } |
|
940 while (resG.graph->valid(v) && !resG.graph->valid(out)) { |
|
941 resG.graph->next(v); |
|
942 if (resG.graph->valid(v)) resG.graph->first(out, v); |
|
943 while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } |
|
944 } |
|
945 if (!resG.graph->valid(out)) { |
|
946 out_or_in=0; |
|
947 resG.graph->first(v); |
|
948 if (resG.graph->valid(v)) resG.graph->first(in, v); else in=INVALID; |
|
949 while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); } |
|
950 while (resG.graph->valid(v) && !resG.graph->valid(in)) { |
|
951 resG.graph->next(v); |
|
952 if (resG.graph->valid(v)) resG.graph->first(in, v); |
|
953 while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); } |
|
954 } |
|
955 } |
|
956 } |
|
957 // EdgeIt& operator++() { |
|
958 // if (out_or_in) { |
|
959 // ++out; |
|
960 // while (out.valid() && !(Edge::resCap()>0) ) { ++out; } |
|
961 // while (v.valid() && !out.valid()) { |
|
962 // ++v; |
|
963 // if (v.valid()) G->first(out, v); |
|
964 // while (out.valid() && !(Edge::resCap()>0) ) { ++out; } |
|
965 // } |
|
966 // if (!out.valid()) { |
|
967 // out_or_in=0; |
|
968 // G->first(v); |
|
969 // if (v.valid()) G->first(in, v); else in=OldInEdgeIt(); |
|
970 // while (in.valid() && !(Edge::resCap()>0) ) { ++in; } |
|
971 // while (v.valid() && !in.valid()) { |
|
972 // ++v; |
|
973 // if (v.valid()) G->first(in, v); |
|
974 // while (in.valid() && !(Edge::resCap()>0) ) { ++in; } |
|
975 // } |
|
976 // } |
|
977 // } else { |
|
978 // ++in; |
|
979 // while (in.valid() && !(Edge::resCap()>0) ) { ++in; } |
|
980 // while (v.valid() && !in.valid()) { |
|
981 // ++v; |
|
982 // if (v.valid()) G->first(in, v); |
|
983 // while (in.valid() && !(Edge::resCap()>0) ) { ++in; } |
|
984 // } |
|
985 // } |
|
986 // return *this; |
|
987 // } |
|
988 }; |
|
989 |
|
990 NodeIt& first(NodeIt& v) const { graph->first(v); return v; } |
|
991 OutEdgeIt& first(OutEdgeIt& e, Node v) const { |
|
992 e=OutEdgeIt(*this, v); |
|
993 return e; |
|
994 } |
|
995 EdgeIt& first(EdgeIt& e) const { |
|
996 e=EdgeIt(*this); |
|
997 return e; |
|
998 } |
|
999 |
|
1000 NodeIt& next(NodeIt& n) const { return graph->next(n); } |
|
1001 |
|
1002 OutEdgeIt& next(OutEdgeIt& e) const { |
|
1003 if (e.out_or_in) { |
|
1004 Node v=graph->aNode(e.out); |
|
1005 graph->next(e.out); |
|
1006 while( graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); } |
|
1007 if (!graph->valid(e.out)) { |
|
1008 e.out_or_in=0; |
|
1009 graph->first(e.in, v); |
|
1010 while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } |
|
1011 } |
|
1012 } else { |
|
1013 graph->next(e.in); |
|
1014 while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } |
|
1015 } |
|
1016 return e; |
|
1017 } |
|
1018 |
|
1019 EdgeIt& next(EdgeIt& e) const { |
|
1020 if (e.out_or_in) { |
|
1021 graph->next(e.out); |
|
1022 while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); } |
|
1023 while (graph->valid(e.v) && !graph->valid(e.out)) { |
|
1024 graph->next(e.v); |
|
1025 if (graph->valid(e.v)) graph->first(e.out, e.v); |
|
1026 while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); } |
|
1027 } |
|
1028 if (!graph->valid(e.out)) { |
|
1029 e.out_or_in=0; |
|
1030 graph->first(e.v); |
|
1031 if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=INVALID; |
|
1032 while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } |
|
1033 while (graph->valid(e.v) && !graph->valid(e.in)) { |
|
1034 graph->next(e.v); |
|
1035 if (graph->valid(e.v)) graph->first(e.in, e.v); |
|
1036 while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } |
|
1037 } |
|
1038 } |
|
1039 } else { |
|
1040 graph->next(e.in); |
|
1041 while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } |
|
1042 while (graph->valid(e.v) && !graph->valid(e.in)) { |
|
1043 graph->next(e.v); |
|
1044 if (graph->valid(e.v)) graph->first(e.in, e.v); |
|
1045 while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } |
|
1046 } |
|
1047 } |
|
1048 return e; |
|
1049 } |
|
1050 |
|
1051 |
|
1052 template< typename It > |
|
1053 It first() const { |
|
1054 It e; |
|
1055 first(e); |
|
1056 return e; |
|
1057 } |
|
1058 |
|
1059 template< typename It > |
|
1060 It first(Node v) const { |
|
1061 It e; |
|
1062 first(e, v); |
|
1063 return e; |
|
1064 } |
|
1065 |
|
1066 Node source(Edge e) const { |
|
1067 return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); } |
|
1068 Node target(Edge e) const { |
|
1069 return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); } |
|
1070 |
|
1071 Node aNode(OutEdgeIt e) const { |
|
1072 return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); } |
|
1073 Node bNode(OutEdgeIt e) const { |
|
1074 return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); } |
|
1075 |
|
1076 int nodeNum() const { return graph->nodeNum(); } |
|
1077 //FIXME |
|
1078 //int edgeNum() const { return graph->edgeNum(); } |
|
1079 |
|
1080 |
|
1081 int id(Node v) const { return graph->id(v); } |
|
1082 |
|
1083 bool valid(Node n) const { return graph->valid(n); } |
|
1084 bool valid(Edge e) const { |
|
1085 return e.out_or_in ? graph->valid(e.out) : graph->valid(e.in); } |
|
1086 |
|
1087 void augment(const Edge& e, Number a) const { |
|
1088 if (e.out_or_in) |
|
1089 flow->set(e.out, flow->get(e.out)+a); |
|
1090 else |
|
1091 flow->set(e.in, flow->get(e.in)-a); |
|
1092 } |
|
1093 |
|
1094 Number resCap(const Edge& e) const { |
|
1095 if (e.out_or_in) |
|
1096 return (capacity->get(e.out)-flow->get(e.out)); |
|
1097 else |
|
1098 return (flow->get(e.in)); |
|
1099 } |
|
1100 |
|
1101 Number resCap(OldOutEdgeIt out) const { |
|
1102 return (capacity->get(out)-flow->get(out)); |
|
1103 } |
|
1104 |
|
1105 Number resCap(OldInEdgeIt in) const { |
|
1106 return (flow->get(in)); |
|
1107 } |
|
1108 |
|
1109 // template<typename T> class NodeMap : public Graph::NodeMap<T> { |
|
1110 // public: |
|
1111 // NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) |
|
1112 // : Graph::NodeMap<T>(_G.gw) { } |
|
1113 // NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, |
|
1114 // T a) : Graph::NodeMap<T>(_G.gw, a) { } |
|
1115 // }; |
|
1116 |
|
1117 // template <typename T> |
|
1118 // class NodeMap { |
|
1119 // typename Graph::NodeMap<T> node_map; |
|
1120 // public: |
|
1121 // NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.graph)) { } |
|
1122 // NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.graph), a) { } |
|
1123 // void set(Node nit, T a) { node_map.set(nit, a); } |
|
1124 // T get(Node nit) const { return node_map.get(nit); } |
|
1125 // }; |
|
1126 |
|
1127 template <typename T> |
|
1128 class EdgeMap { |
|
1129 typename Graph::EdgeMap<T> forward_map, backward_map; |
|
1130 public: |
|
1131 EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { } |
|
1132 EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { } |
|
1133 void set(Edge e, T a) { |
|
1134 if (e.out_or_in) |
|
1135 forward_map.set(e.out, a); |
|
1136 else |
|
1137 backward_map.set(e.in, a); |
|
1138 } |
|
1139 T get(Edge e) { |
|
1140 if (e.out_or_in) |
|
1141 return forward_map.get(e.out); |
|
1142 else |
|
1143 return backward_map.get(e.in); |
|
1144 } |
|
1145 }; |
|
1146 }; |
|
1147 |
|
1148 //ErasingFirstGraphWrapper for blocking flows |
|
1149 template<typename Graph, typename FirstOutEdgesMap> |
|
1150 class ErasingFirstGraphWrapper : public GraphWrapper<Graph> { |
|
1151 protected: |
|
1152 FirstOutEdgesMap* first_out_edges; |
|
1153 public: |
|
1154 typedef typename GraphWrapper<Graph>::Node Node; |
|
1155 typedef typename GraphWrapper<Graph>::NodeIt NodeIt; |
|
1156 typedef typename GraphWrapper<Graph>::Edge Edge; |
|
1157 typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt; |
|
1158 typedef typename GraphWrapper<Graph>::InEdgeIt InEdgeIt; |
|
1159 typedef typename GraphWrapper<Graph>::OutEdgeIt OutEdgeIt; |
|
1160 |
|
1161 ErasingFirstGraphWrapper(Graph& _graph, |
|
1162 FirstOutEdgesMap& _first_out_edges) : |
|
1163 GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { } |
|
1164 |
|
1165 template<typename I> I& first(I& i) const { |
|
1166 graph->first(i); |
|
1167 return i; |
|
1168 } |
|
1169 OutEdgeIt& first(OutEdgeIt& e, const Node& n) const { |
|
1170 e=first_out_edges->get(n); |
|
1171 return e; |
|
1172 } |
|
1173 template<typename I, typename P> I& first(I& i, const P& p) const { |
|
1174 graph->first(i, p); |
|
1175 return i; |
|
1176 } |
|
1177 |
|
1178 //template<typename I> I getNext(const I& i) const { |
|
1179 // return gw.getNext(i); |
|
1180 //} |
|
1181 template<typename I> I& next(I &i) const { |
|
1182 graph->next(i); |
|
1183 return i; |
|
1184 } |
|
1185 |
|
1186 template< typename It > It first() const { |
|
1187 It e; this->first(e); return e; } |
|
1188 |
|
1189 template< typename It > It first(const Node& v) const { |
|
1190 It e; this->first(e, v); return e; } |
|
1191 |
|
1192 void erase(const OutEdgeIt& e) const { |
|
1193 OutEdgeIt f=e; |
|
1194 this->next(f); |
|
1195 first_out_edges->set(this->source(e), f); |
|
1196 } |
|
1197 }; |
|
1198 |
|
1199 // // FIXME: comparison should be made better!!! |
|
1200 // template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap> |
|
1201 // class ResGraphWrapper |
|
1202 // { |
|
1203 // Graph* graph; |
|
1204 |
|
1205 // public: |
|
1206 // typedef Graph BaseGraph; |
|
1207 |
|
1208 // typedef typename Graph::Node Node; |
|
1209 // typedef typename Graph::Edge Edge; |
|
1210 |
|
1211 // typedef typename Graph::NodeIt NodeIt; |
|
1212 |
|
1213 // class OutEdgeIt { |
|
1214 // public: |
|
1215 // //Graph::Node n; |
|
1216 // bool out_or_in; |
|
1217 // typename Graph::OutEdgeIt o; |
|
1218 // typename Graph::InEdgeIt i; |
|
1219 // }; |
|
1220 // class InEdgeIt { |
|
1221 // public: |
|
1222 // //Graph::Node n; |
|
1223 // bool out_or_in; |
|
1224 // typename Graph::OutEdgeIt o; |
|
1225 // typename Graph::InEdgeIt i; |
|
1226 // }; |
|
1227 // typedef typename Graph::SymEdgeIt SymEdgeIt; |
|
1228 // typedef typename Graph::EdgeIt EdgeIt; |
|
1229 |
|
1230 // int nodeNum() const { return gw.nodeNum(); } |
|
1231 // int edgeNum() const { return gw.edgeNum(); } |
|
1232 |
|
1233 // Node& first(Node& n) const { return gw.first(n); } |
|
1234 |
|
1235 // // Edge and SymEdge is missing!!!! |
|
1236 // // Edge <-> In/OutEdgeIt conversion is missing!!!! |
|
1237 |
|
1238 // //FIXME |
|
1239 // OutEdgeIt& first(OutEdgeIt& e, const Node& n) const |
|
1240 // { |
|
1241 // e.n=n; |
|
1242 // gw.first(e.o,n); |
|
1243 // while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o)) |
|
1244 // gw.goNext(e.o); |
|
1245 // if(!gw.valid(e.o)) { |
|
1246 // gw.first(e.i,n); |
|
1247 // while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i)) |
|
1248 // gw.goNext(e.i); |
|
1249 // } |
|
1250 // return e; |
|
1251 // } |
|
1252 // /* |
|
1253 // OutEdgeIt &goNext(OutEdgeIt &e) |
|
1254 // { |
|
1255 // if(gw.valid(e.o)) { |
|
1256 // while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o)) |
|
1257 // gw.goNext(e.o); |
|
1258 // if(gw.valid(e.o)) return e; |
|
1259 // else gw.first(e.i,e.n); |
|
1260 // } |
|
1261 // else { |
|
1262 // while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i)) |
|
1263 // gw.goNext(e.i); |
|
1264 // return e; |
|
1265 // } |
|
1266 // } |
|
1267 // OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);} |
|
1268 // */ |
|
1269 // //bool valid(const OutEdgeIt e) { return gw.valid(e.o)||gw.valid(e.i);} |
|
1270 |
|
1271 // //FIXME |
|
1272 // InEdgeIt& first(InEdgeIt& e, const Node& n) const |
|
1273 // { |
|
1274 // e.n=n; |
|
1275 // gw.first(e.i,n); |
|
1276 // while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i)) |
|
1277 // gw.goNext(e.i); |
|
1278 // if(!gw.valid(e.i)) { |
|
1279 // gw.first(e.o,n); |
|
1280 // while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o)) |
|
1281 // gw.goNext(e.o); |
|
1282 // } |
|
1283 // return e; |
|
1284 // } |
|
1285 // /* |
|
1286 // InEdgeIt &goNext(InEdgeIt &e) |
|
1287 // { |
|
1288 // if(gw.valid(e.i)) { |
|
1289 // while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i)) |
|
1290 // gw.goNext(e.i); |
|
1291 // if(gw.valid(e.i)) return e; |
|
1292 // else gw.first(e.o,e.n); |
|
1293 // } |
|
1294 // else { |
|
1295 // while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o)) |
|
1296 // gw.goNext(e.o); |
|
1297 // return e; |
|
1298 // } |
|
1299 // } |
|
1300 // InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);} |
|
1301 // */ |
|
1302 // //bool valid(const InEdgeIt e) { return gw.valid(e.i)||gw.valid(e.o);} |
|
1303 |
|
1304 // //template<typename I> I &goNext(I &i); { return gw.goNext(i); } |
|
1305 // //template<typename I> I next(const I i); { return gw.goNext(i); } |
|
1306 |
|
1307 // template< typename It > It first() const { |
|
1308 // It e; first(e); return e; } |
|
1309 |
|
1310 // template< typename It > It first(Node v) const { |
|
1311 // It e; first(e, v); return e; } |
|
1312 |
|
1313 // Node target(const Edge& e) const { return gw.target(e); } |
|
1314 // Node source(const Edge& e) const { return gw.source(e); } |
|
1315 |
|
1316 // template<typename I> Node aNode(const I& e) const { |
|
1317 // return gw.aNode(e); } |
|
1318 // template<typename I> Node bNode(const I& e) const { |
|
1319 // return gw.bNode(e); } |
|
1320 |
|
1321 // //template<typename I> bool valid(const I i); |
|
1322 // //{ return gw.valid(i); } |
|
1323 |
|
1324 // //template<typename I> void setInvalid(const I &i); |
|
1325 // //{ return gw.setInvalid(i); } |
|
1326 |
|
1327 // Node addNode() { return gw.addNode(); } |
|
1328 // Edge addEdge(const Node& source, const Node& target) { |
|
1329 // return gw.addEdge(source, target); } |
|
1330 |
|
1331 // template<typename I> void erase(const I& i) { gw.erase(i); } |
|
1332 |
|
1333 // void clear() { gw.clear(); } |
|
1334 |
|
1335 // template<typename S> class NodeMap : public Graph::NodeMap<S> { }; |
|
1336 // template<typename S> class EdgeMap : public Graph::EdgeMap<S> { }; |
|
1337 |
|
1338 // void setGraph(Graph& _graph) { graph = &_graph; } |
|
1339 // Graph& getGraph() { return (*graph); } |
|
1340 |
|
1341 // //ResGraphWrapper() : graph(0) { } |
|
1342 // ResGraphWrapper(Graph& _graph) : graph(&_graph) { } |
|
1343 // }; |
|
1344 |
|
1345 } //namespace lemon |
|
1346 |
|
1347 #endif //LEMON_GRAPH_WRAPPER_H |
|
1348 |
|