Changeset 2098:12f67fa3df7d in lemon-0.x

Timestamp:

05/30/06 12:33:50 (17 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2768

Message:

Bug fix in the list bipartite undirected graph

Location:

lemon

Files:

• bits/graph_extender.h (modified) (1 diff)
• list_graph.h (modified) (10 diffs)

lemon/bits/graph_extender.h

@@ -1478 +1478 @@
     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);

lemon/list_graph.h

@@ -649 +649 @@
 
     struct NodeT {
-      int first_edge, next_node;
+      int first_edge, prev, next;
     };
 
@@ -709 +709 @@
     }
     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;
     }
 
@@ -730 +730 @@
     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) {
@@ -737 +737 @@
         }
       } else {
-        node.id = bNodes[node.id >> 1].next_node;
+        node.id = bNodes[node.id >> 1].next;
       }
     }
@@ -744 +744 @@
       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) {
@@ -757 +757 @@
       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) {
@@ -850 +850 @@
       } else {
         aNodeId = first_free_anode;
-        first_free_anode = aNodes[first_free_anode].next_node;
-      }
-      aNodes[aNodeId].next_node = 
-        first_anode != -1 ? (first_anode << 1) : -1;
+        first_free_anode = aNodes[first_free_anode].next;
+      }
+      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;
@@ -866 +871 @@
       } else {
         bNodeId = first_free_bnode;
-        first_free_bnode = bNodes[first_free_bnode].next_node;
-      }
-      bNodes[bNodeId].next_node = 
-        first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
+        first_free_bnode = bNodes[first_free_bnode].next;
+      }
+      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;
@@ -910 +919 @@
       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;
       }
@@ -920 +945 @@
 
     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;