COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/graph_adaptor_extender.h @ 2041:28df5272df99

Last change on this file since 2041:28df5272df99 was 2041:28df5272df99, checked in by Balazs Dezso, 14 years ago

Forgotten functions in the graph adaptor extenders.

File size: 16.5 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
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.
12 *
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
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_BITS_GRAPH_ADAPTOR_EXTENDER_H
20#define LEMON_BITS_GRAPH_ADAPTOR_EXTENDER_H
21
22#include <lemon/bits/invalid.h>
23#include <lemon/error.h>
24
25#include <lemon/bits/default_map.h>
26
27
28///\ingroup graphbits
29///\file
30///\brief Extenders for the graph adaptor types
31namespace lemon {
32
33  /// \ingroup graphbits
34  ///
35  /// \brief Extender for the GraphAdaptors
36  template <typename _Graph>
37  class GraphAdaptorExtender : public _Graph {
38  public:
39
40    typedef _Graph Parent;
41    typedef _Graph Graph;
42    typedef GraphAdaptorExtender Adaptor;
43
44    // Base extensions
45
46    typedef typename Parent::Node Node;
47    typedef typename Parent::Edge Edge;
48
49    int maxId(Node) const {
50      return Parent::maxNodeId();
51    }
52
53    int maxId(Edge) const {
54      return Parent::maxEdgeId();
55    }
56
57    Node fromId(int id, Node) const {
58      return Parent::nodeFromId(id);
59    }
60
61    Edge fromId(int id, Edge) const {
62      return Parent::edgeFromId(id);
63    }
64
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);
70      else
71        return INVALID;
72    }
73
74    class NodeIt : public Node {
75      const Adaptor* graph;
76    public:
77
78      NodeIt() {}
79
80      NodeIt(Invalid i) : Node(i) { }
81
82      explicit NodeIt(const Adaptor& _graph) : graph(&_graph) {
83        _graph.first(static_cast<Node&>(*this));
84      }
85
86      NodeIt(const Adaptor& _graph, const Node& node)
87        : Node(node), graph(&_graph) {}
88
89      NodeIt& operator++() {
90        graph->next(*this);
91        return *this;
92      }
93
94    };
95
96
97    class EdgeIt : public Edge {
98      const Adaptor* graph;
99    public:
100
101      EdgeIt() { }
102
103      EdgeIt(Invalid i) : Edge(i) { }
104
105      explicit EdgeIt(const Adaptor& _graph) : graph(&_graph) {
106        _graph.first(static_cast<Edge&>(*this));
107      }
108
109      EdgeIt(const Adaptor& _graph, const Edge& e) :
110        Edge(e), graph(&_graph) { }
111
112      EdgeIt& operator++() {
113        graph->next(*this);
114        return *this;
115      }
116
117    };
118
119
120    class OutEdgeIt : public Edge {
121      const Adaptor* graph;
122    public:
123
124      OutEdgeIt() { }
125
126      OutEdgeIt(Invalid i) : Edge(i) { }
127
128      OutEdgeIt(const Adaptor& _graph, const Node& node)
129        : graph(&_graph) {
130        _graph.firstOut(*this, node);
131      }
132
133      OutEdgeIt(const Adaptor& _graph, const Edge& edge)
134        : Edge(edge), graph(&_graph) {}
135
136      OutEdgeIt& operator++() {
137        graph->nextOut(*this);
138        return *this;
139      }
140
141    };
142
143
144    class InEdgeIt : public Edge {
145      const Adaptor* graph;
146    public:
147
148      InEdgeIt() { }
149
150      InEdgeIt(Invalid i) : Edge(i) { }
151
152      InEdgeIt(const Adaptor& _graph, const Node& node)
153        : graph(&_graph) {
154        _graph.firstIn(*this, node);
155      }
156
157      InEdgeIt(const Adaptor& _graph, const Edge& edge) :
158        Edge(edge), graph(&_graph) {}
159
160      InEdgeIt& operator++() {
161        graph->nextIn(*this);
162        return *this;
163      }
164
165    };
166
167    /// \brief Base node of the iterator
168    ///
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);
172    }
173    /// \brief Running node of the iterator
174    ///
175    /// Returns the running node (ie. the target in this case) of the
176    /// iterator
177    Node runningNode(const OutEdgeIt &e) const {
178      return Parent::target(e);
179    }
180
181    /// \brief Base node of the iterator
182    ///
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);
186    }
187    /// \brief Running node of the iterator
188    ///
189    /// Returns the running node (ie. the source in this case) of the
190    /// iterator
191    Node runningNode(const InEdgeIt &e) const {
192      return Parent::source(e);
193    }
194
195  };
196
197
198  /// \ingroup graphbits
199  ///
200  /// \brief Extender for the UGraphAdaptors
201  template <typename _UGraph>
202  class UGraphAdaptorExtender : public _UGraph {
203  public:
204   
205    typedef _UGraph Parent;
206    typedef _UGraph UGraph;
207    typedef UGraphAdaptorExtender Adaptor;
208
209    typedef typename Parent::Node Node;
210    typedef typename Parent::Edge Edge;
211    typedef typename Parent::UEdge UEdge;
212
213    // UGraph extension   
214
215    int maxId(Node) const {
216      return Parent::maxNodeId();
217    }
218
219    int maxId(Edge) const {
220      return Parent::maxEdgeId();
221    }
222
223    int maxId(UEdge) const {
224      return Parent::maxUEdgeId();
225    }
226
227    Node fromId(int id, Node) const {
228      return Parent::nodeFromId(id);
229    }
230
231    Edge fromId(int id, Edge) const {
232      return Parent::edgeFromId(id);
233    }
234
235    UEdge fromId(int id, UEdge) const {
236      return Parent::uEdgeFromId(id);
237    }
238
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);
244      else
245        return INVALID;
246    }
247
248    Edge oppositeEdge(const Edge &e) const {
249      return Parent::direct(e, !Parent::direction(e));
250    }
251
252    using Parent::direct;
253    Edge direct(const UEdge &ue, const Node &s) const {
254      return Parent::direct(ue, Parent::source(ue) == s);
255    }
256
257
258    class NodeIt : public Node {
259      const Adaptor* graph;
260    public:
261
262      NodeIt() {}
263
264      NodeIt(Invalid i) : Node(i) { }
265
266      explicit NodeIt(const Adaptor& _graph) : graph(&_graph) {
267        _graph.first(static_cast<Node&>(*this));
268      }
269
270      NodeIt(const Adaptor& _graph, const Node& node)
271        : Node(node), graph(&_graph) {}
272
273      NodeIt& operator++() {
274        graph->next(*this);
275        return *this;
276      }
277
278    };
279
280
281    class EdgeIt : public Edge {
282      const Adaptor* graph;
283    public:
284
285      EdgeIt() { }
286
287      EdgeIt(Invalid i) : Edge(i) { }
288
289      explicit EdgeIt(const Adaptor& _graph) : graph(&_graph) {
290        _graph.first(static_cast<Edge&>(*this));
291      }
292
293      EdgeIt(const Adaptor& _graph, const Edge& e) :
294        Edge(e), graph(&_graph) { }
295
296      EdgeIt& operator++() {
297        graph->next(*this);
298        return *this;
299      }
300
301    };
302
303
304    class OutEdgeIt : public Edge {
305      const Adaptor* graph;
306    public:
307
308      OutEdgeIt() { }
309
310      OutEdgeIt(Invalid i) : Edge(i) { }
311
312      OutEdgeIt(const Adaptor& _graph, const Node& node)
313        : graph(&_graph) {
314        _graph.firstOut(*this, node);
315      }
316
317      OutEdgeIt(const Adaptor& _graph, const Edge& edge)
318        : Edge(edge), graph(&_graph) {}
319
320      OutEdgeIt& operator++() {
321        graph->nextOut(*this);
322        return *this;
323      }
324
325    };
326
327
328    class InEdgeIt : public Edge {
329      const Adaptor* graph;
330    public:
331
332      InEdgeIt() { }
333
334      InEdgeIt(Invalid i) : Edge(i) { }
335
336      InEdgeIt(const Adaptor& _graph, const Node& node)
337        : graph(&_graph) {
338        _graph.firstIn(*this, node);
339      }
340
341      InEdgeIt(const Adaptor& _graph, const Edge& edge) :
342        Edge(edge), graph(&_graph) {}
343
344      InEdgeIt& operator++() {
345        graph->nextIn(*this);
346        return *this;
347      }
348
349    };
350
351    class UEdgeIt : public Parent::UEdge {
352      const Adaptor* graph;
353    public:
354
355      UEdgeIt() { }
356
357      UEdgeIt(Invalid i) : UEdge(i) { }
358
359      explicit UEdgeIt(const Adaptor& _graph) : graph(&_graph) {
360        _graph.first(static_cast<UEdge&>(*this));
361      }
362
363      UEdgeIt(const Adaptor& _graph, const UEdge& e) :
364        UEdge(e), graph(&_graph) { }
365
366      UEdgeIt& operator++() {
367        graph->next(*this);
368        return *this;
369      }
370
371    };
372
373    class IncEdgeIt : public Parent::UEdge {
374      friend class UGraphAdaptorExtender;
375      const Adaptor* graph;
376      bool direction;
377    public:
378
379      IncEdgeIt() { }
380
381      IncEdgeIt(Invalid i) : UEdge(i), direction(false) { }
382
383      IncEdgeIt(const Adaptor& _graph, const Node &n) : graph(&_graph) {
384        _graph.firstInc(static_cast<UEdge&>(*this), direction, n);
385      }
386
387      IncEdgeIt(const Adaptor& _graph, const UEdge &ue, const Node &n)
388        : graph(&_graph), UEdge(ue) {
389        direction = (_graph.source(ue) == n);
390      }
391
392      IncEdgeIt& operator++() {
393        graph->nextInc(*this, direction);
394        return *this;
395      }
396    };
397
398    /// \brief Base node of the iterator
399    ///
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);
403    }
404    /// \brief Running node of the iterator
405    ///
406    /// Returns the running node (ie. the target in this case) of the
407    /// iterator
408    Node runningNode(const OutEdgeIt &e) const {
409      return Parent::target((Edge)e);
410    }
411
412    /// \brief Base node of the iterator
413    ///
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);
417    }
418    /// \brief Running node of the iterator
419    ///
420    /// Returns the running node (ie. the source in this case) of the
421    /// iterator
422    Node runningNode(const InEdgeIt &e) const {
423      return Parent::source((Edge)e);
424    }
425
426    /// Base node of the iterator
427    ///
428    /// Returns the base node of the iterator
429    Node baseNode(const IncEdgeIt &e) const {
430      return e.direction ? source(e) : target(e);
431    }
432    /// Running node of the iterator
433    ///
434    /// Returns the running node of the iterator
435    Node runningNode(const IncEdgeIt &e) const {
436      return e.direction ? target(e) : source(e);
437    }
438
439  };
440
441  /// \ingroup graphbits
442  ///
443  /// \brief Extender for the BpUGraphAdaptors
444  template <typename Base>
445  class BpUGraphAdaptorExtender : public Base {
446  public:
447    typedef Base Parent;
448    typedef BpUGraphAdaptorExtender Graph;
449
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;
455
456    Node oppositeNode(const UEdge& edge, const Node& node) const {
457      return source(edge) == node ?
458        target(edge) : source(edge);
459    }
460
461
462    int maxId(Node) const {
463      return Parent::maxNodeId();
464    }
465    int maxId(BNode) const {
466      return Parent::maxBNodeId();
467    }
468    int maxId(ANode) const {
469      return Parent::maxANodeId();
470    }
471    int maxId(Edge) const {
472      return Parent::maxEdgeId();
473    }
474    int maxId(UEdge) const {
475      return Parent::maxUEdgeId();
476    }
477
478
479    Node fromId(int id, Node) const {
480      return Parent::nodeFromId(id);
481    }
482    ANode fromId(int id, ANode) const {
483      return Parent::fromANodeId(id);
484    }
485    BNode fromId(int id, BNode) const {
486      return Parent::fromBNodeId(id);
487    }
488    Edge fromId(int id, Edge) const {
489      return Parent::edgeFromId(id);
490    }
491    UEdge fromId(int id, UEdge) const {
492      return Parent::uEdgeFromId(id);
493    } 
494 
495    class NodeIt : public Node {
496      const Graph* graph;
497    public:
498   
499      NodeIt() { }
500   
501      NodeIt(Invalid i) : Node(INVALID) { }
502   
503      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
504        graph->first(static_cast<Node&>(*this));
505      }
506
507      NodeIt(const Graph& _graph, const Node& node)
508        : Node(node), graph(&_graph) { }
509   
510      NodeIt& operator++() {
511        graph->next(*this);
512        return *this;
513      }
514
515    };
516
517    class ANodeIt : public Node {
518      friend class BpUGraphAdaptorExtender;
519      const Graph* graph;
520    public:
521   
522      ANodeIt() { }
523   
524      ANodeIt(Invalid i) : Node(INVALID) { }
525   
526      explicit ANodeIt(const Graph& _graph) : graph(&_graph) {
527        graph->firstANode(static_cast<Node&>(*this));
528      }
529
530      ANodeIt(const Graph& _graph, const Node& node)
531        : Node(node), graph(&_graph) {}
532   
533      ANodeIt& operator++() {
534        graph->nextANode(*this);
535        return *this;
536      }
537    };
538
539    class BNodeIt : public Node {
540      friend class BpUGraphAdaptorExtender;
541      const Graph* graph;
542    public:
543   
544      BNodeIt() { }
545   
546      BNodeIt(Invalid i) : Node(INVALID) { }
547   
548      explicit BNodeIt(const Graph& _graph) : graph(&_graph) {
549        graph->firstBNode(static_cast<Node&>(*this));
550      }
551
552      BNodeIt(const Graph& _graph, const Node& node)
553        : Node(node), graph(&_graph) {}
554   
555      BNodeIt& operator++() {
556        graph->nextBNode(*this);
557        return *this;
558      }
559    };
560
561    class EdgeIt : public Edge {
562      friend class BpUGraphAdaptorExtender;
563      const Graph* graph;
564    public:
565   
566      EdgeIt() { }
567   
568      EdgeIt(Invalid i) : Edge(INVALID) { }
569   
570      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
571        graph->first(static_cast<Edge&>(*this));
572      }
573
574      EdgeIt(const Graph& _graph, const Edge& edge)
575        : Edge(edge), graph(&_graph) { }
576   
577      EdgeIt& operator++() {
578        graph->next(*this);
579        return *this;
580      }
581
582    };
583
584    class UEdgeIt : public UEdge {
585      friend class BpUGraphAdaptorExtender;
586      const Graph* graph;
587    public:
588   
589      UEdgeIt() { }
590   
591      UEdgeIt(Invalid i) : UEdge(INVALID) { }
592   
593      explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
594        graph->first(static_cast<UEdge&>(*this));
595      }
596
597      UEdgeIt(const Graph& _graph, const UEdge& edge)
598        : UEdge(edge), graph(&_graph) { }
599   
600      UEdgeIt& operator++() {
601        graph->next(*this);
602        return *this;
603      }
604    };
605
606    class OutEdgeIt : public Edge {
607      friend class BpUGraphAdaptorExtender;
608      const Graph* graph;
609    public:
610   
611      OutEdgeIt() { }
612   
613      OutEdgeIt(Invalid i) : Edge(i) { }
614   
615      OutEdgeIt(const Graph& _graph, const Node& node)
616        : graph(&_graph) {
617        graph->firstOut(*this, node);
618      }
619   
620      OutEdgeIt(const Graph& _graph, const Edge& edge)
621        : Edge(edge), graph(&_graph) {}
622   
623      OutEdgeIt& operator++() {
624        graph->nextOut(*this);
625        return *this;
626      }
627
628    };
629
630
631    class InEdgeIt : public Edge {
632      friend class BpUGraphAdaptorExtender;
633      const Graph* graph;
634    public:
635   
636      InEdgeIt() { }
637   
638      InEdgeIt(Invalid i) : Edge(i) { }
639   
640      InEdgeIt(const Graph& _graph, const Node& node)
641        : graph(&_graph) {
642        graph->firstIn(*this, node);
643      }
644   
645      InEdgeIt(const Graph& _graph, const Edge& edge) :
646        Edge(edge), graph(&_graph) {}
647   
648      InEdgeIt& operator++() {
649        graph->nextIn(*this);
650        return *this;
651      }
652
653    };
654 
655    /// \brief Base node of the iterator
656    ///
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);
660    }
661    /// \brief Running node of the iterator
662    ///
663    /// Returns the running node (ie. the target in this case) of the
664    /// iterator
665    Node runningNode(const OutEdgeIt &e) const {
666      return Parent::target((Edge&)e);
667    }
668 
669    /// \brief Base node of the iterator
670    ///
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);
674    }
675    /// \brief Running node of the iterator
676    ///
677    /// Returns the running node (ie. the source in this case) of the
678    /// iterator
679    Node runningNode(const InEdgeIt &e) const {
680      return Parent::source((Edge&)e);
681    }
682 
683    class IncEdgeIt : public Parent::UEdge {
684      friend class BpUGraphAdaptorExtender;
685      const Graph* graph;
686      bool direction;
687    public:
688   
689      IncEdgeIt() { }
690   
691      IncEdgeIt(Invalid i) : UEdge(i), direction(true) { }
692   
693      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
694        graph->firstInc(*this, direction, n);
695      }
696
697      IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
698        : graph(&_graph), UEdge(ue) {
699        direction = (graph->source(ue) == n);
700      }
701
702      IncEdgeIt& operator++() {
703        graph->nextInc(*this, direction);
704        return *this;
705      }
706    };
707 
708
709    /// Base node of the iterator
710    ///
711    /// Returns the base node of the iterator
712    Node baseNode(const IncEdgeIt &e) const {
713      return e.direction ? source(e) : target(e);
714    }
715
716    /// Running node of the iterator
717    ///
718    /// Returns the running node of the iterator
719    Node runningNode(const IncEdgeIt &e) const {
720      return e.direction ? target(e) : source(e);
721    }
722
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);
728      else
729        return INVALID;
730    }
731
732    Edge oppositeEdge(const Edge &e) const {
733      return Parent::direct(e, !Parent::direction(e));
734    }
735
736    using Parent::direct;
737    Edge direct(const UEdge &ue, const Node &s) const {
738      return Parent::direct(ue, Parent::source(ue) == s);
739    }
740
741  };
742
743
744}
745
746
747#endif
Note: See TracBrowser for help on using the repository browser.