277 } |
277 } |
278 return INVALID; |
278 return INVALID; |
279 } |
279 } |
280 }; |
280 }; |
281 |
281 |
|
282 template <typename Base> |
|
283 class BidirBpUGraphExtender : public Base { |
|
284 public: |
|
285 typedef Base Parent; |
|
286 typedef BidirBpUGraphExtender Graph; |
|
287 |
|
288 typedef typename Parent::Node Node; |
|
289 typedef typename Parent::UEdge UEdge; |
|
290 |
|
291 |
|
292 using Parent::first; |
|
293 using Parent::next; |
|
294 |
|
295 using Parent::id; |
|
296 |
|
297 class ANode : public Node { |
|
298 friend class BidirBpUGraphExtender; |
|
299 public: |
|
300 ANode() {} |
|
301 ANode(const Node& node) : Node(node) { |
|
302 LEMON_ASSERT(Parent::aNode(node) || node == INVALID, |
|
303 typename Parent::NodeSetError()); |
|
304 } |
|
305 ANode& operator=(const Node& node) { |
|
306 LEMON_ASSERT(Parent::aNode(node) || node == INVALID, |
|
307 typename Parent::NodeSetError()); |
|
308 Node::operator=(node); |
|
309 return *this; |
|
310 } |
|
311 ANode(Invalid) : Node(INVALID) {} |
|
312 }; |
|
313 |
|
314 void first(ANode& node) const { |
|
315 Parent::firstANode(static_cast<Node&>(node)); |
|
316 } |
|
317 void next(ANode& node) const { |
|
318 Parent::nextANode(static_cast<Node&>(node)); |
|
319 } |
|
320 |
|
321 int id(const ANode& node) const { |
|
322 return Parent::aNodeId(node); |
|
323 } |
|
324 |
|
325 class BNode : public Node { |
|
326 friend class BidirBpUGraphExtender; |
|
327 public: |
|
328 BNode() {} |
|
329 BNode(const Node& node) : Node(node) { |
|
330 LEMON_ASSERT(Parent::bNode(node) || node == INVALID, |
|
331 typename Parent::NodeSetError()); |
|
332 } |
|
333 BNode& operator=(const Node& node) { |
|
334 LEMON_ASSERT(Parent::bNode(node) || node == INVALID, |
|
335 typename Parent::NodeSetError()); |
|
336 Node::operator=(node); |
|
337 return *this; |
|
338 } |
|
339 BNode(Invalid) : Node(INVALID) {} |
|
340 }; |
|
341 |
|
342 void first(BNode& node) const { |
|
343 Parent::firstBNode(static_cast<Node&>(node)); |
|
344 } |
|
345 void next(BNode& node) const { |
|
346 Parent::nextBNode(static_cast<Node&>(node)); |
|
347 } |
|
348 |
|
349 int id(const BNode& node) const { |
|
350 return Parent::aNodeId(node); |
|
351 } |
|
352 |
|
353 Node source(const UEdge& edge) const { |
|
354 return aNode(edge); |
|
355 } |
|
356 Node target(const UEdge& edge) const { |
|
357 return bNode(edge); |
|
358 } |
|
359 |
|
360 void firstInc(UEdge& edge, bool& direction, const Node& node) const { |
|
361 if (Parent::aNode(node)) { |
|
362 Parent::firstFromANode(edge, node); |
|
363 direction = true; |
|
364 } else { |
|
365 Parent::firstFromBNode(edge, node); |
|
366 direction = static_cast<UEdge&>(edge) == INVALID; |
|
367 } |
|
368 } |
|
369 void nextInc(UEdge& edge, bool& direction) const { |
|
370 if (direction) { |
|
371 Parent::nextFromANode(edge); |
|
372 } else { |
|
373 Parent::nextFromBNode(edge); |
|
374 if (edge == INVALID) direction = true; |
|
375 } |
|
376 } |
|
377 |
|
378 class Edge : public UEdge { |
|
379 friend class BidirBpUGraphExtender; |
|
380 protected: |
|
381 bool forward; |
|
382 |
|
383 Edge(const UEdge& edge, bool _forward) |
|
384 : UEdge(edge), forward(_forward) {} |
|
385 |
|
386 public: |
|
387 Edge() {} |
|
388 Edge (Invalid) : UEdge(INVALID), forward(true) {} |
|
389 bool operator==(const Edge& i) const { |
|
390 return UEdge::operator==(i) && forward == i.forward; |
|
391 } |
|
392 bool operator!=(const Edge& i) const { |
|
393 return UEdge::operator!=(i) || forward != i.forward; |
|
394 } |
|
395 bool operator<(const Edge& i) const { |
|
396 return UEdge::operator<(i) || |
|
397 (!(i.forward<forward) && UEdge(*this)<UEdge(i)); |
|
398 } |
|
399 }; |
|
400 |
|
401 void first(Edge& edge) const { |
|
402 Parent::first(static_cast<UEdge&>(edge)); |
|
403 edge.forward = true; |
|
404 } |
|
405 |
|
406 void next(Edge& edge) const { |
|
407 if (!edge.forward) { |
|
408 Parent::next(static_cast<UEdge&>(edge)); |
|
409 } |
|
410 edge.forward = !edge.forward; |
|
411 } |
|
412 |
|
413 void firstOut(Edge& edge, const Node& node) const { |
|
414 if (Parent::aNode(node)) { |
|
415 Parent::firstFromANode(edge, node); |
|
416 edge.forward = true; |
|
417 } else { |
|
418 Parent::firstFromBNode(edge, node); |
|
419 edge.forward = static_cast<UEdge&>(edge) == INVALID; |
|
420 } |
|
421 } |
|
422 void nextOut(Edge& edge) const { |
|
423 if (edge.forward) { |
|
424 Parent::nextFromANode(edge); |
|
425 } else { |
|
426 Parent::nextFromBNode(edge); |
|
427 edge.forward = static_cast<UEdge&>(edge) == INVALID; |
|
428 } |
|
429 } |
|
430 |
|
431 void firstIn(Edge& edge, const Node& node) const { |
|
432 if (Parent::bNode(node)) { |
|
433 Parent::firstFromBNode(edge, node); |
|
434 edge.forward = true; |
|
435 } else { |
|
436 Parent::firstFromANode(edge, node); |
|
437 edge.forward = static_cast<UEdge&>(edge) == INVALID; |
|
438 } |
|
439 } |
|
440 void nextIn(Edge& edge) const { |
|
441 if (edge.forward) { |
|
442 Parent::nextFromBNode(edge); |
|
443 } else { |
|
444 Parent::nextFromANode(edge); |
|
445 edge.forward = static_cast<UEdge&>(edge) == INVALID; |
|
446 } |
|
447 } |
|
448 |
|
449 Node source(const Edge& edge) const { |
|
450 return edge.forward ? Parent::aNode(edge) : Parent::bNode(edge); |
|
451 } |
|
452 Node target(const Edge& edge) const { |
|
453 return edge.forward ? Parent::bNode(edge) : Parent::aNode(edge); |
|
454 } |
|
455 |
|
456 int id(const Edge& edge) const { |
|
457 return (Parent::id(static_cast<const UEdge&>(edge)) << 1) + |
|
458 (edge.forward ? 0 : 1); |
|
459 } |
|
460 Edge edgeFromId(int id) const { |
|
461 return Edge(Parent::fromUEdgeId(id >> 1), (id & 1) == 0); |
|
462 } |
|
463 int maxEdgeId() const { |
|
464 return (Parent::maxUEdgeId() << 1) + 1; |
|
465 } |
|
466 |
|
467 bool direction(const Edge& edge) const { |
|
468 return edge.forward; |
|
469 } |
|
470 |
|
471 Edge direct(const UEdge& edge, bool direction) const { |
|
472 return Edge(edge, direction); |
|
473 } |
|
474 |
|
475 int edgeNum() const { |
|
476 return 2 * Parent::uEdgeNum(); |
|
477 } |
|
478 |
|
479 int uEdgeNum() const { |
|
480 return Parent::uEdgeNum(); |
|
481 } |
|
482 |
|
483 |
|
484 }; |
282 } |
485 } |
283 |
486 |
284 #endif |
487 #endif |