95 typedef Graph BaseGraph; |
95 typedef Graph BaseGraph; |
96 typedef Graph ParentGraph; |
96 typedef Graph ParentGraph; |
97 |
97 |
98 GraphWrapper(Graph& _graph) : graph(&_graph) { } |
98 GraphWrapper(Graph& _graph) : graph(&_graph) { } |
99 GraphWrapper(const GraphWrapper<Graph>& gw) : graph(gw.graph) { } |
99 GraphWrapper(const GraphWrapper<Graph>& gw) : graph(gw.graph) { } |
100 // Graph& getGraph() const { return *graph; } |
|
101 |
100 |
102 typedef typename Graph::Node Node; |
101 typedef typename Graph::Node Node; |
103 class NodeIt : public Node { |
102 class NodeIt : public Node { |
104 const GraphWrapper<Graph>* gw; |
103 const GraphWrapper<Graph>* gw; |
105 friend class GraphWrapper<Graph>; |
104 friend class GraphWrapper<Graph>; |
106 public: |
105 public: |
107 NodeIt() { } |
106 NodeIt() { } |
108 // NodeIt(const NodeIt& n) : Node(n), gw(n.gw) { } |
|
109 NodeIt(Invalid i) : Node(i) { } |
107 NodeIt(Invalid i) : Node(i) { } |
110 NodeIt(const GraphWrapper<Graph>& _gw) : |
108 NodeIt(const GraphWrapper<Graph>& _gw) : |
111 Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) { } |
109 Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) { } |
112 NodeIt(const GraphWrapper<Graph>& _gw, const Node& n) : |
110 NodeIt(const GraphWrapper<Graph>& _gw, const Node& n) : |
113 Node(n), gw(&_gw) { } |
111 Node(n), gw(&_gw) { } |
121 class OutEdgeIt : public Edge { |
119 class OutEdgeIt : public Edge { |
122 const GraphWrapper<Graph>* gw; |
120 const GraphWrapper<Graph>* gw; |
123 friend class GraphWrapper<Graph>; |
121 friend class GraphWrapper<Graph>; |
124 public: |
122 public: |
125 OutEdgeIt() { } |
123 OutEdgeIt() { } |
126 //OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { } |
|
127 OutEdgeIt(Invalid i) : Edge(i) { } |
124 OutEdgeIt(Invalid i) : Edge(i) { } |
128 OutEdgeIt(const GraphWrapper<Graph>& _gw, const Node& n) : |
125 OutEdgeIt(const GraphWrapper<Graph>& _gw, const Node& n) : |
129 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { } |
126 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { } |
130 OutEdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) : |
127 OutEdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) : |
131 Edge(e), gw(&_gw) { } |
128 Edge(e), gw(&_gw) { } |
138 class InEdgeIt : public Edge { |
135 class InEdgeIt : public Edge { |
139 const GraphWrapper<Graph>* gw; |
136 const GraphWrapper<Graph>* gw; |
140 friend class GraphWrapper<Graph>; |
137 friend class GraphWrapper<Graph>; |
141 public: |
138 public: |
142 InEdgeIt() { } |
139 InEdgeIt() { } |
143 //InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { } |
|
144 InEdgeIt(Invalid i) : Edge(i) { } |
140 InEdgeIt(Invalid i) : Edge(i) { } |
145 InEdgeIt(const GraphWrapper<Graph>& _gw, const Node& n) : |
141 InEdgeIt(const GraphWrapper<Graph>& _gw, const Node& n) : |
146 Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { } |
142 Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { } |
147 InEdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) : |
143 InEdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) : |
148 Edge(e), gw(&_gw) { } |
144 Edge(e), gw(&_gw) { } |
150 *(static_cast<Edge*>(this))= |
146 *(static_cast<Edge*>(this))= |
151 ++(typename Graph::InEdgeIt(*(gw->graph), *this)); |
147 ++(typename Graph::InEdgeIt(*(gw->graph), *this)); |
152 return *this; |
148 return *this; |
153 } |
149 } |
154 }; |
150 }; |
155 //typedef typename Graph::SymEdgeIt SymEdgeIt; |
|
156 class EdgeIt : public Edge { |
151 class EdgeIt : public Edge { |
157 const GraphWrapper<Graph>* gw; |
152 const GraphWrapper<Graph>* gw; |
158 friend class GraphWrapper<Graph>; |
153 friend class GraphWrapper<Graph>; |
159 public: |
154 public: |
160 EdgeIt() { } |
155 EdgeIt() { } |
161 //EdgeIt(const EdgeIt& e) : Edge(e), gw(e.gw) { } |
|
162 EdgeIt(Invalid i) : Edge(i) { } |
156 EdgeIt(Invalid i) : Edge(i) { } |
163 EdgeIt(const GraphWrapper<Graph>& _gw) : |
157 EdgeIt(const GraphWrapper<Graph>& _gw) : |
164 Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { } |
158 Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { } |
165 EdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) : |
159 EdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) : |
166 Edge(e), gw(&_gw) { } |
160 Edge(e), gw(&_gw) { } |
182 } |
176 } |
183 EdgeIt& first(EdgeIt& i) const { |
177 EdgeIt& first(EdgeIt& i) const { |
184 i=EdgeIt(*this); return i; |
178 i=EdgeIt(*this); return i; |
185 } |
179 } |
186 |
180 |
187 // NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; } |
|
188 // OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; } |
|
189 // InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; } |
|
190 // EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; } |
|
191 |
|
192 Node tail(const Edge& e) const { |
181 Node tail(const Edge& e) const { |
193 return Node(graph->tail(static_cast<typename Graph::Edge>(e))); } |
182 return Node(graph->tail(static_cast<typename Graph::Edge>(e))); } |
194 Node head(const Edge& e) const { |
183 Node head(const Edge& e) const { |
195 return Node(graph->head(static_cast<typename Graph::Edge>(e))); } |
184 return Node(graph->head(static_cast<typename Graph::Edge>(e))); } |
196 |
185 |
197 // bool valid(const Node& n) const { |
|
198 // return graph->valid(static_cast<typename Graph::Node>(n)); } |
|
199 // bool valid(const Edge& e) const { |
|
200 // return graph->valid(static_cast<typename Graph::Edge>(e)); } |
|
201 |
|
202 int nodeNum() const { return graph->nodeNum(); } |
186 int nodeNum() const { return graph->nodeNum(); } |
203 int edgeNum() const { return graph->edgeNum(); } |
187 int edgeNum() const { return graph->edgeNum(); } |
204 |
|
205 // Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); } |
|
206 // Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); } |
|
207 // Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); } |
|
208 // Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); } |
|
209 |
188 |
210 Node addNode() const { return Node(graph->addNode()); } |
189 Node addNode() const { return Node(graph->addNode()); } |
211 Edge addEdge(const Node& tail, const Node& head) const { |
190 Edge addEdge(const Node& tail, const Node& head) const { |
212 return Edge(graph->addEdge(tail, head)); } |
191 return Edge(graph->addEdge(tail, head)); } |
213 |
192 |
258 class OutEdgeIt : public Edge { |
237 class OutEdgeIt : public Edge { |
259 const RevGraphWrapper<Graph>* gw; |
238 const RevGraphWrapper<Graph>* gw; |
260 friend class GraphWrapper<Graph>; |
239 friend class GraphWrapper<Graph>; |
261 public: |
240 public: |
262 OutEdgeIt() { } |
241 OutEdgeIt() { } |
263 //OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { } |
|
264 OutEdgeIt(Invalid i) : Edge(i) { } |
242 OutEdgeIt(Invalid i) : Edge(i) { } |
265 OutEdgeIt(const RevGraphWrapper<Graph>& _gw, const Node& n) : |
243 OutEdgeIt(const RevGraphWrapper<Graph>& _gw, const Node& n) : |
266 Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { } |
244 Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { } |
267 OutEdgeIt(const RevGraphWrapper<Graph>& _gw, const Edge& e) : |
245 OutEdgeIt(const RevGraphWrapper<Graph>& _gw, const Edge& e) : |
268 Edge(e), gw(&_gw) { } |
246 Edge(e), gw(&_gw) { } |
275 class InEdgeIt : public Edge { |
253 class InEdgeIt : public Edge { |
276 const RevGraphWrapper<Graph>* gw; |
254 const RevGraphWrapper<Graph>* gw; |
277 friend class GraphWrapper<Graph>; |
255 friend class GraphWrapper<Graph>; |
278 public: |
256 public: |
279 InEdgeIt() { } |
257 InEdgeIt() { } |
280 //InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { } |
|
281 InEdgeIt(Invalid i) : Edge(i) { } |
258 InEdgeIt(Invalid i) : Edge(i) { } |
282 InEdgeIt(const RevGraphWrapper<Graph>& _gw, const Node& n) : |
259 InEdgeIt(const RevGraphWrapper<Graph>& _gw, const Node& n) : |
283 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { } |
260 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { } |
284 InEdgeIt(const RevGraphWrapper<Graph>& _gw, const Edge& e) : |
261 InEdgeIt(const RevGraphWrapper<Graph>& _gw, const Edge& e) : |
285 Edge(e), gw(&_gw) { } |
262 Edge(e), gw(&_gw) { } |
295 i=OutEdgeIt(*this, p); return i; |
272 i=OutEdgeIt(*this, p); return i; |
296 } |
273 } |
297 InEdgeIt& first(InEdgeIt& i, const Node& p) const { |
274 InEdgeIt& first(InEdgeIt& i, const Node& p) const { |
298 i=InEdgeIt(*this, p); return i; |
275 i=InEdgeIt(*this, p); return i; |
299 } |
276 } |
300 |
|
301 // using GraphWrapper<Graph>::next; |
|
302 // OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; } |
|
303 // InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; } |
|
304 |
|
305 // Node aNode(const OutEdgeIt& e) const { |
|
306 // return Node(this->graph->aNode(e.e)); } |
|
307 // Node aNode(const InEdgeIt& e) const { |
|
308 // return Node(this->graph->aNode(e.e)); } |
|
309 // Node bNode(const OutEdgeIt& e) const { |
|
310 // return Node(this->graph->bNode(e.e)); } |
|
311 // Node bNode(const InEdgeIt& e) const { |
|
312 // return Node(this->graph->bNode(e.e)); } |
|
313 |
277 |
314 Node tail(const Edge& e) const { |
278 Node tail(const Edge& e) const { |
315 return GraphWrapper<Graph>::head(e); } |
279 return GraphWrapper<Graph>::head(e); } |
316 Node head(const Edge& e) const { |
280 Node head(const Edge& e) const { |
317 return GraphWrapper<Graph>::tail(e); } |
281 return GraphWrapper<Graph>::tail(e); } |
361 class NodeIt : public Node { |
325 class NodeIt : public Node { |
362 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw; |
326 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw; |
363 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>; |
327 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>; |
364 public: |
328 public: |
365 NodeIt() { } |
329 NodeIt() { } |
366 // NodeIt(const NodeIt& n) : Node(n), gw(n.gw) { } |
|
367 NodeIt(Invalid i) : Node(i) { } |
330 NodeIt(Invalid i) : Node(i) { } |
368 NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) : |
331 NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) : |
369 Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) { |
332 Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) { |
370 while (*static_cast<Node*>(this)!=INVALID && |
333 while (*static_cast<Node*>(this)!=INVALID && |
371 !(*(gw->node_filter_map))[*this]) |
334 !(*(gw->node_filter_map))[*this]) |
389 class OutEdgeIt : public Edge { |
352 class OutEdgeIt : public Edge { |
390 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw; |
353 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw; |
391 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>; |
354 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>; |
392 public: |
355 public: |
393 OutEdgeIt() { } |
356 OutEdgeIt() { } |
394 // OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { } |
|
395 OutEdgeIt(Invalid i) : Edge(i) { } |
357 OutEdgeIt(Invalid i) : Edge(i) { } |
396 OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) : |
358 OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) : |
397 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { |
359 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { |
398 while (*static_cast<Edge*>(this)!=INVALID && |
360 while (*static_cast<Edge*>(this)!=INVALID && |
399 !(*(gw->edge_filter_map))[*this]) |
361 !(*(gw->edge_filter_map))[*this]) |
443 class EdgeIt : public Edge { |
405 class EdgeIt : public Edge { |
444 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw; |
406 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw; |
445 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>; |
407 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>; |
446 public: |
408 public: |
447 EdgeIt() { } |
409 EdgeIt() { } |
448 // EdgeIt(const EdgeIt& e) : Edge(e), gw(e.gw) { } |
|
449 EdgeIt(Invalid i) : Edge(i) { } |
410 EdgeIt(Invalid i) : Edge(i) { } |
450 EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) : |
411 EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) : |
451 Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { |
412 Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { |
452 while (*static_cast<Edge*>(this)!=INVALID && |
413 while (*static_cast<Edge*>(this)!=INVALID && |
453 !(*(gw->edge_filter_map))[*this]) |
414 !(*(gw->edge_filter_map))[*this]) |
479 } |
440 } |
480 EdgeIt& first(EdgeIt& i) const { |
441 EdgeIt& first(EdgeIt& i) const { |
481 i=EdgeIt(*this); return i; |
442 i=EdgeIt(*this); return i; |
482 } |
443 } |
483 |
444 |
484 // NodeIt& next(NodeIt& i) const { |
|
485 // this->graph->next(i.n); |
|
486 // while (this->graph->valid(i) && !(*node_filter_map)[i.n]) { |
|
487 // this->graph->next(i.n); } |
|
488 // return i; |
|
489 // } |
|
490 // OutEdgeIt& next(OutEdgeIt& i) const { |
|
491 // this->graph->next(i.e); |
|
492 // while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { |
|
493 // this->graph->next(i.e); } |
|
494 // return i; |
|
495 // } |
|
496 // InEdgeIt& next(InEdgeIt& i) const { |
|
497 // this->graph->next(i.e); |
|
498 // while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { |
|
499 // this->graph->next(i.e); } |
|
500 // return i; |
|
501 // } |
|
502 // EdgeIt& next(EdgeIt& i) const { |
|
503 // this->graph->next(i.e); |
|
504 // while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { |
|
505 // this->graph->next(i.e); } |
|
506 // return i; |
|
507 // } |
|
508 |
|
509 // Node aNode(const OutEdgeIt& e) const { |
|
510 // return Node(this->graph->aNode(e.e)); } |
|
511 // Node aNode(const InEdgeIt& e) const { |
|
512 // return Node(this->graph->aNode(e.e)); } |
|
513 // Node bNode(const OutEdgeIt& e) const { |
|
514 // return Node(this->graph->bNode(e.e)); } |
|
515 // Node bNode(const InEdgeIt& e) const { |
|
516 // return Node(this->graph->bNode(e.e)); } |
|
517 |
|
518 /// This function hides \c n in the graph, i.e. the iteration |
445 /// This function hides \c n in the graph, i.e. the iteration |
519 /// jumps over it. This is done by simply setting the value of \c n |
446 /// jumps over it. This is done by simply setting the value of \c n |
520 /// to be false in the corresponding node-map. |
447 /// to be false in the corresponding node-map. |
521 void hide(const Node& n) const { node_filter_map->set(n, false); } |
448 void hide(const Node& n) const { node_filter_map->set(n, false); } |
522 |
449 |
599 operator Edge() const { |
519 operator Edge() const { |
600 if (out_or_in) return Edge(out); else return Edge(in); |
520 if (out_or_in) return Edge(out); else return Edge(in); |
601 } |
521 } |
602 }; |
522 }; |
603 |
523 |
604 //FIXME InEdgeIt |
|
605 typedef OutEdgeIt InEdgeIt; |
524 typedef OutEdgeIt InEdgeIt; |
606 |
525 |
607 using GraphWrapper<Graph>::first; |
526 using GraphWrapper<Graph>::first; |
608 // NodeIt& first(NodeIt& i) const { |
|
609 // i=NodeIt(*this); return i; |
|
610 // } |
|
611 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { |
527 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { |
612 i=OutEdgeIt(*this, p); return i; |
528 i=OutEdgeIt(*this, p); return i; |
613 } |
529 } |
614 //FIXME |
|
615 // InEdgeIt& first(InEdgeIt& i, const Node& p) const { |
|
616 // i=InEdgeIt(*this, p); return i; |
|
617 // } |
|
618 // EdgeIt& first(EdgeIt& i) const { |
|
619 // i=EdgeIt(*this); return i; |
|
620 // } |
|
621 |
530 |
622 using GraphWrapper<Graph>::next; |
531 using GraphWrapper<Graph>::next; |
623 // NodeIt& next(NodeIt& n) const { |
532 |
624 // GraphWrapper<Graph>::next(n); |
|
625 // return n; |
|
626 // } |
|
627 OutEdgeIt& next(OutEdgeIt& e) const { |
533 OutEdgeIt& next(OutEdgeIt& e) const { |
628 if (e.out_or_in) { |
534 if (e.out_or_in) { |
629 typename Graph::Node n=this->graph->tail(e.out); |
535 typename Graph::Node n=this->graph->tail(e.out); |
630 this->graph->next(e.out); |
536 this->graph->next(e.out); |
631 if (!this->graph->valid(e.out)) { |
537 if (!this->graph->valid(e.out)) { |
754 /// If \c _backward is false, then we get an edge corresponding to the |
654 /// If \c _backward is false, then we get an edge corresponding to the |
755 /// original one, otherwise its oppositely directed pair is obtained. |
655 /// original one, otherwise its oppositely directed pair is obtained. |
756 Edge(const typename Graph::Edge& e, bool _backward/*=false*/) : |
656 Edge(const typename Graph::Edge& e, bool _backward/*=false*/) : |
757 Graph::Edge(e), backward(_backward) { } |
657 Graph::Edge(e), backward(_backward) { } |
758 Edge(Invalid i) : Graph::Edge(i), backward(true) { } |
658 Edge(Invalid i) : Graph::Edge(i), backward(true) { } |
759 //the unique invalid iterator |
|
760 // friend bool operator==(const Edge& u, const Edge& v) { |
|
761 // return (u.backward==v.backward && |
|
762 // static_cast<typename Graph::Edge>(u)== |
|
763 // static_cast<typename Graph::Edge>(v)); |
|
764 // } |
|
765 // friend bool operator!=(const Edge& u, const Edge& v) { |
|
766 // return (u.backward!=v.backward || |
|
767 // static_cast<typename Graph::Edge>(u)!= |
|
768 // static_cast<typename Graph::Edge>(v)); |
|
769 // } |
|
770 bool operator==(const Edge& v) const { |
659 bool operator==(const Edge& v) const { |
771 return (this->backward==v.backward && |
660 return (this->backward==v.backward && |
772 static_cast<typename Graph::Edge>(*this)== |
661 static_cast<typename Graph::Edge>(*this)== |
773 static_cast<typename Graph::Edge>(v)); |
662 static_cast<typename Graph::Edge>(v)); |
774 } |
663 } |
786 const SubBidirGraphWrapper<Graph, |
675 const SubBidirGraphWrapper<Graph, |
787 ForwardFilterMap, BackwardFilterMap>* gw; |
676 ForwardFilterMap, BackwardFilterMap>* gw; |
788 public: |
677 public: |
789 OutEdgeIt() { } |
678 OutEdgeIt() { } |
790 OutEdgeIt(Invalid i) : Edge(i) { } |
679 OutEdgeIt(Invalid i) : Edge(i) { } |
791 //the unique invalid iterator |
|
792 OutEdgeIt(const SubBidirGraphWrapper<Graph, |
680 OutEdgeIt(const SubBidirGraphWrapper<Graph, |
793 ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) : |
681 ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) : |
794 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), false), gw(&_gw) { |
682 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), false), gw(&_gw) { |
795 while (*static_cast<GraphEdge*>(this)!=INVALID && |
683 while (*static_cast<GraphEdge*>(this)!=INVALID && |
796 !(*(gw->forward_filter))[*this]) |
684 !(*(gw->forward_filter))[*this]) |
844 const SubBidirGraphWrapper<Graph, |
732 const SubBidirGraphWrapper<Graph, |
845 ForwardFilterMap, BackwardFilterMap>* gw; |
733 ForwardFilterMap, BackwardFilterMap>* gw; |
846 public: |
734 public: |
847 InEdgeIt() { } |
735 InEdgeIt() { } |
848 InEdgeIt(Invalid i) : Edge(i) { } |
736 InEdgeIt(Invalid i) : Edge(i) { } |
849 //the unique invalid iterator |
|
850 InEdgeIt(const SubBidirGraphWrapper<Graph, |
737 InEdgeIt(const SubBidirGraphWrapper<Graph, |
851 ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) : |
738 ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) : |
852 Edge(typename Graph::InEdgeIt(*(_gw.graph), n), false), gw(&_gw) { |
739 Edge(typename Graph::InEdgeIt(*(_gw.graph), n), false), gw(&_gw) { |
853 while (*static_cast<GraphEdge*>(this)!=INVALID && |
740 while (*static_cast<GraphEdge*>(this)!=INVALID && |
854 !(*(gw->forward_filter))[*this]) |
741 !(*(gw->forward_filter))[*this]) |
902 const SubBidirGraphWrapper<Graph, |
789 const SubBidirGraphWrapper<Graph, |
903 ForwardFilterMap, BackwardFilterMap>* gw; |
790 ForwardFilterMap, BackwardFilterMap>* gw; |
904 public: |
791 public: |
905 EdgeIt() { } |
792 EdgeIt() { } |
906 EdgeIt(Invalid i) : Edge(i) { } |
793 EdgeIt(Invalid i) : Edge(i) { } |
907 //the unique invalid iterator |
|
908 EdgeIt(const SubBidirGraphWrapper<Graph, |
794 EdgeIt(const SubBidirGraphWrapper<Graph, |
909 ForwardFilterMap, BackwardFilterMap>& _gw) : |
795 ForwardFilterMap, BackwardFilterMap>& _gw) : |
910 Edge(typename Graph::OutEdgeIt(*(_gw.graph)), false), gw(&_gw) { |
796 Edge(typename Graph::OutEdgeIt(*(_gw.graph)), false), gw(&_gw) { |
911 while (*static_cast<GraphEdge*>(this)!=INVALID && |
797 while (*static_cast<GraphEdge*>(this)!=INVALID && |
912 !(*(gw->forward_filter))[*this]) |
798 !(*(gw->forward_filter))[*this]) |
951 return *this; |
837 return *this; |
952 } |
838 } |
953 }; |
839 }; |
954 |
840 |
955 using GraphWrapper<Graph>::first; |
841 using GraphWrapper<Graph>::first; |
956 // NodeIt& first(NodeIt& i) const { |
|
957 // i=NodeIt(*this); return i; |
|
958 // } |
|
959 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { |
842 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { |
960 i=OutEdgeIt(*this, p); return i; |
843 i=OutEdgeIt(*this, p); return i; |
961 } |
844 } |
962 InEdgeIt& first(InEdgeIt& i, const Node& p) const { |
845 InEdgeIt& first(InEdgeIt& i, const Node& p) const { |
963 i=InEdgeIt(*this, p); return i; |
846 i=InEdgeIt(*this, p); return i; |
964 } |
847 } |
965 EdgeIt& first(EdgeIt& i) const { |
848 EdgeIt& first(EdgeIt& i) const { |
966 i=EdgeIt(*this); return i; |
849 i=EdgeIt(*this); return i; |
967 } |
850 } |
968 |
851 |
969 // using GraphWrapper<Graph>::next; |
|
970 // // NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; } |
|
971 // OutEdgeIt& next(OutEdgeIt& e) const { |
|
972 // if (!e.backward) { |
|
973 // Node v=this->graph->aNode(e.out); |
|
974 // this->graph->next(e.out); |
|
975 // while(this->graph->valid(e.out) && !(*forward_filter)[e]) { |
|
976 // this->graph->next(e.out); } |
|
977 // if (!this->graph->valid(e.out)) { |
|
978 // e.backward=true; |
|
979 // this->graph->first(e.in, v); |
|
980 // while(this->graph->valid(e.in) && !(*backward_filter)[e]) { |
|
981 // this->graph->next(e.in); } |
|
982 // } |
|
983 // } else { |
|
984 // this->graph->next(e.in); |
|
985 // while(this->graph->valid(e.in) && !(*backward_filter)[e]) { |
|
986 // this->graph->next(e.in); } |
|
987 // } |
|
988 // return e; |
|
989 // } |
|
990 // // FIXME Not tested |
|
991 // InEdgeIt& next(InEdgeIt& e) const { |
|
992 // if (!e.backward) { |
|
993 // Node v=this->graph->aNode(e.in); |
|
994 // this->graph->next(e.in); |
|
995 // while(this->graph->valid(e.in) && !(*forward_filter)[e]) { |
|
996 // this->graph->next(e.in); } |
|
997 // if (!this->graph->valid(e.in)) { |
|
998 // e.backward=true; |
|
999 // this->graph->first(e.out, v); |
|
1000 // while(this->graph->valid(e.out) && !(*backward_filter)[e]) { |
|
1001 // this->graph->next(e.out); } |
|
1002 // } |
|
1003 // } else { |
|
1004 // this->graph->next(e.out); |
|
1005 // while(this->graph->valid(e.out) && !(*backward_filter)[e]) { |
|
1006 // this->graph->next(e.out); } |
|
1007 // } |
|
1008 // return e; |
|
1009 // } |
|
1010 // EdgeIt& next(EdgeIt& e) const { |
|
1011 // if (!e.backward) { |
|
1012 // this->graph->next(e.e); |
|
1013 // while(this->graph->valid(e.e) && !(*forward_filter)[e]) { |
|
1014 // this->graph->next(e.e); } |
|
1015 // if (!this->graph->valid(e.e)) { |
|
1016 // e.backward=true; |
|
1017 // this->graph->first(e.e); |
|
1018 // while(this->graph->valid(e.e) && !(*backward_filter)[e]) { |
|
1019 // this->graph->next(e.e); } |
|
1020 // } |
|
1021 // } else { |
|
1022 // this->graph->next(e.e); |
|
1023 // while(this->graph->valid(e.e) && !(*backward_filter)[e]) { |
|
1024 // this->graph->next(e.e); } |
|
1025 // } |
|
1026 // return e; |
|
1027 // } |
|
1028 |
852 |
1029 Node tail(Edge e) const { |
853 Node tail(Edge e) const { |
1030 return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); } |
854 return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); } |
1031 Node head(Edge e) const { |
855 Node head(Edge e) const { |
1032 return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); } |
856 return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); } |
1033 |
|
1034 // Node aNode(OutEdgeIt e) const { |
|
1035 // return ((!e.backward) ? this->graph->aNode(e.out) : |
|
1036 // this->graph->aNode(e.in)); } |
|
1037 // Node bNode(OutEdgeIt e) const { |
|
1038 // return ((!e.backward) ? this->graph->bNode(e.out) : |
|
1039 // this->graph->bNode(e.in)); } |
|
1040 |
|
1041 // Node aNode(InEdgeIt e) const { |
|
1042 // return ((!e.backward) ? this->graph->aNode(e.in) : |
|
1043 // this->graph->aNode(e.out)); } |
|
1044 // Node bNode(InEdgeIt e) const { |
|
1045 // return ((!e.backward) ? this->graph->bNode(e.in) : |
|
1046 // this->graph->bNode(e.out)); } |
|
1047 |
857 |
1048 /// Gives back the opposite edge. |
858 /// Gives back the opposite edge. |
1049 Edge opposite(const Edge& e) const { |
859 Edge opposite(const Edge& e) const { |
1050 Edge f=e; |
860 Edge f=e; |
1051 f.backward=!f.backward; |
861 f.backward=!f.backward; |
1180 public: |
984 public: |
1181 ResForwardFilter(/*const Graph& _graph, */ |
985 ResForwardFilter(/*const Graph& _graph, */ |
1182 const CapacityMap& _capacity, const FlowMap& _flow) : |
986 const CapacityMap& _capacity, const FlowMap& _flow) : |
1183 /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { } |
987 /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { } |
1184 ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { } |
988 ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { } |
1185 //void setGraph(const Graph& _graph) { graph=&_graph; } |
|
1186 void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; } |
989 void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; } |
1187 void setFlow(const FlowMap& _flow) { flow=&_flow; } |
990 void setFlow(const FlowMap& _flow) { flow=&_flow; } |
1188 bool operator[](const typename Graph::Edge& e) const { |
991 bool operator[](const typename Graph::Edge& e) const { |
1189 return (Number((*flow)[e]) < Number((*capacity)[e])); |
992 return (Number((*flow)[e]) < Number((*capacity)[e])); |
1190 } |
993 } |
1191 }; |
994 }; |
1192 |
995 |
1193 template<typename Graph, typename Number, |
996 template<typename Graph, typename Number, |
1194 typename CapacityMap, typename FlowMap> |
997 typename CapacityMap, typename FlowMap> |
1195 class ResBackwardFilter { |
998 class ResBackwardFilter { |
1196 //const Graph* graph; |
|
1197 const CapacityMap* capacity; |
999 const CapacityMap* capacity; |
1198 const FlowMap* flow; |
1000 const FlowMap* flow; |
1199 public: |
1001 public: |
1200 ResBackwardFilter(/*const Graph& _graph,*/ |
1002 ResBackwardFilter(/*const Graph& _graph,*/ |
1201 const CapacityMap& _capacity, const FlowMap& _flow) : |
1003 const CapacityMap& _capacity, const FlowMap& _flow) : |
1202 /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { } |
1004 /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { } |
1203 ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { } |
1005 ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { } |
1204 //void setGraph(const Graph& _graph) { graph=&_graph; } |
|
1205 void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; } |
1006 void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; } |
1206 void setFlow(const FlowMap& _flow) { flow=&_flow; } |
1007 void setFlow(const FlowMap& _flow) { flow=&_flow; } |
1207 bool operator[](const typename Graph::Edge& e) const { |
1008 bool operator[](const typename Graph::Edge& e) const { |
1208 return (Number(0) < Number((*flow)[e])); |
1009 return (Number(0) < Number((*flow)[e])); |
1209 } |
1010 } |
1240 void setFlowMap(FlowMap& _flow) { |
1041 void setFlowMap(FlowMap& _flow) { |
1241 flow=&_flow; |
1042 flow=&_flow; |
1242 forward_filter.setFlow(_flow); |
1043 forward_filter.setFlow(_flow); |
1243 backward_filter.setFlow(_flow); |
1044 backward_filter.setFlow(_flow); |
1244 } |
1045 } |
1245 // /// \bug does graph reference needed in filtermaps?? |
|
1246 // void setGraph(const Graph& _graph) { |
|
1247 // Parent::setGraph(_graph); |
|
1248 // forward_filter.setGraph(_graph); |
|
1249 // backward_filter.setGraph(_graph); |
|
1250 // } |
|
1251 public: |
1046 public: |
1252 ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, |
1047 ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, |
1253 FlowMap& _flow) : |
1048 FlowMap& _flow) : |
1254 Parent(), capacity(&_capacity), flow(&_flow), |
1049 Parent(), capacity(&_capacity), flow(&_flow), |
1255 forward_filter(/*_graph,*/ _capacity, _flow), |
1050 forward_filter(/*_graph,*/ _capacity, _flow), |
1259 Parent::setBackwardFilterMap(backward_filter); |
1054 Parent::setBackwardFilterMap(backward_filter); |
1260 } |
1055 } |
1261 |
1056 |
1262 typedef typename Parent::Edge Edge; |
1057 typedef typename Parent::Edge Edge; |
1263 |
1058 |
1264 // bool forward(const Parent::Edge& e) const { return Parent::forward(e); } |
|
1265 //bool backward(const Edge& e) const { return e.backward; } |
|
1266 |
|
1267 void augment(const Edge& e, Number a) const { |
1059 void augment(const Edge& e, Number a) const { |
1268 if (Parent::forward(e)) |
1060 if (Parent::forward(e)) |
1269 // flow->set(e.out, flow->get(e.out)+a); |
|
1270 flow->set(e, (*flow)[e]+a); |
1061 flow->set(e, (*flow)[e]+a); |
1271 else |
1062 else |
1272 //flow->set(e.in, flow->get(e.in)-a); |
|
1273 flow->set(e, (*flow)[e]-a); |
1063 flow->set(e, (*flow)[e]-a); |
1274 } |
|
1275 |
|
1276 /// \deprecated |
|
1277 /// |
|
1278 Number resCap(const Edge& e) const { |
|
1279 if (Parent::forward(e)) |
|
1280 // return (capacity->get(e.out)-flow->get(e.out)); |
|
1281 return ((*capacity)[e]-(*flow)[e]); |
|
1282 else |
|
1283 // return (flow->get(e.in)); |
|
1284 return ((*flow)[e]); |
|
1285 } |
1064 } |
1286 |
1065 |
1287 /// \brief Residual capacity map. |
1066 /// \brief Residual capacity map. |
1288 /// |
1067 /// |
1289 /// In generic residual graphs the residual capacity can be obtained as a map. Not tested. |
1068 /// In generic residual graphs the residual capacity can be obtained as a map. Not tested. |
1295 typedef Edge KeyType; |
1074 typedef Edge KeyType; |
1296 ResCap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _res_graph) : |
1075 ResCap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _res_graph) : |
1297 res_graph(&_res_graph) { } |
1076 res_graph(&_res_graph) { } |
1298 Number operator[](const Edge& e) const { |
1077 Number operator[](const Edge& e) const { |
1299 if (res_graph->forward(e)) |
1078 if (res_graph->forward(e)) |
1300 // return (capacity->get(e.out)-flow->get(e.out)); |
|
1301 return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e]; |
1079 return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e]; |
1302 else |
1080 else |
1303 // return (flow->get(e.in)); |
|
1304 return (*(res_graph->flow))[e]; |
1081 return (*(res_graph->flow))[e]; |
1305 } |
1082 } |
1306 /// \bug not needed with dynamic maps, or does it? |
|
1307 void update() { } |
|
1308 }; |
1083 }; |
1309 |
1084 |
1310 KEEP_MAPS(Parent, ResGraphWrapper); |
1085 KEEP_MAPS(Parent, ResGraphWrapper); |
1311 }; |
1086 }; |
1312 |
1087 |
1339 friend class GraphWrapper<Graph>; |
1114 friend class GraphWrapper<Graph>; |
1340 friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>; |
1115 friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>; |
1341 const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>* gw; |
1116 const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>* gw; |
1342 public: |
1117 public: |
1343 OutEdgeIt() { } |
1118 OutEdgeIt() { } |
1344 //OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { } |
|
1345 OutEdgeIt(Invalid i) : Edge(i) { } |
1119 OutEdgeIt(Invalid i) : Edge(i) { } |
1346 OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _gw, |
1120 OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _gw, |
1347 const Node& n) : |
1121 const Node& n) : |
1348 Edge((*(_gw.first_out_edges))[n]), gw(&_gw) { } |
1122 Edge((*(_gw.first_out_edges))[n]), gw(&_gw) { } |
1349 OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _gw, |
1123 OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _gw, |
1353 *(static_cast<Edge*>(this))= |
1127 *(static_cast<Edge*>(this))= |
1354 ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); |
1128 ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); |
1355 return *this; |
1129 return *this; |
1356 } |
1130 } |
1357 }; |
1131 }; |
1358 // class InEdgeIt { |
|
1359 // friend class GraphWrapper<Graph>; |
|
1360 // friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>; |
|
1361 // // typedef typename Graph::InEdgeIt GraphInEdgeIt; |
|
1362 // typename Graph::InEdgeIt e; |
|
1363 // public: |
|
1364 // InEdgeIt() { } |
|
1365 // InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { } |
|
1366 // InEdgeIt(const Invalid& i) : e(i) { } |
|
1367 // InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G, |
|
1368 // const Node& _n) : |
|
1369 // e(*(_G.graph), typename Graph::Node(_n)) { } |
|
1370 // operator Edge() const { return Edge(typename Graph::Edge(e)); } |
|
1371 // }; |
|
1372 //typedef typename Graph::SymEdgeIt SymEdgeIt; |
|
1373 // class EdgeIt { |
|
1374 // friend class GraphWrapper<Graph>; |
|
1375 // friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>; |
|
1376 // // typedef typename Graph::EdgeIt GraphEdgeIt; |
|
1377 // typename Graph::EdgeIt e; |
|
1378 // public: |
|
1379 // EdgeIt() { } |
|
1380 // EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { } |
|
1381 // EdgeIt(const Invalid& i) : e(i) { } |
|
1382 // EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) : |
|
1383 // e(*(_G.graph)) { } |
|
1384 // operator Edge() const { return Edge(typename Graph::Edge(e)); } |
|
1385 // }; |
|
1386 |
1132 |
1387 using GraphWrapper<Graph>::first; |
1133 using GraphWrapper<Graph>::first; |
1388 // NodeIt& first(NodeIt& i) const { |
|
1389 // i=NodeIt(*this); return i; |
|
1390 // } |
|
1391 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { |
1134 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { |
1392 i=OutEdgeIt(*this, p); return i; |
1135 i=OutEdgeIt(*this, p); return i; |
1393 } |
1136 } |
1394 // InEdgeIt& first(InEdgeIt& i, const Node& p) const { |
|
1395 // i=InEdgeIt(*this, p); return i; |
|
1396 // } |
|
1397 // EdgeIt& first(EdgeIt& i) const { |
|
1398 // i=EdgeIt(*this); return i; |
|
1399 // } |
|
1400 |
|
1401 // using GraphWrapper<Graph>::next; |
|
1402 // // NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; } |
|
1403 // OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; } |
|
1404 // InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; } |
|
1405 // EdgeIt& next(EdgeIt& i) const { this->graph->next(i.e); return i; } |
|
1406 |
|
1407 // Node aNode(const OutEdgeIt& e) const { |
|
1408 // return Node(this->graph->aNode(e.e)); } |
|
1409 // Node aNode(const InEdgeIt& e) const { |
|
1410 // return Node(this->graph->aNode(e.e)); } |
|
1411 // Node bNode(const OutEdgeIt& e) const { |
|
1412 // return Node(this->graph->bNode(e.e)); } |
|
1413 // Node bNode(const InEdgeIt& e) const { |
|
1414 // return Node(this->graph->bNode(e.e)); } |
|
1415 |
|
1416 void erase(const Edge& e) const { |
1137 void erase(const Edge& e) const { |
1417 Node n=tail(e); |
1138 Node n=tail(e); |
1418 typename Graph::OutEdgeIt f(*Parent::graph, n); |
1139 typename Graph::OutEdgeIt f(*Parent::graph, n); |
1419 ++f; |
1140 ++f; |
1420 first_out_edges->set(n, f); |
1141 first_out_edges->set(n, f); |