COIN-OR::LEMON - Graph Library

Changeset 1191:939ee6d1e525 in lemon


Ignore:
Timestamp:
11/16/10 08:19:11 (9 years ago)
Author:
Balazs Dezso <deba@…>
Branch:
default
Phase:
public
Message:

Use member variables to store the highest IDs in bipartite partitions (#69)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/smart_graph.h

    r1189 r1191  
    830830
    831831    int first_red, first_blue;
     832    int max_red, max_blue;
    832833
    833834  public:
     
    891892
    892893    SmartBpGraphBase()
    893       : nodes(), arcs(), first_red(-1), first_blue(-1) {}
     894      : nodes(), arcs(), first_red(-1), first_blue(-1),
     895        max_red(-1), max_blue(-1) {}
    894896
    895897    typedef True NodeNumTag;
     
    898900
    899901    int nodeNum() const { return nodes.size(); }
    900     int redNum() const {
    901       return first_red == -1 ? 0 : nodes[first_red].partition_index + 1;
    902     }
    903     int blueNum() const {
    904       return first_blue == -1 ? 0 : nodes[first_blue].partition_index + 1;
    905     }
     902    int redNum() const { return max_red + 1; }
     903    int blueNum() const { return max_blue + 1; }
    906904    int edgeNum() const { return arcs.size() / 2; }
    907905    int arcNum() const { return arcs.size(); }
    908906
    909907    int maxNodeId() const { return nodes.size()-1; }
    910     int maxRedId() const {
    911       return first_red == -1 ? -1 : nodes[first_red].partition_index;
    912     }
    913     int maxBlueId() const {
    914       return first_blue == -1 ? -1 : nodes[first_blue].partition_index;
    915     }
     908    int maxRedId() const { return max_red; }
     909    int maxBlueId() const { return max_blue; }
    916910    int maxEdgeId() const { return arcs.size() / 2 - 1; }
    917911    int maxArcId() const { return arcs.size()-1; }
     
    10421036      nodes[n].first_out = -1;
    10431037      nodes[n].red = true;
    1044       if (first_red == -1) {
    1045         nodes[n].partition_index = 0;
    1046       } else {
    1047         nodes[n].partition_index = nodes[first_red].partition_index + 1;
    1048       }
     1038      nodes[n].partition_index = ++max_red;
    10491039      nodes[n].partition_next = first_red;
    10501040      first_red = n;
     
    10581048      nodes[n].first_out = -1;
    10591049      nodes[n].red = false;
    1060       if (first_blue == -1) {
    1061         nodes[n].partition_index = 0;
    1062       } else {
    1063         nodes[n].partition_index = nodes[first_blue].partition_index + 1;
    1064       }
     1050      nodes[n].partition_index = ++max_blue;
    10651051      nodes[n].partition_next = first_blue;
    10661052      first_blue = n;
     
    10911077      first_red = -1;
    10921078      first_blue = -1;
     1079      max_blue = -1;
     1080      max_red = -1;
    10931081    }
    10941082
     
    12451233        if (Parent::red(node)) {
    12461234          first_red = nodes[n].partition_next;
     1235          if (first_red != -1) {
     1236            max_red = nodes[first_red].partition_index;
     1237          } else {
     1238            max_red = -1;
     1239          }
    12471240          Parent::notifier(RedNode()).erase(node);         
    12481241        } else {
    12491242          first_blue = nodes[n].partition_next;
     1243          if (first_blue != -1) {
     1244            max_blue = nodes[first_blue].partition_index;
     1245          } else {
     1246            max_blue = -1;
     1247          }
    12501248          Parent::notifier(BlueNode()).erase(node);
    12511249        }
Note: See TracChangeset for help on using the changeset viewer.