1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2013
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/core.h>
23 #include <lemon/error.h>
27 template <typename _Digraph>
28 class DigraphAdaptorExtender : public _Digraph {
29 typedef _Digraph Parent;
33 typedef _Digraph Digraph;
34 typedef DigraphAdaptorExtender Adaptor;
38 typedef typename Parent::Node Node;
39 typedef typename Parent::Arc Arc;
41 int maxId(Node) const {
42 return Parent::maxNodeId();
45 int maxId(Arc) const {
46 return Parent::maxArcId();
49 Node fromId(int id, Node) const {
50 return Parent::nodeFromId(id);
53 Arc fromId(int id, Arc) const {
54 return Parent::arcFromId(id);
57 Node oppositeNode(const Node &n, const Arc &e) const {
58 if (n == Parent::source(e))
59 return Parent::target(e);
60 else if(n==Parent::target(e))
61 return Parent::source(e);
66 class NodeIt : public Node {
67 const Adaptor* _adaptor;
72 NodeIt(Invalid i) : Node(i) { }
74 explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
75 _adaptor->first(static_cast<Node&>(*this));
78 NodeIt(const Adaptor& adaptor, const Node& node)
79 : Node(node), _adaptor(&adaptor) {}
81 NodeIt& operator++() {
82 _adaptor->next(*this);
88 LemonRangeWrapper1<NodeIt, Adaptor> nodes() const {
89 return LemonRangeWrapper1<NodeIt, Adaptor>(*this);
92 class ArcIt : public Arc {
93 const Adaptor* _adaptor;
98 ArcIt(Invalid i) : Arc(i) { }
100 explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
101 _adaptor->first(static_cast<Arc&>(*this));
104 ArcIt(const Adaptor& adaptor, const Arc& e) :
105 Arc(e), _adaptor(&adaptor) { }
107 ArcIt& operator++() {
108 _adaptor->next(*this);
114 LemonRangeWrapper1<ArcIt, Adaptor> arcs() const {
115 return LemonRangeWrapper1<ArcIt, Adaptor>(*this);
119 class OutArcIt : public Arc {
120 const Adaptor* _adaptor;
125 OutArcIt(Invalid i) : Arc(i) { }
127 OutArcIt(const Adaptor& adaptor, const Node& node)
128 : _adaptor(&adaptor) {
129 _adaptor->firstOut(*this, node);
132 OutArcIt(const Adaptor& adaptor, const Arc& arc)
133 : Arc(arc), _adaptor(&adaptor) {}
135 OutArcIt& operator++() {
136 _adaptor->nextOut(*this);
142 LemonRangeWrapper2<OutArcIt, Adaptor, Node> outArcs(const Node& u) const {
143 return LemonRangeWrapper2<OutArcIt, Adaptor, Node>(*this, u);
147 class InArcIt : public Arc {
148 const Adaptor* _adaptor;
153 InArcIt(Invalid i) : Arc(i) { }
155 InArcIt(const Adaptor& adaptor, const Node& node)
156 : _adaptor(&adaptor) {
157 _adaptor->firstIn(*this, node);
160 InArcIt(const Adaptor& adaptor, const Arc& arc) :
161 Arc(arc), _adaptor(&adaptor) {}
163 InArcIt& operator++() {
164 _adaptor->nextIn(*this);
170 LemonRangeWrapper2<InArcIt, Adaptor, Node> inArcs(const Node& u) const {
171 return LemonRangeWrapper2<InArcIt, Adaptor, Node>(*this, u);
174 Node baseNode(const OutArcIt &e) const {
175 return Parent::source(e);
177 Node runningNode(const OutArcIt &e) const {
178 return Parent::target(e);
181 Node baseNode(const InArcIt &e) const {
182 return Parent::target(e);
184 Node runningNode(const InArcIt &e) const {
185 return Parent::source(e);
190 template <typename _Graph>
191 class GraphAdaptorExtender : public _Graph {
192 typedef _Graph Parent;
196 typedef _Graph Graph;
197 typedef GraphAdaptorExtender Adaptor;
199 typedef True UndirectedTag;
201 typedef typename Parent::Node Node;
202 typedef typename Parent::Arc Arc;
203 typedef typename Parent::Edge Edge;
207 int maxId(Node) const {
208 return Parent::maxNodeId();
211 int maxId(Arc) const {
212 return Parent::maxArcId();
215 int maxId(Edge) const {
216 return Parent::maxEdgeId();
219 Node fromId(int id, Node) const {
220 return Parent::nodeFromId(id);
223 Arc fromId(int id, Arc) const {
224 return Parent::arcFromId(id);
227 Edge fromId(int id, Edge) const {
228 return Parent::edgeFromId(id);
231 Node oppositeNode(const Node &n, const Edge &e) const {
232 if( n == Parent::u(e))
234 else if( n == Parent::v(e))
240 Arc oppositeArc(const Arc &a) const {
241 return Parent::direct(a, !Parent::direction(a));
244 using Parent::direct;
245 Arc direct(const Edge &e, const Node &s) const {
246 return Parent::direct(e, Parent::u(e) == s);
250 class NodeIt : public Node {
251 const Adaptor* _adaptor;
256 NodeIt(Invalid i) : Node(i) { }
258 explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
259 _adaptor->first(static_cast<Node&>(*this));
262 NodeIt(const Adaptor& adaptor, const Node& node)
263 : Node(node), _adaptor(&adaptor) {}
265 NodeIt& operator++() {
266 _adaptor->next(*this);
272 LemonRangeWrapper1<NodeIt, Adaptor> nodes() const {
273 return LemonRangeWrapper1<NodeIt, Adaptor>(*this);
277 class ArcIt : public Arc {
278 const Adaptor* _adaptor;
283 ArcIt(Invalid i) : Arc(i) { }
285 explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
286 _adaptor->first(static_cast<Arc&>(*this));
289 ArcIt(const Adaptor& adaptor, const Arc& e) :
290 Arc(e), _adaptor(&adaptor) { }
292 ArcIt& operator++() {
293 _adaptor->next(*this);
299 LemonRangeWrapper1<ArcIt, Adaptor> arcs() const {
300 return LemonRangeWrapper1<ArcIt, Adaptor>(*this);
304 class OutArcIt : public Arc {
305 const Adaptor* _adaptor;
310 OutArcIt(Invalid i) : Arc(i) { }
312 OutArcIt(const Adaptor& adaptor, const Node& node)
313 : _adaptor(&adaptor) {
314 _adaptor->firstOut(*this, node);
317 OutArcIt(const Adaptor& adaptor, const Arc& arc)
318 : Arc(arc), _adaptor(&adaptor) {}
320 OutArcIt& operator++() {
321 _adaptor->nextOut(*this);
327 LemonRangeWrapper2<OutArcIt, Adaptor, Node> outArcs(const Node& u) const {
328 return LemonRangeWrapper2<OutArcIt, Adaptor, Node>(*this, u);
332 class InArcIt : public Arc {
333 const Adaptor* _adaptor;
338 InArcIt(Invalid i) : Arc(i) { }
340 InArcIt(const Adaptor& adaptor, const Node& node)
341 : _adaptor(&adaptor) {
342 _adaptor->firstIn(*this, node);
345 InArcIt(const Adaptor& adaptor, const Arc& arc) :
346 Arc(arc), _adaptor(&adaptor) {}
348 InArcIt& operator++() {
349 _adaptor->nextIn(*this);
355 LemonRangeWrapper2<InArcIt, Adaptor, Node> inArcs(const Node& u) const {
356 return LemonRangeWrapper2<InArcIt, Adaptor, Node>(*this, u);
359 class EdgeIt : public Parent::Edge {
360 const Adaptor* _adaptor;
365 EdgeIt(Invalid i) : Edge(i) { }
367 explicit EdgeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
368 _adaptor->first(static_cast<Edge&>(*this));
371 EdgeIt(const Adaptor& adaptor, const Edge& e) :
372 Edge(e), _adaptor(&adaptor) { }
374 EdgeIt& operator++() {
375 _adaptor->next(*this);
381 LemonRangeWrapper1<EdgeIt, Adaptor> edges() const {
382 return LemonRangeWrapper1<EdgeIt, Adaptor>(*this);
386 class IncEdgeIt : public Edge {
387 friend class GraphAdaptorExtender;
388 const Adaptor* _adaptor;
394 IncEdgeIt(Invalid i) : Edge(i), direction(false) { }
396 IncEdgeIt(const Adaptor& adaptor, const Node &n) : _adaptor(&adaptor) {
397 _adaptor->firstInc(static_cast<Edge&>(*this), direction, n);
400 IncEdgeIt(const Adaptor& adaptor, const Edge &e, const Node &n)
401 : _adaptor(&adaptor), Edge(e) {
402 direction = (_adaptor->u(e) == n);
405 IncEdgeIt& operator++() {
406 _adaptor->nextInc(*this, direction);
411 LemonRangeWrapper2<IncEdgeIt, Adaptor, Node> incEdges(const Node& u) const {
412 return LemonRangeWrapper2<IncEdgeIt, Adaptor, Node>(*this, u);
416 Node baseNode(const OutArcIt &a) const {
417 return Parent::source(a);
419 Node runningNode(const OutArcIt &a) const {
420 return Parent::target(a);
423 Node baseNode(const InArcIt &a) const {
424 return Parent::target(a);
426 Node runningNode(const InArcIt &a) const {
427 return Parent::source(a);
430 Node baseNode(const IncEdgeIt &e) const {
431 return e.direction ? Parent::u(e) : Parent::v(e);
433 Node runningNode(const IncEdgeIt &e) const {
434 return e.direction ? Parent::v(e) : Parent::u(e);