# HG changeset patch
# User deba
# Date 1148985230 0
# Node ID 12f67fa3df7d678174b4e679f9d154c3f6d44c40
# Parent  6b2903440d2b3f7e363324d7d9be65d0660d45b3
Bug fix in the list bipartite undirected graph

diff -r 6b2903440d2b -r 12f67fa3df7d lemon/bits/graph_extender.h
--- a/lemon/bits/graph_extender.h	Sun May 21 22:18:57 2006 +0000
+++ b/lemon/bits/graph_extender.h	Tue May 30 10:33:50 2006 +0000
@@ -1477,12 +1477,19 @@
 
     void erase(const Node& node) {
       UEdge uedge;
-      bool dir;
-      Parent::firstInc(uedge, dir, node);
-      while (uedge != INVALID ) {
-	erase(uedge);
-	Parent::firstInc(uedge, dir, node);
-      } 
+      if (Parent::aNode(node)) {
+        Parent::firstFromANode(uedge, node);
+        while (uedge != INVALID) {
+          erase(uedge);
+          Parent::firstFromANode(uedge, node);
+        }
+      } else {
+        Parent::firstFromBNode(uedge, node);
+        while (uedge != INVALID) {
+          erase(uedge);
+          Parent::firstFromBNode(uedge, node);
+        }
+      }
 
       getNotifier(Node()).erase(node);
       Parent::erase(node);
diff -r 6b2903440d2b -r 12f67fa3df7d lemon/list_graph.h
--- a/lemon/list_graph.h	Sun May 21 22:18:57 2006 +0000
+++ b/lemon/list_graph.h	Tue May 30 10:33:50 2006 +0000
@@ -648,7 +648,7 @@
   protected:
 
     struct NodeT {
-      int first_edge, next_node;
+      int first_edge, prev, next;
     };
 
     struct UEdgeT {
@@ -708,14 +708,14 @@
       node.id = first_anode != -1 ? (first_anode << 1) : -1;
     }
     void nextANode(Node& node) const {
-      node.id = aNodes[node.id >> 1].next_node;
+      node.id = aNodes[node.id >> 1].next;
     }
 
     void firstBNode(Node& node) const {
-      node.id =  first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
+      node.id = first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
     }
     void nextBNode(Node& node) const {
-      node.id = bNodes[node.id >> 1].next_node;
+      node.id = bNodes[node.id >> 1].next;
     }
 
     void first(Node& node) const {
@@ -729,22 +729,22 @@
     }
     void next(Node& node) const {
       if (aNode(node)) {
-        node.id = aNodes[node.id >> 1].next_node;
+        node.id = aNodes[node.id >> 1].next;
         if (node.id == -1) {
           if (first_bnode != -1) {
             node.id = (first_bnode << 1) + 1;
           }
         }
       } else {
-        node.id = bNodes[node.id >> 1].next_node;
+        node.id = bNodes[node.id >> 1].next;
       }
     }
   
     void first(UEdge& edge) const {
       int aNodeId = first_anode;
       while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
-        aNodeId = aNodes[aNodeId].next_node != -1 ? 
-          aNodes[aNodeId].next_node >> 1 : -1;
+        aNodeId = aNodes[aNodeId].next != -1 ? 
+          aNodes[aNodeId].next >> 1 : -1;
       }
       if (aNodeId != -1) {
         edge.id = aNodes[aNodeId].first_edge;
@@ -756,11 +756,11 @@
       int aNodeId = edges[edge.id].aNode >> 1;
       edge.id = edges[edge.id].next_out;
       if (edge.id == -1) {
-        aNodeId = aNodes[aNodeId].next_node != -1 ? 
-          aNodes[aNodeId].next_node >> 1 : -1;
+        aNodeId = aNodes[aNodeId].next != -1 ? 
+          aNodes[aNodeId].next >> 1 : -1;
         while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
-          aNodeId = aNodes[aNodeId].next_node != -1 ? 
-          aNodes[aNodeId].next_node >> 1 : -1;
+          aNodeId = aNodes[aNodeId].next != -1 ? 
+          aNodes[aNodeId].next >> 1 : -1;
         }
         if (aNodeId != -1) {
           edge.id = aNodes[aNodeId].first_edge;
@@ -849,10 +849,15 @@
         aNodes.push_back(NodeT());
       } else {
         aNodeId = first_free_anode;
-        first_free_anode = aNodes[first_free_anode].next_node;
+        first_free_anode = aNodes[first_free_anode].next;
       }
-      aNodes[aNodeId].next_node = 
-        first_anode != -1 ? (first_anode << 1) : -1;
+      if (first_anode != -1) {
+        aNodes[aNodeId].next = first_anode << 1;
+        aNodes[first_anode].prev = aNodeId << 1;
+      } else {
+        aNodes[aNodeId].next = -1;
+      }
+      aNodes[aNodeId].prev = -1;
       first_anode = aNodeId;
       aNodes[aNodeId].first_edge = -1;
       return Node(aNodeId << 1);
@@ -865,10 +870,14 @@
         bNodes.push_back(NodeT());
       } else {
         bNodeId = first_free_bnode;
-        first_free_bnode = bNodes[first_free_bnode].next_node;
+        first_free_bnode = bNodes[first_free_bnode].next;
       }
-      bNodes[bNodeId].next_node = 
-        first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
+      if (first_bnode != -1) {
+        bNodes[bNodeId].next = (first_bnode << 1) + 1;
+        bNodes[first_bnode].prev = (bNodeId << 1) + 1;
+      } else {
+        bNodes[bNodeId].next = -1;
+      }
       first_bnode = bNodeId;
       bNodes[bNodeId].first_edge = -1;
       return Node((bNodeId << 1) + 1);
@@ -909,32 +918,51 @@
     void erase(const Node& node) {
       if (aNode(node)) {
         int aNodeId = node.id >> 1;
-        aNodes[aNodeId].next_node = first_free_anode;
+        if (aNodes[aNodeId].prev != -1) {
+          aNodes[aNodes[aNodeId].prev >> 1].next = aNodes[aNodeId].next;
+        } else {
+          first_anode = aNodes[aNodeId].next >> 1;
+        }
+        if (aNodes[aNodeId].next != -1) {
+          aNodes[aNodes[aNodeId].next >> 1].prev = aNodes[aNodeId].prev;
+        }
+        aNodes[aNodeId].next = first_free_anode;
         first_free_anode = aNodeId;
       } else {
         int bNodeId = node.id >> 1;
-        bNodes[bNodeId].next_node = first_free_bnode;
+        if (bNodes[bNodeId].prev != -1) {
+          bNodes[bNodes[bNodeId].prev >> 1].next = bNodes[bNodeId].next;
+        } else {
+          first_bnode = bNodes[bNodeId].next >> 1;
+        }
+        if (bNodes[bNodeId].next != -1) {
+          bNodes[bNodes[bNodeId].next >> 1].prev = bNodes[bNodeId].prev;
+        }
+        bNodes[bNodeId].next = first_free_bnode;
         first_free_bnode = bNodeId;
       }
     }
 
     void erase(const UEdge& edge) {
+
       if (edges[edge.id].prev_out != -1) {
         edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
       } else {
-        aNodes[edges[edge.id].aNode].first_edge = edges[edge.id].next_out;
+        aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out;
       }
       if (edges[edge.id].next_out != -1) {
         edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;
       }
+
       if (edges[edge.id].prev_in != -1) {
         edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
       } else {
-        bNodes[edges[edge.id].bNode].first_edge = edges[edge.id].next_in;
+        bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in;
       }
       if (edges[edge.id].next_in != -1) {
         edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;
       }
+
       edges[edge.id].next_out = first_free_edge;
       first_free_edge = edge.id;
     }