564 |
564 |
565 ///@} |
565 ///@} |
566 |
566 |
567 /**************** Undirected List Graph ****************/ |
567 /**************** Undirected List Graph ****************/ |
568 |
568 |
569 typedef UGraphExtender<UGraphBaseExtender< |
569 typedef UGraphExtender<UndirGraphExtender<ListGraphBase> > |
570 ListGraphBase> > ExtendedListUGraphBase; |
570 ExtendedListUGraphBase; |
571 |
571 |
572 /// \addtogroup graphs |
572 /// \addtogroup graphs |
573 /// @{ |
573 /// @{ |
574 |
574 |
575 ///An undirected list graph class. |
575 ///An undirected list graph class. |
649 |
649 |
650 struct NodeT { |
650 struct NodeT { |
651 int first_edge, next_node; |
651 int first_edge, next_node; |
652 }; |
652 }; |
653 |
653 |
654 struct EdgeT { |
654 struct UEdgeT { |
655 int aNode, prev_out, next_out; |
655 int aNode, prev_out, next_out; |
656 int bNode, prev_in, next_in; |
656 int bNode, prev_in, next_in; |
657 }; |
657 }; |
658 |
658 |
659 std::vector<NodeT> aNodes; |
659 std::vector<NodeT> aNodes; |
660 std::vector<NodeT> bNodes; |
660 std::vector<NodeT> bNodes; |
661 |
661 |
662 std::vector<EdgeT> edges; |
662 std::vector<UEdgeT> edges; |
663 |
663 |
664 int first_anode; |
664 int first_anode; |
665 int first_free_anode; |
665 int first_free_anode; |
666 |
666 |
667 int first_bnode; |
667 int first_bnode; |
683 bool operator==(const Node i) const {return id==i.id;} |
683 bool operator==(const Node i) const {return id==i.id;} |
684 bool operator!=(const Node i) const {return id!=i.id;} |
684 bool operator!=(const Node i) const {return id!=i.id;} |
685 bool operator<(const Node i) const {return id<i.id;} |
685 bool operator<(const Node i) const {return id<i.id;} |
686 }; |
686 }; |
687 |
687 |
688 class Edge { |
688 class UEdge { |
689 friend class ListBpUGraphBase; |
689 friend class ListBpUGraphBase; |
690 protected: |
690 protected: |
691 int id; |
691 int id; |
692 |
692 |
693 explicit Edge(int _id) { id = _id;} |
693 explicit UEdge(int _id) { id = _id;} |
694 public: |
694 public: |
695 Edge() {} |
695 UEdge() {} |
696 Edge (Invalid) { id = -1; } |
696 UEdge (Invalid) { id = -1; } |
697 bool operator==(const Edge i) const {return id==i.id;} |
697 bool operator==(const UEdge i) const {return id==i.id;} |
698 bool operator!=(const Edge i) const {return id!=i.id;} |
698 bool operator!=(const UEdge i) const {return id!=i.id;} |
699 bool operator<(const Edge i) const {return id<i.id;} |
699 bool operator<(const UEdge i) const {return id<i.id;} |
700 }; |
700 }; |
701 |
701 |
702 ListBpUGraphBase() |
702 ListBpUGraphBase() |
703 : first_anode(-1), first_free_anode(-1), |
703 : first_anode(-1), first_free_anode(-1), |
704 first_bnode(-1), first_free_bnode(-1), |
704 first_bnode(-1), first_free_bnode(-1), |
738 } else { |
738 } else { |
739 node.id = bNodes[node.id >> 1].next_node; |
739 node.id = bNodes[node.id >> 1].next_node; |
740 } |
740 } |
741 } |
741 } |
742 |
742 |
743 void first(Edge& edge) const { |
743 void first(UEdge& edge) const { |
744 int aNodeId = first_anode; |
744 int aNodeId = first_anode; |
745 while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) { |
745 while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) { |
746 aNodeId = aNodes[aNodeId].next_node != -1 ? |
746 aNodeId = aNodes[aNodeId].next_node != -1 ? |
747 aNodes[aNodeId].next_node >> 1 : -1; |
747 aNodes[aNodeId].next_node >> 1 : -1; |
748 } |
748 } |
750 edge.id = aNodes[aNodeId].first_edge; |
750 edge.id = aNodes[aNodeId].first_edge; |
751 } else { |
751 } else { |
752 edge.id = -1; |
752 edge.id = -1; |
753 } |
753 } |
754 } |
754 } |
755 void next(Edge& edge) const { |
755 void next(UEdge& edge) const { |
756 int aNodeId = edges[edge.id].aNode >> 1; |
756 int aNodeId = edges[edge.id].aNode >> 1; |
757 edge.id = edges[edge.id].next_out; |
757 edge.id = edges[edge.id].next_out; |
758 if (edge.id == -1) { |
758 if (edge.id == -1) { |
759 aNodeId = aNodes[aNodeId].next_node != -1 ? |
759 aNodeId = aNodes[aNodeId].next_node != -1 ? |
760 aNodes[aNodeId].next_node >> 1 : -1; |
760 aNodes[aNodeId].next_node >> 1 : -1; |
768 edge.id = -1; |
768 edge.id = -1; |
769 } |
769 } |
770 } |
770 } |
771 } |
771 } |
772 |
772 |
773 void firstOut(Edge& edge, const Node& node) const { |
773 void firstFromANode(UEdge& edge, const Node& node) const { |
774 LEMON_ASSERT((node.id & 1) == 0, NodeSetError()); |
774 LEMON_ASSERT((node.id & 1) == 0, NodeSetError()); |
775 edge.id = aNodes[node.id >> 1].first_edge; |
775 edge.id = aNodes[node.id >> 1].first_edge; |
776 } |
776 } |
777 void nextOut(Edge& edge) const { |
777 void nextFromANode(UEdge& edge) const { |
778 edge.id = edges[edge.id].next_out; |
778 edge.id = edges[edge.id].next_out; |
779 } |
779 } |
780 |
780 |
781 void firstIn(Edge& edge, const Node& node) const { |
781 void firstFromBNode(UEdge& edge, const Node& node) const { |
782 LEMON_ASSERT((node.id & 1) == 1, NodeSetError()); |
782 LEMON_ASSERT((node.id & 1) == 1, NodeSetError()); |
783 edge.id = bNodes[node.id >> 1].first_edge; |
783 edge.id = bNodes[node.id >> 1].first_edge; |
784 } |
784 } |
785 void nextIn(Edge& edge) const { |
785 void nextFromBNode(UEdge& edge) const { |
786 edge.id = edges[edge.id].next_in; |
786 edge.id = edges[edge.id].next_in; |
787 } |
787 } |
788 |
788 |
789 static int id(const Node& node) { |
789 static int id(const Node& node) { |
790 return node.id; |
790 return node.id; |
795 int maxNodeId() const { |
795 int maxNodeId() const { |
796 return aNodes.size() > bNodes.size() ? |
796 return aNodes.size() > bNodes.size() ? |
797 aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1; |
797 aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1; |
798 } |
798 } |
799 |
799 |
800 static int id(const Edge& edge) { |
800 static int id(const UEdge& edge) { |
801 return edge.id; |
801 return edge.id; |
802 } |
802 } |
803 static Edge edgeFromId(int id) { |
803 static UEdge uEdgeFromId(int id) { |
804 return Edge(id); |
804 return UEdge(id); |
805 } |
805 } |
806 int maxEdgeId() const { |
806 int maxUEdgeId() const { |
807 return edges.size(); |
807 return edges.size(); |
808 } |
808 } |
809 |
809 |
810 static int aNodeId(const Node& node) { |
810 static int aNodeId(const Node& node) { |
811 return node.id >> 1; |
811 return node.id >> 1; |
825 } |
825 } |
826 int maxBNodeId() const { |
826 int maxBNodeId() const { |
827 return bNodes.size(); |
827 return bNodes.size(); |
828 } |
828 } |
829 |
829 |
830 Node aNode(const Edge& edge) const { |
830 Node aNode(const UEdge& edge) const { |
831 return Node(edges[edge.id].aNode); |
831 return Node(edges[edge.id].aNode); |
832 } |
832 } |
833 Node bNode(const Edge& edge) const { |
833 Node bNode(const UEdge& edge) const { |
834 return Node(edges[edge.id].bNode); |
834 return Node(edges[edge.id].bNode); |
835 } |
835 } |
836 |
836 |
837 static bool aNode(const Node& node) { |
837 static bool aNode(const Node& node) { |
838 return (node.id & 1) == 0; |
838 return (node.id & 1) == 0; |
872 first_bnode = bNodeId; |
872 first_bnode = bNodeId; |
873 bNodes[bNodeId].first_edge = -1; |
873 bNodes[bNodeId].first_edge = -1; |
874 return Node((bNodeId << 1) + 1); |
874 return Node((bNodeId << 1) + 1); |
875 } |
875 } |
876 |
876 |
877 Edge addEdge(const Node& source, const Node& target) { |
877 UEdge addEdge(const Node& source, const Node& target) { |
878 LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError()); |
878 LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError()); |
879 int edgeId; |
879 int edgeId; |
880 if (first_free_edge != -1) { |
880 if (first_free_edge != -1) { |
881 edgeId = first_free_edge; |
881 edgeId = first_free_edge; |
882 first_free_edge = edges[edgeId].next_out; |
882 first_free_edge = edges[edgeId].next_out; |
883 } else { |
883 } else { |
884 edgeId = edges.size(); |
884 edgeId = edges.size(); |
885 edges.push_back(EdgeT()); |
885 edges.push_back(UEdgeT()); |
886 } |
886 } |
887 if ((source.id & 1) == 0) { |
887 if ((source.id & 1) == 0) { |
888 edges[edgeId].aNode = source.id; |
888 edges[edgeId].aNode = source.id; |
889 edges[edgeId].bNode = target.id; |
889 edges[edgeId].bNode = target.id; |
890 } else { |
890 } else { |
901 edges[edgeId].prev_in = -1; |
901 edges[edgeId].prev_in = -1; |
902 if (bNodes[edges[edgeId].bNode >> 1].first_edge != -1) { |
902 if (bNodes[edges[edgeId].bNode >> 1].first_edge != -1) { |
903 edges[bNodes[edges[edgeId].bNode >> 1].first_edge].prev_in = edgeId; |
903 edges[bNodes[edges[edgeId].bNode >> 1].first_edge].prev_in = edgeId; |
904 } |
904 } |
905 bNodes[edges[edgeId].bNode >> 1].first_edge = edgeId; |
905 bNodes[edges[edgeId].bNode >> 1].first_edge = edgeId; |
906 return Edge(edgeId); |
906 return UEdge(edgeId); |
907 } |
907 } |
908 |
908 |
909 void erase(const Node& node) { |
909 void erase(const Node& node) { |
910 if (aNode(node)) { |
910 if (aNode(node)) { |
911 int aNodeId = node.id >> 1; |
911 int aNodeId = node.id >> 1; |
916 bNodes[bNodeId].next_node = first_free_bnode; |
916 bNodes[bNodeId].next_node = first_free_bnode; |
917 first_free_bnode = bNodeId; |
917 first_free_bnode = bNodeId; |
918 } |
918 } |
919 } |
919 } |
920 |
920 |
921 void erase(const Edge& edge) { |
921 void erase(const UEdge& edge) { |
922 if (edges[edge.id].prev_out != -1) { |
922 if (edges[edge.id].prev_out != -1) { |
923 edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out; |
923 edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out; |
924 } else { |
924 } else { |
925 aNodes[edges[edge.id].aNode].first_edge = edges[edge.id].next_out; |
925 aNodes[edges[edge.id].aNode].first_edge = edges[edge.id].next_out; |
926 } |
926 } |