27 TrivGraphWrapper(Graph& _graph) : graph(&_graph) { } |
27 TrivGraphWrapper(Graph& _graph) : graph(&_graph) { } |
28 |
28 |
29 void setGraph(Graph& _graph) { graph = &_graph; } |
29 void setGraph(Graph& _graph) { graph = &_graph; } |
30 Graph& getGraph() const { return (*graph); } |
30 Graph& getGraph() const { return (*graph); } |
31 |
31 |
32 template<typename I> I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); } |
32 template<typename I> I& first(I& i) const { return graph->first(i); } |
33 template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const { |
33 template<typename I, typename P> I& first(I& i, const P& p) const { |
34 return graph->/*getF*/first(i, p); } |
34 return graph->first(i, p); } |
35 |
35 |
36 template<typename I> I getNext(const I& i) const { |
36 template<typename I> I getNext(const I& i) const { |
37 return graph->getNext(i); } |
37 return graph->getNext(i); } |
38 template<typename I> I& next(I &i) const { return graph->next(i); } |
38 template<typename I> I& next(I &i) const { return graph->next(i); } |
39 |
39 |
40 template< typename It > It first() const { |
40 template< typename It > It first() const { |
41 It e; /*getF*/first(e); return e; } |
41 It e; first(e); return e; } |
42 |
42 |
43 template< typename It > It first(const Node& v) const { |
43 template< typename It > It first(const Node& v) const { |
44 It e; /*getF*/first(e, v); return e; } |
44 It e; first(e, v); return e; } |
45 |
45 |
46 Node head(const Edge& e) const { return graph->head(e); } |
46 Node head(const Edge& e) const { return graph->head(e); } |
47 Node tail(const Edge& e) const { return graph->tail(e); } |
47 Node tail(const Edge& e) const { return graph->tail(e); } |
48 |
48 |
49 template<typename I> bool valid(const I& i) const |
49 template<typename I> bool valid(const I& i) const |
80 public: |
80 public: |
81 EdgeMap(const TrivGraphWrapper<Graph>& _G) : |
81 EdgeMap(const TrivGraphWrapper<Graph>& _G) : |
82 Graph::EdgeMap<T>(_G.getGraph()) { } |
82 Graph::EdgeMap<T>(_G.getGraph()) { } |
83 EdgeMap(const TrivGraphWrapper<Graph>& _G, T a) : |
83 EdgeMap(const TrivGraphWrapper<Graph>& _G, T a) : |
84 Graph::EdgeMap<T>(_G.getGraph(), a) { } |
84 Graph::EdgeMap<T>(_G.getGraph(), a) { } |
|
85 }; |
|
86 }; |
|
87 |
|
88 template<typename GraphWrapper> |
|
89 class GraphWrapperSkeleton { |
|
90 protected: |
|
91 GraphWrapper gw; |
|
92 |
|
93 public: |
|
94 typedef typename GraphWrapper::BaseGraph BaseGraph; |
|
95 |
|
96 typedef typename GraphWrapper::Node Node; |
|
97 typedef typename GraphWrapper::NodeIt NodeIt; |
|
98 |
|
99 typedef typename GraphWrapper::Edge Edge; |
|
100 typedef typename GraphWrapper::OutEdgeIt OutEdgeIt; |
|
101 typedef typename GraphWrapper::InEdgeIt InEdgeIt; |
|
102 //typedef typename GraphWrapper::SymEdgeIt SymEdgeIt; |
|
103 typedef typename GraphWrapper::EdgeIt EdgeIt; |
|
104 |
|
105 //GraphWrapperSkeleton() : gw() { } |
|
106 GraphWrapperSkeleton(GraphWrapper& _gw) : gw(_gw) { } |
|
107 |
|
108 void setGraph(BaseGraph& _graph) { gw.setGraph(_graph); } |
|
109 BaseGraph& getGraph() const { return gw.getGraph(); } |
|
110 |
|
111 template<typename I> I& first(I& i) const { return gw.first(i); } |
|
112 template<typename I, typename P> I& first(I& i, const P& p) const { |
|
113 return gw.first(i, p); } |
|
114 |
|
115 template<typename I> I getNext(const I& i) const { return gw.getNext(i); } |
|
116 template<typename I> I& next(I &i) const { return gw.next(i); } |
|
117 |
|
118 template< typename It > It first() const { |
|
119 It e; this->first(e); return e; } |
|
120 |
|
121 template< typename It > It first(const Node& v) const { |
|
122 It e; this->first(e, v); return e; } |
|
123 |
|
124 Node head(const Edge& e) const { return gw.head(e); } |
|
125 Node tail(const Edge& e) const { return gw.tail(e); } |
|
126 |
|
127 template<typename I> bool valid(const I& i) const { return gw.valid(i); } |
|
128 |
|
129 //template<typename I> void setInvalid(const I &i); |
|
130 //{ return graph->setInvalid(i); } |
|
131 |
|
132 int nodeNum() const { return gw.nodeNum(); } |
|
133 int edgeNum() const { return gw.edgeNum(); } |
|
134 |
|
135 template<typename I> Node aNode(const I& e) const { return gw.aNode(e); } |
|
136 template<typename I> Node bNode(const I& e) const { return gw.bNode(e); } |
|
137 |
|
138 Node addNode() const { return gw.addNode(); } |
|
139 Edge addEdge(const Node& tail, const Node& head) const { |
|
140 return gw.addEdge(tail, head); } |
|
141 |
|
142 template<typename I> void erase(const I& i) const { gw.erase(i); } |
|
143 |
|
144 void clear() const { gw.clear(); } |
|
145 |
|
146 template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> { |
|
147 public: |
|
148 NodeMap(const GraphWrapperSkeleton<GraphWrapper>& _G) : |
|
149 GraphWrapper::NodeMap<T>(_G.gw) { } |
|
150 NodeMap(const GraphWrapperSkeleton<GraphWrapper>& _G, T a) : |
|
151 GraphWrapper::NodeMap<T>(_G.gw, a) { } |
|
152 }; |
|
153 |
|
154 template<typename T> class EdgeMap : public GraphWrapper::EdgeMap<T> { |
|
155 public: |
|
156 EdgeMap(const GraphWrapperSkeleton<GraphWrapper>& _G) : |
|
157 GraphWrapper::EdgeMap<T>(_G.gw) { } |
|
158 EdgeMap(const GraphWrapperSkeleton<GraphWrapper>& _G, T a) : |
|
159 GraphWrapper::EdgeMap<T>(_G.gw, a) { } |
85 }; |
160 }; |
86 }; |
161 }; |
87 |
162 |
88 template<typename Graph> |
163 template<typename Graph> |
89 class RevGraphWrapper |
164 class RevGraphWrapper |
107 RevGraphWrapper(Graph& _graph) : graph(&_graph) { } |
182 RevGraphWrapper(Graph& _graph) : graph(&_graph) { } |
108 |
183 |
109 void setGraph(Graph& _graph) { graph = &_graph; } |
184 void setGraph(Graph& _graph) { graph = &_graph; } |
110 Graph& getGraph() const { return (*graph); } |
185 Graph& getGraph() const { return (*graph); } |
111 |
186 |
112 template<typename I> I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); } |
187 template<typename I> I& first(I& i) const { return graph->first(i); } |
113 template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const { |
188 template<typename I, typename P> I& first(I& i, const P& p) const { |
114 return graph->/*getF*/first(i, p); } |
189 return graph->first(i, p); } |
115 |
190 |
116 template<typename I> I getNext(const I& i) const { |
191 template<typename I> I getNext(const I& i) const { |
117 return graph->getNext(i); } |
192 return graph->getNext(i); } |
118 template<typename I> I& next(I &i) const { return graph->next(i); } |
193 template<typename I> I& next(I &i) const { return graph->next(i); } |
119 |
194 |
120 template< typename It > It first() const { |
195 template< typename It > It first() const { |
121 It e; /*getF*/first(e); return e; } |
196 It e; first(e); return e; } |
122 |
197 |
123 template< typename It > It first(const Node& v) const { |
198 template< typename It > It first(const Node& v) const { |
124 It e; /*getF*/first(e, v); return e; } |
199 It e; first(e, v); return e; } |
125 |
200 |
126 Node head(const Edge& e) const { return graph->tail(e); } |
201 Node head(const Edge& e) const { return graph->tail(e); } |
127 Node tail(const Edge& e) const { return graph->head(e); } |
202 Node tail(const Edge& e) const { return graph->head(e); } |
128 |
203 |
129 template<typename I> bool valid(const I& i) const |
204 template<typename I> bool valid(const I& i) const |
225 public: |
300 public: |
226 OutEdgeIt() : Edge() { } |
301 OutEdgeIt() : Edge() { } |
227 OutEdgeIt(const Invalid& i) : Edge(i) { } |
302 OutEdgeIt(const Invalid& i) : Edge(i) { } |
228 OutEdgeIt(const UndirGraphWrapper& _G, const Node& n) : Edge() { |
303 OutEdgeIt(const UndirGraphWrapper& _G, const Node& n) : Edge() { |
229 out_or_in=true; |
304 out_or_in=true; |
230 _G.graph->/*getF*/first(out, n); |
305 _G.graph->first(out, n); |
231 if (!(_G.graph->valid(out))) { |
306 if (!(_G.graph->valid(out))) { |
232 out_or_in=false; |
307 out_or_in=false; |
233 _G.graph->/*getF*/first(in, n); |
308 _G.graph->first(in, n); |
234 } |
309 } |
235 } |
310 } |
236 }; |
311 }; |
237 |
312 |
238 OutEdgeIt& /*getF*/first(OutEdgeIt& e, const Node& n) const { |
313 OutEdgeIt& first(OutEdgeIt& e, const Node& n) const { |
239 e.out_or_in=true; |
314 e.out_or_in=true; |
240 graph->/*getF*/first(e.out, n); |
315 graph->first(e.out, n); |
241 if (!(graph->valid(e.out))) { |
316 if (!(graph->valid(e.out))) { |
242 e.out_or_in=false; |
317 e.out_or_in=false; |
243 graph->/*getF*/first(e.in, n); |
318 graph->first(e.in, n); |
244 } |
319 } |
245 return e; |
320 return e; |
246 } |
321 } |
247 |
322 |
248 OutEdgeIt& next(OutEdgeIt& e) const { |
323 OutEdgeIt& next(OutEdgeIt& e) const { |
249 if (e.out_or_in) { |
324 if (e.out_or_in) { |
250 Node n=graph->tail(e.out); |
325 Node n=graph->tail(e.out); |
251 graph->next(e.out); |
326 graph->next(e.out); |
252 if (!graph->valid(e.out)) { |
327 if (!graph->valid(e.out)) { |
253 e.out_or_in=false; |
328 e.out_or_in=false; |
254 graph->/*getF*/first(e.in, n); |
329 graph->first(e.in, n); |
255 } |
330 } |
256 } else { |
331 } else { |
257 graph->next(e.in); |
332 graph->next(e.in); |
258 } |
333 } |
259 return e; |
334 return e; |
264 Node bNode(const OutEdgeIt& e) const { |
339 Node bNode(const OutEdgeIt& e) const { |
265 if (e.out_or_in) return graph->head(e); else return graph->tail(e); } |
340 if (e.out_or_in) return graph->head(e); else return graph->tail(e); } |
266 |
341 |
267 typedef OutEdgeIt InEdgeIt; |
342 typedef OutEdgeIt InEdgeIt; |
268 |
343 |
269 template<typename I> I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); } |
344 template<typename I> I& first(I& i) const { return graph->first(i); } |
270 // template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const { |
345 // template<typename I, typename P> I& first(I& i, const P& p) const { |
271 // return graph->/*getF*/first(i, p); } |
346 // return graph->first(i, p); } |
272 |
347 |
273 template<typename I> I getNext(const I& i) const { |
348 template<typename I> I getNext(const I& i) const { |
274 return graph->getNext(i); } |
349 return graph->getNext(i); } |
275 template<typename I> I& next(I &i) const { return graph->next(i); } |
350 template<typename I> I& next(I &i) const { return graph->next(i); } |
276 |
351 |
277 template< typename It > It first() const { |
352 template< typename It > It first() const { |
278 It e; /*getF*/first(e); return e; } |
353 It e; first(e); return e; } |
279 |
354 |
280 template< typename It > It first(const Node& v) const { |
355 template< typename It > It first(const Node& v) const { |
281 It e; /*getF*/first(e, v); return e; } |
356 It e; first(e, v); return e; } |
282 |
357 |
283 Node head(const Edge& e) const { return graph->head(e); } |
358 Node head(const Edge& e) const { return graph->head(e); } |
284 Node tail(const Edge& e) const { return graph->tail(e); } |
359 Node tail(const Edge& e) const { return graph->tail(e); } |
285 |
360 |
286 template<typename I> bool valid(const I& i) const |
361 template<typename I> bool valid(const I& i) const |
346 // typedef typename Graph::EdgeIt EdgeIt; |
421 // typedef typename Graph::EdgeIt EdgeIt; |
347 |
422 |
348 // int nodeNum() const { return graph->nodeNum(); } |
423 // int nodeNum() const { return graph->nodeNum(); } |
349 // int edgeNum() const { return graph->edgeNum(); } |
424 // int edgeNum() const { return graph->edgeNum(); } |
350 |
425 |
351 // template<typename I> I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); } |
426 // template<typename I> I& first(I& i) const { return graph->first(i); } |
352 // template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const { |
427 // template<typename I, typename P> I& first(I& i, const P& p) const { |
353 // return graph->/*getF*/first(i, p); } |
428 // return graph->first(i, p); } |
354 // //template<typename I> I next(const I i); { return graph->goNext(i); } |
429 // //template<typename I> I next(const I i); { return graph->goNext(i); } |
355 // //template<typename I> I &goNext(I &i); { return graph->goNext(i); } |
430 // //template<typename I> I &goNext(I &i); { return graph->goNext(i); } |
356 |
431 |
357 // template< typename It > It first() const { |
432 // template< typename It > It first() const { |
358 // It e; /*getF*/first(e); return e; } |
433 // It e; first(e); return e; } |
359 |
434 |
360 // template< typename It > It first(Node v) const { |
435 // template< typename It > It first(Node v) const { |
361 // It e; /*getF*/first(e, v); return e; } |
436 // It e; first(e, v); return e; } |
362 |
437 |
363 // Node head(const Edge& e) const { return graph->head(e); } |
438 // Node head(const Edge& e) const { return graph->head(e); } |
364 // Node tail(const Edge& e) const { return graph->tail(e); } |
439 // Node tail(const Edge& e) const { return graph->tail(e); } |
365 |
440 |
366 // template<typename I> Node aNode(const I& e) const { |
441 // template<typename I> Node aNode(const I& e) const { |
453 //FIXME |
528 //FIXME |
454 OutEdgeIt(const Edge& e) : Edge(e) { } |
529 OutEdgeIt(const Edge& e) : Edge(e) { } |
455 OutEdgeIt(const Invalid& i) : Edge(i) { } |
530 OutEdgeIt(const Invalid& i) : Edge(i) { } |
456 private: |
531 private: |
457 OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() { |
532 OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() { |
458 resG.graph->/*getF*/first(out, v); |
533 resG.graph->first(out, v); |
459 while( resG.graph->valid(out) && !(resG.free(out)>0) ) { resG.graph->next(out); } |
534 while( resG.graph->valid(out) && !(resG.free(out)>0) ) { resG.graph->next(out); } |
460 if (!resG.graph->valid(out)) { |
535 if (!resG.graph->valid(out)) { |
461 out_or_in=0; |
536 out_or_in=0; |
462 resG.graph->/*getF*/first(in, v); |
537 resG.graph->first(in, v); |
463 while( resG.graph->valid(in) && !(resG.free(in)>0) ) { resG.graph->next(in); } |
538 while( resG.graph->valid(in) && !(resG.free(in)>0) ) { resG.graph->next(in); } |
464 } |
539 } |
465 } |
540 } |
466 // public: |
541 // public: |
467 // OutEdgeIt& operator++() { |
542 // OutEdgeIt& operator++() { |
488 public: |
563 public: |
489 EdgeIt() { } |
564 EdgeIt() { } |
490 //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { } |
565 //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { } |
491 EdgeIt(const Invalid& i) : Edge(i) { } |
566 EdgeIt(const Invalid& i) : Edge(i) { } |
492 EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() { |
567 EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() { |
493 resG.graph->/*getF*/first(v); |
568 resG.graph->first(v); |
494 if (resG.graph->valid(v)) resG.graph->/*getF*/first(out, v); else out=OldOutEdgeIt(INVALID); |
569 if (resG.graph->valid(v)) resG.graph->first(out, v); else out=OldOutEdgeIt(INVALID); |
495 while (resG.graph->valid(out) && !(resG.free(out)>0) ) { resG.graph->next(out); } |
570 while (resG.graph->valid(out) && !(resG.free(out)>0) ) { resG.graph->next(out); } |
496 while (resG.graph->valid(v) && !resG.graph->valid(out)) { |
571 while (resG.graph->valid(v) && !resG.graph->valid(out)) { |
497 resG.graph->next(v); |
572 resG.graph->next(v); |
498 if (resG.graph->valid(v)) resG.graph->/*getF*/first(out, v); |
573 if (resG.graph->valid(v)) resG.graph->first(out, v); |
499 while (resG.graph->valid(out) && !(resG.free(out)>0) ) { resG.graph->next(out); } |
574 while (resG.graph->valid(out) && !(resG.free(out)>0) ) { resG.graph->next(out); } |
500 } |
575 } |
501 if (!resG.graph->valid(out)) { |
576 if (!resG.graph->valid(out)) { |
502 out_or_in=0; |
577 out_or_in=0; |
503 resG.graph->/*getF*/first(v); |
578 resG.graph->first(v); |
504 if (resG.graph->valid(v)) resG.graph->/*getF*/first(in, v); else in=OldInEdgeIt(INVALID); |
579 if (resG.graph->valid(v)) resG.graph->first(in, v); else in=OldInEdgeIt(INVALID); |
505 while (resG.graph->valid(in) && !(resG.free(in)>0) ) { resG.graph->next(in); } |
580 while (resG.graph->valid(in) && !(resG.free(in)>0) ) { resG.graph->next(in); } |
506 while (resG.graph->valid(v) && !resG.graph->valid(in)) { |
581 while (resG.graph->valid(v) && !resG.graph->valid(in)) { |
507 resG.graph->next(v); |
582 resG.graph->next(v); |
508 if (resG.graph->valid(v)) resG.graph->/*getF*/first(in, v); |
583 if (resG.graph->valid(v)) resG.graph->first(in, v); |
509 while (resG.graph->valid(in) && !(resG.free(in)>0) ) { resG.graph->next(in); } |
584 while (resG.graph->valid(in) && !(resG.free(in)>0) ) { resG.graph->next(in); } |
510 } |
585 } |
511 } |
586 } |
512 } |
587 } |
513 // EdgeIt& operator++() { |
588 // EdgeIt& operator++() { |
514 // if (out_or_in) { |
589 // if (out_or_in) { |
515 // ++out; |
590 // ++out; |
516 // while (out.valid() && !(Edge::free()>0) ) { ++out; } |
591 // while (out.valid() && !(Edge::free()>0) ) { ++out; } |
517 // while (v.valid() && !out.valid()) { |
592 // while (v.valid() && !out.valid()) { |
518 // ++v; |
593 // ++v; |
519 // if (v.valid()) G->/*getF*/first(out, v); |
594 // if (v.valid()) G->first(out, v); |
520 // while (out.valid() && !(Edge::free()>0) ) { ++out; } |
595 // while (out.valid() && !(Edge::free()>0) ) { ++out; } |
521 // } |
596 // } |
522 // if (!out.valid()) { |
597 // if (!out.valid()) { |
523 // out_or_in=0; |
598 // out_or_in=0; |
524 // G->/*getF*/first(v); |
599 // G->first(v); |
525 // if (v.valid()) G->/*getF*/first(in, v); else in=OldInEdgeIt(); |
600 // if (v.valid()) G->first(in, v); else in=OldInEdgeIt(); |
526 // while (in.valid() && !(Edge::free()>0) ) { ++in; } |
601 // while (in.valid() && !(Edge::free()>0) ) { ++in; } |
527 // while (v.valid() && !in.valid()) { |
602 // while (v.valid() && !in.valid()) { |
528 // ++v; |
603 // ++v; |
529 // if (v.valid()) G->/*getF*/first(in, v); |
604 // if (v.valid()) G->first(in, v); |
530 // while (in.valid() && !(Edge::free()>0) ) { ++in; } |
605 // while (in.valid() && !(Edge::free()>0) ) { ++in; } |
531 // } |
606 // } |
532 // } |
607 // } |
533 // } else { |
608 // } else { |
534 // ++in; |
609 // ++in; |
535 // while (in.valid() && !(Edge::free()>0) ) { ++in; } |
610 // while (in.valid() && !(Edge::free()>0) ) { ++in; } |
536 // while (v.valid() && !in.valid()) { |
611 // while (v.valid() && !in.valid()) { |
537 // ++v; |
612 // ++v; |
538 // if (v.valid()) G->/*getF*/first(in, v); |
613 // if (v.valid()) G->first(in, v); |
539 // while (in.valid() && !(Edge::free()>0) ) { ++in; } |
614 // while (in.valid() && !(Edge::free()>0) ) { ++in; } |
540 // } |
615 // } |
541 // } |
616 // } |
542 // return *this; |
617 // return *this; |
543 // } |
618 // } |
544 }; |
619 }; |
545 |
620 |
546 NodeIt& /*getF*/first(NodeIt& v) const { return graph->/*getF*/first(v); } |
621 NodeIt& first(NodeIt& v) const { return graph->first(v); } |
547 OutEdgeIt& /*getF*/first(OutEdgeIt& e, Node v) const { |
622 OutEdgeIt& first(OutEdgeIt& e, Node v) const { |
548 e=OutEdgeIt(*this, v); |
623 e=OutEdgeIt(*this, v); |
549 return e; |
624 return e; |
550 } |
625 } |
551 EdgeIt& /*getF*/first(EdgeIt& e) const { |
626 EdgeIt& first(EdgeIt& e) const { |
552 e=EdgeIt(*this); |
627 e=EdgeIt(*this); |
553 return e; |
628 return e; |
554 } |
629 } |
555 |
630 |
556 NodeIt& next(NodeIt& n) const { return graph->next(n); } |
631 NodeIt& next(NodeIt& n) const { return graph->next(n); } |
576 if (e.out_or_in) { |
651 if (e.out_or_in) { |
577 graph->next(e.out); |
652 graph->next(e.out); |
578 while (graph->valid(e.out) && !(free(e.out)>0) ) { graph->next(e.out); } |
653 while (graph->valid(e.out) && !(free(e.out)>0) ) { graph->next(e.out); } |
579 while (graph->valid(e.v) && !graph->valid(e.out)) { |
654 while (graph->valid(e.v) && !graph->valid(e.out)) { |
580 graph->next(e.v); |
655 graph->next(e.v); |
581 if (graph->valid(e.v)) graph->/*getF*/first(e.out, e.v); |
656 if (graph->valid(e.v)) graph->first(e.out, e.v); |
582 while (graph->valid(e.out) && !(free(e.out)>0) ) { graph->next(e.out); } |
657 while (graph->valid(e.out) && !(free(e.out)>0) ) { graph->next(e.out); } |
583 } |
658 } |
584 if (!graph->valid(e.out)) { |
659 if (!graph->valid(e.out)) { |
585 e.out_or_in=0; |
660 e.out_or_in=0; |
586 graph->/*getF*/first(e.v); |
661 graph->first(e.v); |
587 if (graph->valid(e.v)) graph->/*getF*/first(e.in, e.v); else e.in=OldInEdgeIt(INVALID); |
662 if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=OldInEdgeIt(INVALID); |
588 while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); } |
663 while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); } |
589 while (graph->valid(e.v) && !graph->valid(e.in)) { |
664 while (graph->valid(e.v) && !graph->valid(e.in)) { |
590 graph->next(e.v); |
665 graph->next(e.v); |
591 if (graph->valid(e.v)) graph->/*getF*/first(e.in, e.v); |
666 if (graph->valid(e.v)) graph->first(e.in, e.v); |
592 while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); } |
667 while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); } |
593 } |
668 } |
594 } |
669 } |
595 } else { |
670 } else { |
596 graph->next(e.in); |
671 graph->next(e.in); |
597 while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); } |
672 while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); } |
598 while (graph->valid(e.v) && !graph->valid(e.in)) { |
673 while (graph->valid(e.v) && !graph->valid(e.in)) { |
599 graph->next(e.v); |
674 graph->next(e.v); |
600 if (graph->valid(e.v)) graph->/*getF*/first(e.in, e.v); |
675 if (graph->valid(e.v)) graph->first(e.in, e.v); |
601 while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); } |
676 while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); } |
602 } |
677 } |
603 } |
678 } |
604 return e; |
679 return e; |
605 } |
680 } |
606 |
681 |
607 |
682 |
608 template< typename It > |
683 template< typename It > |
609 It first() const { |
684 It first() const { |
610 It e; |
685 It e; |
611 /*getF*/first(e); |
686 first(e); |
612 return e; |
687 return e; |
613 } |
688 } |
614 |
689 |
615 template< typename It > |
690 template< typename It > |
616 It first(Node v) const { |
691 It first(Node v) const { |
617 It e; |
692 It e; |
618 /*getF*/first(e, v); |
693 first(e, v); |
619 return e; |
694 return e; |
620 } |
695 } |
621 |
696 |
622 Node tail(Edge e) const { |
697 Node tail(Edge e) const { |
623 return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); } |
698 return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); } |
706 const CapacityMap& _capacity) : |
781 const CapacityMap& _capacity) : |
707 ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity), |
782 ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity), |
708 first_out_edges(*this) /*, dist(*this)*/ { |
783 first_out_edges(*this) /*, dist(*this)*/ { |
709 for(NodeIt n=this->template first<NodeIt>(); this->valid(n); this->next(n)) { |
784 for(NodeIt n=this->template first<NodeIt>(); this->valid(n); this->next(n)) { |
710 OutEdgeIt e; |
785 OutEdgeIt e; |
711 ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::/*getF*/first(e, n); |
786 ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n); |
712 first_out_edges.set(n, e); |
787 first_out_edges.set(n, e); |
713 } |
788 } |
714 } |
789 } |
715 |
790 |
716 //void setGraph(Graph& _graph) { graph = &_graph; } |
791 //void setGraph(Graph& _graph) { graph = &_graph; } |
737 typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt; |
812 typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt; |
738 //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt; |
813 //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt; |
739 //typedef typename Graph::SymEdgeIt SymEdgeIt; |
814 //typedef typename Graph::SymEdgeIt SymEdgeIt; |
740 //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt; |
815 //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt; |
741 |
816 |
742 NodeIt& /*getF*/first(NodeIt& n) const { |
817 NodeIt& first(NodeIt& n) const { |
743 return ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::/*getF*/first(n); |
818 return ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(n); |
744 } |
819 } |
745 |
820 |
746 OutEdgeIt& /*getF*/first(OutEdgeIt& e, const Node& n) const { |
821 OutEdgeIt& first(OutEdgeIt& e, const Node& n) const { |
747 e=first_out_edges.get(n); |
822 e=first_out_edges.get(n); |
748 return e; |
823 return e; |
749 } |
824 } |
750 |
825 |
751 //ROSSZ template<typename I> I& /*getF*/first(I& i) const { return /*getF*/first(i); } |
826 //ROSSZ template<typename I> I& first(I& i) const { return first(i); } |
752 //ROSSZ template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const { |
827 //ROSSZ template<typename I, typename P> I& first(I& i, const P& p) const { |
753 // return /*getF*/first(i, p); } |
828 // return first(i, p); } |
754 |
829 |
755 //template<typename I> I getNext(const I& i) const { |
830 //template<typename I> I getNext(const I& i) const { |
756 // return graph->getNext(i); } |
831 // return graph->getNext(i); } |
757 //template<typename I> I& next(I &i) const { return graph->next(i); } |
832 //template<typename I> I& next(I &i) const { return graph->next(i); } |
758 |
833 |
759 template< typename It > It first() const { |
834 template< typename It > It first() const { |
760 It e; /*getF*/first(e); return e; } |
835 It e; first(e); return e; } |
761 |
836 |
762 template< typename It > It first(const Node& v) const { |
837 template< typename It > It first(const Node& v) const { |
763 It e; /*getF*/first(e, v); return e; } |
838 It e; first(e, v); return e; } |
764 |
839 |
765 //Node head(const Edge& e) const { return graph->head(e); } |
840 //Node head(const Edge& e) const { return graph->head(e); } |
766 //Node tail(const Edge& e) const { return graph->tail(e); } |
841 //Node tail(const Edge& e) const { return graph->tail(e); } |
767 |
842 |
768 //template<typename I> bool valid(const I& i) const |
843 //template<typename I> bool valid(const I& i) const |
836 FilterGraphWrapper(const Graph& _G, FlowMap& _flow, |
911 FilterGraphWrapper(const Graph& _G, FlowMap& _flow, |
837 const CapacityMap& _capacity) : |
912 const CapacityMap& _capacity) : |
838 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity), dist(*this, graph->nodeNum()) { |
913 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity), dist(*this, graph->nodeNum()) { |
839 } |
914 } |
840 |
915 |
841 OutEdgeIt& /*getF*/first(OutEdgeIt& e, const Node& n) const { |
916 OutEdgeIt& first(OutEdgeIt& e, const Node& n) const { |
842 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::/*getF*/first(e, n); |
917 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n); |
843 while (valid(e) && (dist.get(tail(e))/*+1!=*/>=dist.get(head(e)))) |
918 while (valid(e) && (dist.get(tail(e))/*+1!=*/>=dist.get(head(e)))) |
844 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e); |
919 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e); |
845 return e; |
920 return e; |
846 } |
921 } |
847 |
922 |
854 while (valid(e) && (dist.get(tail(e))/*+1!*/>=dist.get(head(e)))) |
929 while (valid(e) && (dist.get(tail(e))/*+1!*/>=dist.get(head(e)))) |
855 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e); |
930 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e); |
856 return e; |
931 return e; |
857 } |
932 } |
858 |
933 |
859 NodeIt& /*getF*/first(NodeIt& n) const { |
934 NodeIt& first(NodeIt& n) const { |
860 return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::/*getF*/first(n); |
935 return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(n); |
861 } |
936 } |
862 |
937 |
863 void erase(const Edge& e) { |
938 void erase(const Edge& e) { |
864 OutEdgeIt f(e); |
939 OutEdgeIt f(e); |
865 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f); |
940 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f); |
872 //TrivGraphWrapper(Graph& _graph) : graph(&_graph) { } |
947 //TrivGraphWrapper(Graph& _graph) : graph(&_graph) { } |
873 |
948 |
874 //void setGraph(Graph& _graph) { graph = &_graph; } |
949 //void setGraph(Graph& _graph) { graph = &_graph; } |
875 //Graph& getGraph() const { return (*graph); } |
950 //Graph& getGraph() const { return (*graph); } |
876 |
951 |
877 //template<typename I> I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); } |
952 //template<typename I> I& first(I& i) const { return graph->first(i); } |
878 //template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const { |
953 //template<typename I, typename P> I& first(I& i, const P& p) const { |
879 // return graph->/*getF*/first(i, p); } |
954 // return graph->first(i, p); } |
880 |
955 |
881 //template<typename I> I getNext(const I& i) const { |
956 //template<typename I> I getNext(const I& i) const { |
882 // return graph->getNext(i); } |
957 // return graph->getNext(i); } |
883 //template<typename I> I& next(I &i) const { return graph->next(i); } |
958 //template<typename I> I& next(I &i) const { return graph->next(i); } |
884 |
959 |
885 template< typename It > It first() const { |
960 template< typename It > It first() const { |
886 It e; /*getF*/first(e); return e; } |
961 It e; first(e); return e; } |
887 |
962 |
888 template< typename It > It first(const Node& v) const { |
963 template< typename It > It first(const Node& v) const { |
889 It e; /*getF*/first(e, v); return e; } |
964 It e; first(e, v); return e; } |
890 |
965 |
891 //Node head(const Edge& e) const { return graph->head(e); } |
966 //Node head(const Edge& e) const { return graph->head(e); } |
892 //Node tail(const Edge& e) const { return graph->tail(e); } |
967 //Node tail(const Edge& e) const { return graph->tail(e); } |
893 |
968 |
894 //template<typename I> bool valid(const I& i) const |
969 //template<typename I> bool valid(const I& i) const |
968 // typedef typename Graph::EdgeIt EdgeIt; |
1043 // typedef typename Graph::EdgeIt EdgeIt; |
969 |
1044 |
970 // int nodeNum() const { return graph->nodeNum(); } |
1045 // int nodeNum() const { return graph->nodeNum(); } |
971 // int edgeNum() const { return graph->edgeNum(); } |
1046 // int edgeNum() const { return graph->edgeNum(); } |
972 |
1047 |
973 // Node& /*getF*/first(Node& n) const { return graph->/*getF*/first(n); } |
1048 // Node& first(Node& n) const { return graph->first(n); } |
974 |
1049 |
975 // // Edge and SymEdge is missing!!!! |
1050 // // Edge and SymEdge is missing!!!! |
976 // // Edge <-> In/OutEdgeIt conversion is missing!!!! |
1051 // // Edge <-> In/OutEdgeIt conversion is missing!!!! |
977 |
1052 |
978 // //FIXME |
1053 // //FIXME |
979 // OutEdgeIt& /*getF*/first(OutEdgeIt& e, const Node& n) const |
1054 // OutEdgeIt& first(OutEdgeIt& e, const Node& n) const |
980 // { |
1055 // { |
981 // e.n=n; |
1056 // e.n=n; |
982 // graph->/*getF*/first(e.o,n); |
1057 // graph->first(e.o,n); |
983 // while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o)) |
1058 // while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o)) |
984 // graph->goNext(e.o); |
1059 // graph->goNext(e.o); |
985 // if(!graph->valid(e.o)) { |
1060 // if(!graph->valid(e.o)) { |
986 // graph->/*getF*/first(e.i,n); |
1061 // graph->first(e.i,n); |
987 // while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i)) |
1062 // while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i)) |
988 // graph->goNext(e.i); |
1063 // graph->goNext(e.i); |
989 // } |
1064 // } |
990 // return e; |
1065 // return e; |
991 // } |
1066 // } |
1007 // OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);} |
1082 // OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);} |
1008 // */ |
1083 // */ |
1009 // //bool valid(const OutEdgeIt e) { return graph->valid(e.o)||graph->valid(e.i);} |
1084 // //bool valid(const OutEdgeIt e) { return graph->valid(e.o)||graph->valid(e.i);} |
1010 |
1085 |
1011 // //FIXME |
1086 // //FIXME |
1012 // InEdgeIt& /*getF*/first(InEdgeIt& e, const Node& n) const |
1087 // InEdgeIt& first(InEdgeIt& e, const Node& n) const |
1013 // { |
1088 // { |
1014 // e.n=n; |
1089 // e.n=n; |
1015 // graph->/*getF*/first(e.i,n); |
1090 // graph->first(e.i,n); |
1016 // while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i)) |
1091 // while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i)) |
1017 // graph->goNext(e.i); |
1092 // graph->goNext(e.i); |
1018 // if(!graph->valid(e.i)) { |
1093 // if(!graph->valid(e.i)) { |
1019 // graph->/*getF*/first(e.o,n); |
1094 // graph->first(e.o,n); |
1020 // while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o)) |
1095 // while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o)) |
1021 // graph->goNext(e.o); |
1096 // graph->goNext(e.o); |
1022 // } |
1097 // } |
1023 // return e; |
1098 // return e; |
1024 // } |
1099 // } |
1043 |
1118 |
1044 // //template<typename I> I &goNext(I &i); { return graph->goNext(i); } |
1119 // //template<typename I> I &goNext(I &i); { return graph->goNext(i); } |
1045 // //template<typename I> I next(const I i); { return graph->goNext(i); } |
1120 // //template<typename I> I next(const I i); { return graph->goNext(i); } |
1046 |
1121 |
1047 // template< typename It > It first() const { |
1122 // template< typename It > It first() const { |
1048 // It e; /*getF*/first(e); return e; } |
1123 // It e; first(e); return e; } |
1049 |
1124 |
1050 // template< typename It > It first(Node v) const { |
1125 // template< typename It > It first(Node v) const { |
1051 // It e; /*getF*/first(e, v); return e; } |
1126 // It e; first(e, v); return e; } |
1052 |
1127 |
1053 // Node head(const Edge& e) const { return graph->head(e); } |
1128 // Node head(const Edge& e) const { return graph->head(e); } |
1054 // Node tail(const Edge& e) const { return graph->tail(e); } |
1129 // Node tail(const Edge& e) const { return graph->tail(e); } |
1055 |
1130 |
1056 // template<typename I> Node aNode(const I& e) const { |
1131 // template<typename I> Node aNode(const I& e) const { |