COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/graph_adaptor_extender.h @ 2553:bfced05fa852

Last change on this file since 2553:bfced05fa852 was 2553:bfced05fa852, checked in by Alpar Juttner, 12 years ago

Happy New Year to LEMON (+ better update-copyright-header script)

File size: 16.6 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2008
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(static_cast<const 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(static_cast<const 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(static_cast<const 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(static_cast<const 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
457    int maxId(Node) const {
458      return Parent::maxNodeId();
459    }
460    int maxId(BNode) const {
461      return Parent::maxBNodeId();
462    }
463    int maxId(ANode) const {
464      return Parent::maxANodeId();
465    }
466    int maxId(Edge) const {
467      return Parent::maxEdgeId();
468    }
469    int maxId(UEdge) const {
470      return Parent::maxUEdgeId();
471    }
472
473
474    Node fromId(int id, Node) const {
475      return Parent::nodeFromId(id);
476    }
477    ANode fromId(int id, ANode) const {
478      return Parent::nodeFromANodeId(id);
479    }
480    BNode fromId(int id, BNode) const {
481      return Parent::nodeFromBNodeId(id);
482    }
483    Edge fromId(int id, Edge) const {
484      return Parent::edgeFromId(id);
485    }
486    UEdge fromId(int id, UEdge) const {
487      return Parent::uEdgeFromId(id);
488    } 
489 
490    class NodeIt : public Node {
491      const Graph* graph;
492    public:
493   
494      NodeIt() { }
495   
496      NodeIt(Invalid i) : Node(INVALID) { }
497   
498      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
499        graph->first(static_cast<Node&>(*this));
500      }
501
502      NodeIt(const Graph& _graph, const Node& node)
503        : Node(node), graph(&_graph) { }
504   
505      NodeIt& operator++() {
506        graph->next(*this);
507        return *this;
508      }
509
510    };
511
512    class ANodeIt : public Node {
513      friend class BpUGraphAdaptorExtender;
514      const Graph* graph;
515    public:
516   
517      ANodeIt() { }
518   
519      ANodeIt(Invalid i) : Node(INVALID) { }
520   
521      explicit ANodeIt(const Graph& _graph) : graph(&_graph) {
522        graph->firstANode(static_cast<Node&>(*this));
523      }
524
525      ANodeIt(const Graph& _graph, const Node& node)
526        : Node(node), graph(&_graph) {}
527   
528      ANodeIt& operator++() {
529        graph->nextANode(*this);
530        return *this;
531      }
532    };
533
534    class BNodeIt : public Node {
535      friend class BpUGraphAdaptorExtender;
536      const Graph* graph;
537    public:
538   
539      BNodeIt() { }
540   
541      BNodeIt(Invalid i) : Node(INVALID) { }
542   
543      explicit BNodeIt(const Graph& _graph) : graph(&_graph) {
544        graph->firstBNode(static_cast<Node&>(*this));
545      }
546
547      BNodeIt(const Graph& _graph, const Node& node)
548        : Node(node), graph(&_graph) {}
549   
550      BNodeIt& operator++() {
551        graph->nextBNode(*this);
552        return *this;
553      }
554    };
555
556    class EdgeIt : public Edge {
557      friend class BpUGraphAdaptorExtender;
558      const Graph* graph;
559    public:
560   
561      EdgeIt() { }
562   
563      EdgeIt(Invalid i) : Edge(INVALID) { }
564   
565      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
566        graph->first(static_cast<Edge&>(*this));
567      }
568
569      EdgeIt(const Graph& _graph, const Edge& edge)
570        : Edge(edge), graph(&_graph) { }
571   
572      EdgeIt& operator++() {
573        graph->next(*this);
574        return *this;
575      }
576
577    };
578
579    class UEdgeIt : public UEdge {
580      friend class BpUGraphAdaptorExtender;
581      const Graph* graph;
582    public:
583   
584      UEdgeIt() { }
585   
586      UEdgeIt(Invalid i) : UEdge(INVALID) { }
587   
588      explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
589        graph->first(static_cast<UEdge&>(*this));
590      }
591
592      UEdgeIt(const Graph& _graph, const UEdge& edge)
593        : UEdge(edge), graph(&_graph) { }
594   
595      UEdgeIt& operator++() {
596        graph->next(*this);
597        return *this;
598      }
599    };
600
601    class OutEdgeIt : public Edge {
602      friend class BpUGraphAdaptorExtender;
603      const Graph* graph;
604    public:
605   
606      OutEdgeIt() { }
607   
608      OutEdgeIt(Invalid i) : Edge(i) { }
609   
610      OutEdgeIt(const Graph& _graph, const Node& node)
611        : graph(&_graph) {
612        graph->firstOut(*this, node);
613      }
614   
615      OutEdgeIt(const Graph& _graph, const Edge& edge)
616        : Edge(edge), graph(&_graph) {}
617   
618      OutEdgeIt& operator++() {
619        graph->nextOut(*this);
620        return *this;
621      }
622
623    };
624
625
626    class InEdgeIt : public Edge {
627      friend class BpUGraphAdaptorExtender;
628      const Graph* graph;
629    public:
630   
631      InEdgeIt() { }
632   
633      InEdgeIt(Invalid i) : Edge(i) { }
634   
635      InEdgeIt(const Graph& _graph, const Node& node)
636        : graph(&_graph) {
637        graph->firstIn(*this, node);
638      }
639   
640      InEdgeIt(const Graph& _graph, const Edge& edge) :
641        Edge(edge), graph(&_graph) {}
642   
643      InEdgeIt& operator++() {
644        graph->nextIn(*this);
645        return *this;
646      }
647
648    };
649 
650    /// \brief Base node of the iterator
651    ///
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(static_cast<const Edge&>(e));
655    }
656    /// \brief Running node of the iterator
657    ///
658    /// Returns the running node (ie. the target in this case) of the
659    /// iterator
660    Node runningNode(const OutEdgeIt &e) const {
661      return Parent::target(static_cast<const Edge&>(e));
662    }
663 
664    /// \brief Base node of the iterator
665    ///
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(static_cast<const Edge&>(e));
669    }
670    /// \brief Running node of the iterator
671    ///
672    /// Returns the running node (ie. the source in this case) of the
673    /// iterator
674    Node runningNode(const InEdgeIt &e) const {
675      return Parent::source(static_cast<const Edge&>(e));
676    }
677 
678    class IncEdgeIt : public Parent::UEdge {
679      friend class BpUGraphAdaptorExtender;
680      const Graph* graph;
681      bool direction;
682    public:
683   
684      IncEdgeIt() { }
685   
686      IncEdgeIt(Invalid i) : UEdge(i), direction(true) { }
687   
688      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
689        graph->firstInc(*this, direction, n);
690      }
691
692      IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
693        : graph(&_graph), UEdge(ue) {
694        direction = (graph->source(ue) == n);
695      }
696
697      IncEdgeIt& operator++() {
698        graph->nextInc(*this, direction);
699        return *this;
700      }
701    };
702 
703
704    /// Base node of the iterator
705    ///
706    /// Returns the base node of the iterator
707    Node baseNode(const IncEdgeIt &e) const {
708      return e.direction ? source(e) : target(e);
709    }
710
711    /// Running node of the iterator
712    ///
713    /// Returns the running node of the iterator
714    Node runningNode(const IncEdgeIt &e) const {
715      return e.direction ? target(e) : source(e);
716    }
717
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);
723      else
724        return INVALID;
725    }
726
727    Edge oppositeEdge(const Edge &e) const {
728      return Parent::direct(e, !Parent::direction(e));
729    }
730
731    using Parent::direct;
732    Edge direct(const UEdge &ue, const Node &s) const {
733      return Parent::direct(ue, Parent::source(ue) == s);
734    }
735
736  };
737
738
739}
740
741
742#endif
Note: See TracBrowser for help on using the repository browser.