COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/undir_graph_extender.h @ 1704:467d7927a901

Last change on this file since 1704:467d7927a901 was 1704:467d7927a901, checked in by Balazs Dezso, 14 years ago

findUndirEdge, ConUndirEdgeIt?
some modification in the undir graph extenders

File size: 7.8 KB
Line 
1/* -*- C++ -*-
2 *
3 * lemon/undir_graph_extender.h - Part of LEMON, a generic C++
4 * optimization library
5 *
6 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi
7 * Kutatocsoport (Egervary Research Group on Combinatorial Optimization,
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 adaptors. It would
42      // be reasonable to syncronize...
43      bool forward;
44
45      Edge(const UndirEdge &ue, bool _forward) :
46        UndirEdge(ue), forward(_forward) {}
47
48    public:
49      Edge() {}
50
51      /// Invalid edge constructor
52      Edge(Invalid i) : UndirEdge(i), forward(true) {}
53
54      bool operator==(const Edge &that) const {
55        return forward==that.forward && UndirEdge(*this)==UndirEdge(that);
56      }
57      bool operator!=(const Edge &that) const {
58        return forward!=that.forward || UndirEdge(*this)!=UndirEdge(that);
59      }
60      bool operator<(const Edge &that) const {
61        return forward<that.forward ||
62          (!(that.forward<forward) && UndirEdge(*this)<UndirEdge(that));
63      }
64    };
65
66
67    /// \brief Edge of opposite direction.
68    ///
69    /// Returns the Edge of opposite direction.
70    Edge oppositeEdge(const Edge &e) const {
71      return Edge(e,!e.forward);
72    }
73
74  public:
75    /// \todo Shouldn't the "source" of an undirected edge be called "aNode"
76    /// or something???
77    using Parent::source;
78
79    /// Source of the given Edge.
80    Node source(const Edge &e) const {
81      return e.forward ? Parent::source(e) : Parent::target(e);
82    }
83
84    /// \todo Shouldn't the "target" of an undirected edge be called "bNode"
85    /// or something???
86    using Parent::target;
87
88    /// Target of the given Edge.
89    Node target(const Edge &e) const {
90      return e.forward ? Parent::target(e) : Parent::source(e);
91    }
92
93    Node oppositeNode(const Node &n, const UndirEdge &e) const {
94      if( n == Parent::source(e))
95        return Parent::target(e);
96      else if( n == Parent::target(e))
97        return Parent::source(e);
98      else
99        return INVALID;
100    }
101
102    /// \brief Directed edge from an undirected edge and a source node.
103    ///
104    /// Returns a (directed) Edge corresponding to the specified UndirEdge
105    /// and source Node.
106    ///
107    Edge direct(const UndirEdge &ue, const Node &s) const {
108      return Edge(ue, s == source(ue));
109    }
110
111    /// \brief Directed edge from an undirected edge.
112    ///
113    /// Returns a directed edge corresponding to the specified UndirEdge.
114    /// If the given bool is true the given undirected edge and the
115    /// returned edge have the same source node.
116    Edge direct(const UndirEdge &ue, bool d) const {
117      return Edge(ue, d);
118    }
119
120    /// Returns whether the given directed edge is same orientation as the
121    /// corresponding undirected edge.
122    ///
123    /// \todo reference to the corresponding point of the undirected graph
124    /// concept. "What does the direction of an undirected edge mean?"
125    bool direction(const Edge &e) const { return e.forward; }
126
127
128    using Parent::first;
129    void first(Edge &e) const {
130      Parent::first(e);
131      e.forward=true;
132    }
133
134    using Parent::next;
135    void next(Edge &e) const {
136      if( e.forward ) {
137        e.forward = false;
138      }
139      else {
140        Parent::next(e);
141        e.forward = true;
142      }
143    }
144
145  public:
146
147    void firstOut(Edge &e, const Node &n) const {
148      Parent::firstIn(e,n);
149      if( UndirEdge(e) != INVALID ) {
150        e.forward = false;
151      }
152      else {
153        Parent::firstOut(e,n);
154        e.forward = true;
155      }
156    }
157    void nextOut(Edge &e) const {
158      if( ! e.forward ) {
159        Node n = Parent::target(e);
160        Parent::nextIn(e);
161        if( UndirEdge(e) == INVALID ) {
162          Parent::firstOut(e, n);
163          e.forward = true;
164        }
165      }
166      else {
167        Parent::nextOut(e);
168      }
169    }
170
171    void firstIn(Edge &e, const Node &n) const {
172      Parent::firstOut(e,n);
173      if( UndirEdge(e) != INVALID ) {
174        e.forward = false;
175      }
176      else {
177        Parent::firstIn(e,n);
178        e.forward = true;
179      }
180    }
181    void nextIn(Edge &e) const {
182      if( ! e.forward ) {
183        Node n = Parent::source(e);
184        Parent::nextOut(e);
185        if( UndirEdge(e) == INVALID ) {
186          Parent::firstIn(e, n);
187          e.forward = true;
188        }
189      }
190      else {
191        Parent::nextIn(e);
192      }
193    }
194
195    void firstInc(UndirEdge &e, const Node &n) const {
196      Parent::firstOut(e, n);
197      if (e != INVALID) return;
198      Parent::firstIn(e, n);
199    }
200    void nextInc(UndirEdge &e, const Node &n) const {
201      if (Parent::source(e) == n) {
202        Parent::nextOut(e);
203        if (e != INVALID) return;
204        Parent::firstIn(e, n);
205      } else {
206        Parent::nextIn(e);
207      }
208    }
209
210    void firstInc(UndirEdge &e, bool &d, const Node &n) const {
211      d = true;
212      Parent::firstOut(e, n);
213      if (e != INVALID) return;
214      d = false;
215      Parent::firstIn(e, n);
216    }
217    void nextInc(UndirEdge &e, bool &d) const {
218      if (d) {
219        Node s = Parent::source(e);
220        Parent::nextOut(e);
221        if (e != INVALID) return;
222        d = false;
223        Parent::firstIn(e, s);
224      } else {
225        Parent::nextIn(e);
226      }
227    }
228
229    // Miscellaneous stuff:
230
231    /// \todo these methods (id, maxEdgeId) should be moved into separate
232    /// Extender
233
234    // using Parent::id;
235    // Using "using" is not a good idea, cause it could be that there is
236    // no "id" in Parent...
237
238    int id(const Node &n) const {
239      return Parent::id(n);
240    }
241
242    int id(const UndirEdge &e) const {
243      return Parent::id(e);
244    }
245
246    int id(const Edge &e) const {
247      return 2 * Parent::id(e) + int(e.forward);
248    }
249
250
251    int maxId(Node) const {
252      return Parent::maxId(Node());
253    }
254
255    int maxId(Edge) const {
256      return 2 * Parent::maxId(typename Parent::Edge()) + 1;
257    }
258    int maxId(UndirEdge) const {
259      return Parent::maxId(typename Parent::Edge());
260    }
261
262
263    int edgeNum() const {
264      return 2 * Parent::edgeNum();
265    }
266
267    int undirEdgeNum() const {
268      return Parent::edgeNum();
269    }
270
271    Edge findEdge(Node source, Node target, Edge prev) const {
272      if (prev == INVALID) {
273        UndirEdge edge = Parent::findEdge(source, target);
274        if (edge != INVALID) return direct(edge, true);
275        edge = Parent::findEdge(target, source);
276        if (edge != INVALID) return direct(edge, false);
277      } else if (direction(prev)) {
278        UndirEdge edge = Parent::findEdge(source, target, prev);
279        if (edge != INVALID) return direct(edge, true);
280        edge = Parent::findEdge(target, source);
281        if (edge != INVALID) return direct(edge, false);       
282      } else {
283        UndirEdge edge = Parent::findEdge(target, source, prev);
284        if (edge != INVALID) return direct(edge, false);             
285      }
286      return INVALID;
287    }
288
289    UndirEdge findUndirEdge(Node source, Node target, UndirEdge prev) const {
290      if (prev == INVALID) {
291        UndirEdge edge = Parent::findEdge(source, target);
292        if (edge != INVALID) return edge;
293        edge = Parent::findEdge(target, source);
294        if (edge != INVALID) return edge;
295      } else if (Parent::source(prev) == source) {
296        UndirEdge edge = Parent::findEdge(source, target, prev);
297        if (edge != INVALID) return edge;
298        edge = Parent::findEdge(target, source);
299        if (edge != INVALID) return edge;       
300      } else {
301        UndirEdge edge = Parent::findEdge(target, source, prev);
302        if (edge != INVALID) return edge;             
303      }
304      return INVALID;
305    }
306
307  };
308
309}
310
311#endif // LEMON_UNDIR_GRAPH_EXTENDER_H
Note: See TracBrowser for help on using the repository browser.