Removed references to the gui.
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;
457 int maxId(Node) const {
458 return Parent::maxNodeId();
460 int maxId(BNode) const {
461 return Parent::maxBNodeId();
463 int maxId(ANode) const {
464 return Parent::maxANodeId();
466 int maxId(Edge) const {
467 return Parent::maxEdgeId();
469 int maxId(UEdge) const {
470 return Parent::maxUEdgeId();
474 Node fromId(int id, Node) const {
475 return Parent::nodeFromId(id);
477 ANode fromId(int id, ANode) const {
478 return Parent::fromANodeId(id);
480 BNode fromId(int id, BNode) const {
481 return Parent::fromBNodeId(id);
483 Edge fromId(int id, Edge) const {
484 return Parent::edgeFromId(id);
486 UEdge fromId(int id, UEdge) const {
487 return Parent::uEdgeFromId(id);
490 class NodeIt : public Node {
496 NodeIt(Invalid i) : Node(INVALID) { }
498 explicit NodeIt(const Graph& _graph) : graph(&_graph) {
499 graph->first(static_cast<Node&>(*this));
502 NodeIt(const Graph& _graph, const Node& node)
503 : Node(node), graph(&_graph) { }
505 NodeIt& operator++() {
512 class ANodeIt : public Node {
513 friend class BpUGraphAdaptorExtender;
519 ANodeIt(Invalid i) : Node(INVALID) { }
521 explicit ANodeIt(const Graph& _graph) : graph(&_graph) {
522 graph->firstANode(static_cast<Node&>(*this));
525 ANodeIt(const Graph& _graph, const Node& node)
526 : Node(node), graph(&_graph) {}
528 ANodeIt& operator++() {
529 graph->nextANode(*this);
534 class BNodeIt : public Node {
535 friend class BpUGraphAdaptorExtender;
541 BNodeIt(Invalid i) : Node(INVALID) { }
543 explicit BNodeIt(const Graph& _graph) : graph(&_graph) {
544 graph->firstBNode(static_cast<Node&>(*this));
547 BNodeIt(const Graph& _graph, const Node& node)
548 : Node(node), graph(&_graph) {}
550 BNodeIt& operator++() {
551 graph->nextBNode(*this);
556 class EdgeIt : public Edge {
557 friend class BpUGraphAdaptorExtender;
563 EdgeIt(Invalid i) : Edge(INVALID) { }
565 explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
566 graph->first(static_cast<Edge&>(*this));
569 EdgeIt(const Graph& _graph, const Edge& edge)
570 : Edge(edge), graph(&_graph) { }
572 EdgeIt& operator++() {
579 class UEdgeIt : public UEdge {
580 friend class BpUGraphAdaptorExtender;
586 UEdgeIt(Invalid i) : UEdge(INVALID) { }
588 explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
589 graph->first(static_cast<UEdge&>(*this));
592 UEdgeIt(const Graph& _graph, const UEdge& edge)
593 : UEdge(edge), graph(&_graph) { }
595 UEdgeIt& operator++() {
601 class OutEdgeIt : public Edge {
602 friend class BpUGraphAdaptorExtender;
608 OutEdgeIt(Invalid i) : Edge(i) { }
610 OutEdgeIt(const Graph& _graph, const Node& node)
612 graph->firstOut(*this, node);
615 OutEdgeIt(const Graph& _graph, const Edge& edge)
616 : Edge(edge), graph(&_graph) {}
618 OutEdgeIt& operator++() {
619 graph->nextOut(*this);
626 class InEdgeIt : public Edge {
627 friend class BpUGraphAdaptorExtender;
633 InEdgeIt(Invalid i) : Edge(i) { }
635 InEdgeIt(const Graph& _graph, const Node& node)
637 graph->firstIn(*this, node);
640 InEdgeIt(const Graph& _graph, const Edge& edge) :
641 Edge(edge), graph(&_graph) {}
643 InEdgeIt& operator++() {
644 graph->nextIn(*this);
650 /// \brief Base node of the iterator
652 /// Returns the base node (ie. the source in this case) of the iterator
653 Node baseNode(const OutEdgeIt &e) const {
654 return Parent::source((Edge&)e);
656 /// \brief Running node of the iterator
658 /// Returns the running node (ie. the target in this case) of the
660 Node runningNode(const OutEdgeIt &e) const {
661 return Parent::target((Edge&)e);
664 /// \brief Base node of the iterator
666 /// Returns the base node (ie. the target in this case) of the iterator
667 Node baseNode(const InEdgeIt &e) const {
668 return Parent::target((Edge&)e);
670 /// \brief Running node of the iterator
672 /// Returns the running node (ie. the source in this case) of the
674 Node runningNode(const InEdgeIt &e) const {
675 return Parent::source((Edge&)e);
678 class IncEdgeIt : public Parent::UEdge {
679 friend class BpUGraphAdaptorExtender;
686 IncEdgeIt(Invalid i) : UEdge(i), direction(true) { }
688 IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
689 graph->firstInc(*this, direction, n);
692 IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
693 : graph(&_graph), UEdge(ue) {
694 direction = (graph->source(ue) == n);
697 IncEdgeIt& operator++() {
698 graph->nextInc(*this, direction);
704 /// Base node of the iterator
706 /// Returns the base node of the iterator
707 Node baseNode(const IncEdgeIt &e) const {
708 return e.direction ? source(e) : target(e);
711 /// Running node of the iterator
713 /// Returns the running node of the iterator
714 Node runningNode(const IncEdgeIt &e) const {
715 return e.direction ? target(e) : source(e);
718 Node oppositeNode(const Node &n, const UEdge &e) const {
719 if( n == Parent::source(e))
720 return Parent::target(e);
721 else if( n == Parent::target(e))
722 return Parent::source(e);
727 Edge oppositeEdge(const Edge &e) const {
728 return Parent::direct(e, !Parent::direction(e));
731 using Parent::direct;
732 Edge direct(const UEdge &ue, const Node &s) const {
733 return Parent::direct(ue, Parent::source(ue) == s);