374 return INVALID; |
375 return INVALID; |
375 } |
376 } |
376 |
377 |
377 }; |
378 }; |
378 |
379 |
|
380 |
|
381 template <typename _Base> |
|
382 class UndirBipartiteGraphExtender : public _Base { |
|
383 public: |
|
384 typedef _Base Parent; |
|
385 typedef UndirBipartiteGraphExtender Graph; |
|
386 |
|
387 typedef typename Parent::Node Node; |
|
388 typedef typename Parent::Edge UndirEdge; |
|
389 |
|
390 using Parent::first; |
|
391 using Parent::next; |
|
392 |
|
393 using Parent::id; |
|
394 |
|
395 Node source(const UndirEdge& edge) const { |
|
396 return upperNode(edge); |
|
397 } |
|
398 Node target(const UndirEdge& edge) const { |
|
399 return lowerNode(edge); |
|
400 } |
|
401 |
|
402 void firstInc(UndirEdge& edge, bool& direction, const Node& node) const { |
|
403 if (Parent::upper(node)) { |
|
404 Parent::firstDown(edge, node); |
|
405 direction = true; |
|
406 } else { |
|
407 Parent::firstUp(edge, node); |
|
408 direction = static_cast<UndirEdge&>(edge) == INVALID; |
|
409 } |
|
410 } |
|
411 void nextInc(UndirEdge& edge, bool& direction) const { |
|
412 if (direction) { |
|
413 Parent::nextDown(edge); |
|
414 } else { |
|
415 Parent::nextUp(edge); |
|
416 if (edge == INVALID) direction = true; |
|
417 } |
|
418 } |
|
419 |
|
420 int maxUndirEdgeId() const { |
|
421 return Parent::maxEdgeId(); |
|
422 } |
|
423 |
|
424 UndirEdge undirEdgeFromId(int id) const { |
|
425 return Parent::edgeFromId(id); |
|
426 } |
|
427 |
|
428 class Edge : public UndirEdge { |
|
429 friend class UndirBipartiteGraphExtender; |
|
430 protected: |
|
431 bool forward; |
|
432 |
|
433 Edge(const UndirEdge& edge, bool _forward) |
|
434 : UndirEdge(edge), forward(_forward) {} |
|
435 |
|
436 public: |
|
437 Edge() {} |
|
438 Edge (Invalid) : UndirEdge(INVALID), forward(true) {} |
|
439 bool operator==(const Edge& i) const { |
|
440 return UndirEdge::operator==(i) && forward == i.forward; |
|
441 } |
|
442 bool operator!=(const Edge& i) const { |
|
443 return UndirEdge::operator!=(i) || forward != i.forward; |
|
444 } |
|
445 bool operator<(const Edge& i) const { |
|
446 return UndirEdge::operator<(i) || |
|
447 (!(i.forward<forward) && UndirEdge(*this)<UndirEdge(i)); |
|
448 } |
|
449 }; |
|
450 |
|
451 void first(Edge& edge) const { |
|
452 Parent::first(static_cast<UndirEdge&>(edge)); |
|
453 edge.forward = true; |
|
454 } |
|
455 |
|
456 void next(Edge& edge) const { |
|
457 if (!edge.forward) { |
|
458 Parent::next(static_cast<UndirEdge&>(edge)); |
|
459 } |
|
460 edge.forward = !edge.forward; |
|
461 } |
|
462 |
|
463 void firstOut(Edge& edge, const Node& node) const { |
|
464 if (Parent::upper(node)) { |
|
465 Parent::firstDown(edge, node); |
|
466 edge.forward = true; |
|
467 } else { |
|
468 Parent::firstUp(edge, node); |
|
469 edge.forward = static_cast<UndirEdge&>(edge) == INVALID; |
|
470 } |
|
471 } |
|
472 void nextOut(Edge& edge) const { |
|
473 if (edge.forward) { |
|
474 Parent::nextDown(edge); |
|
475 } else { |
|
476 Parent::nextUp(edge); |
|
477 if (edge == INVALID) { |
|
478 edge.forward = true; |
|
479 } |
|
480 } |
|
481 } |
|
482 |
|
483 void firstIn(Edge& edge, const Node& node) const { |
|
484 if (Parent::lower(node)) { |
|
485 Parent::firstUp(edge, node); |
|
486 edge.forward = true; |
|
487 } else { |
|
488 Parent::firstDown(edge, node); |
|
489 edge.forward = static_cast<UndirEdge&>(edge) == INVALID; |
|
490 } |
|
491 } |
|
492 void nextIn(Edge& edge) const { |
|
493 if (edge.forward) { |
|
494 Parent::nextUp(edge); |
|
495 } else { |
|
496 Parent::nextDown(edge); |
|
497 if (edge == INVALID) { |
|
498 edge.forward = true; |
|
499 } |
|
500 } |
|
501 } |
|
502 |
|
503 Node source(const Edge& edge) const { |
|
504 return edge.forward ? Parent::upperNode(edge) : Parent::lowerNode(edge); |
|
505 } |
|
506 Node target(const Edge& edge) const { |
|
507 return edge.forward ? Parent::lowerNode(edge) : Parent::upperNode(edge); |
|
508 } |
|
509 |
|
510 bool direction(const Edge& edge) const { |
|
511 return edge.forward; |
|
512 } |
|
513 |
|
514 Edge direct(const UndirEdge& edge, const Node& node) const { |
|
515 return Edge(edge, node == Parent::source(edge)); |
|
516 } |
|
517 |
|
518 Edge direct(const UndirEdge& edge, bool direction) const { |
|
519 return Edge(edge, direction); |
|
520 } |
|
521 |
|
522 Node oppositeNode(const UndirEdge& edge, const Node& node) const { |
|
523 return source(edge) == node ? |
|
524 target(edge) : source(edge); |
|
525 } |
|
526 |
|
527 Edge oppositeEdge(const Edge& edge) const { |
|
528 return Edge(edge, !edge.forward); |
|
529 } |
|
530 |
|
531 int id(const Edge& edge) const { |
|
532 return (Parent::id(edge) << 1) + (edge.forward ? 0 : 1); |
|
533 } |
|
534 Edge edgeFromId(int id) const { |
|
535 return Edge(Parent::fromId(id >> 1, UndirEdge()), (id & 1) == 0); |
|
536 } |
|
537 int maxEdgeId() const { |
|
538 return (Parent::maxId(UndirEdge()) << 1) + 1; |
|
539 } |
|
540 |
|
541 class UpperNode : public Node { |
|
542 friend class UndirBipartiteGraphExtender; |
|
543 public: |
|
544 UpperNode() {} |
|
545 UpperNode(const Node& node) : Node(node) { |
|
546 LEMON_ASSERT(Parent::upper(node) || node == INVALID, |
|
547 typename Parent::NodeSetError()); |
|
548 } |
|
549 UpperNode(Invalid) : Node(INVALID) {} |
|
550 }; |
|
551 |
|
552 void first(UpperNode& node) const { |
|
553 Parent::firstUpper(static_cast<Node&>(node)); |
|
554 } |
|
555 void next(UpperNode& node) const { |
|
556 Parent::nextUpper(static_cast<Node&>(node)); |
|
557 } |
|
558 |
|
559 int id(const UpperNode& node) const { |
|
560 return Parent::upperId(node); |
|
561 } |
|
562 |
|
563 class LowerNode : public Node { |
|
564 friend class UndirBipartiteGraphExtender; |
|
565 public: |
|
566 LowerNode() {} |
|
567 LowerNode(const Node& node) : Node(node) { |
|
568 LEMON_ASSERT(Parent::lower(node) || node == INVALID, |
|
569 typename Parent::NodeSetError()); |
|
570 } |
|
571 LowerNode(Invalid) : Node(INVALID) {} |
|
572 }; |
|
573 |
|
574 void first(LowerNode& node) const { |
|
575 Parent::firstLower(static_cast<Node&>(node)); |
|
576 } |
|
577 void next(LowerNode& node) const { |
|
578 Parent::nextLower(static_cast<Node&>(node)); |
|
579 } |
|
580 |
|
581 int id(const LowerNode& node) const { |
|
582 return Parent::upperId(node); |
|
583 } |
|
584 |
|
585 |
|
586 |
|
587 int maxId(Node) const { |
|
588 return Parent::maxNodeId(); |
|
589 } |
|
590 int maxId(LowerNode) const { |
|
591 return Parent::maxLowerId(); |
|
592 } |
|
593 int maxId(UpperNode) const { |
|
594 return Parent::maxUpperId(); |
|
595 } |
|
596 int maxId(Edge) const { |
|
597 return maxEdgeId(); |
|
598 } |
|
599 int maxId(UndirEdge) const { |
|
600 return maxUndirEdgeId(); |
|
601 } |
|
602 |
|
603 |
|
604 Node fromId(int id, Node) const { |
|
605 return Parent::nodeFromId(id); |
|
606 } |
|
607 UpperNode fromId(int id, UpperNode) const { |
|
608 return Parent::fromUpperId(id); |
|
609 } |
|
610 LowerNode fromId(int id, LowerNode) const { |
|
611 return Parent::fromLowerId(id); |
|
612 } |
|
613 Edge fromId(int id, Edge) const { |
|
614 return edgeFromId(id); |
|
615 } |
|
616 UndirEdge fromId(int id, UndirEdge) const { |
|
617 return undirEdgeFromId(id); |
|
618 } |
|
619 |
|
620 }; |
|
621 |
379 } |
622 } |
380 |
623 |
381 #endif // LEMON_UNDIR_GRAPH_EXTENDER_H |
624 #endif // LEMON_UNDIR_GRAPH_EXTENDER_H |