COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/undir_graph_extender.h @ 1627:3fd1ba6e9872

Last change on this file since 1627:3fd1ba6e9872 was 1627:3fd1ba6e9872, checked in by Balazs Dezso, 14 years ago

Some modification on the undirected graph interface.
Doc improvments

File size: 6.4 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  protected:
75
76    template <typename E>
77    Node _dirSource(const E &e) const {
78      return e.forward ? Parent::source(e) : Parent::target(e);
79    }
80
81    template <typename E>
82    Node _dirTarget(const E &e) const {
83      return e.forward ? Parent::target(e) : Parent::source(e);
84    }
85
86  public:
87    /// \todo Shouldn't the "source" of an undirected edge be called "aNode"
88    /// or something???
89    using Parent::source;
90
91    /// Source of the given Edge.
92    Node source(const Edge &e) const {
93      return _dirSource(e);
94    }
95
96    /// \todo Shouldn't the "target" of an undirected edge be called "bNode"
97    /// or something???
98    using Parent::target;
99
100    /// Target of the given Edge.
101    Node target(const Edge &e) const {
102      return _dirTarget(e);
103    }
104
105    Node oppositeNode(const Node &n, const UndirEdge &e) const {
106      if( n == Parent::source(e))
107        return Parent::target(e);
108      else if( n == Parent::target(e))
109        return Parent::source(e);
110      else
111        return INVALID;
112    }
113
114    /// \brief Directed edge from an undirected edge and a source node.
115    ///
116    /// Returns a (directed) Edge corresponding to the specified UndirEdge
117    /// and source Node.
118    ///
119    Edge direct(const UndirEdge &ue, const Node &s) const {
120      return Edge(ue, s == source(ue));
121    }
122
123    /// \brief Directed edge from an undirected edge.
124    ///
125    /// Returns a directed edge corresponding to the specified UndirEdge.
126    /// If the given bool is true the given undirected edge and the
127    /// returned edge have the same source node.
128    Edge direct(const UndirEdge &ue, bool d) const {
129      return Edge(ue, d);
130    }
131
132    /// Returns whether the given directed edge is same orientation as the
133    /// corresponding undirected edge.
134    ///
135    /// \todo reference to the corresponding point of the undirected graph
136    /// concept. "What does the direction of an undirected edge mean?"
137    bool direction(const Edge &e) const { return e.forward; }
138
139
140    using Parent::first;
141    void first(Edge &e) const {
142      Parent::first(e);
143      e.forward=true;
144    }
145
146    using Parent::next;
147    void next(Edge &e) const {
148      if( e.forward ) {
149        e.forward = false;
150      }
151      else {
152        Parent::next(e);
153        e.forward = true;
154      }
155    }
156
157   
158  protected:
159
160    template <typename E>
161    void _dirFirstOut(E &e, const Node &n) const {
162      Parent::firstIn(e,n);
163      if( UndirEdge(e) != INVALID ) {
164        e.forward = false;
165      }
166      else {
167        Parent::firstOut(e,n);
168        e.forward = true;
169      }
170    }
171    template <typename E>
172    void _dirFirstIn(E &e, const Node &n) const {
173      Parent::firstOut(e,n);
174      if( UndirEdge(e) != INVALID ) {
175        e.forward = false;
176      }
177      else {
178        Parent::firstIn(e,n);
179        e.forward = true;
180      }
181    }
182
183    template <typename E>
184    void _dirNextOut(E &e) const {
185      if( ! e.forward ) {
186        Node n = Parent::target(e);
187        Parent::nextIn(e);
188        if( UndirEdge(e) == INVALID ) {
189          Parent::firstOut(e, n);
190          e.forward = true;
191        }
192      }
193      else {
194        Parent::nextOut(e);
195      }
196    }
197    template <typename E>
198    void _dirNextIn(E &e) const {
199      if( ! e.forward ) {
200        Node n = Parent::source(e);
201        Parent::nextOut(e);
202        if( UndirEdge(e) == INVALID ) {
203          Parent::firstIn(e, n);
204          e.forward = true;
205        }
206      }
207      else {
208        Parent::nextIn(e);
209      }
210    }
211
212  public:
213
214    void firstOut(Edge &e, const Node &n) const {
215      _dirFirstOut(e, n);
216    }
217    void firstIn(Edge &e, const Node &n) const {
218      _dirFirstIn(e, n);
219    }
220
221    void nextOut(Edge &e) const {
222      _dirNextOut(e);
223    }
224    void nextIn(Edge &e) const {
225      _dirNextIn(e);
226    }
227
228    // Miscellaneous stuff:
229
230    /// \todo these methods (id, maxEdgeId) should be moved into separate
231    /// Extender
232
233    // using Parent::id;
234    // Using "using" is not a good idea, cause it could be that there is
235    // no "id" in Parent...
236
237    int id(const Node &n) const {
238      return Parent::id(n);
239    }
240
241    int id(const UndirEdge &e) const {
242      return Parent::id(e);
243    }
244
245    int id(const Edge &e) const {
246      return 2 * Parent::id(e) + int(e.forward);
247    }
248
249
250    int maxId(Node) const {
251      return Parent::maxId(Node());
252    }
253
254    int maxId(Edge) const {
255      return 2 * Parent::maxId(typename Parent::Edge()) + 1;
256    }
257    int maxId(UndirEdge) const {
258      return Parent::maxId(typename Parent::Edge());
259    }
260
261
262    int edgeNum() const {
263      return 2 * Parent::edgeNum();
264    }
265    int undirEdgeNum() const {
266      return Parent::edgeNum();
267    }
268
269  };
270
271}
272
273#endif // LEMON_UNDIR_GRAPH_EXTENDER_H
Note: See TracBrowser for help on using the repository browser.