634 } |
634 } |
635 erase(b); |
635 erase(b); |
636 } |
636 } |
637 }; |
637 }; |
638 |
638 |
|
639 |
|
640 class ListBpUGraphBase { |
|
641 public: |
|
642 |
|
643 class NodeSetError : public LogicError { |
|
644 virtual const char* exceptionName() const { |
|
645 return "lemon::ListBpUGraph::NodeSetError"; |
|
646 } |
|
647 }; |
|
648 |
|
649 protected: |
|
650 |
|
651 struct NodeT { |
|
652 int first_edge, next_node; |
|
653 }; |
|
654 |
|
655 struct EdgeT { |
|
656 int aNode, prev_out, next_out; |
|
657 int bNode, prev_in, next_in; |
|
658 }; |
|
659 |
|
660 std::vector<NodeT> aNodes; |
|
661 std::vector<NodeT> bNodes; |
|
662 |
|
663 std::vector<EdgeT> edges; |
|
664 |
|
665 int first_anode; |
|
666 int first_free_anode; |
|
667 |
|
668 int first_bnode; |
|
669 int first_free_bnode; |
|
670 |
|
671 int first_free_edge; |
|
672 |
|
673 public: |
|
674 |
|
675 class Node { |
|
676 friend class ListBpUGraphBase; |
|
677 protected: |
|
678 int id; |
|
679 |
|
680 Node(int _id) : id(_id) {} |
|
681 public: |
|
682 Node() {} |
|
683 Node(Invalid) { id = -1; } |
|
684 bool operator==(const Node i) const {return id==i.id;} |
|
685 bool operator!=(const Node i) const {return id!=i.id;} |
|
686 bool operator<(const Node i) const {return id<i.id;} |
|
687 }; |
|
688 |
|
689 class Edge { |
|
690 friend class ListBpUGraphBase; |
|
691 protected: |
|
692 int id; |
|
693 |
|
694 Edge(int _id) { id = _id;} |
|
695 public: |
|
696 Edge() {} |
|
697 Edge (Invalid) { id = -1; } |
|
698 bool operator==(const Edge i) const {return id==i.id;} |
|
699 bool operator!=(const Edge i) const {return id!=i.id;} |
|
700 bool operator<(const Edge i) const {return id<i.id;} |
|
701 }; |
|
702 |
|
703 ListBpUGraphBase() |
|
704 : first_anode(-1), first_free_anode(-1), |
|
705 first_bnode(-1), first_free_bnode(-1), |
|
706 first_free_edge(-1) {} |
|
707 |
|
708 void firstANode(Node& node) const { |
|
709 node.id = first_anode != -1 ? (first_anode << 1) : -1; |
|
710 } |
|
711 void nextANode(Node& node) const { |
|
712 node.id = aNodes[node.id >> 1].next_node; |
|
713 } |
|
714 |
|
715 void firstBNode(Node& node) const { |
|
716 node.id = first_bnode != -1 ? (first_bnode << 1) + 1 : -1; |
|
717 } |
|
718 void nextBNode(Node& node) const { |
|
719 node.id = aNodes[node.id >> 1].next_node; |
|
720 } |
|
721 |
|
722 void first(Node& node) const { |
|
723 if (first_anode != -1) { |
|
724 node.id = (first_anode << 1); |
|
725 } else if (first_bnode != -1) { |
|
726 node.id = (first_bnode << 1) + 1; |
|
727 } else { |
|
728 node.id = -1; |
|
729 } |
|
730 } |
|
731 void next(Node& node) const { |
|
732 if (aNode(node)) { |
|
733 node.id = aNodes[node.id >> 1].next_node; |
|
734 if (node.id == -1) { |
|
735 if (first_bnode != -1) { |
|
736 node.id = (first_bnode << 1) + 1; |
|
737 } |
|
738 } |
|
739 } else { |
|
740 node.id = bNodes[node.id >> 1].next_node; |
|
741 } |
|
742 } |
|
743 |
|
744 void first(Edge& edge) const { |
|
745 int aNodeId = first_anode; |
|
746 while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) { |
|
747 aNodeId = aNodes[aNodeId].next_node != -1 ? |
|
748 aNodes[aNodeId].next_node >> 1 : -1; |
|
749 } |
|
750 if (aNodeId != -1) { |
|
751 edge.id = aNodes[aNodeId].first_edge; |
|
752 } else { |
|
753 edge.id = -1; |
|
754 } |
|
755 } |
|
756 void next(Edge& edge) const { |
|
757 int aNodeId = edges[edge.id].aNode >> 1; |
|
758 edge.id = edges[edge.id].next_out; |
|
759 if (edge.id == -1) { |
|
760 aNodeId = aNodes[aNodeId].next_node != -1 ? |
|
761 aNodes[aNodeId].next_node >> 1 : -1; |
|
762 while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) { |
|
763 aNodeId = aNodes[aNodeId].next_node != -1 ? |
|
764 aNodes[aNodeId].next_node >> 1 : -1; |
|
765 } |
|
766 if (aNodeId != -1) { |
|
767 edge.id = aNodes[aNodeId].first_edge; |
|
768 } else { |
|
769 edge.id = -1; |
|
770 } |
|
771 } |
|
772 } |
|
773 |
|
774 void firstOut(Edge& edge, const Node& node) const { |
|
775 LEMON_ASSERT((node.id & 1) == 0, NodeSetError()); |
|
776 edge.id = aNodes[node.id >> 1].first_edge; |
|
777 } |
|
778 void nextOut(Edge& edge) const { |
|
779 edge.id = edges[edge.id].next_out; |
|
780 } |
|
781 |
|
782 void firstIn(Edge& edge, const Node& node) const { |
|
783 LEMON_ASSERT((node.id & 1) == 1, NodeSetError()); |
|
784 edge.id = bNodes[node.id >> 1].first_edge; |
|
785 } |
|
786 void nextIn(Edge& edge) const { |
|
787 edge.id = edges[edge.id].next_in; |
|
788 } |
|
789 |
|
790 static int id(const Node& node) { |
|
791 return node.id; |
|
792 } |
|
793 static Node nodeFromId(int id) { |
|
794 return Node(id); |
|
795 } |
|
796 int maxNodeId() const { |
|
797 return aNodes.size() > bNodes.size() ? |
|
798 aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1; |
|
799 } |
|
800 |
|
801 static int id(const Edge& edge) { |
|
802 return edge.id; |
|
803 } |
|
804 static Edge edgeFromId(int id) { |
|
805 return Edge(id); |
|
806 } |
|
807 int maxEdgeId() const { |
|
808 return edges.size(); |
|
809 } |
|
810 |
|
811 static int aNodeId(const Node& node) { |
|
812 return node.id >> 1; |
|
813 } |
|
814 static Node fromANodeId(int id, Node) { |
|
815 return Node(id << 1); |
|
816 } |
|
817 int maxANodeId() const { |
|
818 return aNodes.size(); |
|
819 } |
|
820 |
|
821 static int bNodeId(const Node& node) { |
|
822 return node.id >> 1; |
|
823 } |
|
824 static Node fromBNodeId(int id) { |
|
825 return Node((id << 1) + 1); |
|
826 } |
|
827 int maxBNodeId() const { |
|
828 return bNodes.size(); |
|
829 } |
|
830 |
|
831 Node aNode(const Edge& edge) const { |
|
832 return Node(edges[edge.id].aNode); |
|
833 } |
|
834 Node bNode(const Edge& edge) const { |
|
835 return Node(edges[edge.id].bNode); |
|
836 } |
|
837 |
|
838 static bool aNode(const Node& node) { |
|
839 return (node.id & 1) == 0; |
|
840 } |
|
841 |
|
842 static bool bNode(const Node& node) { |
|
843 return (node.id & 1) == 1; |
|
844 } |
|
845 |
|
846 Node addANode() { |
|
847 int aNodeId; |
|
848 if (first_free_anode == -1) { |
|
849 aNodeId = aNodes.size(); |
|
850 aNodes.push_back(NodeT()); |
|
851 } else { |
|
852 aNodeId = first_free_anode; |
|
853 first_free_anode = aNodes[first_free_anode].next_node; |
|
854 } |
|
855 aNodes[aNodeId].next_node = |
|
856 first_anode != -1 ? (first_anode << 1) : -1; |
|
857 first_anode = aNodeId; |
|
858 aNodes[aNodeId].first_edge = -1; |
|
859 return Node(aNodeId << 1); |
|
860 } |
|
861 |
|
862 Node addBNode() { |
|
863 int bNodeId; |
|
864 if (first_free_anode == -1) { |
|
865 bNodeId = bNodes.size(); |
|
866 bNodes.push_back(NodeT()); |
|
867 } else { |
|
868 bNodeId = first_free_bnode; |
|
869 first_free_bnode = bNodes[first_free_bnode].next_node; |
|
870 } |
|
871 bNodes[bNodeId].next_node = |
|
872 first_bnode != -1 ? (first_bnode << 1) + 1 : -1; |
|
873 first_bnode = bNodeId; |
|
874 bNodes[bNodeId].first_edge = -1; |
|
875 return Node((bNodeId << 1) + 1); |
|
876 } |
|
877 |
|
878 Edge addEdge(const Node& source, const Node& target) { |
|
879 LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError()); |
|
880 int edgeId; |
|
881 if (first_free_edge != -1) { |
|
882 edgeId = first_free_edge; |
|
883 first_free_edge = edges[edgeId].next_out; |
|
884 } else { |
|
885 edgeId = edges.size(); |
|
886 edges.push_back(EdgeT()); |
|
887 } |
|
888 if ((source.id & 1) == 0) { |
|
889 edges[edgeId].aNode = source.id; |
|
890 edges[edgeId].bNode = target.id; |
|
891 } else { |
|
892 edges[edgeId].aNode = target.id; |
|
893 edges[edgeId].bNode = source.id; |
|
894 } |
|
895 edges[edgeId].next_out = aNodes[edges[edgeId].aNode >> 1].first_edge; |
|
896 edges[edgeId].prev_out = -1; |
|
897 if (aNodes[edges[edgeId].aNode >> 1].first_edge != -1) { |
|
898 edges[aNodes[edges[edgeId].aNode >> 1].first_edge].prev_out = edgeId; |
|
899 } |
|
900 aNodes[edges[edgeId].aNode >> 1].first_edge = edgeId; |
|
901 edges[edgeId].next_in = bNodes[edges[edgeId].bNode >> 1].first_edge; |
|
902 edges[edgeId].prev_in = -1; |
|
903 if (bNodes[edges[edgeId].bNode >> 1].first_edge != -1) { |
|
904 edges[bNodes[edges[edgeId].bNode >> 1].first_edge].prev_in = edgeId; |
|
905 } |
|
906 bNodes[edges[edgeId].bNode >> 1].first_edge = edgeId; |
|
907 return Edge(edgeId); |
|
908 } |
|
909 |
|
910 void erase(const Node& node) { |
|
911 if (aNode(node)) { |
|
912 int aNodeId = node.id >> 1; |
|
913 aNodes[aNodeId].next_node = first_free_anode; |
|
914 first_free_anode = aNodeId; |
|
915 } else { |
|
916 int bNodeId = node.id >> 1; |
|
917 bNodes[bNodeId].next_node = first_free_bnode; |
|
918 first_free_bnode = bNodeId; |
|
919 } |
|
920 } |
|
921 |
|
922 void erase(const Edge& edge) { |
|
923 if (edges[edge.id].prev_out != -1) { |
|
924 edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out; |
|
925 } else { |
|
926 aNodes[edges[edge.id].aNode].first_edge = edges[edge.id].next_out; |
|
927 } |
|
928 if (edges[edge.id].next_out != -1) { |
|
929 edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out; |
|
930 } |
|
931 if (edges[edge.id].prev_in != -1) { |
|
932 edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in; |
|
933 } else { |
|
934 bNodes[edges[edge.id].bNode].first_edge = edges[edge.id].next_in; |
|
935 } |
|
936 if (edges[edge.id].next_in != -1) { |
|
937 edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in; |
|
938 } |
|
939 edges[edge.id].next_out = first_free_edge; |
|
940 first_free_edge = edge.id; |
|
941 } |
|
942 |
|
943 void clear() { |
|
944 aNodes.clear(); |
|
945 bNodes.clear(); |
|
946 edges.clear(); |
|
947 first_anode = -1; |
|
948 first_free_anode = -1; |
|
949 first_bnode = -1; |
|
950 first_free_bnode = -1; |
|
951 first_free_edge = -1; |
|
952 } |
|
953 |
|
954 }; |
|
955 |
|
956 |
|
957 typedef BpUGraphExtender< BpUGraphBaseExtender< |
|
958 ListBpUGraphBase> > ExtendedListBpUGraphBase; |
|
959 |
|
960 /// \ingroup graphs |
|
961 /// |
|
962 /// \brief A smart bipartite undirected graph class. |
|
963 /// |
|
964 /// This is a bipartite undirected graph implementation. |
|
965 /// Except from this it conforms to |
|
966 /// the \ref concept::BpUGraph "BpUGraph" concept. |
|
967 /// \sa concept::BpUGraph. |
|
968 /// |
|
969 class ListBpUGraph : public ExtendedListBpUGraphBase {}; |
|
970 |
639 |
971 |
640 /// @} |
972 /// @} |
641 } //namespace lemon |
973 } //namespace lemon |
642 |
974 |
643 |
975 |