1 /* -*- C++ -*- |
|
2 * |
|
3 * src/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 |
|
25 namespace 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 |
|