1.1 --- a/lemon/list_graph.h Sun May 21 22:18:57 2006 +0000
1.2 +++ b/lemon/list_graph.h Tue May 30 10:33:50 2006 +0000
1.3 @@ -648,7 +648,7 @@
1.4 protected:
1.5
1.6 struct NodeT {
1.7 - int first_edge, next_node;
1.8 + int first_edge, prev, next;
1.9 };
1.10
1.11 struct UEdgeT {
1.12 @@ -708,14 +708,14 @@
1.13 node.id = first_anode != -1 ? (first_anode << 1) : -1;
1.14 }
1.15 void nextANode(Node& node) const {
1.16 - node.id = aNodes[node.id >> 1].next_node;
1.17 + node.id = aNodes[node.id >> 1].next;
1.18 }
1.19
1.20 void firstBNode(Node& node) const {
1.21 - node.id = first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
1.22 + node.id = first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
1.23 }
1.24 void nextBNode(Node& node) const {
1.25 - node.id = bNodes[node.id >> 1].next_node;
1.26 + node.id = bNodes[node.id >> 1].next;
1.27 }
1.28
1.29 void first(Node& node) const {
1.30 @@ -729,22 +729,22 @@
1.31 }
1.32 void next(Node& node) const {
1.33 if (aNode(node)) {
1.34 - node.id = aNodes[node.id >> 1].next_node;
1.35 + node.id = aNodes[node.id >> 1].next;
1.36 if (node.id == -1) {
1.37 if (first_bnode != -1) {
1.38 node.id = (first_bnode << 1) + 1;
1.39 }
1.40 }
1.41 } else {
1.42 - node.id = bNodes[node.id >> 1].next_node;
1.43 + node.id = bNodes[node.id >> 1].next;
1.44 }
1.45 }
1.46
1.47 void first(UEdge& edge) const {
1.48 int aNodeId = first_anode;
1.49 while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
1.50 - aNodeId = aNodes[aNodeId].next_node != -1 ?
1.51 - aNodes[aNodeId].next_node >> 1 : -1;
1.52 + aNodeId = aNodes[aNodeId].next != -1 ?
1.53 + aNodes[aNodeId].next >> 1 : -1;
1.54 }
1.55 if (aNodeId != -1) {
1.56 edge.id = aNodes[aNodeId].first_edge;
1.57 @@ -756,11 +756,11 @@
1.58 int aNodeId = edges[edge.id].aNode >> 1;
1.59 edge.id = edges[edge.id].next_out;
1.60 if (edge.id == -1) {
1.61 - aNodeId = aNodes[aNodeId].next_node != -1 ?
1.62 - aNodes[aNodeId].next_node >> 1 : -1;
1.63 + aNodeId = aNodes[aNodeId].next != -1 ?
1.64 + aNodes[aNodeId].next >> 1 : -1;
1.65 while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
1.66 - aNodeId = aNodes[aNodeId].next_node != -1 ?
1.67 - aNodes[aNodeId].next_node >> 1 : -1;
1.68 + aNodeId = aNodes[aNodeId].next != -1 ?
1.69 + aNodes[aNodeId].next >> 1 : -1;
1.70 }
1.71 if (aNodeId != -1) {
1.72 edge.id = aNodes[aNodeId].first_edge;
1.73 @@ -849,10 +849,15 @@
1.74 aNodes.push_back(NodeT());
1.75 } else {
1.76 aNodeId = first_free_anode;
1.77 - first_free_anode = aNodes[first_free_anode].next_node;
1.78 + first_free_anode = aNodes[first_free_anode].next;
1.79 }
1.80 - aNodes[aNodeId].next_node =
1.81 - first_anode != -1 ? (first_anode << 1) : -1;
1.82 + if (first_anode != -1) {
1.83 + aNodes[aNodeId].next = first_anode << 1;
1.84 + aNodes[first_anode].prev = aNodeId << 1;
1.85 + } else {
1.86 + aNodes[aNodeId].next = -1;
1.87 + }
1.88 + aNodes[aNodeId].prev = -1;
1.89 first_anode = aNodeId;
1.90 aNodes[aNodeId].first_edge = -1;
1.91 return Node(aNodeId << 1);
1.92 @@ -865,10 +870,14 @@
1.93 bNodes.push_back(NodeT());
1.94 } else {
1.95 bNodeId = first_free_bnode;
1.96 - first_free_bnode = bNodes[first_free_bnode].next_node;
1.97 + first_free_bnode = bNodes[first_free_bnode].next;
1.98 }
1.99 - bNodes[bNodeId].next_node =
1.100 - first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
1.101 + if (first_bnode != -1) {
1.102 + bNodes[bNodeId].next = (first_bnode << 1) + 1;
1.103 + bNodes[first_bnode].prev = (bNodeId << 1) + 1;
1.104 + } else {
1.105 + bNodes[bNodeId].next = -1;
1.106 + }
1.107 first_bnode = bNodeId;
1.108 bNodes[bNodeId].first_edge = -1;
1.109 return Node((bNodeId << 1) + 1);
1.110 @@ -909,32 +918,51 @@
1.111 void erase(const Node& node) {
1.112 if (aNode(node)) {
1.113 int aNodeId = node.id >> 1;
1.114 - aNodes[aNodeId].next_node = first_free_anode;
1.115 + if (aNodes[aNodeId].prev != -1) {
1.116 + aNodes[aNodes[aNodeId].prev >> 1].next = aNodes[aNodeId].next;
1.117 + } else {
1.118 + first_anode = aNodes[aNodeId].next >> 1;
1.119 + }
1.120 + if (aNodes[aNodeId].next != -1) {
1.121 + aNodes[aNodes[aNodeId].next >> 1].prev = aNodes[aNodeId].prev;
1.122 + }
1.123 + aNodes[aNodeId].next = first_free_anode;
1.124 first_free_anode = aNodeId;
1.125 } else {
1.126 int bNodeId = node.id >> 1;
1.127 - bNodes[bNodeId].next_node = first_free_bnode;
1.128 + if (bNodes[bNodeId].prev != -1) {
1.129 + bNodes[bNodes[bNodeId].prev >> 1].next = bNodes[bNodeId].next;
1.130 + } else {
1.131 + first_bnode = bNodes[bNodeId].next >> 1;
1.132 + }
1.133 + if (bNodes[bNodeId].next != -1) {
1.134 + bNodes[bNodes[bNodeId].next >> 1].prev = bNodes[bNodeId].prev;
1.135 + }
1.136 + bNodes[bNodeId].next = first_free_bnode;
1.137 first_free_bnode = bNodeId;
1.138 }
1.139 }
1.140
1.141 void erase(const UEdge& edge) {
1.142 +
1.143 if (edges[edge.id].prev_out != -1) {
1.144 edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
1.145 } else {
1.146 - aNodes[edges[edge.id].aNode].first_edge = edges[edge.id].next_out;
1.147 + aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out;
1.148 }
1.149 if (edges[edge.id].next_out != -1) {
1.150 edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;
1.151 }
1.152 +
1.153 if (edges[edge.id].prev_in != -1) {
1.154 edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
1.155 } else {
1.156 - bNodes[edges[edge.id].bNode].first_edge = edges[edge.id].next_in;
1.157 + bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in;
1.158 }
1.159 if (edges[edge.id].next_in != -1) {
1.160 edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;
1.161 }
1.162 +
1.163 edges[edge.id].next_out = first_free_edge;
1.164 first_free_edge = edge.id;
1.165 }