COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/undir_graph_extender.h @ 1030:c8a41699e613

Last change on this file since 1030:c8a41699e613 was 1030:c8a41699e613, checked in by Mihaly Barasz, 16 years ago

Undirected graph documentation and concept refinements.

  • quite a few bug fixes
  • concept::UndirGraph? is almost complete and looks quite good.
File size: 5.7 KB
RevLine 
[962]1/* -*- C++ -*-
2 *
3 * src/lemon/undir_graph_extender.h - Part of LEMON, a generic C++
4 * optimization library
5 *
6 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi
7 * Kutatocsoport (Egervary Combinatorial Optimization Research Group,
8 * EGRES).
9 *
10 * Permission to use, modify and distribute this software is granted
11 * provided that this copyright notice appears in all copies. For
12 * precise terms see the accompanying LICENSE file.
13 *
14 * This software is provided "AS IS" with no warranty of any kind,
15 * express or implied, and with no claim as to its suitability for any
16 * purpose.
17 *
18 */
19
20#ifndef LEMON_UNDIR_GRAPH_EXTENDER_H
21#define LEMON_UNDIR_GRAPH_EXTENDER_H
22
23#include <lemon/invalid.h>
24
25namespace lemon {
26
27  template <typename _Base>
28  class UndirGraphExtender : public _Base {
29    typedef _Base Parent;
30    typedef UndirGraphExtender Graph;
31
32  public:
33
34    typedef typename Parent::Edge UndirEdge;
35    typedef typename Parent::Node Node;
36
37    class Edge : public UndirEdge {
[978]38      friend class UndirGraphExtender;
[962]39
40    protected:
41      // FIXME: Marci use opposite logic in his graph wrappers. It would
42      // be reasonable to syncronize...
43      bool forward;
44
45    public:
46      Edge() {}
47      /// Construct a direct edge from undirect edge and a direction.
48      Edge(const UndirEdge &ue, bool _forward) :
49        UndirEdge(ue), forward(_forward) {}
50      /// Invalid edge constructor
51      Edge(Invalid i) : UndirEdge(i), forward(false) {}
52
53      bool operator==(const Edge &that) const {
54        return forward==that.forward && UndirEdge(*this)==UndirEdge(that);
55      }
56      bool operator!=(const Edge &that) const {
57        return forward!=that.forward || UndirEdge(*this)!=UndirEdge(that);
58      }
59      bool operator<(const Edge &that) const {
60        return forward<that.forward ||
61          (!(that.forward<forward) && UndirEdge(*this)<UndirEdge(that));
62      }
63    };
64
65
66    /// \brief Returns the Edge of opposite direction.
67    ///
68    /// \bug Is this a good name for this? Or "reverse" is better?
69    Edge opposite(const Edge &e) const {
70      return Edge(e,!e.forward);
71    }
72
[1021]73  protected:
74
75    template <typename E>
76    Node _dirSource(const E &e) const {
[986]77      return e.forward ? Parent::source(e) : Parent::target(e);
[962]78    }
79
[1021]80    template <typename E>
81    Node _dirTarget(const E &e) const {
82      return e.forward ? Parent::target(e) : Parent::source(e);
83    }
84
85  public:
[986]86    /// \todo Shouldn't the "source" of an undirected edge be called "aNode"
[962]87    /// or something???
[986]88    using Parent::source;
[962]89
[1021]90    /// Source of the given Edge.
91    Node source(const Edge &e) const {
92      return _dirSource(e);
[962]93    }
94
[986]95    /// \todo Shouldn't the "target" of an undirected edge be called "bNode"
[962]96    /// or something???
[986]97    using Parent::target;
[962]98
[1021]99    /// Target of the given Edge.
100    Node target(const Edge &e) const {
101      return _dirTarget(e);
102    }
103
[962]104    /// Returns whether the given directed edge is same orientation as the
105    /// corresponding undirected edge.
106    ///
107    /// \todo reference to the corresponding point of the undirected graph
108    /// concept. "What does the direction of an undirected edge mean?"
109    bool forward(const Edge &e) const { return e.forward; }
110
[1030]111    Node oppositeNode(const Node &n, const UndirEdge &e) const {
[986]112      if( n == Parent::source(e))
113        return Parent::target(e);
114      else if( n == Parent::target(e))
115        return Parent::source(e);
[962]116      else
117        return INVALID;
118    }
119
120
121    using Parent::first;
122    void first(Edge &e) const {
123      Parent::first(e);
124      e.forward=true;
125    }
126
127    using Parent::next;
128    void next(Edge &e) const {
129      if( e.forward ) {
130        e.forward = false;
131      }
132      else {
133        Parent::next(e);
134        e.forward = true;
135      }
136    }
137
[1021]138   
139  protected:
140
141    template <typename E>
142    void _dirFirstOut(E &e, const Node &n) const {
[962]143      Parent::firstOut(e,n);
144      if( UndirEdge(e) != INVALID ) {
145        e.forward = true;
146      }
147      else {
148        Parent::firstIn(e,n);
149        e.forward = false;
150      }
151    }
[1021]152    template <typename E>
153    void _dirFirstIn(E &e, const Node &n) const {
[962]154      Parent::firstIn(e,n);
155      if( UndirEdge(e) != INVALID ) {
156        e.forward = true;
157      }
158      else {
159        Parent::firstOut(e,n);
160        e.forward = false;
161      }
162    }
163
[1021]164    template <typename E>
165    void _dirNextOut(E &e) const {
[962]166      if( e.forward ) {
167        Parent::nextOut(e);
168        if( UndirEdge(e) == INVALID ) {
[986]169          Parent::firstIn(e, Parent::source(e));
[962]170          e.forward = false;
171        }
172      }
173      else {
174        Parent::nextIn(e);
175      }
176    }
[1021]177    template <typename E>
178    void _dirNextIn(E &e) const {
[962]179      if( e.forward ) {
180        Parent::nextIn(e);
181        if( UndirEdge(e) == INVALID ) {
[986]182          Parent::firstOut(e, Parent::target(e));
[962]183          e.forward = false;
184        }
185      }
186      else {
187        Parent::nextOut(e);
188      }
189    }
190
[1021]191  public:
192
193    void firstOut(Edge &e, const Node &n) const {
194      _dirFirstOut(e, n);
195    }
196    void firstIn(Edge &e, const Node &n) const {
197      _dirFirstIn(e, n);
198    }
199
200    void nextOut(Edge &e) const {
201      _dirNextOut(e);
202    }
203    void nextIn(Edge &e) const {
204      _dirNextIn(e);
205    }
206
[962]207    // Miscellaneous stuff:
208
209    /// \todo these methods (id, maxEdgeId) should be moved into separate
210    /// Extender
211
[1021]212    // using Parent::id;
213    // Using "using" is not a good idea, cause it could be that there is
214    // no "id" in Parent...
215
216    int id(const Node &n) const {
217      return Parent::id(n);
218    }
219
220    int id(const UndirEdge &e) const {
221      return Parent::id(e);
222    }
[962]223
224    int id(const Edge &e) const {
[981]225      return 2 * Parent::id(e) + int(e.forward);
[962]226    }
227
[1021]228
229    int maxId(Node n) const {
230      return Parent::maxId(Node());
231    }
232
233    int maxId(Edge) const {
[981]234      return 2 * Parent::maxId(typename Parent::Edge()) + 1;
[962]235    }
[1021]236    int maxId(UndirEdge) const {
[981]237      return Parent::maxId(typename Parent::Edge());
[962]238    }
239
240  };
241
242}
243
244#endif // LEMON_UNDIR_GRAPH_EXTENDER_H
Note: See TracBrowser for help on using the repository browser.