407 } |
403 } |
408 }; |
404 }; |
409 |
405 |
410 using Parent::forward; |
406 using Parent::forward; |
411 using Parent::backward; |
407 using Parent::backward; |
412 bool forward(const Edge& e) const { return !e.backward; } |
408 using Parent::setForward; |
413 bool backward(const Edge& e) const { return e.backward; } |
409 using Parent::setBackward; |
414 |
410 static bool forward(const Edge& e) { return !e.backward; } |
415 using Parent::first; |
411 static bool backward(const Edge& e) { return e.backward; } |
416 void first(Edge& i) const { |
412 static void setForward(Edge& e) { e.backward=false; } |
417 Parent1::graph->first(*static_cast<Graph1Edge*>(&i)); |
413 static void setBackward(Edge& e) { e.backward=true; } |
418 i.backward=false; |
414 }; |
419 if (*static_cast<Graph1Edge*>(&i)==INVALID) { |
415 |
420 Parent2::graph->first(*static_cast<Graph2Edge*>(&i)); |
|
421 i.backward=true; |
|
422 } |
|
423 } |
|
424 void firstIn(Edge& i, const Node& n) const { |
|
425 if (!backward(n)) { |
|
426 Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n); |
|
427 if (*static_cast<Graph1Edge*>(&i)==INVALID) |
|
428 i=INVALID; |
|
429 else |
|
430 i.backward=false; |
|
431 } else { |
|
432 Parent2::graph->firstIn(*static_cast<Graph2Edge*>(&i), n); |
|
433 i.backward=true; |
|
434 } |
|
435 } |
|
436 void firstOut(Edge& i, const Node& n) const { |
|
437 if (!backward(n)) { |
|
438 Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n); |
|
439 if (*static_cast<Graph1Edge*>(&i)==INVALID) |
|
440 i=INVALID; |
|
441 else |
|
442 i.backward=false; |
|
443 } else { |
|
444 Parent2::graph->firstOut(*static_cast<Graph2Edge*>(&i), n); |
|
445 i.backward=true; |
|
446 } |
|
447 } |
|
448 |
|
449 using Parent::next; |
|
450 void next(Edge& i) const { |
|
451 if (!(i.backward)) { |
|
452 Parent1::graph->next(*static_cast<Graph1Edge*>(&i)); |
|
453 if (*static_cast<Graph1Edge*>(&i)==INVALID) { |
|
454 Parent2::graph->first(*static_cast<Graph2Edge*>(&i)); |
|
455 i.backward=true; |
|
456 } |
|
457 } else { |
|
458 Parent2::graph->next(*static_cast<Graph2Edge*>(&i)); |
|
459 } |
|
460 } |
|
461 void nextIn(Edge& i) const { |
|
462 if (!(i.backward)) { |
|
463 Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i)); |
|
464 if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID; |
|
465 } else { |
|
466 Parent2::graph->nextIn(*static_cast<Graph2Edge*>(&i)); |
|
467 } |
|
468 } |
|
469 void nextOut(Edge& i) const { |
|
470 if (!(i.backward)) { |
|
471 Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i)); |
|
472 if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID; |
|
473 } else { |
|
474 Parent2::graph->nextOut(*static_cast<Graph2Edge*>(&i)); |
|
475 } |
|
476 } |
|
477 |
|
478 Node source(const Edge& i) const { |
|
479 if (!(i.backward)) { |
|
480 return |
|
481 Node(Parent1::graph->source(i), INVALID, false); |
|
482 } else { |
|
483 return |
|
484 Node(INVALID, Parent2::graph->source(i), true); |
|
485 } |
|
486 } |
|
487 |
|
488 Node target(const Edge& i) const { |
|
489 if (!(i.backward)) { |
|
490 return |
|
491 Node(Parent1::graph->target(i), INVALID, false); |
|
492 } else { |
|
493 return |
|
494 Node(INVALID, Parent2::graph->target(i), true); |
|
495 } |
|
496 } |
|
497 |
|
498 using Parent::id; |
|
499 int id(const Edge& n) const { |
|
500 if (!n.backward) |
|
501 return this->Parent1::graph->id(n); |
|
502 else |
|
503 return this->Parent2::graph->id(n); |
|
504 } |
|
505 |
|
506 template <typename _Value> |
|
507 class EdgeMap { |
|
508 protected: |
|
509 typedef typename Parent::Graph1::template EdgeMap<_Value> ParentMap1; |
|
510 typedef typename Parent::Graph2::template EdgeMap<_Value> ParentMap2; |
|
511 ParentMap1 forward_map; |
|
512 ParentMap2 backward_map; |
|
513 public: |
|
514 typedef _Value Value; |
|
515 typedef Edge Key; |
|
516 EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw) : |
|
517 forward_map(*(gw.Parent1::graph)), |
|
518 backward_map(*(gw.Parent2::graph)) { } |
|
519 EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw, |
|
520 const _Value& value) : |
|
521 forward_map(*(gw.Parent1::graph), value), |
|
522 backward_map(*(gw.Parent2::graph), value) { } |
|
523 _Value operator[](const Edge& n) const { |
|
524 if (!n.backward) |
|
525 return forward_map[n]; |
|
526 else |
|
527 return backward_map[n]; |
|
528 } |
|
529 void set(const Edge& n, const _Value& value) { |
|
530 if (!n.backward) |
|
531 forward_map.set(n, value); |
|
532 else |
|
533 backward_map.set(n, value); |
|
534 } |
|
535 // using ParentMap1::operator[]; |
|
536 // using ParentMap2::operator[]; |
|
537 }; |
|
538 |
|
539 }; |
|
540 |
416 |
541 |
417 |
542 /*! A graph wrapper base class |
418 /*! A graph wrapper base class |
543 for merging the node-sets and edge-sets of |
419 for merging the node-sets and edge-sets of |
544 two node-disjoint graphs |
420 two node-disjoint graphs |
545 into one graph. |
421 into one graph. |
546 Specialization for the case when _Graph1::Edge and _Graph2::Edge |
422 Specialization for the case when _Graph1::Edge and _Graph2::Edge |
547 are the same. |
423 are the same. |
548 */ |
424 */ |
549 template <typename _Graph1, typename _Graph2> |
425 template <typename _Graph1, typename _Graph2> |
550 class MergeEdgeGraphWrapperBase< |
426 class MergeEdgeGraphWrapperBaseBase< |
551 _Graph1, _Graph2, typename boost::enable_if< |
427 _Graph1, _Graph2, typename boost::enable_if< |
552 boost::is_same<typename _Graph1::Edge, typename _Graph2::Edge> >::type> : |
428 boost::is_same<typename _Graph1::Edge, typename _Graph2::Edge> >::type> : |
553 public MergeNodeGraphWrapperBase<_Graph1, _Graph2> { |
429 public MergeNodeGraphWrapperBase<_Graph1, _Graph2> { |
554 public: |
430 public: |
555 static void printEdge() { std::cout << "edge: same" << std::endl; } |
431 static void printEdge() { std::cout << "edge: same" << std::endl; } |
592 } |
464 } |
593 }; |
465 }; |
594 |
466 |
595 using Parent::forward; |
467 using Parent::forward; |
596 using Parent::backward; |
468 using Parent::backward; |
597 bool forward(const Edge& e) const { return !e.backward; } |
469 using Parent::setForward; |
598 bool backward(const Edge& e) const { return e.backward; } |
470 using Parent::setBackward; |
|
471 static bool forward(const Edge& e) { return !e.backward; } |
|
472 static bool backward(const Edge& e) { return e.backward; } |
|
473 static void setForward(Edge& e) { e.backward=false; } |
|
474 static void setBackward(Edge& e) { e.backward=true; } |
|
475 }; |
|
476 |
|
477 |
|
478 /*! A grah wrapper base class |
|
479 for merging the node-sets and edge-sets of |
|
480 two node-disjoint graphs |
|
481 into one graph. |
|
482 Specialized implementation for the case |
|
483 when _Graph1::Edge is a base class and _Graph2::Edge |
|
484 is derived from it. |
|
485 */ |
|
486 template <typename _Graph1, typename _Graph2> |
|
487 class MergeEdgeGraphWrapperBaseBase< |
|
488 _Graph1, _Graph2, typename boost::enable_if< |
|
489 boost::is_base_and_derived<typename _Graph1::Edge, typename _Graph2::Edge> >::type> : |
|
490 public MergeNodeGraphWrapperBase<_Graph1, _Graph2> { |
|
491 public: |
|
492 static void printEdge() { std::cout << "edge: 2nd is derived" << std::endl; } |
|
493 typedef _Graph1 Graph1; |
|
494 typedef _Graph2 Graph2; |
|
495 typedef MergeNodeGraphWrapperBase<_Graph1, _Graph2> Parent; |
|
496 typedef typename Parent::Parent1 Parent1; |
|
497 typedef typename Parent::Parent2 Parent2; |
|
498 // typedef P1<_Graph1> Parent1; |
|
499 // typedef P2<_Graph2> Parent2; |
|
500 typedef typename Parent1::Edge Graph1Edge; |
|
501 typedef typename Parent2::Edge Graph2Edge; |
|
502 protected: |
|
503 MergeEdgeGraphWrapperBaseBase() { } |
|
504 public: |
|
505 |
|
506 class Edge : public Graph2Edge { |
|
507 friend class MergeEdgeGraphWrapperBaseBase<_Graph1, _Graph2>; |
|
508 protected: |
|
509 bool backward; //true, iff backward |
|
510 public: |
|
511 Edge() { } |
|
512 /// \todo =false is needed, or causes problems? |
|
513 /// If \c _backward is false, then we get an edge corresponding to the |
|
514 /// original one, otherwise its oppositely directed pair is obtained. |
|
515 Edge(const Graph1Edge& n1, |
|
516 const Graph2Edge& n2, bool _backward) : |
|
517 Graph2Edge(n2), backward(_backward) { |
|
518 if (!backward) *this=n1; |
|
519 } |
|
520 Edge(Invalid i) : Graph2Edge(i), backward(true) { } |
|
521 bool operator==(const Edge& v) const { |
|
522 if (backward) |
|
523 return (v.backward && |
|
524 static_cast<Graph2Edge>(*this)==static_cast<Graph2Edge>(v)); |
|
525 else |
|
526 return (!v.backward && |
|
527 static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v)); |
|
528 } |
|
529 bool operator!=(const Edge& v) const { |
|
530 return !(*this==v); |
|
531 } |
|
532 }; |
|
533 |
|
534 using Parent::forward; |
|
535 using Parent::backward; |
|
536 using Parent::setForward; |
|
537 using Parent::setBackward; |
|
538 static bool forward(const Edge& e) { return !e.backward; } |
|
539 static bool backward(const Edge& e) { return e.backward; } |
|
540 static void setForward(Edge& e) { e.backward=false; } |
|
541 static void setBackward(Edge& e) { e.backward=true; } |
|
542 }; |
|
543 |
|
544 |
|
545 /*! A grah wrapper base class |
|
546 for merging the node-sets and edge-sets of |
|
547 two node-disjoint graphs |
|
548 into one graph. |
|
549 Specialized implementation for the case |
|
550 when _Graph1::Edge is derived from _Graph2::Edge. |
|
551 */ |
|
552 template <typename _Graph1, typename _Graph2> |
|
553 class MergeEdgeGraphWrapperBaseBase< |
|
554 _Graph1, _Graph2, typename boost::enable_if< |
|
555 boost::is_base_and_derived<typename _Graph2::Edge, typename _Graph1::Edge> >::type> : |
|
556 public MergeNodeGraphWrapperBase<_Graph1, _Graph2> { |
|
557 public: |
|
558 static void printEdge() { std::cout << "edge: 1st is derived" << std::endl; } |
|
559 typedef _Graph1 Graph1; |
|
560 typedef _Graph2 Graph2; |
|
561 typedef MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2> Parent; |
|
562 typedef typename Parent::Parent1 Parent1; |
|
563 typedef typename Parent::Parent2 Parent2; |
|
564 // typedef P1<_Graph1> Parent1; |
|
565 // typedef P2<_Graph2> Parent2; |
|
566 typedef typename Parent1::Edge Graph1Edge; |
|
567 typedef typename Parent2::Edge Graph2Edge; |
|
568 protected: |
|
569 MergeEdgeGraphWrapperBaseBase() { } |
|
570 public: |
|
571 |
|
572 class Edge : public Graph1Edge { |
|
573 friend class MergeEdgeGraphWrapperBaseBase<_Graph1, _Graph2>; |
|
574 protected: |
|
575 bool backward; //true, iff backward |
|
576 public: |
|
577 Edge() { } |
|
578 /// \todo =false is needed, or causes problems? |
|
579 /// If \c _backward is false, then we get an edge corresponding to the |
|
580 /// original one, otherwise its oppositely directed pair is obtained. |
|
581 Edge(const Graph1Edge& n1, |
|
582 const Graph2Edge& n2, bool _backward) : |
|
583 Graph1Edge(n1), backward(_backward) { |
|
584 if (backward) *this=n2; |
|
585 } |
|
586 Edge(Invalid i) : Graph1Edge(i), backward(true) { } |
|
587 bool operator==(const Edge& v) const { |
|
588 if (backward) |
|
589 return (v.backward && |
|
590 static_cast<Graph2Edge>(*this)==static_cast<Graph2Edge>(v)); |
|
591 else |
|
592 return (!v.backward && |
|
593 static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v)); |
|
594 } |
|
595 bool operator!=(const Edge& v) const { |
|
596 return !(*this==v); |
|
597 } |
|
598 }; |
|
599 |
|
600 using Parent::forward; |
|
601 using Parent::backward; |
|
602 using Parent::setForward; |
|
603 using Parent::setBackward; |
|
604 static bool forward(const Edge& e) { return !e.backward; } |
|
605 static bool backward(const Edge& e) { return e.backward; } |
|
606 static void setForward(Edge& e) { e.backward=false; } |
|
607 static void setBackward(Edge& e) { e.backward=true; } |
|
608 }; |
|
609 |
|
610 |
|
611 template <typename _Graph1, typename _Graph2> |
|
612 class MergeEdgeGraphWrapperBase : |
|
613 public MergeEdgeGraphWrapperBaseBase<_Graph1, _Graph2> { |
|
614 public: |
|
615 typedef MergeEdgeGraphWrapperBaseBase<_Graph1, _Graph2> Parent; |
|
616 typedef _Graph1 Graph1; |
|
617 typedef _Graph2 Graph2; |
|
618 typedef typename Parent::Parent1 Parent1; |
|
619 typedef typename Parent::Parent2 Parent2; |
|
620 typedef typename Parent1::Node Graph1Node; |
|
621 typedef typename Parent2::Node Graph2Node; |
|
622 typedef typename Parent1::Edge Graph1Edge; |
|
623 typedef typename Parent2::Edge Graph2Edge; |
|
624 |
|
625 typedef typename Parent::Node Node; |
|
626 typedef typename Parent::Edge Edge; |
599 |
627 |
600 using Parent::first; |
628 using Parent::first; |
601 void first(Edge& i) const { |
629 void first(Edge& i) const { |
602 Parent1::graph->first(*static_cast<Graph1Edge*>(&i)); |
630 Parent1::graph->first(*static_cast<Graph1Edge*>(&i)); |
603 i.backward=false; |
631 this->setForward(i); |
604 if (*static_cast<Graph1Edge*>(&i)==INVALID) { |
632 if (*static_cast<Graph1Edge*>(&i)==INVALID) { |
605 Parent2::graph->first(*static_cast<Graph1Edge*>(&i)); |
633 Parent2::graph->first(*static_cast<Graph2Edge*>(&i)); |
606 i.backward=true; |
634 this->setBackward(i); |
607 } |
635 } |
608 } |
636 } |
609 void firstIn(Edge& i, const Node& n) const { |
637 void firstIn(Edge& i, const Node& n) const { |
610 if (!backward(n)) { |
638 if (forward(n)) { |
611 Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n); |
639 Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n); |
612 if (*static_cast<Graph1Edge*>(&i)==INVALID) |
640 if (*static_cast<Graph1Edge*>(&i)==INVALID) |
613 i=INVALID; |
641 i=INVALID; |
614 else |
642 else |
615 i.backward=false; |
643 this->setForward(i); |
616 } else { |
644 } else { |
617 Parent2::graph->firstIn(*static_cast<Graph1Edge*>(&i), n); |
645 Parent2::graph->firstIn(*static_cast<Graph2Edge*>(&i), n); |
618 i.backward=true; |
646 this->setBackward(i); |
619 } |
647 } |
620 } |
648 } |
621 void firstOut(Edge& i, const Node& n) const { |
649 void firstOut(Edge& i, const Node& n) const { |
622 if (!backward(n)) { |
650 if (forward(n)) { |
623 Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n); |
651 Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n); |
624 if (*static_cast<Graph1Edge*>(&i)==INVALID) |
652 if (*static_cast<Graph1Edge*>(&i)==INVALID) |
625 i=INVALID; |
653 i=INVALID; |
626 else |
654 else |
627 i.backward=false; |
655 this->setForward(i); |
628 } else { |
656 } else { |
629 Parent2::graph->firstOut(*static_cast<Graph1Edge*>(&i), n); |
657 Parent2::graph->firstOut(*static_cast<Graph2Edge*>(&i), n); |
630 i.backward=true; |
658 this->setBackward(i); |
631 } |
659 } |
632 } |
660 } |
633 |
661 |
634 using Parent::next; |
662 using Parent::next; |
635 void next(Edge& i) const { |
663 void next(Edge& i) const { |
636 if (!(i.backward)) { |
664 if (forward(i)) { |
637 Parent1::graph->next(*static_cast<Graph1Edge*>(&i)); |
665 Parent1::graph->next(*static_cast<Graph1Edge*>(&i)); |
638 if (*static_cast<Graph1Edge*>(&i)==INVALID) { |
666 if (*static_cast<Graph1Edge*>(&i)==INVALID) { |
639 Parent2::graph->first(*static_cast<Graph1Edge*>(&i)); |
667 Parent2::graph->first(*static_cast<Graph2Edge*>(&i)); |
640 i.backward=true; |
668 this->setBackward(i); |
641 } |
669 } |
642 } else { |
670 } else { |
643 Parent2::graph->next(*static_cast<Graph1Edge*>(&i)); |
671 Parent2::graph->next(*static_cast<Graph2Edge*>(&i)); |
644 } |
672 } |
645 } |
673 } |
646 void nextIn(Edge& i) const { |
674 void nextIn(Edge& i) const { |
647 if (!(i.backward)) { |
675 if (forward(i)) { |
648 Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i)); |
676 Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i)); |
649 if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID; |
677 if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID; |
650 } else { |
678 } else { |
651 Parent2::graph->nextIn(*static_cast<Graph1Edge*>(&i)); |
679 Parent2::graph->nextIn(*static_cast<Graph2Edge*>(&i)); |
652 } |
680 } |
653 } |
681 } |
654 void nextOut(Edge& i) const { |
682 void nextOut(Edge& i) const { |
655 if (!(i.backward)) { |
683 if (Parent::forward(i)) { |
656 Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i)); |
684 Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i)); |
657 if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID; |
685 if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID; |
658 } else { |
686 } else { |
659 Parent2::graph->nextOut(*static_cast<Graph1Edge*>(&i)); |
687 Parent2::graph->nextOut(*static_cast<Graph2Edge*>(&i)); |
660 } |
688 } |
661 } |
689 } |
662 |
690 |
663 Node source(const Edge& i) const { |
691 Node source(const Edge& i) const { |
664 if (!(i.backward)) { |
692 if (forward(i)) { |
665 return |
693 return |
666 Node(Parent1::graph->source(i), INVALID, false); |
694 Node(Parent1::graph->source(i), INVALID, false); |
667 } else { |
695 } else { |
668 return |
696 return |
669 Node(INVALID, Parent2::graph->source(i), true); |
697 Node(INVALID, Parent2::graph->source(i), true); |
670 } |
698 } |
671 } |
699 } |
672 |
700 |
673 Node target(const Edge& i) const { |
701 Node target(const Edge& i) const { |
674 if (!(i.backward)) { |
702 if (forward(i)) { |
675 return |
703 return |
676 Node(Parent1::graph->target(i), INVALID, false); |
704 Node(Parent1::graph->target(i), INVALID, false); |
677 } else { |
705 } else { |
678 return |
706 return |
679 Node(INVALID, Parent2::graph->target(i), true); |
707 Node(INVALID, Parent2::graph->target(i), true); |
680 } |
708 } |
681 } |
709 } |
682 |
710 |
683 using Parent::id; |
711 using Parent::id; |
684 int id(const Edge& n) const { |
712 int id(const Edge& n) const { |
685 if (!n.backward) |
713 if (forward(n)) |
686 return this->Parent1::graph->id(n); |
714 return this->Parent1::graph->id(n); |
687 else |
715 else |
688 return this->Parent2::graph->id(n); |
716 return this->Parent2::graph->id(n); |
689 } |
717 } |
690 |
718 |
722 }; |
750 }; |
723 |
751 |
724 }; |
752 }; |
725 |
753 |
726 |
754 |
727 /*! A grah wrapper base class |
755 |
728 for merging the node-sets and edge-sets of |
756 /*! A graph wrapper class |
729 two node-disjoint graphs |
757 for merging two node-disjoint graphs |
730 into one graph. |
758 into one graph. |
731 Specialized implementation for the case |
759 Different implementations are according to the relation of |
732 when _Graph1::Edge is a base class and _Graph2::Edge |
760 _Graph1::Edge and _Graph2::Edge. |
733 is derived from it. |
761 If _Graph1::Edge and _Graph2::Edge are unrelated, then |
734 */ |
762 MergeEdgeGraphWrapper<_Graph1, _Graph2>::Edge |
735 template <typename _Graph1, typename _Graph2> |
763 is derived from both. |
736 class MergeEdgeGraphWrapperBase< |
764 If _Graph1::Edge and _Graph2::Edge are the same type, then |
737 _Graph1, _Graph2, typename boost::enable_if< |
765 MergeEdgeGraphWrapper<_Graph1, _Graph2>::Edge |
738 boost::is_base_and_derived<typename _Graph1::Edge, typename _Graph2::Edge> >::type> : |
766 is derived from _Graph1::Edge. |
739 public MergeNodeGraphWrapperBase<_Graph1, _Graph2> { |
767 If one of _Graph1::Edge and _Graph2::Edge |
740 public: |
768 is derived from the other one, then |
741 static void printEdge() { std::cout << "edge: 2nd is derived" << std::endl; } |
769 MergeEdgeGraphWrapper<_Graph1, _Graph2>::Edge |
742 typedef _Graph1 Graph1; |
770 is derived from the derived type. |
743 typedef _Graph2 Graph2; |
771 It does not satisfy |
744 typedef MergeNodeGraphWrapperBase<_Graph1, _Graph2> Parent; |
772 */ |
745 typedef typename Parent::Parent1 Parent1; |
|
746 typedef typename Parent::Parent2 Parent2; |
|
747 // typedef P1<_Graph1> Parent1; |
|
748 // typedef P2<_Graph2> Parent2; |
|
749 typedef typename Parent1::Edge Graph1Edge; |
|
750 typedef typename Parent2::Edge Graph2Edge; |
|
751 protected: |
|
752 MergeEdgeGraphWrapperBase() { } |
|
753 public: |
|
754 template <typename _Value> class EdgeMap; |
|
755 |
|
756 typedef typename Parent::Node Node; |
|
757 |
|
758 class Edge : public Graph2Edge { |
|
759 friend class MergeEdgeGraphWrapperBase<_Graph1, _Graph2>; |
|
760 template <typename _Value> friend class EdgeMap; |
|
761 protected: |
|
762 bool backward; //true, iff backward |
|
763 public: |
|
764 Edge() { } |
|
765 /// \todo =false is needed, or causes problems? |
|
766 /// If \c _backward is false, then we get an edge corresponding to the |
|
767 /// original one, otherwise its oppositely directed pair is obtained. |
|
768 Edge(const Graph1Edge& n1, |
|
769 const Graph2Edge& n2, bool _backward) : |
|
770 Graph2Edge(n2), backward(_backward) { |
|
771 if (!backward) *this=n1; |
|
772 } |
|
773 Edge(Invalid i) : Graph2Edge(i), backward(true) { } |
|
774 bool operator==(const Edge& v) const { |
|
775 if (backward) |
|
776 return (v.backward && |
|
777 static_cast<Graph2Edge>(*this)==static_cast<Graph2Edge>(v)); |
|
778 else |
|
779 return (!v.backward && |
|
780 static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v)); |
|
781 } |
|
782 bool operator!=(const Edge& v) const { |
|
783 return !(*this==v); |
|
784 } |
|
785 }; |
|
786 |
|
787 using Parent::forward; |
|
788 using Parent::backward; |
|
789 bool forward(const Edge& e) const { return !e.backward; } |
|
790 bool backward(const Edge& e) const { return e.backward; } |
|
791 |
|
792 using Parent::first; |
|
793 void first(Edge& i) const { |
|
794 Parent1::graph->first(*static_cast<Graph1Edge*>(&i)); |
|
795 i.backward=false; |
|
796 if (*static_cast<Graph1Edge*>(&i)==INVALID) { |
|
797 Parent2::graph->first(*static_cast<Graph2Edge*>(&i)); |
|
798 i.backward=true; |
|
799 } |
|
800 } |
|
801 void firstIn(Edge& i, const Node& n) const { |
|
802 if (!backward(n)) { |
|
803 Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n); |
|
804 if (*static_cast<Graph1Edge*>(&i)==INVALID) |
|
805 i=INVALID; |
|
806 else |
|
807 i.backward=false; |
|
808 } else { |
|
809 Parent2::graph->firstIn(*static_cast<Graph2Edge*>(&i), n); |
|
810 i.backward=true; |
|
811 } |
|
812 } |
|
813 void firstOut(Edge& i, const Node& n) const { |
|
814 if (!backward(n)) { |
|
815 Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n); |
|
816 if (*static_cast<Graph1Edge*>(&i)==INVALID) |
|
817 i=INVALID; |
|
818 else |
|
819 i.backward=false; |
|
820 } else { |
|
821 Parent2::graph->firstOut(*static_cast<Graph2Edge*>(&i), n); |
|
822 i.backward=true; |
|
823 } |
|
824 } |
|
825 |
|
826 using Parent::next; |
|
827 void next(Edge& i) const { |
|
828 if (!(i.backward)) { |
|
829 Parent1::graph->next(*static_cast<Graph1Edge*>(&i)); |
|
830 if (*static_cast<Graph1Edge*>(&i)==INVALID) { |
|
831 Parent2::graph->first(*static_cast<Graph2Edge*>(&i)); |
|
832 i.backward=true; |
|
833 } |
|
834 } else { |
|
835 Parent2::graph->next(*static_cast<Graph2Edge*>(&i)); |
|
836 } |
|
837 } |
|
838 void nextIn(Edge& i) const { |
|
839 if (!(i.backward)) { |
|
840 Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i)); |
|
841 if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID; |
|
842 } else { |
|
843 Parent2::graph->nextIn(*static_cast<Graph2Edge*>(&i)); |
|
844 } |
|
845 } |
|
846 void nextOut(Edge& i) const { |
|
847 if (!(i.backward)) { |
|
848 Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i)); |
|
849 if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID; |
|
850 } else { |
|
851 Parent2::graph->nextOut(*static_cast<Graph2Edge*>(&i)); |
|
852 } |
|
853 } |
|
854 |
|
855 Node source(const Edge& i) const { |
|
856 if (!(i.backward)) { |
|
857 return |
|
858 Node(Parent1::graph->source(i), INVALID, false); |
|
859 } else { |
|
860 return |
|
861 Node(INVALID, Parent2::graph->source(i), true); |
|
862 } |
|
863 } |
|
864 |
|
865 Node target(const Edge& i) const { |
|
866 if (!(i.backward)) { |
|
867 return |
|
868 Node(Parent1::graph->target(i), INVALID, false); |
|
869 } else { |
|
870 return |
|
871 Node(INVALID, Parent2::graph->target(i), true); |
|
872 } |
|
873 } |
|
874 |
|
875 using Parent::id; |
|
876 int id(const Edge& n) const { |
|
877 if (!n.backward) |
|
878 return this->Parent1::graph->id(n); |
|
879 else |
|
880 return this->Parent2::graph->id(n); |
|
881 } |
|
882 |
|
883 template <typename _Value> |
|
884 class EdgeMap { |
|
885 protected: |
|
886 typedef typename Parent::Graph1::template EdgeMap<_Value> ParentMap1; |
|
887 typedef typename Parent::Graph2::template EdgeMap<_Value> ParentMap2; |
|
888 ParentMap1 forward_map; |
|
889 ParentMap2 backward_map; |
|
890 public: |
|
891 typedef _Value Value; |
|
892 typedef Edge Key; |
|
893 EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw) : |
|
894 forward_map(*(gw.Parent1::graph)), |
|
895 backward_map(*(gw.Parent2::graph)) { } |
|
896 EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw, |
|
897 const _Value& value) : |
|
898 forward_map(*(gw.Parent1::graph), value), |
|
899 backward_map(*(gw.Parent2::graph), value) { } |
|
900 _Value operator[](const Edge& n) const { |
|
901 if (!n.backward) |
|
902 return forward_map[n]; |
|
903 else |
|
904 return backward_map[n]; |
|
905 } |
|
906 void set(const Edge& n, const _Value& value) { |
|
907 if (!n.backward) |
|
908 forward_map.set(n, value); |
|
909 else |
|
910 backward_map.set(n, value); |
|
911 } |
|
912 // using ParentMap1::operator[]; |
|
913 // using ParentMap2::operator[]; |
|
914 }; |
|
915 |
|
916 }; |
|
917 |
|
918 |
|
919 /*! A grah wrapper base class |
|
920 for merging the node-sets and edge-sets of |
|
921 two node-disjoint graphs |
|
922 into one graph. |
|
923 Specialized implementation for the case |
|
924 when _Graph1::Edge is derived from _Graph2::Edge. |
|
925 */ |
|
926 template <typename _Graph1, typename _Graph2> |
|
927 class MergeEdgeGraphWrapperBase< |
|
928 _Graph1, _Graph2, typename boost::enable_if< |
|
929 boost::is_base_and_derived<typename _Graph2::Edge, typename _Graph1::Edge> >::type> : |
|
930 public MergeNodeGraphWrapperBase<_Graph1, _Graph2> { |
|
931 public: |
|
932 static void printEdge() { std::cout << "edge: 1st is derived" << std::endl; } |
|
933 typedef _Graph1 Graph1; |
|
934 typedef _Graph2 Graph2; |
|
935 typedef MergeNodeGraphWrapperBase<_Graph1, _Graph2> Parent; |
|
936 typedef typename Parent::Parent1 Parent1; |
|
937 typedef typename Parent::Parent2 Parent2; |
|
938 // typedef P1<_Graph1> Parent1; |
|
939 // typedef P2<_Graph2> Parent2; |
|
940 typedef typename Parent1::Edge Graph1Edge; |
|
941 typedef typename Parent2::Edge Graph2Edge; |
|
942 protected: |
|
943 MergeEdgeGraphWrapperBase() { } |
|
944 public: |
|
945 template <typename _Value> class EdgeMap; |
|
946 |
|
947 typedef typename Parent::Node Node; |
|
948 |
|
949 class Edge : public Graph1Edge { |
|
950 friend class MergeEdgeGraphWrapperBase<_Graph1, _Graph2>; |
|
951 template <typename _Value> friend class EdgeMap; |
|
952 protected: |
|
953 bool backward; //true, iff backward |
|
954 public: |
|
955 Edge() { } |
|
956 /// \todo =false is needed, or causes problems? |
|
957 /// If \c _backward is false, then we get an edge corresponding to the |
|
958 /// original one, otherwise its oppositely directed pair is obtained. |
|
959 Edge(const Graph1Edge& n1, |
|
960 const Graph2Edge& n2, bool _backward) : |
|
961 Graph1Edge(n1), backward(_backward) { |
|
962 if (backward) *this=n2; |
|
963 } |
|
964 Edge(Invalid i) : Graph1Edge(i), backward(true) { } |
|
965 bool operator==(const Edge& v) const { |
|
966 if (backward) |
|
967 return (v.backward && |
|
968 static_cast<Graph2Edge>(*this)==static_cast<Graph2Edge>(v)); |
|
969 else |
|
970 return (!v.backward && |
|
971 static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v)); |
|
972 } |
|
973 bool operator!=(const Edge& v) const { |
|
974 return !(*this==v); |
|
975 } |
|
976 }; |
|
977 |
|
978 using Parent::forward; |
|
979 using Parent::backward; |
|
980 bool forward(const Edge& e) const { return !e.backward; } |
|
981 bool backward(const Edge& e) const { return e.backward; } |
|
982 |
|
983 using Parent::first; |
|
984 void first(Edge& i) const { |
|
985 Parent1::graph->first(*static_cast<Graph1Edge*>(&i)); |
|
986 i.backward=false; |
|
987 if (*static_cast<Graph1Edge*>(&i)==INVALID) { |
|
988 Parent2::graph->first(*static_cast<Graph2Edge*>(&i)); |
|
989 i.backward=true; |
|
990 } |
|
991 } |
|
992 void firstIn(Edge& i, const Node& n) const { |
|
993 if (!backward(n)) { |
|
994 Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n); |
|
995 if (*static_cast<Graph1Edge*>(&i)==INVALID) |
|
996 i=INVALID; |
|
997 else |
|
998 i.backward=false; |
|
999 } else { |
|
1000 Parent2::graph->firstIn(*static_cast<Graph2Edge*>(&i), n); |
|
1001 i.backward=true; |
|
1002 } |
|
1003 } |
|
1004 void firstOut(Edge& i, const Node& n) const { |
|
1005 if (!backward(n)) { |
|
1006 Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n); |
|
1007 if (*static_cast<Graph1Edge*>(&i)==INVALID) |
|
1008 i=INVALID; |
|
1009 else |
|
1010 i.backward=false; |
|
1011 } else { |
|
1012 Parent2::graph->firstOut(*static_cast<Graph2Edge*>(&i), n); |
|
1013 i.backward=true; |
|
1014 } |
|
1015 } |
|
1016 |
|
1017 using Parent::next; |
|
1018 void next(Edge& i) const { |
|
1019 if (!(i.backward)) { |
|
1020 Parent1::graph->next(*static_cast<Graph1Edge*>(&i)); |
|
1021 if (*static_cast<Graph1Edge*>(&i)==INVALID) { |
|
1022 Parent2::graph->first(*static_cast<Graph2Edge*>(&i)); |
|
1023 i.backward=true; |
|
1024 } |
|
1025 } else { |
|
1026 Parent2::graph->next(*static_cast<Graph2Edge*>(&i)); |
|
1027 } |
|
1028 } |
|
1029 void nextIn(Edge& i) const { |
|
1030 if (!(i.backward)) { |
|
1031 Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i)); |
|
1032 if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID; |
|
1033 } else { |
|
1034 Parent2::graph->nextIn(*static_cast<Graph2Edge*>(&i)); |
|
1035 } |
|
1036 } |
|
1037 void nextOut(Edge& i) const { |
|
1038 if (!(i.backward)) { |
|
1039 Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i)); |
|
1040 if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID; |
|
1041 } else { |
|
1042 Parent2::graph->nextOut(*static_cast<Graph2Edge*>(&i)); |
|
1043 } |
|
1044 } |
|
1045 |
|
1046 Node source(const Edge& i) const { |
|
1047 if (!(i.backward)) { |
|
1048 return |
|
1049 Node(Parent1::graph->source(i), INVALID, false); |
|
1050 } else { |
|
1051 return |
|
1052 Node(INVALID, Parent2::graph->source(i), true); |
|
1053 } |
|
1054 } |
|
1055 |
|
1056 Node target(const Edge& i) const { |
|
1057 if (!(i.backward)) { |
|
1058 return |
|
1059 Node(Parent1::graph->target(i), INVALID, false); |
|
1060 } else { |
|
1061 return |
|
1062 Node(INVALID, Parent2::graph->target(i), true); |
|
1063 } |
|
1064 } |
|
1065 |
|
1066 using Parent::id; |
|
1067 int id(const Edge& n) const { |
|
1068 if (!n.backward) |
|
1069 return this->Parent1::graph->id(n); |
|
1070 else |
|
1071 return this->Parent2::graph->id(n); |
|
1072 } |
|
1073 |
|
1074 template <typename _Value> |
|
1075 class EdgeMap { |
|
1076 protected: |
|
1077 typedef typename Parent::Graph1::template EdgeMap<_Value> ParentMap1; |
|
1078 typedef typename Parent::Graph2::template EdgeMap<_Value> ParentMap2; |
|
1079 ParentMap1 forward_map; |
|
1080 ParentMap2 backward_map; |
|
1081 public: |
|
1082 typedef _Value Value; |
|
1083 typedef Edge Key; |
|
1084 EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw) : |
|
1085 forward_map(*(gw.Parent1::graph)), |
|
1086 backward_map(*(gw.Parent2::graph)) { } |
|
1087 EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw, |
|
1088 const _Value& value) : |
|
1089 forward_map(*(gw.Parent1::graph), value), |
|
1090 backward_map(*(gw.Parent2::graph), value) { } |
|
1091 _Value operator[](const Edge& n) const { |
|
1092 if (!n.backward) |
|
1093 return forward_map[n]; |
|
1094 else |
|
1095 return backward_map[n]; |
|
1096 } |
|
1097 void set(const Edge& n, const _Value& value) { |
|
1098 if (!n.backward) |
|
1099 forward_map.set(n, value); |
|
1100 else |
|
1101 backward_map.set(n, value); |
|
1102 } |
|
1103 // using ParentMap1::operator[]; |
|
1104 // using ParentMap2::operator[]; |
|
1105 }; |
|
1106 |
|
1107 }; |
|
1108 |
|
1109 |
|
1110 /*! A graph wrapper class |
|
1111 for merging the node-sets and edge-sets of |
|
1112 two node-disjoint graphs |
|
1113 into one graph. |
|
1114 */ |
|
1115 template <typename _Graph1, typename _Graph2> |
773 template <typename _Graph1, typename _Graph2> |
1116 class MergeEdgeGraphWrapper : public |
774 class MergeEdgeGraphWrapper : public |
1117 IterableGraphExtender<MergeEdgeGraphWrapperBase<_Graph1, _Graph2> > { |
775 IterableGraphExtender<MergeEdgeGraphWrapperBase<_Graph1, _Graph2> > { |
1118 public: |
776 public: |
1119 typedef _Graph1 Graph1; |
777 typedef _Graph1 Graph1; |