Use member variables to store the highest IDs in bipartite partitions (#69)
authorBalazs Dezso <deba@inf.elte.hu>
Tue, 16 Nov 2010 08:19:11 +0100
changeset 1023939ee6d1e525
parent 1022 523e45e37e52
child 1024 b84e68af8248
Use member variables to store the highest IDs in bipartite partitions (#69)
lemon/smart_graph.h
     1.1 --- a/lemon/smart_graph.h	Tue Nov 16 00:59:36 2010 +0100
     1.2 +++ b/lemon/smart_graph.h	Tue Nov 16 08:19:11 2010 +0100
     1.3 @@ -829,6 +829,7 @@
     1.4      std::vector<ArcT> arcs;
     1.5  
     1.6      int first_red, first_blue;
     1.7 +    int max_red, max_blue;
     1.8  
     1.9    public:
    1.10  
    1.11 @@ -890,29 +891,22 @@
    1.12  
    1.13  
    1.14      SmartBpGraphBase()
    1.15 -      : nodes(), arcs(), first_red(-1), first_blue(-1) {}
    1.16 +      : nodes(), arcs(), first_red(-1), first_blue(-1),
    1.17 +        max_red(-1), max_blue(-1) {}
    1.18  
    1.19      typedef True NodeNumTag;
    1.20      typedef True EdgeNumTag;
    1.21      typedef True ArcNumTag;
    1.22  
    1.23      int nodeNum() const { return nodes.size(); }
    1.24 -    int redNum() const {
    1.25 -      return first_red == -1 ? 0 : nodes[first_red].partition_index + 1;
    1.26 -    }
    1.27 -    int blueNum() const {
    1.28 -      return first_blue == -1 ? 0 : nodes[first_blue].partition_index + 1;
    1.29 -    }
    1.30 +    int redNum() const { return max_red + 1; }
    1.31 +    int blueNum() const { return max_blue + 1; }
    1.32      int edgeNum() const { return arcs.size() / 2; }
    1.33      int arcNum() const { return arcs.size(); }
    1.34  
    1.35      int maxNodeId() const { return nodes.size()-1; }
    1.36 -    int maxRedId() const {
    1.37 -      return first_red == -1 ? -1 : nodes[first_red].partition_index;
    1.38 -    }
    1.39 -    int maxBlueId() const {
    1.40 -      return first_blue == -1 ? -1 : nodes[first_blue].partition_index;
    1.41 -    }
    1.42 +    int maxRedId() const { return max_red; }
    1.43 +    int maxBlueId() const { return max_blue; }
    1.44      int maxEdgeId() const { return arcs.size() / 2 - 1; }
    1.45      int maxArcId() const { return arcs.size()-1; }
    1.46  
    1.47 @@ -1041,11 +1035,7 @@
    1.48        nodes.push_back(NodeT());
    1.49        nodes[n].first_out = -1;
    1.50        nodes[n].red = true;
    1.51 -      if (first_red == -1) {
    1.52 -        nodes[n].partition_index = 0;
    1.53 -      } else {
    1.54 -        nodes[n].partition_index = nodes[first_red].partition_index + 1;
    1.55 -      }
    1.56 +      nodes[n].partition_index = ++max_red;
    1.57        nodes[n].partition_next = first_red;
    1.58        first_red = n;
    1.59  
    1.60 @@ -1057,11 +1047,7 @@
    1.61        nodes.push_back(NodeT());
    1.62        nodes[n].first_out = -1;
    1.63        nodes[n].red = false;
    1.64 -      if (first_blue == -1) {
    1.65 -        nodes[n].partition_index = 0;
    1.66 -      } else {
    1.67 -        nodes[n].partition_index = nodes[first_blue].partition_index + 1;
    1.68 -      }
    1.69 +      nodes[n].partition_index = ++max_blue;
    1.70        nodes[n].partition_next = first_blue;
    1.71        first_blue = n;
    1.72  
    1.73 @@ -1090,6 +1076,8 @@
    1.74        nodes.clear();
    1.75        first_red = -1;
    1.76        first_blue = -1;
    1.77 +      max_blue = -1;
    1.78 +      max_red = -1;
    1.79      }
    1.80  
    1.81    };
    1.82 @@ -1244,9 +1232,19 @@
    1.83          Node node = nodeFromId(n);
    1.84          if (Parent::red(node)) {
    1.85            first_red = nodes[n].partition_next;
    1.86 +          if (first_red != -1) {
    1.87 +            max_red = nodes[first_red].partition_index;
    1.88 +          } else {
    1.89 +            max_red = -1;
    1.90 +          }
    1.91            Parent::notifier(RedNode()).erase(node);          
    1.92          } else {
    1.93            first_blue = nodes[n].partition_next;
    1.94 +          if (first_blue != -1) {
    1.95 +            max_blue = nodes[first_blue].partition_index;
    1.96 +          } else {
    1.97 +            max_blue = -1;
    1.98 +          }
    1.99            Parent::notifier(BlueNode()).erase(node);
   1.100          }
   1.101          Parent::notifier(Node()).erase(node);