481 sym_edge_maps.erase(e); |
480 sym_edge_maps.erase(e); |
482 sym_edge_maps.erase(f); |
481 sym_edge_maps.erase(f); |
483 ListGraph::erase(f); |
482 ListGraph::erase(f); |
484 ListGraph::erase(e); |
483 ListGraph::erase(e); |
485 } |
484 } |
|
485 };*/ |
|
486 |
|
487 class SymListGraph : public ListGraph { |
|
488 typedef ListGraph Parent; |
|
489 public: |
|
490 |
|
491 typedef SymListGraph Graph; |
|
492 |
|
493 typedef ListGraph::Node Node; |
|
494 typedef ListGraph::NodeIt NodeIt; |
|
495 |
|
496 class SymEdge; |
|
497 class SymEdgeIt; |
|
498 |
|
499 class Edge; |
|
500 class EdgeIt; |
|
501 class OutEdgeIt; |
|
502 class InEdgeIt; |
|
503 |
|
504 template <typename Value> |
|
505 class NodeMap : public Parent::NodeMap<Value> { |
|
506 public: |
|
507 NodeMap(const SymListGraph& g) |
|
508 : SymListGraph::Parent::NodeMap<Value>(g) {} |
|
509 NodeMap(const SymListGraph& g, Value v) |
|
510 : SymListGraph::Parent::NodeMap<Value>(g, v) {} |
|
511 template<typename TT> |
|
512 NodeMap(const NodeMap<TT>& copy) |
|
513 : SymListGraph::Parent::NodeMap<Value>(copy) { } |
|
514 }; |
|
515 |
|
516 template <typename Value> |
|
517 class SymEdgeMap : public Parent::EdgeMap<Value> { |
|
518 public: |
|
519 typedef SymEdge KeyType; |
|
520 |
|
521 SymEdgeMap(const SymListGraph& g) |
|
522 : SymListGraph::Parent::EdgeMap<Value>(g) {} |
|
523 SymEdgeMap(const SymListGraph& g, Value v) |
|
524 : SymListGraph::Parent::EdgeMap<Value>(g, v) {} |
|
525 template<typename TT> |
|
526 SymEdgeMap(const SymEdgeMap<TT>& copy) |
|
527 : SymListGraph::Parent::EdgeMap<Value>(copy) { } |
|
528 |
|
529 }; |
|
530 |
|
531 // Create edge map registry. |
|
532 CREATE_EDGE_MAP_REGISTRY; |
|
533 // Create edge maps. |
|
534 CREATE_EDGE_MAP(ArrayMap); |
|
535 |
|
536 class Edge { |
|
537 friend class SymListGraph; |
|
538 friend class SymListGraph::EdgeIt; |
|
539 friend class SymListGraph::OutEdgeIt; |
|
540 friend class SymListGraph::InEdgeIt; |
|
541 |
|
542 protected: |
|
543 int id; |
|
544 |
|
545 Edge(int pid) { id = pid; } |
|
546 |
|
547 public: |
|
548 /// An Edge with id \c n. |
|
549 |
|
550 Edge() { } |
|
551 Edge (Invalid) { id = -1; } |
|
552 |
|
553 operator SymEdge(){ return SymEdge(id >> 1);} |
|
554 |
|
555 bool operator==(const Edge i) const {return id == i.id;} |
|
556 bool operator!=(const Edge i) const {return id != i.id;} |
|
557 bool operator<(const Edge i) const {return id < i.id;} |
|
558 // ///Validity check |
|
559 // operator bool() { return n!=-1; } |
|
560 }; |
|
561 |
|
562 class SymEdge : public ListGraph::Edge { |
|
563 friend class SymListGraph; |
|
564 friend class SymListGraph::Edge; |
|
565 typedef ListGraph::Edge Parent; |
|
566 |
|
567 protected: |
|
568 SymEdge(int pid) : Parent(pid) {} |
|
569 public: |
|
570 |
|
571 SymEdge() { } |
|
572 SymEdge(const ListGraph::Edge& i) : Parent(i) {} |
|
573 SymEdge (Invalid) : Parent(INVALID) {} |
|
574 |
|
575 }; |
|
576 |
|
577 class OutEdgeIt { |
|
578 Parent::OutEdgeIt out; |
|
579 Parent::InEdgeIt in; |
|
580 public: |
|
581 OutEdgeIt() {} |
|
582 OutEdgeIt(const SymListGraph& g, Edge e) { |
|
583 if ((e.id & 1) == 0) { |
|
584 out = Parent::OutEdgeIt(g, SymEdge(e)); |
|
585 in = Parent::InEdgeIt(g, g.tail(e)); |
|
586 } else { |
|
587 out = Parent::OutEdgeIt(INVALID); |
|
588 in = Parent::InEdgeIt(g, SymEdge(e)); |
|
589 } |
|
590 } |
|
591 OutEdgeIt (Invalid i) : out(INVALID), in(INVALID) { } |
|
592 |
|
593 OutEdgeIt(const SymListGraph& g, const Node v) |
|
594 : out(g, v), in(g, v) {} |
|
595 OutEdgeIt &operator++() { |
|
596 if (out != INVALID) { |
|
597 ++out; |
|
598 } else { |
|
599 ++in; |
|
600 } |
|
601 return *this; |
|
602 } |
|
603 |
|
604 operator Edge() const { |
|
605 if (out == INVALID && in == INVALID) return INVALID; |
|
606 return out != INVALID ? forward(out) : backward(in); |
|
607 } |
|
608 |
|
609 bool operator==(const Edge i) const {return Edge(*this) == i;} |
|
610 bool operator!=(const Edge i) const {return Edge(*this) != i;} |
|
611 bool operator<(const Edge i) const {return Edge(*this) < i;} |
|
612 }; |
|
613 |
|
614 class InEdgeIt { |
|
615 Parent::OutEdgeIt out; |
|
616 Parent::InEdgeIt in; |
|
617 public: |
|
618 InEdgeIt() {} |
|
619 InEdgeIt(const SymListGraph& g, Edge e) { |
|
620 if ((e.id & 1) == 0) { |
|
621 out = Parent::OutEdgeIt(g, SymEdge(e)); |
|
622 in = Parent::InEdgeIt(g, g.tail(e)); |
|
623 } else { |
|
624 out = Parent::OutEdgeIt(INVALID); |
|
625 in = Parent::InEdgeIt(g, SymEdge(e)); |
|
626 } |
|
627 } |
|
628 InEdgeIt (Invalid i) : out(INVALID), in(INVALID) { } |
|
629 |
|
630 InEdgeIt(const SymListGraph& g, const Node v) |
|
631 : out(g, v), in(g, v) {} |
|
632 |
|
633 InEdgeIt &operator++() { |
|
634 if (out != INVALID) { |
|
635 ++out; |
|
636 } else { |
|
637 ++in; |
|
638 } |
|
639 return *this; |
|
640 } |
|
641 |
|
642 operator Edge() const { |
|
643 if (out == INVALID && in == INVALID) return INVALID; |
|
644 return out != INVALID ? backward(out) : forward(in); |
|
645 } |
|
646 |
|
647 bool operator==(const Edge i) const {return Edge(*this) == i;} |
|
648 bool operator!=(const Edge i) const {return Edge(*this) != i;} |
|
649 bool operator<(const Edge i) const {return Edge(*this) < i;} |
|
650 }; |
|
651 |
|
652 class SymEdgeIt : public Parent::EdgeIt { |
|
653 |
|
654 public: |
|
655 SymEdgeIt() {} |
|
656 |
|
657 SymEdgeIt(const SymListGraph& g) |
|
658 : SymListGraph::Parent::EdgeIt(g) {} |
|
659 |
|
660 SymEdgeIt(const SymListGraph& g, SymEdge e) |
|
661 : SymListGraph::Parent::EdgeIt(g, e) {} |
|
662 |
|
663 SymEdgeIt(Invalid i) |
|
664 : SymListGraph::Parent::EdgeIt(INVALID) {} |
|
665 |
|
666 SymEdgeIt& operator++() { |
|
667 SymListGraph::Parent::EdgeIt::operator++(); |
|
668 return *this; |
|
669 } |
|
670 |
|
671 operator SymEdge() const { |
|
672 return SymEdge |
|
673 (static_cast<const SymListGraph::Parent::EdgeIt&>(*this)); |
|
674 } |
|
675 bool operator==(const SymEdge i) const {return SymEdge(*this) == i;} |
|
676 bool operator!=(const SymEdge i) const {return SymEdge(*this) != i;} |
|
677 bool operator<(const SymEdge i) const {return SymEdge(*this) < i;} |
|
678 }; |
|
679 |
|
680 class EdgeIt { |
|
681 SymEdgeIt it; |
|
682 bool fw; |
|
683 public: |
|
684 EdgeIt(const SymListGraph& g) : it(g), fw(true) {} |
|
685 EdgeIt (Invalid i) : it(i) { } |
|
686 EdgeIt(const SymListGraph& g, Edge e) |
|
687 : it(g, SymEdge(e)), fw(id(e) & 1 == 0) { } |
|
688 EdgeIt() { } |
|
689 EdgeIt& operator++() { |
|
690 fw = !fw; |
|
691 if (fw) ++it; |
|
692 return *this; |
|
693 } |
|
694 operator Edge() const { |
|
695 if (it == INVALID) return INVALID; |
|
696 return fw ? forward(it) : backward(it); |
|
697 } |
|
698 bool operator==(const Edge i) const {return Edge(*this) == i;} |
|
699 bool operator!=(const Edge i) const {return Edge(*this) != i;} |
|
700 bool operator<(const Edge i) const {return Edge(*this) < i;} |
|
701 |
|
702 }; |
|
703 |
|
704 ///Number of nodes. |
|
705 int nodeNum() const { return Parent::nodeNum(); } |
|
706 ///Number of edges. |
|
707 int edgeNum() const { return 2*Parent::edgeNum(); } |
|
708 ///Number of symmetric edges. |
|
709 int symEdgeNum() const { return Parent::edgeNum(); } |
|
710 |
|
711 ///Set the expected maximum number of edges. |
|
712 |
|
713 ///With this function, it is possible to set the expected number of edges. |
|
714 ///The use of this fasten the building of the graph and makes |
|
715 ///it possible to avoid the superfluous memory allocation. |
|
716 void reserveSymEdge(int n) { Parent::reserveEdge(n); }; |
|
717 |
|
718 /// Maximum node ID. |
|
719 |
|
720 /// Maximum node ID. |
|
721 ///\sa id(Node) |
|
722 int maxNodeId() const { return Parent::maxNodeId(); } |
|
723 /// Maximum edge ID. |
|
724 |
|
725 /// Maximum edge ID. |
|
726 ///\sa id(Edge) |
|
727 int maxEdgeId() const { return 2*Parent::maxEdgeId(); } |
|
728 /// Maximum symmetric edge ID. |
|
729 |
|
730 /// Maximum symmetric edge ID. |
|
731 ///\sa id(SymEdge) |
|
732 int maxSymEdgeId() const { return Parent::maxEdgeId(); } |
|
733 |
|
734 |
|
735 Node tail(Edge e) const { |
|
736 return (e.id & 1) == 0 ? |
|
737 Parent::tail(SymEdge(e)) : Parent::head(SymEdge(e)); |
|
738 } |
|
739 |
|
740 Node head(Edge e) const { |
|
741 return (e.id & 1) == 0 ? |
|
742 Parent::head(SymEdge(e)) : Parent::tail(SymEdge(e)); |
|
743 } |
|
744 |
|
745 Node tail(SymEdge e) const { |
|
746 return Parent::tail(e); |
|
747 } |
|
748 |
|
749 Node head(SymEdge e) const { |
|
750 return Parent::head(e); |
|
751 } |
|
752 |
|
753 NodeIt& first(NodeIt& v) const { |
|
754 v=NodeIt(*this); return v; } |
|
755 EdgeIt& first(EdgeIt& e) const { |
|
756 e=EdgeIt(*this); return e; } |
|
757 SymEdgeIt& first(SymEdgeIt& e) const { |
|
758 e=SymEdgeIt(*this); return e; } |
|
759 OutEdgeIt& first(OutEdgeIt& e, const Node v) const { |
|
760 e=OutEdgeIt(*this,v); return e; } |
|
761 InEdgeIt& first(InEdgeIt& e, const Node v) const { |
|
762 e=InEdgeIt(*this,v); return e; } |
|
763 |
|
764 /// Node ID. |
|
765 |
|
766 /// The ID of a valid Node is a nonnegative integer not greater than |
|
767 /// \ref maxNodeId(). The range of the ID's is not surely continuous |
|
768 /// and the greatest node ID can be actually less then \ref maxNodeId(). |
|
769 /// |
|
770 /// The ID of the \ref INVALID node is -1. |
|
771 ///\return The ID of the node \c v. |
|
772 static int id(Node v) { return Parent::id(v); } |
|
773 /// Edge ID. |
|
774 |
|
775 /// The ID of a valid Edge is a nonnegative integer not greater than |
|
776 /// \ref maxEdgeId(). The range of the ID's is not surely continuous |
|
777 /// and the greatest edge ID can be actually less then \ref maxEdgeId(). |
|
778 /// |
|
779 /// The ID of the \ref INVALID edge is -1. |
|
780 ///\return The ID of the edge \c e. |
|
781 static int id(Edge e) { return e.id; } |
|
782 |
|
783 /// The ID of a valid SymEdge is a nonnegative integer not greater than |
|
784 /// \ref maxSymEdgeId(). The range of the ID's is not surely continuous |
|
785 /// and the greatest edge ID can be actually less then \ref maxSymEdgeId(). |
|
786 /// |
|
787 /// The ID of the \ref INVALID symmetric edge is -1. |
|
788 ///\return The ID of the edge \c e. |
|
789 static int id(SymEdge e) { return Parent::id(e); } |
|
790 |
|
791 /// Adds a new node to the graph. |
|
792 |
|
793 /// \warning It adds the new node to the front of the list. |
|
794 /// (i.e. the lastly added node becomes the first.) |
|
795 Node addNode() { |
|
796 return Parent::addNode(); |
|
797 } |
|
798 |
|
799 SymEdge addEdge(Node u, Node v) { |
|
800 SymEdge se = Parent::addEdge(u, v); |
|
801 edge_maps.add(forward(se)); |
|
802 edge_maps.add(backward(se)); |
|
803 return se; |
|
804 } |
|
805 |
|
806 /// Finds an edge between two nodes. |
|
807 |
|
808 /// Finds an edge from node \c u to node \c v. |
|
809 /// |
|
810 /// If \c prev is \ref INVALID (this is the default value), then |
|
811 /// It finds the first edge from \c u to \c v. Otherwise it looks for |
|
812 /// the next edge from \c u to \c v after \c prev. |
|
813 /// \return The found edge or INVALID if there is no such an edge. |
|
814 Edge findEdge(Node u, Node v, Edge prev = INVALID) |
|
815 { |
|
816 if (prev == INVALID || id(prev) & 1 == 0) { |
|
817 SymEdge se = Parent::findEdge(u, v, SymEdge(prev)); |
|
818 if (se != INVALID) return forward(se); |
|
819 } else { |
|
820 SymEdge se = Parent::findEdge(v, u, SymEdge(prev)); |
|
821 if (se != INVALID) return backward(se); |
|
822 } |
|
823 return INVALID; |
|
824 } |
|
825 |
|
826 // /// Finds an symmetric edge between two nodes. |
|
827 |
|
828 // /// Finds an symmetric edge from node \c u to node \c v. |
|
829 // /// |
|
830 // /// If \c prev is \ref INVALID (this is the default value), then |
|
831 // /// It finds the first edge from \c u to \c v. Otherwise it looks for |
|
832 // /// the next edge from \c u to \c v after \c prev. |
|
833 // /// \return The found edge or INVALID if there is no such an edge. |
|
834 |
|
835 // SymEdge findEdge(Node u, Node v, SymEdge prev = INVALID) |
|
836 // { |
|
837 // if (prev == INVALID || id(prev) & 1 == 0) { |
|
838 // SymEdge se = Parent::findEdge(u, v, SymEdge(prev)); |
|
839 // if (se != INVALID) return se; |
|
840 // } else { |
|
841 // SymEdge se = Parent::findEdge(v, u, SymEdge(prev)); |
|
842 // if (se != INVALID) return se; |
|
843 // } |
|
844 // return INVALID; |
|
845 // } |
|
846 |
|
847 public: |
|
848 |
|
849 void erase(Node n) { |
|
850 for (OutEdgeIt it(*this, n); it != INVALID; ++it) { |
|
851 edge_maps.erase(it); |
|
852 edge_maps.erase(opposite(it)); |
|
853 } |
|
854 Parent::erase(n); |
|
855 } |
|
856 |
|
857 void erase(SymEdge e) { |
|
858 edge_maps.erase(forward(e)); |
|
859 edge_maps.erase(backward(e)); |
|
860 Parent::erase(e); |
|
861 }; |
|
862 |
|
863 void clear() { |
|
864 edge_maps.clear(); |
|
865 Parent::clear(); |
|
866 } |
|
867 |
|
868 static Edge opposite(Edge e) { |
|
869 return Edge(id(e) ^ 1); |
|
870 } |
|
871 |
|
872 static Edge forward(SymEdge e) { |
|
873 return Edge(id(e) << 1); |
|
874 } |
|
875 |
|
876 static Edge backward(SymEdge e) { |
|
877 return Edge((id(e) << 1) | 1); |
|
878 } |
|
879 |
486 }; |
880 }; |
487 |
|
488 |
881 |
489 ///A graph class containing only nodes. |
882 ///A graph class containing only nodes. |
490 |
883 |
491 ///This class implements a graph structure without edges. |
884 ///This class implements a graph structure without edges. |
492 ///The most useful application of this class is to be the node set of an |
885 ///The most useful application of this class is to be the node set of an |