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