COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/undir_graph_extender.h @ 1021:fd1d073b6557

Last change on this file since 1021:fd1d073b6557 was 1021:fd1d073b6557, checked in by Mihaly Barasz, 19 years ago

Advances in UndirGraph?.

File size: 5.7 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(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
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 oppsiteNode(const Node &n, const Edge &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::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    }
152    template <typename E>
153    void _dirFirstIn(E &e, const Node &n) const {
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
164    template <typename E>
165    void _dirNextOut(E &e) const {
166      if( e.forward ) {
167        Parent::nextOut(e);
168        if( UndirEdge(e) == INVALID ) {
169          Parent::firstIn(e, Parent::source(e));
170          e.forward = false;
171        }
172      }
173      else {
174        Parent::nextIn(e);
175      }
176    }
177    template <typename E>
178    void _dirNextIn(E &e) const {
179      if( e.forward ) {
180        Parent::nextIn(e);
181        if( UndirEdge(e) == INVALID ) {
182          Parent::firstOut(e, Parent::target(e));
183          e.forward = false;
184        }
185      }
186      else {
187        Parent::nextOut(e);
188      }
189    }
190
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
207    // Miscellaneous stuff:
208
209    /// \todo these methods (id, maxEdgeId) should be moved into separate
210    /// Extender
211
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    }
223
224    int id(const Edge &e) const {
225      return 2 * Parent::id(e) + int(e.forward);
226    }
227
228
229    int maxId(Node n) const {
230      return Parent::maxId(Node());
231    }
232
233    int maxId(Edge) const {
234      return 2 * Parent::maxId(typename Parent::Edge()) + 1;
235    }
236    int maxId(UndirEdge) const {
237      return Parent::maxId(typename Parent::Edge());
238    }
239
240  };
241
242}
243
244#endif // LEMON_UNDIR_GRAPH_EXTENDER_H
Note: See TracBrowser for help on using the repository browser.