COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/undir_graph_extender.h @ 1557:3e8d928e283d

Last change on this file since 1557:3e8d928e283d was 1435:8e85e6bbefdf, checked in by Akos Ladanyi, 19 years ago

trunk/src/* move to trunk/

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