COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/graph_extender.h @ 1819:fd82adfbe905

Last change on this file since 1819:fd82adfbe905 was 1791:62e7d237e1fb, checked in by Balazs Dezso, 18 years ago

Modification on the base graph concept
The extended interface does not changed

File size: 9.2 KB
Line 
1/* -*- C++ -*-
2 * lemon/graph_extender.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi
5 * Kutatocsoport (Egervary Research Group on Combinatorial Optimization,
6 * EGRES).
7 *
8 * Permission to use, modify and distribute this software is granted
9 * provided that this copyright notice appears in all copies. For
10 * precise terms see the accompanying LICENSE file.
11 *
12 * This software is provided "AS IS" with no warranty of any kind,
13 * express or implied, and with no claim as to its suitability for any
14 * purpose.
15 *
16 */
17
18#ifndef LEMON_GRAPH_EXTENDER_H
19#define LEMON_GRAPH_EXTENDER_H
20
21#include <lemon/invalid.h>
22
23namespace lemon {
24
25  template <typename _Base>
26  class GraphExtender : public _Base {
27  public:
28
29    typedef _Base Parent;
30    typedef GraphExtender Graph;
31
32    typedef typename Parent::Node Node;
33    typedef typename Parent::Edge Edge;
34
35    int maxId(Node) const {
36      return Parent::maxNodeId();
37    }
38
39    int maxId(Edge) const {
40      return Parent::maxEdgeId();
41    }
42
43    Node fromId(int id, Node) const {
44      return Parent::nodeFromId(id);
45    }
46
47    Edge fromId(int id, Edge) const {
48      return Parent::edgeFromId(id);
49    }
50
51    Node oppositeNode(const Node &n, const Edge &e) const {
52      if (n == Parent::source(e))
53        return Parent::target(e);
54      else if(n==Parent::target(e))
55        return Parent::source(e);
56      else
57        return INVALID;
58    }
59
60  };
61
62  template <typename _Base>
63  class UndirGraphExtender : public _Base {
64    typedef _Base Parent;
65    typedef UndirGraphExtender Graph;
66
67  public:
68
69    typedef typename Parent::Edge UndirEdge;
70    typedef typename Parent::Node Node;
71
72    class Edge : public UndirEdge {
73      friend class UndirGraphExtender;
74
75    protected:
76      // FIXME: Marci use opposite logic in his graph adaptors. It would
77      // be reasonable to syncronize...
78      bool forward;
79
80      Edge(const UndirEdge &ue, bool _forward) :
81        UndirEdge(ue), forward(_forward) {}
82
83    public:
84      Edge() {}
85
86      /// Invalid edge constructor
87      Edge(Invalid i) : UndirEdge(i), forward(true) {}
88
89      bool operator==(const Edge &that) const {
90        return forward==that.forward && UndirEdge(*this)==UndirEdge(that);
91      }
92      bool operator!=(const Edge &that) const {
93        return forward!=that.forward || UndirEdge(*this)!=UndirEdge(that);
94      }
95      bool operator<(const Edge &that) const {
96        return forward<that.forward ||
97          (!(that.forward<forward) && UndirEdge(*this)<UndirEdge(that));
98      }
99    };
100
101
102    /// \brief Edge of opposite direction.
103    ///
104    /// Returns the Edge of opposite direction.
105    Edge oppositeEdge(const Edge &e) const {
106      return Edge(e,!e.forward);
107    }
108
109  public:
110    /// \todo Shouldn't the "source" of an undirected edge be called "aNode"
111    /// or something???
112    using Parent::source;
113
114    /// Source of the given Edge.
115    Node source(const Edge &e) const {
116      return e.forward ? Parent::source(e) : Parent::target(e);
117    }
118
119    /// \todo Shouldn't the "target" of an undirected edge be called "bNode"
120    /// or something???
121    using Parent::target;
122
123    /// Target of the given Edge.
124    Node target(const Edge &e) const {
125      return e.forward ? Parent::target(e) : Parent::source(e);
126    }
127
128    Node oppositeNode(const Node &n, const UndirEdge &e) const {
129      if( n == Parent::source(e))
130        return Parent::target(e);
131      else if( n == Parent::target(e))
132        return Parent::source(e);
133      else
134        return INVALID;
135    }
136
137    /// \brief Directed edge from an undirected edge and a source node.
138    ///
139    /// Returns a (directed) Edge corresponding to the specified UndirEdge
140    /// and source Node.
141    ///
142    Edge direct(const UndirEdge &ue, const Node &s) const {
143      return Edge(ue, s == source(ue));
144    }
145
146    /// \brief Directed edge from an undirected edge.
147    ///
148    /// Returns a directed edge corresponding to the specified UndirEdge.
149    /// If the given bool is true the given undirected edge and the
150    /// returned edge have the same source node.
151    Edge direct(const UndirEdge &ue, bool d) const {
152      return Edge(ue, d);
153    }
154
155    /// Returns whether the given directed edge is same orientation as the
156    /// corresponding undirected edge.
157    ///
158    /// \todo reference to the corresponding point of the undirected graph
159    /// concept. "What does the direction of an undirected edge mean?"
160    bool direction(const Edge &e) const { return e.forward; }
161
162
163    using Parent::first;
164    void first(Edge &e) const {
165      Parent::first(e);
166      e.forward=true;
167    }
168
169    using Parent::next;
170    void next(Edge &e) const {
171      if( e.forward ) {
172        e.forward = false;
173      }
174      else {
175        Parent::next(e);
176        e.forward = true;
177      }
178    }
179
180  public:
181
182    void firstOut(Edge &e, const Node &n) const {
183      Parent::firstIn(e,n);
184      if( UndirEdge(e) != INVALID ) {
185        e.forward = false;
186      }
187      else {
188        Parent::firstOut(e,n);
189        e.forward = true;
190      }
191    }
192    void nextOut(Edge &e) const {
193      if( ! e.forward ) {
194        Node n = Parent::target(e);
195        Parent::nextIn(e);
196        if( UndirEdge(e) == INVALID ) {
197          Parent::firstOut(e, n);
198          e.forward = true;
199        }
200      }
201      else {
202        Parent::nextOut(e);
203      }
204    }
205
206    void firstIn(Edge &e, const Node &n) const {
207      Parent::firstOut(e,n);
208      if( UndirEdge(e) != INVALID ) {
209        e.forward = false;
210      }
211      else {
212        Parent::firstIn(e,n);
213        e.forward = true;
214      }
215    }
216    void nextIn(Edge &e) const {
217      if( ! e.forward ) {
218        Node n = Parent::source(e);
219        Parent::nextOut(e);
220        if( UndirEdge(e) == INVALID ) {
221          Parent::firstIn(e, n);
222          e.forward = true;
223        }
224      }
225      else {
226        Parent::nextIn(e);
227      }
228    }
229
230    void firstInc(UndirEdge &e, const Node &n) const {
231      Parent::firstOut(e, n);
232      if (e != INVALID) return;
233      Parent::firstIn(e, n);
234    }
235    void nextInc(UndirEdge &e, const Node &n) const {
236      if (Parent::source(e) == n) {
237        Parent::nextOut(e);
238        if (e != INVALID) return;
239        Parent::firstIn(e, n);
240      } else {
241        Parent::nextIn(e);
242      }
243    }
244
245    void firstInc(UndirEdge &e, bool &d, const Node &n) const {
246      d = true;
247      Parent::firstOut(e, n);
248      if (e != INVALID) return;
249      d = false;
250      Parent::firstIn(e, n);
251    }
252    void nextInc(UndirEdge &e, bool &d) const {
253      if (d) {
254        Node s = Parent::source(e);
255        Parent::nextOut(e);
256        if (e != INVALID) return;
257        d = false;
258        Parent::firstIn(e, s);
259      } else {
260        Parent::nextIn(e);
261      }
262    }
263
264    // Miscellaneous stuff:
265
266    /// \todo these methods (id, maxEdgeId) should be moved into separate
267    /// Extender
268
269    // using Parent::id;
270    // Using "using" is not a good idea, cause it could be that there is
271    // no "id" in Parent...
272
273    int id(const Node &n) const {
274      return Parent::id(n);
275    }
276
277    int id(const UndirEdge &e) const {
278      return Parent::id(e);
279    }
280
281    int id(const Edge &e) const {
282      return 2 * Parent::id(e) + int(e.forward);
283    }
284
285    int maxNodeId() const {
286      return Parent::maxNodeId();
287    }
288
289    int maxEdgeId() const {
290      return 2 * Parent::maxEdgeId() + 1;
291    }
292
293    int maxUndirEdgeId() const {
294      return Parent::maxEdgeId();
295    }
296
297    int maxId(Node) const {
298      return maxNodeId();
299    }
300
301    int maxId(Edge) const {
302      return maxEdgeId();
303    }
304    int maxId(UndirEdge) const {
305      return maxUndirEdgeId();
306    }
307
308    int edgeNum() const {
309      return 2 * Parent::edgeNum();
310    }
311
312    int undirEdgeNum() const {
313      return Parent::edgeNum();
314    }
315
316    Node nodeFromId(int id) const {
317      return Parent::nodeFromId(id);
318    }
319
320    Edge edgeFromId(int id) const {
321      return direct(Parent::edgeFromId(id >> 1), bool(id & 1));
322    }
323
324    UndirEdge undirEdgeFromId(int id) const {
325      return Parent::edgeFromId(id >> 1);
326    }
327
328    Node fromId(int id, Node) const {
329      return nodeFromId(id);
330    }
331
332    Edge fromId(int id, Edge) const {
333      return edgeFromId(id);
334    }
335
336    UndirEdge fromId(int id, UndirEdge) const {
337      return undirEdgeFromId(id);
338    }
339
340
341    Edge findEdge(Node source, Node target, Edge prev) const {
342      if (prev == INVALID) {
343        UndirEdge edge = Parent::findEdge(source, target);
344        if (edge != INVALID) return direct(edge, true);
345        edge = Parent::findEdge(target, source);
346        if (edge != INVALID) return direct(edge, false);
347      } else if (direction(prev)) {
348        UndirEdge edge = Parent::findEdge(source, target, prev);
349        if (edge != INVALID) return direct(edge, true);
350        edge = Parent::findEdge(target, source);
351        if (edge != INVALID) return direct(edge, false);       
352      } else {
353        UndirEdge edge = Parent::findEdge(target, source, prev);
354        if (edge != INVALID) return direct(edge, false);             
355      }
356      return INVALID;
357    }
358
359    UndirEdge findUndirEdge(Node source, Node target, UndirEdge prev) const {
360      if (prev == INVALID) {
361        UndirEdge edge = Parent::findEdge(source, target);
362        if (edge != INVALID) return edge;
363        edge = Parent::findEdge(target, source);
364        if (edge != INVALID) return edge;
365      } else if (Parent::source(prev) == source) {
366        UndirEdge edge = Parent::findEdge(source, target, prev);
367        if (edge != INVALID) return edge;
368        edge = Parent::findEdge(target, source);
369        if (edge != INVALID) return edge;       
370      } else {
371        UndirEdge edge = Parent::findEdge(target, source, prev);
372        if (edge != INVALID) return edge;             
373      }
374      return INVALID;
375    }
376
377  };
378
379}
380
381#endif // LEMON_UNDIR_GRAPH_EXTENDER_H
Note: See TracBrowser for help on using the repository browser.