- A primitive function type interface for Preflow.
- A compilation bug fixed
3 * src/lemon/undir_graph_extender.h - Part of LEMON, a generic C++
6 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi
7 * Kutatocsoport (Egervary Combinatorial Optimization Research Group,
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.
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
20 #ifndef LEMON_UNDIR_GRAPH_EXTENDER_H
21 #define LEMON_UNDIR_GRAPH_EXTENDER_H
23 #include <lemon/invalid.h>
27 template <typename _Base>
28 class UndirGraphExtender : public _Base {
30 typedef UndirGraphExtender Graph;
34 typedef typename Parent::Edge UndirEdge;
35 typedef typename Parent::Node Node;
37 class Edge : public UndirEdge {
38 friend class UndirGraphExtender;
41 // FIXME: Marci use opposite logic in his graph wrappers. It would
42 // be reasonable to syncronize...
48 /// \brief Directed edge from undirected edge and a direction.
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) {}
55 /// \brief Directed edge from undirected edge and a source node.
57 /// Constructs a directed edge from undirected edge and a source node.
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); }
63 /// Invalid edge constructor
64 Edge(Invalid i) : UndirEdge(i), forward(true) {}
66 bool operator==(const Edge &that) const {
67 return forward==that.forward && UndirEdge(*this)==UndirEdge(that);
69 bool operator!=(const Edge &that) const {
70 return forward!=that.forward || UndirEdge(*this)!=UndirEdge(that);
72 bool operator<(const Edge &that) const {
73 return forward<that.forward ||
74 (!(that.forward<forward) && UndirEdge(*this)<UndirEdge(that));
79 /// \brief Edge of opposite direction.
81 /// Returns the Edge of opposite direction.
82 Edge opposite(const Edge &e) const {
83 return Edge(e,!e.forward);
89 Node _dirSource(const E &e) const {
90 return e.forward ? Parent::source(e) : Parent::target(e);
94 Node _dirTarget(const E &e) const {
95 return e.forward ? Parent::target(e) : Parent::source(e);
99 /// \todo Shouldn't the "source" of an undirected edge be called "aNode"
101 using Parent::source;
103 /// Source of the given Edge.
104 Node source(const Edge &e) const {
105 return _dirSource(e);
108 /// \todo Shouldn't the "target" of an undirected edge be called "bNode"
110 using Parent::target;
112 /// Target of the given Edge.
113 Node target(const Edge &e) const {
114 return _dirTarget(e);
117 /// Returns whether the given directed edge is same orientation as the
118 /// corresponding undirected edge.
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; }
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);
133 /// Directed edge from an undirected edge and a source node.
135 /// Returns a (directed) Edge corresponding to the specified UndirEdge
138 ///\todo Do we need this?
140 ///\todo Better name...
141 Edge edgeWithSource(const UndirEdge &ue, const Node &s) const {
142 return Edge(*this, ue, s);
146 void first(Edge &e) const {
152 void next(Edge &e) const {
165 template <typename E>
166 void _dirFirstOut(E &e, const Node &n) const {
167 Parent::firstIn(e,n);
168 if( UndirEdge(e) != INVALID ) {
172 Parent::firstOut(e,n);
176 template <typename E>
177 void _dirFirstIn(E &e, const Node &n) const {
178 Parent::firstOut(e,n);
179 if( UndirEdge(e) != INVALID ) {
183 Parent::firstIn(e,n);
188 template <typename E>
189 void _dirNextOut(E &e) const {
191 Node n = Parent::target(e);
193 if( UndirEdge(e) == INVALID ) {
194 Parent::firstOut(e, n);
202 template <typename E>
203 void _dirNextIn(E &e) const {
205 Node n = Parent::source(e);
207 if( UndirEdge(e) == INVALID ) {
208 Parent::firstIn(e, n);
219 void firstOut(Edge &e, const Node &n) const {
222 void firstIn(Edge &e, const Node &n) const {
226 void nextOut(Edge &e) const {
229 void nextIn(Edge &e) const {
233 // Miscellaneous stuff:
235 /// \todo these methods (id, maxEdgeId) should be moved into separate
239 // Using "using" is not a good idea, cause it could be that there is
240 // no "id" in Parent...
242 int id(const Node &n) const {
243 return Parent::id(n);
246 int id(const UndirEdge &e) const {
247 return Parent::id(e);
250 int id(const Edge &e) const {
251 return 2 * Parent::id(e) + int(e.forward);
255 int maxId(Node) const {
256 return Parent::maxId(Node());
259 int maxId(Edge) const {
260 return 2 * Parent::maxId(typename Parent::Edge()) + 1;
262 int maxId(UndirEdge) const {
263 return Parent::maxId(typename Parent::Edge());
267 int edgeNum() const {
268 return 2 * Parent::edgeNum();
270 int undirEdgeNum() const {
271 return Parent::edgeNum();
278 #endif // LEMON_UNDIR_GRAPH_EXTENDER_H