733 |
718 |
734 }; |
719 }; |
735 |
720 |
736 ///@} |
721 ///@} |
737 |
722 |
738 /**************** Undirected List Graph ****************/ |
723 class ListUGraphBase { |
739 |
724 |
740 typedef UGraphExtender<UndirGraphExtender<ListGraphBase> > |
725 protected: |
741 ExtendedListUGraphBase; |
726 |
|
727 struct NodeT { |
|
728 int first_out; |
|
729 int prev, next; |
|
730 }; |
|
731 |
|
732 struct EdgeT { |
|
733 int target; |
|
734 int prev_out, next_out; |
|
735 }; |
|
736 |
|
737 std::vector<NodeT> nodes; |
|
738 |
|
739 int first_node; |
|
740 |
|
741 int first_free_node; |
|
742 |
|
743 std::vector<EdgeT> edges; |
|
744 |
|
745 int first_free_edge; |
|
746 |
|
747 public: |
|
748 |
|
749 typedef ListUGraphBase Graph; |
|
750 |
|
751 class Node { |
|
752 friend class ListUGraphBase; |
|
753 protected: |
|
754 |
|
755 int id; |
|
756 explicit Node(int pid) { id = pid;} |
|
757 |
|
758 public: |
|
759 Node() {} |
|
760 Node (Invalid) { id = -1; } |
|
761 bool operator==(const Node& node) const {return id == node.id;} |
|
762 bool operator!=(const Node& node) const {return id != node.id;} |
|
763 bool operator<(const Node& node) const {return id < node.id;} |
|
764 }; |
|
765 |
|
766 class UEdge { |
|
767 friend class ListUGraphBase; |
|
768 protected: |
|
769 |
|
770 int id; |
|
771 explicit UEdge(int pid) { id = pid;} |
|
772 |
|
773 public: |
|
774 UEdge() {} |
|
775 UEdge (Invalid) { id = -1; } |
|
776 bool operator==(const UEdge& edge) const {return id == edge.id;} |
|
777 bool operator!=(const UEdge& edge) const {return id != edge.id;} |
|
778 bool operator<(const UEdge& edge) const {return id < edge.id;} |
|
779 }; |
|
780 |
|
781 class Edge { |
|
782 friend class ListUGraphBase; |
|
783 protected: |
|
784 |
|
785 int id; |
|
786 explicit Edge(int pid) { id = pid;} |
|
787 |
|
788 public: |
|
789 operator UEdge() const { return UEdge(id / 2); } |
|
790 |
|
791 Edge() {} |
|
792 Edge (Invalid) { id = -1; } |
|
793 bool operator==(const Edge& edge) const {return id == edge.id;} |
|
794 bool operator!=(const Edge& edge) const {return id != edge.id;} |
|
795 bool operator<(const Edge& edge) const {return id < edge.id;} |
|
796 }; |
|
797 |
|
798 |
|
799 |
|
800 ListUGraphBase() |
|
801 : nodes(), first_node(-1), |
|
802 first_free_node(-1), edges(), first_free_edge(-1) {} |
|
803 |
|
804 |
|
805 int maxNodeId() const { return nodes.size()-1; } |
|
806 int maxUEdgeId() const { return edges.size() / 2 - 1; } |
|
807 int maxEdgeId() const { return edges.size()-1; } |
|
808 |
|
809 Node source(Edge e) const { return Node(edges[e.id ^ 1].target); } |
|
810 Node target(Edge e) const { return Node(edges[e.id].target); } |
|
811 |
|
812 Node source(UEdge e) const { return Node(edges[2 * e.id].target); } |
|
813 Node target(UEdge e) const { return Node(edges[2 * e.id + 1].target); } |
|
814 |
|
815 static bool direction(Edge e) { |
|
816 return (e.id & 1) == 1; |
|
817 } |
|
818 |
|
819 static Edge direct(UEdge e, bool d) { |
|
820 return Edge(e.id * 2 + (d ? 1 : 0)); |
|
821 } |
|
822 |
|
823 void first(Node& node) const { |
|
824 node.id = first_node; |
|
825 } |
|
826 |
|
827 void next(Node& node) const { |
|
828 node.id = nodes[node.id].next; |
|
829 } |
|
830 |
|
831 void first(Edge& e) const { |
|
832 int n = first_node; |
|
833 while (n != -1 && nodes[n].first_out == -1) { |
|
834 n = nodes[n].next; |
|
835 } |
|
836 e.id = (n == -1) ? -1 : nodes[n].first_out; |
|
837 } |
|
838 |
|
839 void next(Edge& e) const { |
|
840 if (edges[e.id].next_out != -1) { |
|
841 e.id = edges[e.id].next_out; |
|
842 } else { |
|
843 int n = nodes[edges[e.id ^ 1].target].next; |
|
844 while(n != -1 && nodes[n].first_out == -1) { |
|
845 n = nodes[n].next; |
|
846 } |
|
847 e.id = (n == -1) ? -1 : nodes[n].first_out; |
|
848 } |
|
849 } |
|
850 |
|
851 void first(UEdge& e) const { |
|
852 int n = first_node; |
|
853 while (n != -1) { |
|
854 e.id = nodes[n].first_out; |
|
855 while ((e.id & 1) != 1) { |
|
856 e.id = edges[e.id].next_out; |
|
857 } |
|
858 if (e.id != -1) { |
|
859 e.id /= 2; |
|
860 return; |
|
861 } |
|
862 n = nodes[n].next; |
|
863 } |
|
864 e.id = -1; |
|
865 } |
|
866 |
|
867 void next(UEdge& e) const { |
|
868 int n = edges[e.id * 2].target; |
|
869 e.id = edges[(e.id * 2) | 1].next_out; |
|
870 while ((e.id & 1) != 1) { |
|
871 e.id = edges[e.id].next_out; |
|
872 } |
|
873 if (e.id != -1) { |
|
874 e.id /= 2; |
|
875 return; |
|
876 } |
|
877 n = nodes[n].next; |
|
878 while (n != -1) { |
|
879 e.id = nodes[n].first_out; |
|
880 while ((e.id & 1) != 1) { |
|
881 e.id = edges[e.id].next_out; |
|
882 } |
|
883 if (e.id != -1) { |
|
884 e.id /= 2; |
|
885 return; |
|
886 } |
|
887 n = nodes[n].next; |
|
888 } |
|
889 e.id = -1; |
|
890 } |
|
891 |
|
892 void firstOut(Edge &e, const Node& v) const { |
|
893 e.id = nodes[v.id].first_out; |
|
894 } |
|
895 void nextOut(Edge &e) const { |
|
896 e.id = edges[e.id].next_out; |
|
897 } |
|
898 |
|
899 void firstIn(Edge &e, const Node& v) const { |
|
900 e.id = ((nodes[v.id].first_out) ^ 1); |
|
901 if (e.id == -2) e.id = -1; |
|
902 } |
|
903 void nextIn(Edge &e) const { |
|
904 e.id = ((edges[e.id ^ 1].next_out) ^ 1); |
|
905 if (e.id == -2) e.id = -1; |
|
906 } |
|
907 |
|
908 void firstInc(UEdge &e, bool& d, const Node& v) const { |
|
909 int de = nodes[v.id].first_out; |
|
910 e.id = de / 2; |
|
911 d = ((de & 1) == 1); |
|
912 } |
|
913 void nextInc(UEdge &e, bool& d) const { |
|
914 int de = (edges[(e.id * 2) | (d ? 1 : 0)].next_out); |
|
915 e.id = de / 2; |
|
916 d = ((de & 1) == 1); |
|
917 } |
|
918 |
|
919 static int id(Node v) { return v.id; } |
|
920 static int id(Edge e) { return e.id; } |
|
921 static int id(UEdge e) { return e.id; } |
|
922 |
|
923 static Node nodeFromId(int id) { return Node(id);} |
|
924 static Edge edgeFromId(int id) { return Edge(id);} |
|
925 static UEdge uEdgeFromId(int id) { return UEdge(id);} |
|
926 |
|
927 Node addNode() { |
|
928 int n; |
|
929 |
|
930 if(first_free_node==-1) { |
|
931 n = nodes.size(); |
|
932 nodes.push_back(NodeT()); |
|
933 } else { |
|
934 n = first_free_node; |
|
935 first_free_node = nodes[n].next; |
|
936 } |
|
937 |
|
938 nodes[n].next = first_node; |
|
939 if (first_node != -1) nodes[first_node].prev = n; |
|
940 first_node = n; |
|
941 nodes[n].prev = -1; |
|
942 |
|
943 nodes[n].first_out = -1; |
|
944 |
|
945 return Node(n); |
|
946 } |
|
947 |
|
948 UEdge addEdge(Node u, Node v) { |
|
949 int n; |
|
950 |
|
951 if (first_free_edge == -1) { |
|
952 n = edges.size(); |
|
953 edges.push_back(EdgeT()); |
|
954 edges.push_back(EdgeT()); |
|
955 } else { |
|
956 n = first_free_edge; |
|
957 first_free_edge = edges[n].next_out; |
|
958 } |
|
959 |
|
960 edges[n].target = u.id; |
|
961 edges[n | 1].target = v.id; |
|
962 |
|
963 edges[n].next_out = nodes[v.id].first_out; |
|
964 edges[n | 1].next_out = nodes[u.id].first_out; |
|
965 if (nodes[v.id].first_out != -1) { |
|
966 edges[nodes[v.id].first_out].prev_out = n; |
|
967 } |
|
968 if (nodes[u.id].first_out != -1) { |
|
969 edges[nodes[u.id].first_out].prev_out = (n | 1); |
|
970 } |
|
971 |
|
972 edges[n].prev_out = edges[n | 1].prev_out = -1; |
|
973 |
|
974 nodes[v.id].first_out = n; |
|
975 nodes[u.id].first_out = (n | 1); |
|
976 |
|
977 return UEdge(n / 2); |
|
978 } |
|
979 |
|
980 void erase(const Node& node) { |
|
981 int n = node.id; |
|
982 |
|
983 if(nodes[n].next != -1) { |
|
984 nodes[nodes[n].next].prev = nodes[n].prev; |
|
985 } |
|
986 |
|
987 if(nodes[n].prev != -1) { |
|
988 nodes[nodes[n].prev].next = nodes[n].next; |
|
989 } else { |
|
990 first_node = nodes[n].next; |
|
991 } |
|
992 |
|
993 nodes[n].next = first_free_node; |
|
994 first_free_node = n; |
|
995 |
|
996 } |
|
997 |
|
998 void erase(const UEdge& edge) { |
|
999 int n = edge.id * 2; |
|
1000 |
|
1001 if (edges[n].next_out != -1) { |
|
1002 edges[edges[n].next_out].prev_out = edges[n].prev_out; |
|
1003 } |
|
1004 |
|
1005 if (edges[n].prev_out != -1) { |
|
1006 edges[edges[n].prev_out].next_out = edges[n].next_out; |
|
1007 } else { |
|
1008 nodes[edges[n | 1].target].first_out = edges[n].next_out; |
|
1009 } |
|
1010 |
|
1011 if (edges[n | 1].next_out != -1) { |
|
1012 edges[edges[n | 1].next_out].prev_out = edges[n | 1].prev_out; |
|
1013 } |
|
1014 |
|
1015 if (edges[n | 1].prev_out != -1) { |
|
1016 edges[edges[n | 1].prev_out].next_out = edges[n | 1].next_out; |
|
1017 } else { |
|
1018 nodes[edges[n].target].first_out = edges[n | 1].next_out; |
|
1019 } |
|
1020 |
|
1021 edges[n].next_out = first_free_edge; |
|
1022 first_free_edge = n; |
|
1023 |
|
1024 } |
|
1025 |
|
1026 void clear() { |
|
1027 edges.clear(); |
|
1028 nodes.clear(); |
|
1029 first_node = first_free_node = first_free_edge = -1; |
|
1030 } |
|
1031 |
|
1032 protected: |
|
1033 |
|
1034 void changeTarget(UEdge e, Node n) { |
|
1035 if(edges[2 * e.id].next_out != -1) { |
|
1036 edges[edges[2 * e.id].next_out].prev_out = edges[2 * e.id].prev_out; |
|
1037 } |
|
1038 if(edges[2 * e.id].prev_out != -1) { |
|
1039 edges[edges[2 * e.id].prev_out].next_out = |
|
1040 edges[2 * e.id].next_out; |
|
1041 } else { |
|
1042 nodes[edges[(2 * e.id) | 1].target].first_out = |
|
1043 edges[2 * e.id].next_out; |
|
1044 } |
|
1045 |
|
1046 if (nodes[n.id].first_out != -1) { |
|
1047 edges[nodes[n.id].first_out].prev_out = 2 * e.id; |
|
1048 } |
|
1049 edges[(2 * e.id) | 1].target = n.id; |
|
1050 edges[2 * e.id].prev_out = -1; |
|
1051 edges[2 * e.id].next_out = nodes[n.id].first_out; |
|
1052 nodes[n.id].first_out = 2 * e.id; |
|
1053 } |
|
1054 |
|
1055 void changeSource(UEdge e, Node n) { |
|
1056 if(edges[(2 * e.id) | 1].next_out != -1) { |
|
1057 edges[edges[(2 * e.id) | 1].next_out].prev_out = |
|
1058 edges[(2 * e.id) | 1].prev_out; |
|
1059 } |
|
1060 if(edges[(2 * e.id) | 1].prev_out != -1) { |
|
1061 edges[edges[(2 * e.id) | 1].prev_out].next_out = |
|
1062 edges[(2 * e.id) | 1].next_out; |
|
1063 } else { |
|
1064 nodes[edges[2 * e.id].target].first_out = |
|
1065 edges[(2 * e.id) | 1].next_out; |
|
1066 } |
|
1067 |
|
1068 if (nodes[n.id].first_out != -1) { |
|
1069 edges[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1); |
|
1070 } |
|
1071 edges[2 * e.id].target = n.id; |
|
1072 edges[(2 * e.id) | 1].prev_out = -1; |
|
1073 edges[(2 * e.id) | 1].next_out = nodes[n.id].first_out; |
|
1074 nodes[n.id].first_out = ((2 * e.id) | 1); |
|
1075 } |
|
1076 |
|
1077 }; |
|
1078 |
|
1079 // typedef UGraphExtender<UndirGraphExtender<ListGraphBase> > |
|
1080 // ExtendedListUGraphBase; |
|
1081 |
|
1082 typedef UGraphExtender<ListUGraphBase> ExtendedListUGraphBase; |
|
1083 |
|
1084 |
742 |
1085 |
743 /// \addtogroup graphs |
1086 /// \addtogroup graphs |
744 /// @{ |
1087 /// @{ |
745 |
1088 |
746 ///An undirected list graph class. |
1089 ///An undirected list graph class. |