COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/graph_adaptor_extender.h @ 2031:080d51024ac5

Last change on this file since 2031:080d51024ac5 was 2031:080d51024ac5, checked in by Balazs Dezso, 14 years ago

Correcting the structure of the graph's and adaptor's map.
The template assign operators and map iterators can be used for adaptors also.

Some bugfix in the adaptors

New class SwapBpUGraphAdaptor which swaps the two nodeset of the graph.

File size: 16.1 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  };
724
725
726}
727
728
729#endif
Note: See TracBrowser for help on using the repository browser.