COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/iterable_graph_extender.h @ 1956:a055123339d5

Last change on this file since 1956:a055123339d5 was 1956:a055123339d5, checked in by Alpar Juttner, 14 years ago

Unified copyright notices

File size: 12.0 KB
RevLine 
[1956]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
[946]19#ifndef LEMON_ITERABLE_GRAPH_EXTENDER_H
20#define LEMON_ITERABLE_GRAPH_EXTENDER_H
21
22#include <lemon/invalid.h>
[1448]23#include <lemon/utility.h>
[946]24
25namespace lemon {
26 
27  template <typename _Base>
28  class IterableGraphExtender : public _Base {
[962]29  public:
[946]30
[1448]31    /// Indicates that the graph is undirected.
32
33    ///\todo Better name?
34    ///
35    ///\bug Should it be here?
[1909]36    typedef False UTag;
[1448]37
[946]38    typedef _Base Parent;
39    typedef IterableGraphExtender<_Base> Graph;
40
41    typedef typename Parent::Node Node;
42    typedef typename Parent::Edge Edge;
43
44
45    class NodeIt : public Node {
46      const Graph* graph;
47    public:
48
49      NodeIt() {}
50
51      NodeIt(Invalid i) : Node(i) { }
52
[962]53      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
[946]54        _graph.first(*static_cast<Node*>(this));
55      }
56
57      NodeIt(const Graph& _graph, const Node& node)
58        : Node(node), graph(&_graph) {}
59
60      NodeIt& operator++() {
61        graph->next(*this);
62        return *this;
63      }
64
65    };
66
67
68    class EdgeIt : public Edge {
69      const Graph* graph;
70    public:
71
72      EdgeIt() { }
73
74      EdgeIt(Invalid i) : Edge(i) { }
75
[962]76      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
[946]77        _graph.first(*static_cast<Edge*>(this));
78      }
79
80      EdgeIt(const Graph& _graph, const Edge& e) :
81        Edge(e), graph(&_graph) { }
82
83      EdgeIt& operator++() {
84        graph->next(*this);
85        return *this;
86      }
87
88    };
89
90
91    class OutEdgeIt : public Edge {
92      const Graph* graph;
93    public:
94
95      OutEdgeIt() { }
96
97      OutEdgeIt(Invalid i) : Edge(i) { }
98
99      OutEdgeIt(const Graph& _graph, const Node& node)
[962]100        : graph(&_graph) {
[946]101        _graph.firstOut(*this, node);
102      }
103
104      OutEdgeIt(const Graph& _graph, const Edge& edge)
105        : Edge(edge), graph(&_graph) {}
106
107      OutEdgeIt& operator++() {
108        graph->nextOut(*this);
109        return *this;
110      }
111
112    };
113
114
115    class InEdgeIt : public Edge {
116      const Graph* graph;
117    public:
118
119      InEdgeIt() { }
120
121      InEdgeIt(Invalid i) : Edge(i) { }
122
123      InEdgeIt(const Graph& _graph, const Node& node)
[962]124        : graph(&_graph) {
[946]125        _graph.firstIn(*this, node);
126      }
127
128      InEdgeIt(const Graph& _graph, const Edge& edge) :
129        Edge(edge), graph(&_graph) {}
130
131      InEdgeIt& operator++() {
132        graph->nextIn(*this);
133        return *this;
134      }
135
136    };
137
[1627]138    /// \brief Base node of the iterator
[1158]139    ///
140    /// Returns the base node (ie. the source in this case) of the iterator
141    Node baseNode(const OutEdgeIt &e) const {
[1564]142      return Parent::source((Edge)e);
[1158]143    }
[1627]144    /// \brief Running node of the iterator
[1158]145    ///
146    /// Returns the running node (ie. the target in this case) of the
147    /// iterator
148    Node runningNode(const OutEdgeIt &e) const {
[1564]149      return Parent::target((Edge)e);
[1158]150    }
151
[1627]152    /// \brief Base node of the iterator
[1158]153    ///
154    /// Returns the base node (ie. the target in this case) of the iterator
155    Node baseNode(const InEdgeIt &e) const {
[1564]156      return Parent::target((Edge)e);
[1158]157    }
[1627]158    /// \brief Running node of the iterator
[1158]159    ///
160    /// Returns the running node (ie. the source in this case) of the
161    /// iterator
162    Node runningNode(const InEdgeIt &e) const {
[1564]163      return Parent::source((Edge)e);
[1158]164    }
165
[946]166    using Parent::first;
167
[1627]168    /// \brief The opposite node on the given edge.
169    ///
170    /// Gives back the opposite on the given edge.
171    Node oppositeNode(const Node& n, const Edge& e) const {
172      if (Parent::source(e) == n) {
173        return Parent::target(e);
174      } else {
175        return Parent::source(e);
176      }
177    }
178
[946]179  private:
180
[1230]181    // void first(NodeIt &) const;
182    // void first(EdgeIt &) const;
183    // void first(OutEdgeIt &) const;
184    // void first(InEdgeIt &) const;
[946]185
186  };
[1158]187
188
189
190
191
[946]192 
[962]193  template <typename _Base>
[1909]194  class IterableUGraphExtender : public IterableGraphExtender<_Base> {
[962]195  public:
196
[1448]197    /// Indicates that the graph is undirected.
198
199    ///\todo Better name?
200    ///
201    ///\bug Should it be here?
202    ///\bug Should be tested in the concept checker whether it is defined
203    ///correctly.
[1909]204    typedef True UTag;
[1448]205
[962]206    typedef IterableGraphExtender<_Base> Parent;
[1909]207    typedef IterableUGraphExtender<_Base> Graph;
[1021]208    typedef typename Parent::Node Node;
[1627]209    typedef typename Parent::Edge Edge;
[1909]210    typedef typename Parent::UEdge UEdge;
[962]211
[1909]212    class UEdgeIt : public Parent::UEdge {
[962]213      const Graph* graph;
214    public:
215
[1909]216      UEdgeIt() { }
[962]217
[1909]218      UEdgeIt(Invalid i) : UEdge(i) { }
[962]219
[1909]220      explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
221        _graph.first(*static_cast<UEdge*>(this));
[962]222      }
223
[1909]224      UEdgeIt(const Graph& _graph, const UEdge& e) :
225        UEdge(e), graph(&_graph) { }
[962]226
[1909]227      UEdgeIt& operator++() {
[962]228        graph->next(*this);
229        return *this;
230      }
231
232    };
233
[1909]234    class IncEdgeIt : public Parent::UEdge {
[1021]235      const Graph* graph;
[1704]236      bool direction;
[1909]237      friend class IterableUGraphExtender;
[1021]238    public:
239
[1030]240      IncEdgeIt() { }
[1021]241
[1909]242      IncEdgeIt(Invalid i) : UEdge(i), direction(false) { }
[1021]243
[1704]244      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
245        _graph.firstInc(*this, direction, n);
[1021]246      }
247
[1909]248      IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
249        : graph(&_graph), UEdge(ue) {
[1704]250        direction = (_graph.source(ue) == n);
[1158]251      }
[1021]252
[1030]253      IncEdgeIt& operator++() {
[1704]254        graph->nextInc(*this, direction);
[1021]255        return *this;
256      }
257    };
258
[1158]259    using Parent::baseNode;
260    using Parent::runningNode;
261
262    /// Base node of the iterator
263    ///
264    /// Returns the base node of the iterator
265    Node baseNode(const IncEdgeIt &e) const {
[1704]266      return e.direction ? source(e) : target(e);
[1021]267    }
[1158]268    /// Running node of the iterator
269    ///
270    /// Returns the running node of the iterator
271    Node runningNode(const IncEdgeIt &e) const {
[1704]272      return e.direction ? target(e) : source(e);
[1021]273    }
274
[1627]275    /// \brief The opposite node on the given undirected edge.
276    ///
277    /// Gives back the opposite on the given undirected edge.
[1909]278    Node oppositeNode(const Node& n, const UEdge& e) const {
[1627]279      if (Parent::source(e) == n) {
280        return Parent::target(e);
281      } else {
282        return Parent::source(e);
283      }
284    }
285
[962]286  };
[1820]287
288
289  template <typename _Base>
[1910]290  class IterableBpUGraphExtender : public _Base {
[1820]291  public:
292    typedef _Base Parent;
[1910]293    typedef IterableBpUGraphExtender Graph;
[1820]294   
295    typedef typename Parent::Node Node;
[1910]296    typedef typename Parent::ANode ANode;
297    typedef typename Parent::BNode BNode;
[1820]298    typedef typename Parent::Edge Edge;
[1909]299    typedef typename Parent::UEdge UEdge;
[1820]300 
301    class NodeIt : public Node {
302      const Graph* graph;
303    public:
304   
305      NodeIt() { }
306   
307      NodeIt(Invalid i) : Node(INVALID) { }
308   
309      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
310        graph->first(static_cast<Node&>(*this));
311      }
312
313      NodeIt(const Graph& _graph, const Node& node)
314        : Node(node), graph(&_graph) { }
315   
316      NodeIt& operator++() {
317        graph->next(*this);
318        return *this;
319      }
320
321    };
322
[1934]323    class ANodeIt : public Node {
[1910]324      friend class IterableBpUGraphExtender;
[1820]325      const Graph* graph;
326    public:
327   
[1910]328      ANodeIt() { }
[1820]329   
[1910]330      ANodeIt(Invalid i) : Node(INVALID) { }
[1820]331   
[1910]332      explicit ANodeIt(const Graph& _graph) : graph(&_graph) {
333        graph->firstANode(static_cast<Node&>(*this));
[1820]334      }
335
[1910]336      ANodeIt(const Graph& _graph, const Node& node)
[1820]337        : Node(node), graph(&_graph) {}
338   
[1910]339      ANodeIt& operator++() {
340        graph->nextANode(*this);
[1820]341        return *this;
342      }
343    };
344
[1934]345    class BNodeIt : public Node {
[1910]346      friend class IterableBpUGraphExtender;
[1820]347      const Graph* graph;
348    public:
349   
[1910]350      BNodeIt() { }
[1820]351   
[1910]352      BNodeIt(Invalid i) : Node(INVALID) { }
[1820]353   
[1910]354      explicit BNodeIt(const Graph& _graph) : graph(&_graph) {
355        graph->firstBNode(static_cast<Node&>(*this));
[1820]356      }
357
[1910]358      BNodeIt(const Graph& _graph, const Node& node)
[1820]359        : Node(node), graph(&_graph) {}
360   
[1910]361      BNodeIt& operator++() {
362        graph->nextBNode(*this);
[1820]363        return *this;
364      }
365    };
366
367    class EdgeIt : public Edge {
[1910]368      friend class IterableBpUGraphExtender;
[1820]369      const Graph* graph;
370    public:
371   
372      EdgeIt() { }
373   
374      EdgeIt(Invalid i) : Edge(INVALID) { }
375   
376      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
377        graph->first(static_cast<Edge&>(*this));
378      }
379
380      EdgeIt(const Graph& _graph, const Edge& edge)
381        : Edge(edge), graph(&_graph) { }
382   
383      EdgeIt& operator++() {
384        graph->next(*this);
385        return *this;
386      }
387
388    };
389
[1909]390    class UEdgeIt : public UEdge {
[1910]391      friend class IterableBpUGraphExtender;
[1820]392      const Graph* graph;
393    public:
394   
[1909]395      UEdgeIt() { }
[1820]396   
[1909]397      UEdgeIt(Invalid i) : UEdge(INVALID) { }
[1820]398   
[1909]399      explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
400        graph->first(static_cast<UEdge&>(*this));
[1820]401      }
402
[1909]403      UEdgeIt(const Graph& _graph, const UEdge& edge)
404        : UEdge(edge), graph(&_graph) { }
[1820]405   
[1909]406      UEdgeIt& operator++() {
[1820]407        graph->next(*this);
408        return *this;
409      }
410    };
411
412    class OutEdgeIt : public Edge {
[1910]413      friend class IterableBpUGraphExtender;
[1820]414      const Graph* graph;
415    public:
416   
417      OutEdgeIt() { }
418   
419      OutEdgeIt(Invalid i) : Edge(i) { }
420   
421      OutEdgeIt(const Graph& _graph, const Node& node)
422        : graph(&_graph) {
423        graph->firstOut(*this, node);
424      }
425   
426      OutEdgeIt(const Graph& _graph, const Edge& edge)
427        : Edge(edge), graph(&_graph) {}
428   
429      OutEdgeIt& operator++() {
430        graph->nextOut(*this);
431        return *this;
432      }
433
434    };
435
436
437    class InEdgeIt : public Edge {
[1910]438      friend class IterableBpUGraphExtender;
[1820]439      const Graph* graph;
440    public:
441   
442      InEdgeIt() { }
443   
444      InEdgeIt(Invalid i) : Edge(i) { }
445   
446      InEdgeIt(const Graph& _graph, const Node& node)
447        : graph(&_graph) {
448        graph->firstIn(*this, node);
449      }
450   
451      InEdgeIt(const Graph& _graph, const Edge& edge) :
452        Edge(edge), graph(&_graph) {}
453   
454      InEdgeIt& operator++() {
455        graph->nextIn(*this);
456        return *this;
457      }
458
459    };
460 
461    /// \brief Base node of the iterator
462    ///
463    /// Returns the base node (ie. the source in this case) of the iterator
464    Node baseNode(const OutEdgeIt &e) const {
465      return Parent::source((Edge&)e);
466    }
467    /// \brief Running node of the iterator
468    ///
469    /// Returns the running node (ie. the target in this case) of the
470    /// iterator
471    Node runningNode(const OutEdgeIt &e) const {
472      return Parent::target((Edge&)e);
473    }
474 
475    /// \brief Base node of the iterator
476    ///
477    /// Returns the base node (ie. the target in this case) of the iterator
478    Node baseNode(const InEdgeIt &e) const {
479      return Parent::target((Edge&)e);
480    }
481    /// \brief Running node of the iterator
482    ///
483    /// Returns the running node (ie. the source in this case) of the
484    /// iterator
485    Node runningNode(const InEdgeIt &e) const {
486      return Parent::source((Edge&)e);
487    }
488 
[1909]489    class IncEdgeIt : public Parent::UEdge {
[1910]490      friend class IterableBpUGraphExtender;
[1820]491      const Graph* graph;
492      bool direction;
493    public:
494   
495      IncEdgeIt() { }
496   
[1909]497      IncEdgeIt(Invalid i) : UEdge(i), direction(true) { }
[1820]498   
499      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
500        graph->firstInc(*this, direction, n);
501      }
502
[1909]503      IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
504        : graph(&_graph), UEdge(ue) {
[1820]505        direction = (graph->source(ue) == n);
506      }
507
508      IncEdgeIt& operator++() {
509        graph->nextInc(*this, direction);
510        return *this;
511      }
512    };
513 
514
515    /// Base node of the iterator
516    ///
517    /// Returns the base node of the iterator
518    Node baseNode(const IncEdgeIt &e) const {
519      return e.direction ? source(e) : target(e);
520    }
521
522    /// Running node of the iterator
523    ///
524    /// Returns the running node of the iterator
525    Node runningNode(const IncEdgeIt &e) const {
526      return e.direction ? target(e) : source(e);
527    }
528 
529  };
530
[946]531}
532
533#endif // LEMON_GRAPH_EXTENDER_H
Note: See TracBrowser for help on using the repository browser.