Forgotten functions in the graph adaptor extenders.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
19 #ifndef LEMON_BITS_GRAPH_ADAPTOR_EXTENDER_H
20 #define LEMON_BITS_GRAPH_ADAPTOR_EXTENDER_H
22 #include <lemon/bits/invalid.h>
23 #include <lemon/error.h>
25 #include <lemon/bits/default_map.h>
30 ///\brief Extenders for the graph adaptor types
33 /// \ingroup graphbits
35 /// \brief Extender for the GraphAdaptors
36 template <typename _Graph>
37 class GraphAdaptorExtender : public _Graph {
40 typedef _Graph Parent;
42 typedef GraphAdaptorExtender Adaptor;
46 typedef typename Parent::Node Node;
47 typedef typename Parent::Edge Edge;
49 int maxId(Node) const {
50 return Parent::maxNodeId();
53 int maxId(Edge) const {
54 return Parent::maxEdgeId();
57 Node fromId(int id, Node) const {
58 return Parent::nodeFromId(id);
61 Edge fromId(int id, Edge) const {
62 return Parent::edgeFromId(id);
65 Node oppositeNode(const Node &n, const Edge &e) const {
66 if (n == Parent::source(e))
67 return Parent::target(e);
68 else if(n==Parent::target(e))
69 return Parent::source(e);
74 class NodeIt : public Node {
80 NodeIt(Invalid i) : Node(i) { }
82 explicit NodeIt(const Adaptor& _graph) : graph(&_graph) {
83 _graph.first(static_cast<Node&>(*this));
86 NodeIt(const Adaptor& _graph, const Node& node)
87 : Node(node), graph(&_graph) {}
89 NodeIt& operator++() {
97 class EdgeIt : public Edge {
103 EdgeIt(Invalid i) : Edge(i) { }
105 explicit EdgeIt(const Adaptor& _graph) : graph(&_graph) {
106 _graph.first(static_cast<Edge&>(*this));
109 EdgeIt(const Adaptor& _graph, const Edge& e) :
110 Edge(e), graph(&_graph) { }
112 EdgeIt& operator++() {
120 class OutEdgeIt : public Edge {
121 const Adaptor* graph;
126 OutEdgeIt(Invalid i) : Edge(i) { }
128 OutEdgeIt(const Adaptor& _graph, const Node& node)
130 _graph.firstOut(*this, node);
133 OutEdgeIt(const Adaptor& _graph, const Edge& edge)
134 : Edge(edge), graph(&_graph) {}
136 OutEdgeIt& operator++() {
137 graph->nextOut(*this);
144 class InEdgeIt : public Edge {
145 const Adaptor* graph;
150 InEdgeIt(Invalid i) : Edge(i) { }
152 InEdgeIt(const Adaptor& _graph, const Node& node)
154 _graph.firstIn(*this, node);
157 InEdgeIt(const Adaptor& _graph, const Edge& edge) :
158 Edge(edge), graph(&_graph) {}
160 InEdgeIt& operator++() {
161 graph->nextIn(*this);
167 /// \brief Base node of the iterator
169 /// Returns the base node (ie. the source in this case) of the iterator
170 Node baseNode(const OutEdgeIt &e) const {
171 return Parent::source(e);
173 /// \brief Running node of the iterator
175 /// Returns the running node (ie. the target in this case) of the
177 Node runningNode(const OutEdgeIt &e) const {
178 return Parent::target(e);
181 /// \brief Base node of the iterator
183 /// Returns the base node (ie. the target in this case) of the iterator
184 Node baseNode(const InEdgeIt &e) const {
185 return Parent::target(e);
187 /// \brief Running node of the iterator
189 /// Returns the running node (ie. the source in this case) of the
191 Node runningNode(const InEdgeIt &e) const {
192 return Parent::source(e);
198 /// \ingroup graphbits
200 /// \brief Extender for the UGraphAdaptors
201 template <typename _UGraph>
202 class UGraphAdaptorExtender : public _UGraph {
205 typedef _UGraph Parent;
206 typedef _UGraph UGraph;
207 typedef UGraphAdaptorExtender Adaptor;
209 typedef typename Parent::Node Node;
210 typedef typename Parent::Edge Edge;
211 typedef typename Parent::UEdge UEdge;
215 int maxId(Node) const {
216 return Parent::maxNodeId();
219 int maxId(Edge) const {
220 return Parent::maxEdgeId();
223 int maxId(UEdge) const {
224 return Parent::maxUEdgeId();
227 Node fromId(int id, Node) const {
228 return Parent::nodeFromId(id);
231 Edge fromId(int id, Edge) const {
232 return Parent::edgeFromId(id);
235 UEdge fromId(int id, UEdge) const {
236 return Parent::uEdgeFromId(id);
239 Node oppositeNode(const Node &n, const UEdge &e) const {
240 if( n == Parent::source(e))
241 return Parent::target(e);
242 else if( n == Parent::target(e))
243 return Parent::source(e);
248 Edge oppositeEdge(const Edge &e) const {
249 return Parent::direct(e, !Parent::direction(e));
252 using Parent::direct;
253 Edge direct(const UEdge &ue, const Node &s) const {
254 return Parent::direct(ue, Parent::source(ue) == s);
258 class NodeIt : public Node {
259 const Adaptor* graph;
264 NodeIt(Invalid i) : Node(i) { }
266 explicit NodeIt(const Adaptor& _graph) : graph(&_graph) {
267 _graph.first(static_cast<Node&>(*this));
270 NodeIt(const Adaptor& _graph, const Node& node)
271 : Node(node), graph(&_graph) {}
273 NodeIt& operator++() {
281 class EdgeIt : public Edge {
282 const Adaptor* graph;
287 EdgeIt(Invalid i) : Edge(i) { }
289 explicit EdgeIt(const Adaptor& _graph) : graph(&_graph) {
290 _graph.first(static_cast<Edge&>(*this));
293 EdgeIt(const Adaptor& _graph, const Edge& e) :
294 Edge(e), graph(&_graph) { }
296 EdgeIt& operator++() {
304 class OutEdgeIt : public Edge {
305 const Adaptor* graph;
310 OutEdgeIt(Invalid i) : Edge(i) { }
312 OutEdgeIt(const Adaptor& _graph, const Node& node)
314 _graph.firstOut(*this, node);
317 OutEdgeIt(const Adaptor& _graph, const Edge& edge)
318 : Edge(edge), graph(&_graph) {}
320 OutEdgeIt& operator++() {
321 graph->nextOut(*this);
328 class InEdgeIt : public Edge {
329 const Adaptor* graph;
334 InEdgeIt(Invalid i) : Edge(i) { }
336 InEdgeIt(const Adaptor& _graph, const Node& node)
338 _graph.firstIn(*this, node);
341 InEdgeIt(const Adaptor& _graph, const Edge& edge) :
342 Edge(edge), graph(&_graph) {}
344 InEdgeIt& operator++() {
345 graph->nextIn(*this);
351 class UEdgeIt : public Parent::UEdge {
352 const Adaptor* graph;
357 UEdgeIt(Invalid i) : UEdge(i) { }
359 explicit UEdgeIt(const Adaptor& _graph) : graph(&_graph) {
360 _graph.first(static_cast<UEdge&>(*this));
363 UEdgeIt(const Adaptor& _graph, const UEdge& e) :
364 UEdge(e), graph(&_graph) { }
366 UEdgeIt& operator++() {
373 class IncEdgeIt : public Parent::UEdge {
374 friend class UGraphAdaptorExtender;
375 const Adaptor* graph;
381 IncEdgeIt(Invalid i) : UEdge(i), direction(false) { }
383 IncEdgeIt(const Adaptor& _graph, const Node &n) : graph(&_graph) {
384 _graph.firstInc(static_cast<UEdge&>(*this), direction, n);
387 IncEdgeIt(const Adaptor& _graph, const UEdge &ue, const Node &n)
388 : graph(&_graph), UEdge(ue) {
389 direction = (_graph.source(ue) == n);
392 IncEdgeIt& operator++() {
393 graph->nextInc(*this, direction);
398 /// \brief Base node of the iterator
400 /// Returns the base node (ie. the source in this case) of the iterator
401 Node baseNode(const OutEdgeIt &e) const {
402 return Parent::source((Edge)e);
404 /// \brief Running node of the iterator
406 /// Returns the running node (ie. the target in this case) of the
408 Node runningNode(const OutEdgeIt &e) const {
409 return Parent::target((Edge)e);
412 /// \brief Base node of the iterator
414 /// Returns the base node (ie. the target in this case) of the iterator
415 Node baseNode(const InEdgeIt &e) const {
416 return Parent::target((Edge)e);
418 /// \brief Running node of the iterator
420 /// Returns the running node (ie. the source in this case) of the
422 Node runningNode(const InEdgeIt &e) const {
423 return Parent::source((Edge)e);
426 /// Base node of the iterator
428 /// Returns the base node of the iterator
429 Node baseNode(const IncEdgeIt &e) const {
430 return e.direction ? source(e) : target(e);
432 /// Running node of the iterator
434 /// Returns the running node of the iterator
435 Node runningNode(const IncEdgeIt &e) const {
436 return e.direction ? target(e) : source(e);
441 /// \ingroup graphbits
443 /// \brief Extender for the BpUGraphAdaptors
444 template <typename Base>
445 class BpUGraphAdaptorExtender : public Base {
448 typedef BpUGraphAdaptorExtender Graph;
450 typedef typename Parent::Node Node;
451 typedef typename Parent::BNode BNode;
452 typedef typename Parent::ANode ANode;
453 typedef typename Parent::Edge Edge;
454 typedef typename Parent::UEdge UEdge;
456 Node oppositeNode(const UEdge& edge, const Node& node) const {
457 return source(edge) == node ?
458 target(edge) : source(edge);
462 int maxId(Node) const {
463 return Parent::maxNodeId();
465 int maxId(BNode) const {
466 return Parent::maxBNodeId();
468 int maxId(ANode) const {
469 return Parent::maxANodeId();
471 int maxId(Edge) const {
472 return Parent::maxEdgeId();
474 int maxId(UEdge) const {
475 return Parent::maxUEdgeId();
479 Node fromId(int id, Node) const {
480 return Parent::nodeFromId(id);
482 ANode fromId(int id, ANode) const {
483 return Parent::fromANodeId(id);
485 BNode fromId(int id, BNode) const {
486 return Parent::fromBNodeId(id);
488 Edge fromId(int id, Edge) const {
489 return Parent::edgeFromId(id);
491 UEdge fromId(int id, UEdge) const {
492 return Parent::uEdgeFromId(id);
495 class NodeIt : public Node {
501 NodeIt(Invalid i) : Node(INVALID) { }
503 explicit NodeIt(const Graph& _graph) : graph(&_graph) {
504 graph->first(static_cast<Node&>(*this));
507 NodeIt(const Graph& _graph, const Node& node)
508 : Node(node), graph(&_graph) { }
510 NodeIt& operator++() {
517 class ANodeIt : public Node {
518 friend class BpUGraphAdaptorExtender;
524 ANodeIt(Invalid i) : Node(INVALID) { }
526 explicit ANodeIt(const Graph& _graph) : graph(&_graph) {
527 graph->firstANode(static_cast<Node&>(*this));
530 ANodeIt(const Graph& _graph, const Node& node)
531 : Node(node), graph(&_graph) {}
533 ANodeIt& operator++() {
534 graph->nextANode(*this);
539 class BNodeIt : public Node {
540 friend class BpUGraphAdaptorExtender;
546 BNodeIt(Invalid i) : Node(INVALID) { }
548 explicit BNodeIt(const Graph& _graph) : graph(&_graph) {
549 graph->firstBNode(static_cast<Node&>(*this));
552 BNodeIt(const Graph& _graph, const Node& node)
553 : Node(node), graph(&_graph) {}
555 BNodeIt& operator++() {
556 graph->nextBNode(*this);
561 class EdgeIt : public Edge {
562 friend class BpUGraphAdaptorExtender;
568 EdgeIt(Invalid i) : Edge(INVALID) { }
570 explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
571 graph->first(static_cast<Edge&>(*this));
574 EdgeIt(const Graph& _graph, const Edge& edge)
575 : Edge(edge), graph(&_graph) { }
577 EdgeIt& operator++() {
584 class UEdgeIt : public UEdge {
585 friend class BpUGraphAdaptorExtender;
591 UEdgeIt(Invalid i) : UEdge(INVALID) { }
593 explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
594 graph->first(static_cast<UEdge&>(*this));
597 UEdgeIt(const Graph& _graph, const UEdge& edge)
598 : UEdge(edge), graph(&_graph) { }
600 UEdgeIt& operator++() {
606 class OutEdgeIt : public Edge {
607 friend class BpUGraphAdaptorExtender;
613 OutEdgeIt(Invalid i) : Edge(i) { }
615 OutEdgeIt(const Graph& _graph, const Node& node)
617 graph->firstOut(*this, node);
620 OutEdgeIt(const Graph& _graph, const Edge& edge)
621 : Edge(edge), graph(&_graph) {}
623 OutEdgeIt& operator++() {
624 graph->nextOut(*this);
631 class InEdgeIt : public Edge {
632 friend class BpUGraphAdaptorExtender;
638 InEdgeIt(Invalid i) : Edge(i) { }
640 InEdgeIt(const Graph& _graph, const Node& node)
642 graph->firstIn(*this, node);
645 InEdgeIt(const Graph& _graph, const Edge& edge) :
646 Edge(edge), graph(&_graph) {}
648 InEdgeIt& operator++() {
649 graph->nextIn(*this);
655 /// \brief Base node of the iterator
657 /// Returns the base node (ie. the source in this case) of the iterator
658 Node baseNode(const OutEdgeIt &e) const {
659 return Parent::source((Edge&)e);
661 /// \brief Running node of the iterator
663 /// Returns the running node (ie. the target in this case) of the
665 Node runningNode(const OutEdgeIt &e) const {
666 return Parent::target((Edge&)e);
669 /// \brief Base node of the iterator
671 /// Returns the base node (ie. the target in this case) of the iterator
672 Node baseNode(const InEdgeIt &e) const {
673 return Parent::target((Edge&)e);
675 /// \brief Running node of the iterator
677 /// Returns the running node (ie. the source in this case) of the
679 Node runningNode(const InEdgeIt &e) const {
680 return Parent::source((Edge&)e);
683 class IncEdgeIt : public Parent::UEdge {
684 friend class BpUGraphAdaptorExtender;
691 IncEdgeIt(Invalid i) : UEdge(i), direction(true) { }
693 IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
694 graph->firstInc(*this, direction, n);
697 IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
698 : graph(&_graph), UEdge(ue) {
699 direction = (graph->source(ue) == n);
702 IncEdgeIt& operator++() {
703 graph->nextInc(*this, direction);
709 /// Base node of the iterator
711 /// Returns the base node of the iterator
712 Node baseNode(const IncEdgeIt &e) const {
713 return e.direction ? source(e) : target(e);
716 /// Running node of the iterator
718 /// Returns the running node of the iterator
719 Node runningNode(const IncEdgeIt &e) const {
720 return e.direction ? target(e) : source(e);
723 Node oppositeNode(const Node &n, const UEdge &e) const {
724 if( n == Parent::source(e))
725 return Parent::target(e);
726 else if( n == Parent::target(e))
727 return Parent::source(e);
732 Edge oppositeEdge(const Edge &e) const {
733 return Parent::direct(e, !Parent::direction(e));
736 using Parent::direct;
737 Edge direct(const UEdge &ue, const Node &s) const {
738 return Parent::direct(ue, Parent::source(ue) == s);