703 } |
699 } |
704 }; |
700 }; |
705 |
701 |
706 }; |
702 }; |
707 |
703 |
708 ///@} |
|
709 |
|
710 /**************** Undirected List Graph ****************/ |
|
711 |
|
712 typedef UGraphExtender<UndirGraphExtender<ListGraphBase> > |
|
713 ExtendedListUGraphBase; |
|
714 |
|
715 /// \addtogroup graphs |
|
716 /// @{ |
|
717 |
|
718 ///An undirected list graph class. |
|
719 |
|
720 ///This is a simple and fast erasable undirected graph implementation. |
|
721 /// |
|
722 ///It conforms to the |
|
723 ///\ref concept::UGraph "UGraph" concept. |
|
724 /// |
|
725 ///\sa concept::UGraph. |
|
726 /// |
|
727 ///\todo Snapshot, reverseEdge(), changeTarget(), changeSource(), contract() |
|
728 ///haven't been implemented yet. |
|
729 /// |
|
730 class ListUGraph : public ExtendedListUGraphBase { |
|
731 public: |
|
732 typedef ExtendedListUGraphBase Parent; |
|
733 /// \brief Add a new node to the graph. |
|
734 /// |
|
735 /// \return the new node. |
|
736 /// |
|
737 Node addNode() { return Parent::addNode(); } |
|
738 |
|
739 /// \brief Add a new edge to the graph. |
|
740 /// |
|
741 /// Add a new edge to the graph with source node \c s |
|
742 /// and target node \c t. |
|
743 /// \return the new undirected edge. |
|
744 UEdge addEdge(const Node& s, const Node& t) { |
|
745 return Parent::addEdge(s, t); |
|
746 } |
|
747 /// \brief Changes the target of \c e to \c n |
|
748 /// |
|
749 /// Changes the target of \c e to \c n |
|
750 /// |
|
751 /// \note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s |
|
752 /// referencing the changed edge remain |
|
753 /// valid. However <tt>InEdge</tt>'s are invalidated. |
|
754 void changeTarget(UEdge e, Node n) { |
|
755 Parent::changeTarget(e,n); |
|
756 } |
|
757 /// Changes the source of \c e to \c n |
|
758 /// |
|
759 /// Changes the source of \c e to \c n |
|
760 /// |
|
761 ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s |
|
762 ///referencing the changed edge remain |
|
763 ///valid. However <tt>OutEdge</tt>'s are invalidated. |
|
764 void changeSource(UEdge e, Node n) { |
|
765 Parent::changeSource(e,n); |
|
766 } |
|
767 /// \brief Contract two nodes. |
|
768 /// |
|
769 /// This function contracts two nodes. |
|
770 /// |
|
771 /// Node \p b will be removed but instead of deleting |
|
772 /// its neighboring edges, they will be joined to \p a. |
|
773 /// The last parameter \p r controls whether to remove loops. \c true |
|
774 /// means that loops will be removed. |
|
775 /// |
|
776 /// \note The <tt>Edge</tt>s |
|
777 /// referencing a moved edge remain |
|
778 /// valid. |
|
779 void contract(Node a, Node b, bool r = true) { |
|
780 for(IncEdgeIt e(*this, b); e!=INVALID;) { |
|
781 IncEdgeIt f = e; ++f; |
|
782 if (r && runningNode(e) == a) { |
|
783 erase(e); |
|
784 } else if (source(e) == b) { |
|
785 changeSource(e, a); |
|
786 } else { |
|
787 changeTarget(e, a); |
|
788 } |
|
789 e = f; |
|
790 } |
|
791 erase(b); |
|
792 } |
|
793 }; |
|
794 |
|
795 |
|
796 class ListBpUGraphBase { |
|
797 public: |
|
798 |
|
799 class NodeSetError : public LogicError { |
|
800 virtual const char* exceptionName() const { |
|
801 return "lemon::ListBpUGraph::NodeSetError"; |
|
802 } |
|
803 }; |
|
804 |
|
805 protected: |
|
806 |
|
807 struct NodeT { |
|
808 int first_edge, prev, next; |
|
809 }; |
|
810 |
|
811 struct UEdgeT { |
|
812 int aNode, prev_out, next_out; |
|
813 int bNode, prev_in, next_in; |
|
814 }; |
|
815 |
|
816 std::vector<NodeT> aNodes; |
|
817 std::vector<NodeT> bNodes; |
|
818 |
|
819 std::vector<UEdgeT> edges; |
|
820 |
|
821 int first_anode; |
|
822 int first_free_anode; |
|
823 |
|
824 int first_bnode; |
|
825 int first_free_bnode; |
|
826 |
|
827 int first_free_edge; |
|
828 |
|
829 public: |
|
830 |
|
831 class Node { |
|
832 friend class ListBpUGraphBase; |
|
833 protected: |
|
834 int id; |
|
835 |
|
836 explicit Node(int _id) : id(_id) {} |
|
837 public: |
|
838 Node() {} |
|
839 Node(Invalid) { id = -1; } |
|
840 bool operator==(const Node i) const {return id==i.id;} |
|
841 bool operator!=(const Node i) const {return id!=i.id;} |
|
842 bool operator<(const Node i) const {return id<i.id;} |
|
843 }; |
|
844 |
|
845 class UEdge { |
|
846 friend class ListBpUGraphBase; |
|
847 protected: |
|
848 int id; |
|
849 |
|
850 explicit UEdge(int _id) { id = _id;} |
|
851 public: |
|
852 UEdge() {} |
|
853 UEdge (Invalid) { id = -1; } |
|
854 bool operator==(const UEdge i) const {return id==i.id;} |
|
855 bool operator!=(const UEdge i) const {return id!=i.id;} |
|
856 bool operator<(const UEdge i) const {return id<i.id;} |
|
857 }; |
|
858 |
|
859 ListBpUGraphBase() |
|
860 : first_anode(-1), first_free_anode(-1), |
|
861 first_bnode(-1), first_free_bnode(-1), |
|
862 first_free_edge(-1) {} |
|
863 |
|
864 void firstANode(Node& node) const { |
|
865 node.id = first_anode != -1 ? (first_anode << 1) : -1; |
|
866 } |
|
867 void nextANode(Node& node) const { |
|
868 node.id = aNodes[node.id >> 1].next; |
|
869 } |
|
870 |
|
871 void firstBNode(Node& node) const { |
|
872 node.id = first_bnode != -1 ? (first_bnode << 1) + 1 : -1; |
|
873 } |
|
874 void nextBNode(Node& node) const { |
|
875 node.id = bNodes[node.id >> 1].next; |
|
876 } |
|
877 |
|
878 void first(Node& node) const { |
|
879 if (first_anode != -1) { |
|
880 node.id = (first_anode << 1); |
|
881 } else if (first_bnode != -1) { |
|
882 node.id = (first_bnode << 1) + 1; |
|
883 } else { |
|
884 node.id = -1; |
|
885 } |
|
886 } |
|
887 void next(Node& node) const { |
|
888 if (aNode(node)) { |
|
889 node.id = aNodes[node.id >> 1].next; |
|
890 if (node.id == -1) { |
|
891 if (first_bnode != -1) { |
|
892 node.id = (first_bnode << 1) + 1; |
|
893 } |
|
894 } |
|
895 } else { |
|
896 node.id = bNodes[node.id >> 1].next; |
|
897 } |
|
898 } |
|
899 |
|
900 void first(UEdge& edge) const { |
|
901 int aNodeId = first_anode; |
|
902 while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) { |
|
903 aNodeId = aNodes[aNodeId].next != -1 ? |
|
904 aNodes[aNodeId].next >> 1 : -1; |
|
905 } |
|
906 if (aNodeId != -1) { |
|
907 edge.id = aNodes[aNodeId].first_edge; |
|
908 } else { |
|
909 edge.id = -1; |
|
910 } |
|
911 } |
|
912 void next(UEdge& edge) const { |
|
913 int aNodeId = edges[edge.id].aNode >> 1; |
|
914 edge.id = edges[edge.id].next_out; |
|
915 if (edge.id == -1) { |
|
916 aNodeId = aNodes[aNodeId].next != -1 ? |
|
917 aNodes[aNodeId].next >> 1 : -1; |
|
918 while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) { |
|
919 aNodeId = aNodes[aNodeId].next != -1 ? |
|
920 aNodes[aNodeId].next >> 1 : -1; |
|
921 } |
|
922 if (aNodeId != -1) { |
|
923 edge.id = aNodes[aNodeId].first_edge; |
|
924 } else { |
|
925 edge.id = -1; |
|
926 } |
|
927 } |
|
928 } |
|
929 |
|
930 void firstFromANode(UEdge& edge, const Node& node) const { |
|
931 LEMON_ASSERT((node.id & 1) == 0, NodeSetError()); |
|
932 edge.id = aNodes[node.id >> 1].first_edge; |
|
933 } |
|
934 void nextFromANode(UEdge& edge) const { |
|
935 edge.id = edges[edge.id].next_out; |
|
936 } |
|
937 |
|
938 void firstFromBNode(UEdge& edge, const Node& node) const { |
|
939 LEMON_ASSERT((node.id & 1) == 1, NodeSetError()); |
|
940 edge.id = bNodes[node.id >> 1].first_edge; |
|
941 } |
|
942 void nextFromBNode(UEdge& edge) const { |
|
943 edge.id = edges[edge.id].next_in; |
|
944 } |
|
945 |
|
946 static int id(const Node& node) { |
|
947 return node.id; |
|
948 } |
|
949 static Node nodeFromId(int id) { |
|
950 return Node(id); |
|
951 } |
|
952 int maxNodeId() const { |
|
953 return aNodes.size() > bNodes.size() ? |
|
954 aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1; |
|
955 } |
|
956 |
|
957 static int id(const UEdge& edge) { |
|
958 return edge.id; |
|
959 } |
|
960 static UEdge uEdgeFromId(int id) { |
|
961 return UEdge(id); |
|
962 } |
|
963 int maxUEdgeId() const { |
|
964 return edges.size(); |
|
965 } |
|
966 |
|
967 static int aNodeId(const Node& node) { |
|
968 return node.id >> 1; |
|
969 } |
|
970 static Node fromANodeId(int id) { |
|
971 return Node(id << 1); |
|
972 } |
|
973 int maxANodeId() const { |
|
974 return aNodes.size(); |
|
975 } |
|
976 |
|
977 static int bNodeId(const Node& node) { |
|
978 return node.id >> 1; |
|
979 } |
|
980 static Node fromBNodeId(int id) { |
|
981 return Node((id << 1) + 1); |
|
982 } |
|
983 int maxBNodeId() const { |
|
984 return bNodes.size(); |
|
985 } |
|
986 |
|
987 Node aNode(const UEdge& edge) const { |
|
988 return Node(edges[edge.id].aNode); |
|
989 } |
|
990 Node bNode(const UEdge& edge) const { |
|
991 return Node(edges[edge.id].bNode); |
|
992 } |
|
993 |
|
994 static bool aNode(const Node& node) { |
|
995 return (node.id & 1) == 0; |
|
996 } |
|
997 |
|
998 static bool bNode(const Node& node) { |
|
999 return (node.id & 1) == 1; |
|
1000 } |
|
1001 |
|
1002 Node addANode() { |
|
1003 int aNodeId; |
|
1004 if (first_free_anode == -1) { |
|
1005 aNodeId = aNodes.size(); |
|
1006 aNodes.push_back(NodeT()); |
|
1007 } else { |
|
1008 aNodeId = first_free_anode; |
|
1009 first_free_anode = aNodes[first_free_anode].next; |
|
1010 } |
|
1011 if (first_anode != -1) { |
|
1012 aNodes[aNodeId].next = first_anode << 1; |
|
1013 aNodes[first_anode].prev = aNodeId << 1; |
|
1014 } else { |
|
1015 aNodes[aNodeId].next = -1; |
|
1016 } |
|
1017 aNodes[aNodeId].prev = -1; |
|
1018 first_anode = aNodeId; |
|
1019 aNodes[aNodeId].first_edge = -1; |
|
1020 return Node(aNodeId << 1); |
|
1021 } |
|
1022 |
|
1023 Node addBNode() { |
|
1024 int bNodeId; |
|
1025 if (first_free_bnode == -1) { |
|
1026 bNodeId = bNodes.size(); |
|
1027 bNodes.push_back(NodeT()); |
|
1028 } else { |
|
1029 bNodeId = first_free_bnode; |
|
1030 first_free_bnode = bNodes[first_free_bnode].next; |
|
1031 } |
|
1032 if (first_bnode != -1) { |
|
1033 bNodes[bNodeId].next = (first_bnode << 1) + 1; |
|
1034 bNodes[first_bnode].prev = (bNodeId << 1) + 1; |
|
1035 } else { |
|
1036 bNodes[bNodeId].next = -1; |
|
1037 } |
|
1038 first_bnode = bNodeId; |
|
1039 bNodes[bNodeId].first_edge = -1; |
|
1040 return Node((bNodeId << 1) + 1); |
|
1041 } |
|
1042 |
|
1043 UEdge addEdge(const Node& source, const Node& target) { |
|
1044 LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError()); |
|
1045 int edgeId; |
|
1046 if (first_free_edge != -1) { |
|
1047 edgeId = first_free_edge; |
|
1048 first_free_edge = edges[edgeId].next_out; |
|
1049 } else { |
|
1050 edgeId = edges.size(); |
|
1051 edges.push_back(UEdgeT()); |
|
1052 } |
|
1053 if ((source.id & 1) == 0) { |
|
1054 edges[edgeId].aNode = source.id; |
|
1055 edges[edgeId].bNode = target.id; |
|
1056 } else { |
|
1057 edges[edgeId].aNode = target.id; |
|
1058 edges[edgeId].bNode = source.id; |
|
1059 } |
|
1060 edges[edgeId].next_out = aNodes[edges[edgeId].aNode >> 1].first_edge; |
|
1061 edges[edgeId].prev_out = -1; |
|
1062 if (aNodes[edges[edgeId].aNode >> 1].first_edge != -1) { |
|
1063 edges[aNodes[edges[edgeId].aNode >> 1].first_edge].prev_out = edgeId; |
|
1064 } |
|
1065 aNodes[edges[edgeId].aNode >> 1].first_edge = edgeId; |
|
1066 edges[edgeId].next_in = bNodes[edges[edgeId].bNode >> 1].first_edge; |
|
1067 edges[edgeId].prev_in = -1; |
|
1068 if (bNodes[edges[edgeId].bNode >> 1].first_edge != -1) { |
|
1069 edges[bNodes[edges[edgeId].bNode >> 1].first_edge].prev_in = edgeId; |
|
1070 } |
|
1071 bNodes[edges[edgeId].bNode >> 1].first_edge = edgeId; |
|
1072 return UEdge(edgeId); |
|
1073 } |
|
1074 |
|
1075 void erase(const Node& node) { |
|
1076 if (aNode(node)) { |
|
1077 int aNodeId = node.id >> 1; |
|
1078 if (aNodes[aNodeId].prev != -1) { |
|
1079 aNodes[aNodes[aNodeId].prev >> 1].next = aNodes[aNodeId].next; |
|
1080 } else { |
|
1081 first_anode = aNodes[aNodeId].next >> 1; |
|
1082 } |
|
1083 if (aNodes[aNodeId].next != -1) { |
|
1084 aNodes[aNodes[aNodeId].next >> 1].prev = aNodes[aNodeId].prev; |
|
1085 } |
|
1086 aNodes[aNodeId].next = first_free_anode; |
|
1087 first_free_anode = aNodeId; |
|
1088 } else { |
|
1089 int bNodeId = node.id >> 1; |
|
1090 if (bNodes[bNodeId].prev != -1) { |
|
1091 bNodes[bNodes[bNodeId].prev >> 1].next = bNodes[bNodeId].next; |
|
1092 } else { |
|
1093 first_bnode = bNodes[bNodeId].next >> 1; |
|
1094 } |
|
1095 if (bNodes[bNodeId].next != -1) { |
|
1096 bNodes[bNodes[bNodeId].next >> 1].prev = bNodes[bNodeId].prev; |
|
1097 } |
|
1098 bNodes[bNodeId].next = first_free_bnode; |
|
1099 first_free_bnode = bNodeId; |
|
1100 } |
|
1101 } |
|
1102 |
|
1103 void erase(const UEdge& edge) { |
|
1104 |
|
1105 if (edges[edge.id].prev_out != -1) { |
|
1106 edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out; |
|
1107 } else { |
|
1108 aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out; |
|
1109 } |
|
1110 if (edges[edge.id].next_out != -1) { |
|
1111 edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out; |
|
1112 } |
|
1113 |
|
1114 if (edges[edge.id].prev_in != -1) { |
|
1115 edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in; |
|
1116 } else { |
|
1117 bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in; |
|
1118 } |
|
1119 if (edges[edge.id].next_in != -1) { |
|
1120 edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in; |
|
1121 } |
|
1122 |
|
1123 edges[edge.id].next_out = first_free_edge; |
|
1124 first_free_edge = edge.id; |
|
1125 } |
|
1126 |
|
1127 void clear() { |
|
1128 aNodes.clear(); |
|
1129 bNodes.clear(); |
|
1130 edges.clear(); |
|
1131 first_anode = -1; |
|
1132 first_free_anode = -1; |
|
1133 first_bnode = -1; |
|
1134 first_free_bnode = -1; |
|
1135 first_free_edge = -1; |
|
1136 } |
|
1137 |
|
1138 }; |
|
1139 |
|
1140 |
|
1141 typedef BpUGraphExtender< ListBpUGraphBase > ExtendedListBpUGraphBase; |
|
1142 |
|
1143 /// \ingroup graphs |
|
1144 /// |
|
1145 /// \brief A smart bipartite undirected graph class. |
|
1146 /// |
|
1147 /// This is a bipartite undirected graph implementation. |
|
1148 /// It is conforms to the \ref concept::ErasableBpUGraph "ErasableBpUGraph" |
|
1149 /// concept. |
|
1150 /// \sa concept::BpUGraph. |
|
1151 /// |
|
1152 class ListBpUGraph : public ExtendedListBpUGraphBase {}; |
|
1153 |
|
1154 |
|
1155 /// @} |
|
1156 } //namespace lemon |
704 } //namespace lemon |
1157 |
705 |
1158 |
706 |
1159 #endif |
707 #endif |