236 |
236 |
237 int uEdgeNum() const { |
237 int uEdgeNum() const { |
238 return Parent::edgeNum(); |
238 return Parent::edgeNum(); |
239 } |
239 } |
240 |
240 |
241 Edge findEdge(Node source, Node target, Edge prev = INVALID) const { |
241 Edge findEdge(Node s, Node t, Edge p = INVALID) const { |
242 if (prev == INVALID) { |
242 if (p == INVALID) { |
243 UEdge edge = Parent::findEdge(source, target); |
243 UEdge edge = Parent::findEdge(s, t); |
244 if (edge != INVALID) return direct(edge, true); |
244 if (edge != INVALID) return direct(edge, true); |
245 edge = Parent::findEdge(target, source); |
245 edge = Parent::findEdge(t, s); |
246 if (edge != INVALID) return direct(edge, false); |
246 if (edge != INVALID) return direct(edge, false); |
247 } else if (direction(prev)) { |
247 } else if (direction(p)) { |
248 UEdge edge = Parent::findEdge(source, target, prev); |
248 UEdge edge = Parent::findEdge(s, t, p); |
249 if (edge != INVALID) return direct(edge, true); |
249 if (edge != INVALID) return direct(edge, true); |
250 edge = Parent::findEdge(target, source); |
250 edge = Parent::findEdge(t, s); |
251 if (edge != INVALID) return direct(edge, false); |
251 if (edge != INVALID) return direct(edge, false); |
252 } else { |
252 } else { |
253 UEdge edge = Parent::findEdge(target, source, prev); |
253 UEdge edge = Parent::findEdge(t, s, p); |
254 if (edge != INVALID) return direct(edge, false); |
254 if (edge != INVALID) return direct(edge, false); |
255 } |
255 } |
256 return INVALID; |
256 return INVALID; |
257 } |
257 } |
258 |
258 |
259 UEdge findUEdge(Node source, Node target, UEdge prev = INVALID) const { |
259 UEdge findUEdge(Node s, Node t, UEdge p = INVALID) const { |
260 if (source != target) { |
260 if (s != t) { |
261 if (prev == INVALID) { |
261 if (p == INVALID) { |
262 UEdge edge = Parent::findEdge(source, target); |
262 UEdge edge = Parent::findEdge(s, t); |
263 if (edge != INVALID) return edge; |
263 if (edge != INVALID) return edge; |
264 edge = Parent::findEdge(target, source); |
264 edge = Parent::findEdge(t, s); |
265 if (edge != INVALID) return edge; |
265 if (edge != INVALID) return edge; |
266 } else if (Parent::source(prev) == source) { |
266 } else if (Parent::s(p) == s) { |
267 UEdge edge = Parent::findEdge(source, target, prev); |
267 UEdge edge = Parent::findEdge(s, t, p); |
268 if (edge != INVALID) return edge; |
268 if (edge != INVALID) return edge; |
269 edge = Parent::findEdge(target, source); |
269 edge = Parent::findEdge(t, s); |
270 if (edge != INVALID) return edge; |
270 if (edge != INVALID) return edge; |
271 } else { |
271 } else { |
272 UEdge edge = Parent::findEdge(target, source, prev); |
272 UEdge edge = Parent::findEdge(t, s, p); |
273 if (edge != INVALID) return edge; |
273 if (edge != INVALID) return edge; |
274 } |
274 } |
275 } else { |
275 } else { |
276 return Parent::findEdge(source, target, prev); |
276 return Parent::findEdge(s, t, p); |
277 } |
277 } |
278 return INVALID; |
278 return INVALID; |
279 } |
279 } |
280 }; |
280 }; |
281 |
281 |
355 } |
355 } |
356 Node target(const UEdge& edge) const { |
356 Node target(const UEdge& edge) const { |
357 return bNode(edge); |
357 return bNode(edge); |
358 } |
358 } |
359 |
359 |
360 void firstInc(UEdge& edge, bool& direction, const Node& node) const { |
360 void firstInc(UEdge& edge, bool& dir, const Node& node) const { |
361 if (Parent::aNode(node)) { |
361 if (Parent::aNode(node)) { |
362 Parent::firstFromANode(edge, node); |
362 Parent::firstFromANode(edge, node); |
363 direction = true; |
363 dir = true; |
364 } else { |
364 } else { |
365 Parent::firstFromBNode(edge, node); |
365 Parent::firstFromBNode(edge, node); |
366 direction = static_cast<UEdge&>(edge) == INVALID; |
366 dir = static_cast<UEdge&>(edge) == INVALID; |
367 } |
367 } |
368 } |
368 } |
369 void nextInc(UEdge& edge, bool& direction) const { |
369 void nextInc(UEdge& edge, bool& dir) const { |
370 if (direction) { |
370 if (dir) { |
371 Parent::nextFromANode(edge); |
371 Parent::nextFromANode(edge); |
372 } else { |
372 } else { |
373 Parent::nextFromBNode(edge); |
373 Parent::nextFromBNode(edge); |
374 if (edge == INVALID) direction = true; |
374 if (edge == INVALID) dir = true; |
375 } |
375 } |
376 } |
376 } |
377 |
377 |
378 class Edge : public UEdge { |
378 class Edge : public UEdge { |
379 friend class BidirBpUGraphExtender; |
379 friend class BidirBpUGraphExtender; |
455 |
455 |
456 int id(const Edge& edge) const { |
456 int id(const Edge& edge) const { |
457 return (Parent::id(static_cast<const UEdge&>(edge)) << 1) + |
457 return (Parent::id(static_cast<const UEdge&>(edge)) << 1) + |
458 (edge.forward ? 0 : 1); |
458 (edge.forward ? 0 : 1); |
459 } |
459 } |
460 Edge edgeFromId(int id) const { |
460 Edge edgeFromId(int ix) const { |
461 return Edge(Parent::fromUEdgeId(id >> 1), (id & 1) == 0); |
461 return Edge(Parent::fromUEdgeId(ix >> 1), (ix & 1) == 0); |
462 } |
462 } |
463 int maxEdgeId() const { |
463 int maxEdgeId() const { |
464 return (Parent::maxUEdgeId() << 1) + 1; |
464 return (Parent::maxUEdgeId() << 1) + 1; |
465 } |
465 } |
466 |
466 |
467 bool direction(const Edge& edge) const { |
467 bool direction(const Edge& edge) const { |
468 return edge.forward; |
468 return edge.forward; |
469 } |
469 } |
470 |
470 |
471 Edge direct(const UEdge& edge, bool direction) const { |
471 Edge direct(const UEdge& edge, bool dir) const { |
472 return Edge(edge, direction); |
472 return Edge(edge, dir); |
473 } |
473 } |
474 |
474 |
475 int edgeNum() const { |
475 int edgeNum() const { |
476 return 2 * Parent::uEdgeNum(); |
476 return 2 * Parent::uEdgeNum(); |
477 } |
477 } |