COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/undir_graph_extender.h @ 963:5a7556e9e340

Last change on this file since 963:5a7556e9e340 was 962:1a770e9f80b2, checked in by Mihaly Barasz, 20 years ago

Undirect graph implementation.
Not yet done, untested.

File size: 4.6 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 Graph;
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    /// Tail of the given Edge.
74    Node tail(const Edge &e) const {
75      return e.forward ? Parent::tail(e) : Parent::head(e);
76    }
77
78    /// \todo Shouldn't the "tail" of an undirected edge be called "aNode"
79    /// or something???
80    using Parent::tail;
81
82    /// Head of the given Edge.
83    Node head(const Edge &e) const {
84      return e.forward ? Parent::head(e) : Parent::tail(e);
85    }
86
87    /// \todo Shouldn't the "head" of an undirected edge be called "bNode"
88    /// or something???
89    using Parent::head;
90
91    /// Returns whether the given directed edge is same orientation as the
92    /// corresponding undirected edge.
93    ///
94    /// \todo reference to the corresponding point of the undirected graph
95    /// concept. "What does the direction of an undirected edge mean?"
96    bool forward(const Edge &e) const { return e.forward; }
97
98    Node oppsiteNode(const Node &n, const Edge &e) const {
99      if( n == Parent::tail(e))
100        return Parent::head(e);
101      else if( n == Parent::head(e))
102        return Parent::tail(e);
103      else
104        return INVALID;
105    }
106
107
108    using Parent::first;
109    void first(Edge &e) const {
110      Parent::first(e);
111      e.forward=true;
112    }
113
114    using Parent::next;
115    void next(Edge &e) const {
116      if( e.forward ) {
117        e.forward = false;
118      }
119      else {
120        Parent::next(e);
121        e.forward = true;
122      }
123    }
124
125    void firstOut(Edge &e, const Node &n) const {
126      Parent::firstOut(e,n);
127      if( UndirEdge(e) != INVALID ) {
128        e.forward = true;
129      }
130      else {
131        Parent::firstIn(e,n);
132        e.forward = false;
133      }
134    }
135    void firstIn(Edge &e, const Node &n) const {
136      Parent::firstIn(e,n);
137      if( UndirEdge(e) != INVALID ) {
138        e.forward = true;
139      }
140      else {
141        Parent::firstOut(e,n);
142        e.forward = false;
143      }
144    }
145
146    void nextOut(Edge &e) const {
147      if( e.forward ) {
148        Parent::nextOut(e);
149        if( UndirEdge(e) == INVALID ) {
150          Parent::firstIn(e, Parent::tail(e));
151          e.forward = false;
152        }
153      }
154      else {
155        Parent::nextIn(e);
156      }
157    }
158    void nextIn(Edge &e) const {
159      if( e.forward ) {
160        Parent::nextIn(e);
161        if( UndirEdge(e) == INVALID ) {
162          Parent::firstOut(e, Parent::head(e));
163          e.forward = false;
164        }
165      }
166      else {
167        Parent::nextOut(e);
168      }
169    }
170
171    // Miscellaneous stuff:
172
173    /// \todo these methods (id, maxEdgeId) should be moved into separate
174    /// Extender
175
176    using Parent::id;
177
178    int id(const Edge &e) const {
179      return 2*Parent::id(e) + int(e.forward);
180    }
181
182    int maxEdgeId() const {
183      return 2*Parent::maxEdgeId() + 1;
184    }
185    int maxUndirEdgeId() const {
186      return Parent::maxEdgeId();
187    }
188
189  };
190
191}
192
193#endif // LEMON_UNDIR_GRAPH_EXTENDER_H
Note: See TracBrowser for help on using the repository browser.