69 /// Returns the Edge of opposite direction. |
69 /// Returns the Edge of opposite direction. |
70 Edge oppositeEdge(const Edge &e) const { |
70 Edge oppositeEdge(const Edge &e) const { |
71 return Edge(e,!e.forward); |
71 return Edge(e,!e.forward); |
72 } |
72 } |
73 |
73 |
74 protected: |
|
75 |
|
76 template <typename E> |
|
77 Node _dirSource(const E &e) const { |
|
78 return e.forward ? Parent::source(e) : Parent::target(e); |
|
79 } |
|
80 |
|
81 template <typename E> |
|
82 Node _dirTarget(const E &e) const { |
|
83 return e.forward ? Parent::target(e) : Parent::source(e); |
|
84 } |
|
85 |
|
86 public: |
74 public: |
87 /// \todo Shouldn't the "source" of an undirected edge be called "aNode" |
75 /// \todo Shouldn't the "source" of an undirected edge be called "aNode" |
88 /// or something??? |
76 /// or something??? |
89 using Parent::source; |
77 using Parent::source; |
90 |
78 |
91 /// Source of the given Edge. |
79 /// Source of the given Edge. |
92 Node source(const Edge &e) const { |
80 Node source(const Edge &e) const { |
93 return _dirSource(e); |
81 return e.forward ? Parent::source(e) : Parent::target(e); |
94 } |
82 } |
95 |
83 |
96 /// \todo Shouldn't the "target" of an undirected edge be called "bNode" |
84 /// \todo Shouldn't the "target" of an undirected edge be called "bNode" |
97 /// or something??? |
85 /// or something??? |
98 using Parent::target; |
86 using Parent::target; |
99 |
87 |
100 /// Target of the given Edge. |
88 /// Target of the given Edge. |
101 Node target(const Edge &e) const { |
89 Node target(const Edge &e) const { |
102 return _dirTarget(e); |
90 return e.forward ? Parent::target(e) : Parent::source(e); |
103 } |
91 } |
104 |
92 |
105 Node oppositeNode(const Node &n, const UndirEdge &e) const { |
93 Node oppositeNode(const Node &n, const UndirEdge &e) const { |
106 if( n == Parent::source(e)) |
94 if( n == Parent::source(e)) |
107 return Parent::target(e); |
95 return Parent::target(e); |
152 Parent::next(e); |
140 Parent::next(e); |
153 e.forward = true; |
141 e.forward = true; |
154 } |
142 } |
155 } |
143 } |
156 |
144 |
157 |
145 public: |
158 protected: |
146 |
159 |
147 void firstOut(Edge &e, const Node &n) const { |
160 template <typename E> |
|
161 void _dirFirstOut(E &e, const Node &n) const { |
|
162 Parent::firstIn(e,n); |
148 Parent::firstIn(e,n); |
163 if( UndirEdge(e) != INVALID ) { |
149 if( UndirEdge(e) != INVALID ) { |
164 e.forward = false; |
150 e.forward = false; |
165 } |
151 } |
166 else { |
152 else { |
167 Parent::firstOut(e,n); |
153 Parent::firstOut(e,n); |
168 e.forward = true; |
154 e.forward = true; |
169 } |
155 } |
170 } |
156 } |
171 template <typename E> |
157 void nextOut(Edge &e) const { |
172 void _dirFirstIn(E &e, const Node &n) const { |
|
173 Parent::firstOut(e,n); |
|
174 if( UndirEdge(e) != INVALID ) { |
|
175 e.forward = false; |
|
176 } |
|
177 else { |
|
178 Parent::firstIn(e,n); |
|
179 e.forward = true; |
|
180 } |
|
181 } |
|
182 |
|
183 template <typename E> |
|
184 void _dirNextOut(E &e) const { |
|
185 if( ! e.forward ) { |
158 if( ! e.forward ) { |
186 Node n = Parent::target(e); |
159 Node n = Parent::target(e); |
187 Parent::nextIn(e); |
160 Parent::nextIn(e); |
188 if( UndirEdge(e) == INVALID ) { |
161 if( UndirEdge(e) == INVALID ) { |
189 Parent::firstOut(e, n); |
162 Parent::firstOut(e, n); |
192 } |
165 } |
193 else { |
166 else { |
194 Parent::nextOut(e); |
167 Parent::nextOut(e); |
195 } |
168 } |
196 } |
169 } |
197 template <typename E> |
170 |
198 void _dirNextIn(E &e) const { |
171 void firstIn(Edge &e, const Node &n) const { |
|
172 Parent::firstOut(e,n); |
|
173 if( UndirEdge(e) != INVALID ) { |
|
174 e.forward = false; |
|
175 } |
|
176 else { |
|
177 Parent::firstIn(e,n); |
|
178 e.forward = true; |
|
179 } |
|
180 } |
|
181 void nextIn(Edge &e) const { |
199 if( ! e.forward ) { |
182 if( ! e.forward ) { |
200 Node n = Parent::source(e); |
183 Node n = Parent::source(e); |
201 Parent::nextOut(e); |
184 Parent::nextOut(e); |
202 if( UndirEdge(e) == INVALID ) { |
185 if( UndirEdge(e) == INVALID ) { |
203 Parent::firstIn(e, n); |
186 Parent::firstIn(e, n); |
207 else { |
190 else { |
208 Parent::nextIn(e); |
191 Parent::nextIn(e); |
209 } |
192 } |
210 } |
193 } |
211 |
194 |
212 public: |
195 void firstInc(UndirEdge &e, const Node &n) const { |
213 |
196 Parent::firstOut(e, n); |
214 void firstOut(Edge &e, const Node &n) const { |
197 if (e != INVALID) return; |
215 _dirFirstOut(e, n); |
198 Parent::firstIn(e, n); |
216 } |
199 } |
217 void firstIn(Edge &e, const Node &n) const { |
200 void nextInc(UndirEdge &e, const Node &n) const { |
218 _dirFirstIn(e, n); |
201 if (Parent::source(e) == n) { |
219 } |
202 Parent::nextOut(e); |
220 |
203 if (e != INVALID) return; |
221 void nextOut(Edge &e) const { |
204 Parent::firstIn(e, n); |
222 _dirNextOut(e); |
205 } else { |
223 } |
206 Parent::nextIn(e); |
224 void nextIn(Edge &e) const { |
207 } |
225 _dirNextIn(e); |
208 } |
|
209 |
|
210 void firstInc(UndirEdge &e, bool &d, const Node &n) const { |
|
211 d = true; |
|
212 Parent::firstOut(e, n); |
|
213 if (e != INVALID) return; |
|
214 d = false; |
|
215 Parent::firstIn(e, n); |
|
216 } |
|
217 void nextInc(UndirEdge &e, bool &d) const { |
|
218 if (d) { |
|
219 Node s = Parent::source(e); |
|
220 Parent::nextOut(e); |
|
221 if (e != INVALID) return; |
|
222 d = false; |
|
223 Parent::firstIn(e, s); |
|
224 } else { |
|
225 Parent::nextIn(e); |
|
226 } |
226 } |
227 } |
227 |
228 |
228 // Miscellaneous stuff: |
229 // Miscellaneous stuff: |
229 |
230 |
230 /// \todo these methods (id, maxEdgeId) should be moved into separate |
231 /// \todo these methods (id, maxEdgeId) should be moved into separate |
260 |
261 |
261 |
262 |
262 int edgeNum() const { |
263 int edgeNum() const { |
263 return 2 * Parent::edgeNum(); |
264 return 2 * Parent::edgeNum(); |
264 } |
265 } |
|
266 |
265 int undirEdgeNum() const { |
267 int undirEdgeNum() const { |
266 return Parent::edgeNum(); |
268 return Parent::edgeNum(); |
267 } |
269 } |
268 |
270 |
|
271 Edge findEdge(Node source, Node target, Edge prev) const { |
|
272 if (prev == INVALID) { |
|
273 UndirEdge edge = Parent::findEdge(source, target); |
|
274 if (edge != INVALID) return direct(edge, true); |
|
275 edge = Parent::findEdge(target, source); |
|
276 if (edge != INVALID) return direct(edge, false); |
|
277 } else if (direction(prev)) { |
|
278 UndirEdge edge = Parent::findEdge(source, target, prev); |
|
279 if (edge != INVALID) return direct(edge, true); |
|
280 edge = Parent::findEdge(target, source); |
|
281 if (edge != INVALID) return direct(edge, false); |
|
282 } else { |
|
283 UndirEdge edge = Parent::findEdge(target, source, prev); |
|
284 if (edge != INVALID) return direct(edge, false); |
|
285 } |
|
286 return INVALID; |
|
287 } |
|
288 |
|
289 UndirEdge findUndirEdge(Node source, Node target, UndirEdge prev) const { |
|
290 if (prev == INVALID) { |
|
291 UndirEdge edge = Parent::findEdge(source, target); |
|
292 if (edge != INVALID) return edge; |
|
293 edge = Parent::findEdge(target, source); |
|
294 if (edge != INVALID) return edge; |
|
295 } else if (Parent::source(prev) == source) { |
|
296 UndirEdge edge = Parent::findEdge(source, target, prev); |
|
297 if (edge != INVALID) return edge; |
|
298 edge = Parent::findEdge(target, source); |
|
299 if (edge != INVALID) return edge; |
|
300 } else { |
|
301 UndirEdge edge = Parent::findEdge(target, source, prev); |
|
302 if (edge != INVALID) return edge; |
|
303 } |
|
304 return INVALID; |
|
305 } |
|
306 |
269 }; |
307 }; |
270 |
308 |
271 } |
309 } |
272 |
310 |
273 #endif // LEMON_UNDIR_GRAPH_EXTENDER_H |
311 #endif // LEMON_UNDIR_GRAPH_EXTENDER_H |