COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/undir_graph_extender.h @ 1081:c0ad2673b11f

Last change on this file since 1081:c0ad2673b11f was 1060:7a24bb2e7480, checked in by Mihaly Barasz, 16 years ago

Nasty bug in undir_graph_extender.h

File size: 5.8 KB
Line 
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 {
38      friend class UndirGraphExtender;
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(true) {}
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
73  protected:
74
75    template <typename E>
76    Node _dirSource(const E &e) const {
77      return e.forward ? Parent::source(e) : Parent::target(e);
78    }
79
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:
86    /// \todo Shouldn't the "source" of an undirected edge be called "aNode"
87    /// or something???
88    using Parent::source;
89
90    /// Source of the given Edge.
91    Node source(const Edge &e) const {
92      return _dirSource(e);
93    }
94
95    /// \todo Shouldn't the "target" of an undirected edge be called "bNode"
96    /// or something???
97    using Parent::target;
98
99    /// Target of the given Edge.
100    Node target(const Edge &e) const {
101      return _dirTarget(e);
102    }
103
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
111    Node oppositeNode(const Node &n, const UndirEdge &e) const {
112      if( n == Parent::source(e))
113        return Parent::target(e);
114      else if( n == Parent::target(e))
115        return Parent::source(e);
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
138   
139  protected:
140
141    template <typename E>
142    void _dirFirstOut(E &e, const Node &n) const {
143      Parent::firstIn(e,n);
144      if( UndirEdge(e) != INVALID ) {
145        e.forward = false;
146      }
147      else {
148        Parent::firstOut(e,n);
149        e.forward = true;
150      }
151    }
152    template <typename E>
153    void _dirFirstIn(E &e, const Node &n) const {
154      Parent::firstOut(e,n);
155      if( UndirEdge(e) != INVALID ) {
156        e.forward = false;
157      }
158      else {
159        Parent::firstIn(e,n);
160        e.forward = true;
161      }
162    }
163
164    template <typename E>
165    void _dirNextOut(E &e) const {
166      if( ! e.forward ) {
167        Node n = Parent::target(e);
168        Parent::nextIn(e);
169        if( UndirEdge(e) == INVALID ) {
170          Parent::firstOut(e, n);
171          e.forward = true;
172        }
173      }
174      else {
175        Parent::nextOut(e);
176      }
177    }
178    template <typename E>
179    void _dirNextIn(E &e) const {
180      if( ! e.forward ) {
181        Node n = Parent::source(e);
182        Parent::nextOut(e);
183        if( UndirEdge(e) == INVALID ) {
184          Parent::firstIn(e, n);
185          e.forward = true;
186        }
187      }
188      else {
189        Parent::nextIn(e);
190      }
191    }
192
193  public:
194
195    void firstOut(Edge &e, const Node &n) const {
196      _dirFirstOut(e, n);
197    }
198    void firstIn(Edge &e, const Node &n) const {
199      _dirFirstIn(e, n);
200    }
201
202    void nextOut(Edge &e) const {
203      _dirNextOut(e);
204    }
205    void nextIn(Edge &e) const {
206      _dirNextIn(e);
207    }
208
209    // Miscellaneous stuff:
210
211    /// \todo these methods (id, maxEdgeId) should be moved into separate
212    /// Extender
213
214    // using Parent::id;
215    // Using "using" is not a good idea, cause it could be that there is
216    // no "id" in Parent...
217
218    int id(const Node &n) const {
219      return Parent::id(n);
220    }
221
222    int id(const UndirEdge &e) const {
223      return Parent::id(e);
224    }
225
226    int id(const Edge &e) const {
227      return 2 * Parent::id(e) + int(e.forward);
228    }
229
230
231    int maxId(Node) const {
232      return Parent::maxId(Node());
233    }
234
235    int maxId(Edge) const {
236      return 2 * Parent::maxId(typename Parent::Edge()) + 1;
237    }
238    int maxId(UndirEdge) const {
239      return Parent::maxId(typename Parent::Edge());
240    }
241
242
243    int edgeNum() const {
244      return 2 * Parent::edgeNum();
245    }
246    int undirEdgeNum() const {
247      return Parent::edgeNum();
248    }
249
250  };
251
252}
253
254#endif // LEMON_UNDIR_GRAPH_EXTENDER_H
Note: See TracBrowser for help on using the repository browser.