COIN-OR::LEMON - Graph Library

Changeset 2098:12f67fa3df7d in lemon-0.x


Ignore:
Timestamp:
05/30/06 12:33:50 (13 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:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/bits/graph_extender.h

    r2076 r2098  
    14781478    void erase(const Node& node) {
    14791479      UEdge uedge;
    1480       bool dir;
    1481       Parent::firstInc(uedge, dir, node);
    1482       while (uedge != INVALID ) {
    1483         erase(uedge);
    1484         Parent::firstInc(uedge, dir, node);
    1485       }
     1480      if (Parent::aNode(node)) {
     1481        Parent::firstFromANode(uedge, node);
     1482        while (uedge != INVALID) {
     1483          erase(uedge);
     1484          Parent::firstFromANode(uedge, node);
     1485        }
     1486      } else {
     1487        Parent::firstFromBNode(uedge, node);
     1488        while (uedge != INVALID) {
     1489          erase(uedge);
     1490          Parent::firstFromBNode(uedge, node);
     1491        }
     1492      }
    14861493
    14871494      getNotifier(Node()).erase(node);
  • lemon/list_graph.h

    r2076 r2098  
    649649
    650650    struct NodeT {
    651       int first_edge, next_node;
     651      int first_edge, prev, next;
    652652    };
    653653
     
    709709    }
    710710    void nextANode(Node& node) const {
    711       node.id = aNodes[node.id >> 1].next_node;
     711      node.id = aNodes[node.id >> 1].next;
    712712    }
    713713
    714714    void firstBNode(Node& node) const {
    715       node.id =  first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
     715      node.id = first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
    716716    }
    717717    void nextBNode(Node& node) const {
    718       node.id = bNodes[node.id >> 1].next_node;
     718      node.id = bNodes[node.id >> 1].next;
    719719    }
    720720
     
    730730    void next(Node& node) const {
    731731      if (aNode(node)) {
    732         node.id = aNodes[node.id >> 1].next_node;
     732        node.id = aNodes[node.id >> 1].next;
    733733        if (node.id == -1) {
    734734          if (first_bnode != -1) {
     
    737737        }
    738738      } else {
    739         node.id = bNodes[node.id >> 1].next_node;
     739        node.id = bNodes[node.id >> 1].next;
    740740      }
    741741    }
     
    744744      int aNodeId = first_anode;
    745745      while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
    746         aNodeId = aNodes[aNodeId].next_node != -1 ?
    747           aNodes[aNodeId].next_node >> 1 : -1;
     746        aNodeId = aNodes[aNodeId].next != -1 ?
     747          aNodes[aNodeId].next >> 1 : -1;
    748748      }
    749749      if (aNodeId != -1) {
     
    757757      edge.id = edges[edge.id].next_out;
    758758      if (edge.id == -1) {
    759         aNodeId = aNodes[aNodeId].next_node != -1 ?
    760           aNodes[aNodeId].next_node >> 1 : -1;
     759        aNodeId = aNodes[aNodeId].next != -1 ?
     760          aNodes[aNodeId].next >> 1 : -1;
    761761        while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
    762           aNodeId = aNodes[aNodeId].next_node != -1 ?
    763           aNodes[aNodeId].next_node >> 1 : -1;
     762          aNodeId = aNodes[aNodeId].next != -1 ?
     763          aNodes[aNodeId].next >> 1 : -1;
    764764        }
    765765        if (aNodeId != -1) {
     
    850850      } else {
    851851        aNodeId = first_free_anode;
    852         first_free_anode = aNodes[first_free_anode].next_node;
    853       }
    854       aNodes[aNodeId].next_node =
    855         first_anode != -1 ? (first_anode << 1) : -1;
     852        first_free_anode = aNodes[first_free_anode].next;
     853      }
     854      if (first_anode != -1) {
     855        aNodes[aNodeId].next = first_anode << 1;
     856        aNodes[first_anode].prev = aNodeId << 1;
     857      } else {
     858        aNodes[aNodeId].next = -1;
     859      }
     860      aNodes[aNodeId].prev = -1;
    856861      first_anode = aNodeId;
    857862      aNodes[aNodeId].first_edge = -1;
     
    866871      } else {
    867872        bNodeId = first_free_bnode;
    868         first_free_bnode = bNodes[first_free_bnode].next_node;
    869       }
    870       bNodes[bNodeId].next_node =
    871         first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
     873        first_free_bnode = bNodes[first_free_bnode].next;
     874      }
     875      if (first_bnode != -1) {
     876        bNodes[bNodeId].next = (first_bnode << 1) + 1;
     877        bNodes[first_bnode].prev = (bNodeId << 1) + 1;
     878      } else {
     879        bNodes[bNodeId].next = -1;
     880      }
    872881      first_bnode = bNodeId;
    873882      bNodes[bNodeId].first_edge = -1;
     
    910919      if (aNode(node)) {
    911920        int aNodeId = node.id >> 1;
    912         aNodes[aNodeId].next_node = first_free_anode;
     921        if (aNodes[aNodeId].prev != -1) {
     922          aNodes[aNodes[aNodeId].prev >> 1].next = aNodes[aNodeId].next;
     923        } else {
     924          first_anode = aNodes[aNodeId].next >> 1;
     925        }
     926        if (aNodes[aNodeId].next != -1) {
     927          aNodes[aNodes[aNodeId].next >> 1].prev = aNodes[aNodeId].prev;
     928        }
     929        aNodes[aNodeId].next = first_free_anode;
    913930        first_free_anode = aNodeId;
    914931      } else {
    915932        int bNodeId = node.id >> 1;
    916         bNodes[bNodeId].next_node = first_free_bnode;
     933        if (bNodes[bNodeId].prev != -1) {
     934          bNodes[bNodes[bNodeId].prev >> 1].next = bNodes[bNodeId].next;
     935        } else {
     936          first_bnode = bNodes[bNodeId].next >> 1;
     937        }
     938        if (bNodes[bNodeId].next != -1) {
     939          bNodes[bNodes[bNodeId].next >> 1].prev = bNodes[bNodeId].prev;
     940        }
     941        bNodes[bNodeId].next = first_free_bnode;
    917942        first_free_bnode = bNodeId;
    918943      }
     
    920945
    921946    void erase(const UEdge& edge) {
     947
    922948      if (edges[edge.id].prev_out != -1) {
    923949        edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
    924950      } else {
    925         aNodes[edges[edge.id].aNode].first_edge = edges[edge.id].next_out;
     951        aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out;
    926952      }
    927953      if (edges[edge.id].next_out != -1) {
    928954        edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;
    929955      }
     956
    930957      if (edges[edge.id].prev_in != -1) {
    931958        edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
    932959      } else {
    933         bNodes[edges[edge.id].bNode].first_edge = edges[edge.id].next_in;
     960        bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in;
    934961      }
    935962      if (edges[edge.id].next_in != -1) {
    936963        edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;
    937964      }
     965
    938966      edges[edge.id].next_out = first_free_edge;
    939967      first_free_edge = edge.id;
Note: See TracChangeset for help on using the changeset viewer.