1.1 --- a/lemon/bits/graph_extender.h	Sun May 21 22:18:57 2006 +0000
     1.2 +++ b/lemon/bits/graph_extender.h	Tue May 30 10:33:50 2006 +0000
     1.3 @@ -1477,12 +1477,19 @@
     1.4  
     1.5      void erase(const Node& node) {
     1.6        UEdge uedge;
     1.7 -      bool dir;
     1.8 -      Parent::firstInc(uedge, dir, node);
     1.9 -      while (uedge != INVALID ) {
    1.10 -	erase(uedge);
    1.11 -	Parent::firstInc(uedge, dir, node);
    1.12 -      } 
    1.13 +      if (Parent::aNode(node)) {
    1.14 +        Parent::firstFromANode(uedge, node);
    1.15 +        while (uedge != INVALID) {
    1.16 +          erase(uedge);
    1.17 +          Parent::firstFromANode(uedge, node);
    1.18 +        }
    1.19 +      } else {
    1.20 +        Parent::firstFromBNode(uedge, node);
    1.21 +        while (uedge != INVALID) {
    1.22 +          erase(uedge);
    1.23 +          Parent::firstFromBNode(uedge, node);
    1.24 +        }
    1.25 +      }
    1.26  
    1.27        getNotifier(Node()).erase(node);
    1.28        Parent::erase(node);

     2.1 --- a/lemon/list_graph.h	Sun May 21 22:18:57 2006 +0000
     2.2 +++ b/lemon/list_graph.h	Tue May 30 10:33:50 2006 +0000
     2.3 @@ -648,7 +648,7 @@
     2.4    protected:
     2.5  
     2.6      struct NodeT {
     2.7 -      int first_edge, next_node;
     2.8 +      int first_edge, prev, next;
     2.9      };
    2.10  
    2.11      struct UEdgeT {
    2.12 @@ -708,14 +708,14 @@
    2.13        node.id = first_anode != -1 ? (first_anode << 1) : -1;
    2.14      }
    2.15      void nextANode(Node& node) const {
    2.16 -      node.id = aNodes[node.id >> 1].next_node;
    2.17 +      node.id = aNodes[node.id >> 1].next;
    2.18      }
    2.19  
    2.20      void firstBNode(Node& node) const {
    2.21 -      node.id =  first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
    2.22 +      node.id = first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
    2.23      }
    2.24      void nextBNode(Node& node) const {
    2.25 -      node.id = bNodes[node.id >> 1].next_node;
    2.26 +      node.id = bNodes[node.id >> 1].next;
    2.27      }
    2.28  
    2.29      void first(Node& node) const {
    2.30 @@ -729,22 +729,22 @@
    2.31      }
    2.32      void next(Node& node) const {
    2.33        if (aNode(node)) {
    2.34 -        node.id = aNodes[node.id >> 1].next_node;
    2.35 +        node.id = aNodes[node.id >> 1].next;
    2.36          if (node.id == -1) {
    2.37            if (first_bnode != -1) {
    2.38              node.id = (first_bnode << 1) + 1;
    2.39            }
    2.40          }
    2.41        } else {
    2.42 -        node.id = bNodes[node.id >> 1].next_node;
    2.43 +        node.id = bNodes[node.id >> 1].next;
    2.44        }
    2.45      }
    2.46    
    2.47      void first(UEdge& edge) const {
    2.48        int aNodeId = first_anode;
    2.49        while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
    2.50 -        aNodeId = aNodes[aNodeId].next_node != -1 ? 
    2.51 -          aNodes[aNodeId].next_node >> 1 : -1;
    2.52 +        aNodeId = aNodes[aNodeId].next != -1 ? 
    2.53 +          aNodes[aNodeId].next >> 1 : -1;
    2.54        }
    2.55        if (aNodeId != -1) {
    2.56          edge.id = aNodes[aNodeId].first_edge;
    2.57 @@ -756,11 +756,11 @@
    2.58        int aNodeId = edges[edge.id].aNode >> 1;
    2.59        edge.id = edges[edge.id].next_out;
    2.60        if (edge.id == -1) {
    2.61 -        aNodeId = aNodes[aNodeId].next_node != -1 ? 
    2.62 -          aNodes[aNodeId].next_node >> 1 : -1;
    2.63 +        aNodeId = aNodes[aNodeId].next != -1 ? 
    2.64 +          aNodes[aNodeId].next >> 1 : -1;
    2.65          while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
    2.66 -          aNodeId = aNodes[aNodeId].next_node != -1 ? 
    2.67 -          aNodes[aNodeId].next_node >> 1 : -1;
    2.68 +          aNodeId = aNodes[aNodeId].next != -1 ? 
    2.69 +          aNodes[aNodeId].next >> 1 : -1;
    2.70          }
    2.71          if (aNodeId != -1) {
    2.72            edge.id = aNodes[aNodeId].first_edge;
    2.73 @@ -849,10 +849,15 @@
    2.74          aNodes.push_back(NodeT());
    2.75        } else {
    2.76          aNodeId = first_free_anode;
    2.77 -        first_free_anode = aNodes[first_free_anode].next_node;
    2.78 +        first_free_anode = aNodes[first_free_anode].next;
    2.79        }
    2.80 -      aNodes[aNodeId].next_node = 
    2.81 -        first_anode != -1 ? (first_anode << 1) : -1;
    2.82 +      if (first_anode != -1) {
    2.83 +        aNodes[aNodeId].next = first_anode << 1;
    2.84 +        aNodes[first_anode].prev = aNodeId << 1;
    2.85 +      } else {
    2.86 +        aNodes[aNodeId].next = -1;
    2.87 +      }
    2.88 +      aNodes[aNodeId].prev = -1;
    2.89        first_anode = aNodeId;
    2.90        aNodes[aNodeId].first_edge = -1;
    2.91        return Node(aNodeId << 1);
    2.92 @@ -865,10 +870,14 @@
    2.93          bNodes.push_back(NodeT());
    2.94        } else {
    2.95          bNodeId = first_free_bnode;
    2.96 -        first_free_bnode = bNodes[first_free_bnode].next_node;
    2.97 +        first_free_bnode = bNodes[first_free_bnode].next;
    2.98        }
    2.99 -      bNodes[bNodeId].next_node = 
   2.100 -        first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
   2.101 +      if (first_bnode != -1) {
   2.102 +        bNodes[bNodeId].next = (first_bnode << 1) + 1;
   2.103 +        bNodes[first_bnode].prev = (bNodeId << 1) + 1;
   2.104 +      } else {
   2.105 +        bNodes[bNodeId].next = -1;
   2.106 +      }
   2.107        first_bnode = bNodeId;
   2.108        bNodes[bNodeId].first_edge = -1;
   2.109        return Node((bNodeId << 1) + 1);
   2.110 @@ -909,32 +918,51 @@
   2.111      void erase(const Node& node) {
   2.112        if (aNode(node)) {
   2.113          int aNodeId = node.id >> 1;
   2.114 -        aNodes[aNodeId].next_node = first_free_anode;
   2.115 +        if (aNodes[aNodeId].prev != -1) {
   2.116 +          aNodes[aNodes[aNodeId].prev >> 1].next = aNodes[aNodeId].next;
   2.117 +        } else {
   2.118 +          first_anode = aNodes[aNodeId].next >> 1;
   2.119 +        }
   2.120 +        if (aNodes[aNodeId].next != -1) {
   2.121 +          aNodes[aNodes[aNodeId].next >> 1].prev = aNodes[aNodeId].prev;
   2.122 +        }
   2.123 +        aNodes[aNodeId].next = first_free_anode;
   2.124          first_free_anode = aNodeId;
   2.125        } else {
   2.126          int bNodeId = node.id >> 1;
   2.127 -        bNodes[bNodeId].next_node = first_free_bnode;
   2.128 +        if (bNodes[bNodeId].prev != -1) {
   2.129 +          bNodes[bNodes[bNodeId].prev >> 1].next = bNodes[bNodeId].next;
   2.130 +        } else {
   2.131 +          first_bnode = bNodes[bNodeId].next >> 1;
   2.132 +        }
   2.133 +        if (bNodes[bNodeId].next != -1) {
   2.134 +          bNodes[bNodes[bNodeId].next >> 1].prev = bNodes[bNodeId].prev;
   2.135 +        }
   2.136 +        bNodes[bNodeId].next = first_free_bnode;
   2.137          first_free_bnode = bNodeId;
   2.138        }
   2.139      }
   2.140  
   2.141      void erase(const UEdge& edge) {
   2.142 +
   2.143        if (edges[edge.id].prev_out != -1) {
   2.144          edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
   2.145        } else {
   2.146 -        aNodes[edges[edge.id].aNode].first_edge = edges[edge.id].next_out;
   2.147 +        aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out;
   2.148        }
   2.149        if (edges[edge.id].next_out != -1) {
   2.150          edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;
   2.151        }
   2.152 +
   2.153        if (edges[edge.id].prev_in != -1) {
   2.154          edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
   2.155        } else {
   2.156 -        bNodes[edges[edge.id].bNode].first_edge = edges[edge.id].next_in;
   2.157 +        bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in;
   2.158        }
   2.159        if (edges[edge.id].next_in != -1) {
   2.160          edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;
   2.161        }
   2.162 +
   2.163        edges[edge.id].next_out = first_free_edge;
   2.164        first_free_edge = edge.id;
   2.165      }