ListBpGraph implementation (#69)
authorBalazs Dezso <deba@inf.elte.hu>
Mon, 15 Nov 2010 09:46:08 +0100
changeset 1021a12cca3ad15a
parent 1020 5ef0ab7b61cd
child 1022 523e45e37e52
ListBpGraph implementation (#69)
lemon/list_graph.h
lemon/smart_graph.h
test/bpgraph_test.cc
     1.1 --- a/lemon/list_graph.h	Sun Nov 14 22:48:32 2010 +0100
     1.2 +++ b/lemon/list_graph.h	Mon Nov 15 09:46:08 2010 +0100
     1.3 @@ -1599,6 +1599,885 @@
     1.4    };
     1.5  
     1.6    /// @}
     1.7 +
     1.8 +  class ListBpGraphBase {
     1.9 +
    1.10 +  protected:
    1.11 +
    1.12 +    struct NodeT {
    1.13 +      int first_out;
    1.14 +      int prev, next;
    1.15 +      int partition_prev, partition_next;
    1.16 +      int partition_index;
    1.17 +      bool red;
    1.18 +    };
    1.19 +
    1.20 +    struct ArcT {
    1.21 +      int target;
    1.22 +      int prev_out, next_out;
    1.23 +    };
    1.24 +
    1.25 +    std::vector<NodeT> nodes;
    1.26 +
    1.27 +    int first_node, first_red, first_blue;
    1.28 +    int max_red, max_blue;
    1.29 +
    1.30 +    int first_free_red, first_free_blue;
    1.31 +
    1.32 +    std::vector<ArcT> arcs;
    1.33 +
    1.34 +    int first_free_arc;
    1.35 +
    1.36 +  public:
    1.37 +
    1.38 +    typedef ListBpGraphBase BpGraph;
    1.39 +
    1.40 +    class Node {
    1.41 +      friend class ListBpGraphBase;
    1.42 +    protected:
    1.43 +
    1.44 +      int id;
    1.45 +      explicit Node(int pid) { id = pid;}
    1.46 +
    1.47 +    public:
    1.48 +      Node() {}
    1.49 +      Node (Invalid) { id = -1; }
    1.50 +      bool operator==(const Node& node) const {return id == node.id;}
    1.51 +      bool operator!=(const Node& node) const {return id != node.id;}
    1.52 +      bool operator<(const Node& node) const {return id < node.id;}
    1.53 +    };
    1.54 +
    1.55 +    class Edge {
    1.56 +      friend class ListBpGraphBase;
    1.57 +    protected:
    1.58 +
    1.59 +      int id;
    1.60 +      explicit Edge(int pid) { id = pid;}
    1.61 +
    1.62 +    public:
    1.63 +      Edge() {}
    1.64 +      Edge (Invalid) { id = -1; }
    1.65 +      bool operator==(const Edge& edge) const {return id == edge.id;}
    1.66 +      bool operator!=(const Edge& edge) const {return id != edge.id;}
    1.67 +      bool operator<(const Edge& edge) const {return id < edge.id;}
    1.68 +    };
    1.69 +
    1.70 +    class Arc {
    1.71 +      friend class ListBpGraphBase;
    1.72 +    protected:
    1.73 +
    1.74 +      int id;
    1.75 +      explicit Arc(int pid) { id = pid;}
    1.76 +
    1.77 +    public:
    1.78 +      operator Edge() const {
    1.79 +        return id != -1 ? edgeFromId(id / 2) : INVALID;
    1.80 +      }
    1.81 +
    1.82 +      Arc() {}
    1.83 +      Arc (Invalid) { id = -1; }
    1.84 +      bool operator==(const Arc& arc) const {return id == arc.id;}
    1.85 +      bool operator!=(const Arc& arc) const {return id != arc.id;}
    1.86 +      bool operator<(const Arc& arc) const {return id < arc.id;}
    1.87 +    };
    1.88 +
    1.89 +    ListBpGraphBase()
    1.90 +      : nodes(), first_node(-1),
    1.91 +        first_red(-1), first_blue(-1),
    1.92 +        max_red(-1), max_blue(-1),
    1.93 +        first_free_red(-1), first_free_blue(-1),
    1.94 +        arcs(), first_free_arc(-1) {}
    1.95 +
    1.96 +
    1.97 +    bool red(Node n) const { return nodes[n.id].red; }
    1.98 +    bool blue(Node n) const { return !nodes[n.id].red; }
    1.99 +
   1.100 +    int maxNodeId() const { return nodes.size()-1; }
   1.101 +    int maxRedId() const { return max_red; }
   1.102 +    int maxBlueId() const { return max_blue; }
   1.103 +    int maxEdgeId() const { return arcs.size() / 2 - 1; }
   1.104 +    int maxArcId() const { return arcs.size()-1; }
   1.105 +
   1.106 +    Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); }
   1.107 +    Node target(Arc e) const { return Node(arcs[e.id].target); }
   1.108 +
   1.109 +    Node redNode(Edge e) const { return Node(arcs[2 * e.id].target); }
   1.110 +    Node blueNode(Edge e) const { return Node(arcs[2 * e.id + 1].target); }
   1.111 +
   1.112 +    static bool direction(Arc e) {
   1.113 +      return (e.id & 1) == 1;
   1.114 +    }
   1.115 +
   1.116 +    static Arc direct(Edge e, bool d) {
   1.117 +      return Arc(e.id * 2 + (d ? 1 : 0));
   1.118 +    }
   1.119 +
   1.120 +    void first(Node& node) const {
   1.121 +      node.id = first_node;
   1.122 +    }
   1.123 +
   1.124 +    void next(Node& node) const {
   1.125 +      node.id = nodes[node.id].next;
   1.126 +    }
   1.127 +
   1.128 +    void firstRed(Node& node) const {
   1.129 +      node.id = first_red;
   1.130 +    }
   1.131 +
   1.132 +    void nextRed(Node& node) const {
   1.133 +      node.id = nodes[node.id].partition_next;
   1.134 +    }
   1.135 +
   1.136 +    void firstBlue(Node& node) const {
   1.137 +      node.id = first_blue;
   1.138 +    }
   1.139 +
   1.140 +    void nextBlue(Node& node) const {
   1.141 +      node.id = nodes[node.id].partition_next;
   1.142 +    }    
   1.143 +
   1.144 +    void first(Arc& e) const {
   1.145 +      int n = first_node;
   1.146 +      while (n != -1 && nodes[n].first_out == -1) {
   1.147 +        n = nodes[n].next;
   1.148 +      }
   1.149 +      e.id = (n == -1) ? -1 : nodes[n].first_out;
   1.150 +    }
   1.151 +
   1.152 +    void next(Arc& e) const {
   1.153 +      if (arcs[e.id].next_out != -1) {
   1.154 +        e.id = arcs[e.id].next_out;
   1.155 +      } else {
   1.156 +        int n = nodes[arcs[e.id ^ 1].target].next;
   1.157 +        while(n != -1 && nodes[n].first_out == -1) {
   1.158 +          n = nodes[n].next;
   1.159 +        }
   1.160 +        e.id = (n == -1) ? -1 : nodes[n].first_out;
   1.161 +      }
   1.162 +    }
   1.163 +
   1.164 +    void first(Edge& e) const {
   1.165 +      int n = first_node;
   1.166 +      while (n != -1) {
   1.167 +        e.id = nodes[n].first_out;
   1.168 +        while ((e.id & 1) != 1) {
   1.169 +          e.id = arcs[e.id].next_out;
   1.170 +        }
   1.171 +        if (e.id != -1) {
   1.172 +          e.id /= 2;
   1.173 +          return;
   1.174 +        }
   1.175 +        n = nodes[n].next;
   1.176 +      }
   1.177 +      e.id = -1;
   1.178 +    }
   1.179 +
   1.180 +    void next(Edge& e) const {
   1.181 +      int n = arcs[e.id * 2].target;
   1.182 +      e.id = arcs[(e.id * 2) | 1].next_out;
   1.183 +      while ((e.id & 1) != 1) {
   1.184 +        e.id = arcs[e.id].next_out;
   1.185 +      }
   1.186 +      if (e.id != -1) {
   1.187 +        e.id /= 2;
   1.188 +        return;
   1.189 +      }
   1.190 +      n = nodes[n].next;
   1.191 +      while (n != -1) {
   1.192 +        e.id = nodes[n].first_out;
   1.193 +        while ((e.id & 1) != 1) {
   1.194 +          e.id = arcs[e.id].next_out;
   1.195 +        }
   1.196 +        if (e.id != -1) {
   1.197 +          e.id /= 2;
   1.198 +          return;
   1.199 +        }
   1.200 +        n = nodes[n].next;
   1.201 +      }
   1.202 +      e.id = -1;
   1.203 +    }
   1.204 +
   1.205 +    void firstOut(Arc &e, const Node& v) const {
   1.206 +      e.id = nodes[v.id].first_out;
   1.207 +    }
   1.208 +    void nextOut(Arc &e) const {
   1.209 +      e.id = arcs[e.id].next_out;
   1.210 +    }
   1.211 +
   1.212 +    void firstIn(Arc &e, const Node& v) const {
   1.213 +      e.id = ((nodes[v.id].first_out) ^ 1);
   1.214 +      if (e.id == -2) e.id = -1;
   1.215 +    }
   1.216 +    void nextIn(Arc &e) const {
   1.217 +      e.id = ((arcs[e.id ^ 1].next_out) ^ 1);
   1.218 +      if (e.id == -2) e.id = -1;
   1.219 +    }
   1.220 +
   1.221 +    void firstInc(Edge &e, bool& d, const Node& v) const {
   1.222 +      int a = nodes[v.id].first_out;
   1.223 +      if (a != -1 ) {
   1.224 +        e.id = a / 2;
   1.225 +        d = ((a & 1) == 1);
   1.226 +      } else {
   1.227 +        e.id = -1;
   1.228 +        d = true;
   1.229 +      }
   1.230 +    }
   1.231 +    void nextInc(Edge &e, bool& d) const {
   1.232 +      int a = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
   1.233 +      if (a != -1 ) {
   1.234 +        e.id = a / 2;
   1.235 +        d = ((a & 1) == 1);
   1.236 +      } else {
   1.237 +        e.id = -1;
   1.238 +        d = true;
   1.239 +      }
   1.240 +    }
   1.241 +
   1.242 +    static int id(Node v) { return v.id; }
   1.243 +    int redId(Node v) const {
   1.244 +      LEMON_DEBUG(nodes[v.id].red, "Node has to be red");
   1.245 +      return nodes[v.id].partition_index;
   1.246 +    }
   1.247 +    int blueId(Node v) const {
   1.248 +      LEMON_DEBUG(!nodes[v.id].red, "Node has to be blue");
   1.249 +      return nodes[v.id].partition_index;
   1.250 +    }
   1.251 +    static int id(Arc e) { return e.id; }
   1.252 +    static int id(Edge e) { return e.id; }
   1.253 +
   1.254 +    static Node nodeFromId(int id) { return Node(id);}
   1.255 +    static Arc arcFromId(int id) { return Arc(id);}
   1.256 +    static Edge edgeFromId(int id) { return Edge(id);}
   1.257 +
   1.258 +    bool valid(Node n) const {
   1.259 +      return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
   1.260 +        nodes[n.id].prev != -2;
   1.261 +    }
   1.262 +
   1.263 +    bool valid(Arc a) const {
   1.264 +      return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
   1.265 +        arcs[a.id].prev_out != -2;
   1.266 +    }
   1.267 +
   1.268 +    bool valid(Edge e) const {
   1.269 +      return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) &&
   1.270 +        arcs[2 * e.id].prev_out != -2;
   1.271 +    }
   1.272 +
   1.273 +    Node addRedNode() {
   1.274 +      int n;
   1.275 +
   1.276 +      if(first_free_red==-1) {
   1.277 +        n = nodes.size();
   1.278 +        nodes.push_back(NodeT());
   1.279 +        nodes[n].partition_index = ++max_red;
   1.280 +        nodes[n].red = true;
   1.281 +      } else {
   1.282 +        n = first_free_red;
   1.283 +        first_free_red = nodes[n].next;
   1.284 +      }
   1.285 +
   1.286 +      nodes[n].next = first_node;
   1.287 +      if (first_node != -1) nodes[first_node].prev = n;
   1.288 +      first_node = n;
   1.289 +      nodes[n].prev = -1;
   1.290 +
   1.291 +      nodes[n].partition_next = first_red;
   1.292 +      if (first_red != -1) nodes[first_red].partition_prev = n;
   1.293 +      first_red = n;
   1.294 +      nodes[n].partition_prev = -1;
   1.295 +
   1.296 +      nodes[n].first_out = -1;
   1.297 +
   1.298 +      return Node(n);
   1.299 +    }
   1.300 +
   1.301 +    Node addBlueNode() {
   1.302 +      int n;
   1.303 +
   1.304 +      if(first_free_blue==-1) {
   1.305 +        n = nodes.size();
   1.306 +        nodes.push_back(NodeT());
   1.307 +        nodes[n].partition_index = ++max_blue;
   1.308 +        nodes[n].red = false;
   1.309 +      } else {
   1.310 +        n = first_free_blue;
   1.311 +        first_free_blue = nodes[n].next;
   1.312 +      }
   1.313 +
   1.314 +      nodes[n].next = first_node;
   1.315 +      if (first_node != -1) nodes[first_node].prev = n;
   1.316 +      first_node = n;
   1.317 +      nodes[n].prev = -1;
   1.318 +
   1.319 +      nodes[n].partition_next = first_blue;
   1.320 +      if (first_blue != -1) nodes[first_blue].partition_prev = n;
   1.321 +      first_blue = n;
   1.322 +      nodes[n].partition_prev = -1;
   1.323 +
   1.324 +      nodes[n].first_out = -1;
   1.325 +
   1.326 +      return Node(n);
   1.327 +    }
   1.328 +
   1.329 +    Edge addEdge(Node u, Node v) {
   1.330 +      int n;
   1.331 +
   1.332 +      if (first_free_arc == -1) {
   1.333 +        n = arcs.size();
   1.334 +        arcs.push_back(ArcT());
   1.335 +        arcs.push_back(ArcT());
   1.336 +      } else {
   1.337 +        n = first_free_arc;
   1.338 +        first_free_arc = arcs[n].next_out;
   1.339 +      }
   1.340 +
   1.341 +      arcs[n].target = u.id;
   1.342 +      arcs[n | 1].target = v.id;
   1.343 +
   1.344 +      arcs[n].next_out = nodes[v.id].first_out;
   1.345 +      if (nodes[v.id].first_out != -1) {
   1.346 +        arcs[nodes[v.id].first_out].prev_out = n;
   1.347 +      }
   1.348 +      arcs[n].prev_out = -1;
   1.349 +      nodes[v.id].first_out = n;
   1.350 +
   1.351 +      arcs[n | 1].next_out = nodes[u.id].first_out;
   1.352 +      if (nodes[u.id].first_out != -1) {
   1.353 +        arcs[nodes[u.id].first_out].prev_out = (n | 1);
   1.354 +      }
   1.355 +      arcs[n | 1].prev_out = -1;
   1.356 +      nodes[u.id].first_out = (n | 1);
   1.357 +
   1.358 +      return Edge(n / 2);
   1.359 +    }
   1.360 +
   1.361 +    void erase(const Node& node) {
   1.362 +      int n = node.id;
   1.363 +
   1.364 +      if(nodes[n].next != -1) {
   1.365 +        nodes[nodes[n].next].prev = nodes[n].prev;
   1.366 +      }
   1.367 +
   1.368 +      if(nodes[n].prev != -1) {
   1.369 +        nodes[nodes[n].prev].next = nodes[n].next;
   1.370 +      } else {
   1.371 +        first_node = nodes[n].next;
   1.372 +      }
   1.373 +
   1.374 +      if (nodes[n].partition_next != -1) {
   1.375 +        nodes[nodes[n].partition_next].partition_prev = nodes[n].partition_prev;
   1.376 +      }
   1.377 +
   1.378 +      if (nodes[n].partition_prev != -1) {
   1.379 +        nodes[nodes[n].partition_prev].partition_next = nodes[n].partition_next;
   1.380 +      } else {
   1.381 +        if (nodes[n].red) {
   1.382 +          first_red = nodes[n].partition_next;
   1.383 +        } else {
   1.384 +          first_blue = nodes[n].partition_next;
   1.385 +        }
   1.386 +      }
   1.387 +
   1.388 +      if (nodes[n].red) {
   1.389 +        nodes[n].next = first_free_red;
   1.390 +        first_free_red = n;
   1.391 +      } else {
   1.392 +        nodes[n].next = first_free_blue;
   1.393 +        first_free_blue = n;
   1.394 +      }
   1.395 +      nodes[n].prev = -2;
   1.396 +    }
   1.397 +
   1.398 +    void erase(const Edge& edge) {
   1.399 +      int n = edge.id * 2;
   1.400 +
   1.401 +      if (arcs[n].next_out != -1) {
   1.402 +        arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
   1.403 +      }
   1.404 +
   1.405 +      if (arcs[n].prev_out != -1) {
   1.406 +        arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
   1.407 +      } else {
   1.408 +        nodes[arcs[n | 1].target].first_out = arcs[n].next_out;
   1.409 +      }
   1.410 +
   1.411 +      if (arcs[n | 1].next_out != -1) {
   1.412 +        arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
   1.413 +      }
   1.414 +
   1.415 +      if (arcs[n | 1].prev_out != -1) {
   1.416 +        arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
   1.417 +      } else {
   1.418 +        nodes[arcs[n].target].first_out = arcs[n | 1].next_out;
   1.419 +      }
   1.420 +
   1.421 +      arcs[n].next_out = first_free_arc;
   1.422 +      first_free_arc = n;
   1.423 +      arcs[n].prev_out = -2;
   1.424 +      arcs[n | 1].prev_out = -2;
   1.425 +
   1.426 +    }
   1.427 +
   1.428 +    void clear() {
   1.429 +      arcs.clear();
   1.430 +      nodes.clear();
   1.431 +      first_node = first_free_arc = first_red = first_blue =
   1.432 +        max_red = max_blue = first_free_red = first_free_blue = -1;
   1.433 +    }
   1.434 +
   1.435 +  protected:
   1.436 +
   1.437 +    void changeRed(Edge e, Node n) {
   1.438 +      LEMON_DEBUG(nodes[n].red, "Node has to be red");
   1.439 +      if(arcs[(2 * e.id) | 1].next_out != -1) {
   1.440 +        arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
   1.441 +          arcs[(2 * e.id) | 1].prev_out;
   1.442 +      }
   1.443 +      if(arcs[(2 * e.id) | 1].prev_out != -1) {
   1.444 +        arcs[arcs[(2 * e.id) | 1].prev_out].next_out =
   1.445 +          arcs[(2 * e.id) | 1].next_out;
   1.446 +      } else {
   1.447 +        nodes[arcs[2 * e.id].target].first_out =
   1.448 +          arcs[(2 * e.id) | 1].next_out;
   1.449 +      }
   1.450 +
   1.451 +      if (nodes[n.id].first_out != -1) {
   1.452 +        arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
   1.453 +      }
   1.454 +      arcs[2 * e.id].target = n.id;
   1.455 +      arcs[(2 * e.id) | 1].prev_out = -1;
   1.456 +      arcs[(2 * e.id) | 1].next_out = nodes[n.id].first_out;
   1.457 +      nodes[n.id].first_out = ((2 * e.id) | 1);
   1.458 +    }
   1.459 +
   1.460 +    void changeBlue(Edge e, Node n) {
   1.461 +      LEMON_DEBUG(nodes[n].red, "Node has to be blue");
   1.462 +      if(arcs[2 * e.id].next_out != -1) {
   1.463 +        arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
   1.464 +      }
   1.465 +      if(arcs[2 * e.id].prev_out != -1) {
   1.466 +        arcs[arcs[2 * e.id].prev_out].next_out =
   1.467 +          arcs[2 * e.id].next_out;
   1.468 +      } else {
   1.469 +        nodes[arcs[(2 * e.id) | 1].target].first_out =
   1.470 +          arcs[2 * e.id].next_out;
   1.471 +      }
   1.472 +
   1.473 +      if (nodes[n.id].first_out != -1) {
   1.474 +        arcs[nodes[n.id].first_out].prev_out = 2 * e.id;
   1.475 +      }
   1.476 +      arcs[(2 * e.id) | 1].target = n.id;
   1.477 +      arcs[2 * e.id].prev_out = -1;
   1.478 +      arcs[2 * e.id].next_out = nodes[n.id].first_out;
   1.479 +      nodes[n.id].first_out = 2 * e.id;
   1.480 +    }
   1.481 +
   1.482 +  };
   1.483 +
   1.484 +  typedef BpGraphExtender<ListBpGraphBase> ExtendedListBpGraphBase;
   1.485 +
   1.486 +
   1.487 +  /// \addtogroup graphs
   1.488 +  /// @{
   1.489 +
   1.490 +  ///A general undirected graph structure.
   1.491 +
   1.492 +  ///\ref ListBpGraph is a versatile and fast undirected graph
   1.493 +  ///implementation based on linked lists that are stored in
   1.494 +  ///\c std::vector structures.
   1.495 +  ///
   1.496 +  ///This type fully conforms to the \ref concepts::BpGraph "BpGraph concept"
   1.497 +  ///and it also provides several useful additional functionalities.
   1.498 +  ///Most of its member functions and nested classes are documented
   1.499 +  ///only in the concept class.
   1.500 +  ///
   1.501 +  ///This class provides only linear time counting for nodes, edges and arcs.
   1.502 +  ///
   1.503 +  ///\sa concepts::BpGraph
   1.504 +  ///\sa ListDigraph
   1.505 +  class ListBpGraph : public ExtendedListBpGraphBase {
   1.506 +    typedef ExtendedListBpGraphBase Parent;
   1.507 +
   1.508 +  private:
   1.509 +    /// BpGraphs are \e not copy constructible. Use BpGraphCopy instead.
   1.510 +    ListBpGraph(const ListBpGraph &) :ExtendedListBpGraphBase()  {};
   1.511 +    /// \brief Assignment of a graph to another one is \e not allowed.
   1.512 +    /// Use BpGraphCopy instead.
   1.513 +    void operator=(const ListBpGraph &) {}
   1.514 +  public:
   1.515 +    /// Constructor
   1.516 +
   1.517 +    /// Constructor.
   1.518 +    ///
   1.519 +    ListBpGraph() {}
   1.520 +
   1.521 +    typedef Parent::OutArcIt IncEdgeIt;
   1.522 +
   1.523 +    /// \brief Add a new red node to the graph.
   1.524 +    ///
   1.525 +    /// This function adds a red new node to the graph.
   1.526 +    /// \return The new node.
   1.527 +    Node addRedNode() { return Parent::addRedNode(); }
   1.528 +
   1.529 +    /// \brief Add a new blue node to the graph.
   1.530 +    ///
   1.531 +    /// This function adds a blue new node to the graph.
   1.532 +    /// \return The new node.
   1.533 +    Node addBlueNode() { return Parent::addBlueNode(); }
   1.534 +
   1.535 +    /// \brief Add a new edge to the graph.
   1.536 +    ///
   1.537 +    /// This function adds a new edge to the graph between nodes
   1.538 +    /// \c u and \c v with inherent orientation from node \c u to
   1.539 +    /// node \c v.
   1.540 +    /// \return The new edge.
   1.541 +    Edge addEdge(Node u, Node v) {
   1.542 +      return Parent::addEdge(u, v);
   1.543 +    }
   1.544 +
   1.545 +    ///\brief Erase a node from the graph.
   1.546 +    ///
   1.547 +    /// This function erases the given node along with its incident arcs
   1.548 +    /// from the graph.
   1.549 +    ///
   1.550 +    /// \note All iterators referencing the removed node or the incident
   1.551 +    /// edges are invalidated, of course.
   1.552 +    void erase(Node n) { Parent::erase(n); }
   1.553 +
   1.554 +    ///\brief Erase an edge from the graph.
   1.555 +    ///
   1.556 +    /// This function erases the given edge from the graph.
   1.557 +    ///
   1.558 +    /// \note All iterators referencing the removed edge are invalidated,
   1.559 +    /// of course.
   1.560 +    void erase(Edge e) { Parent::erase(e); }
   1.561 +    /// Node validity check
   1.562 +
   1.563 +    /// This function gives back \c true if the given node is valid,
   1.564 +    /// i.e. it is a real node of the graph.
   1.565 +    ///
   1.566 +    /// \warning A removed node could become valid again if new nodes are
   1.567 +    /// added to the graph.
   1.568 +    bool valid(Node n) const { return Parent::valid(n); }
   1.569 +    /// Edge validity check
   1.570 +
   1.571 +    /// This function gives back \c true if the given edge is valid,
   1.572 +    /// i.e. it is a real edge of the graph.
   1.573 +    ///
   1.574 +    /// \warning A removed edge could become valid again if new edges are
   1.575 +    /// added to the graph.
   1.576 +    bool valid(Edge e) const { return Parent::valid(e); }
   1.577 +    /// Arc validity check
   1.578 +
   1.579 +    /// This function gives back \c true if the given arc is valid,
   1.580 +    /// i.e. it is a real arc of the graph.
   1.581 +    ///
   1.582 +    /// \warning A removed arc could become valid again if new edges are
   1.583 +    /// added to the graph.
   1.584 +    bool valid(Arc a) const { return Parent::valid(a); }
   1.585 +
   1.586 +    /// \brief Change the red node of an edge.
   1.587 +    ///
   1.588 +    /// This function changes the red node of the given edge \c e to \c n.
   1.589 +    ///
   1.590 +    ///\note \c EdgeIt and \c ArcIt iterators referencing the
   1.591 +    ///changed edge are invalidated and all other iterators whose
   1.592 +    ///base node is the changed node are also invalidated.
   1.593 +    ///
   1.594 +    ///\warning This functionality cannot be used together with the
   1.595 +    ///Snapshot feature.
   1.596 +    void changeRed(Edge e, Node n) {
   1.597 +      Parent::changeRed(e,n);
   1.598 +    }
   1.599 +    /// \brief Change the blue node of an edge.
   1.600 +    ///
   1.601 +    /// This function changes the blue node of the given edge \c e to \c n.
   1.602 +    ///
   1.603 +    ///\note \c EdgeIt iterators referencing the changed edge remain
   1.604 +    ///valid, but \c ArcIt iterators referencing the changed edge and
   1.605 +    ///all other iterators whose base node is the changed node are also
   1.606 +    ///invalidated.
   1.607 +    ///
   1.608 +    ///\warning This functionality cannot be used together with the
   1.609 +    ///Snapshot feature.
   1.610 +    void changeBlue(Edge e, Node n) {
   1.611 +      Parent::changeBlue(e,n);
   1.612 +    }
   1.613 +
   1.614 +    ///Clear the graph.
   1.615 +
   1.616 +    ///This function erases all nodes and arcs from the graph.
   1.617 +    ///
   1.618 +    ///\note All iterators of the graph are invalidated, of course.
   1.619 +    void clear() {
   1.620 +      Parent::clear();
   1.621 +    }
   1.622 +
   1.623 +    /// Reserve memory for nodes.
   1.624 +
   1.625 +    /// Using this function, it is possible to avoid superfluous memory
   1.626 +    /// allocation: if you know that the graph you want to build will
   1.627 +    /// be large (e.g. it will contain millions of nodes and/or edges),
   1.628 +    /// then it is worth reserving space for this amount before starting
   1.629 +    /// to build the graph.
   1.630 +    /// \sa reserveEdge()
   1.631 +    void reserveNode(int n) { nodes.reserve(n); };
   1.632 +
   1.633 +    /// Reserve memory for edges.
   1.634 +
   1.635 +    /// Using this function, it is possible to avoid superfluous memory
   1.636 +    /// allocation: if you know that the graph you want to build will
   1.637 +    /// be large (e.g. it will contain millions of nodes and/or edges),
   1.638 +    /// then it is worth reserving space for this amount before starting
   1.639 +    /// to build the graph.
   1.640 +    /// \sa reserveNode()
   1.641 +    void reserveEdge(int m) { arcs.reserve(2 * m); };
   1.642 +
   1.643 +    /// \brief Class to make a snapshot of the graph and restore
   1.644 +    /// it later.
   1.645 +    ///
   1.646 +    /// Class to make a snapshot of the graph and restore it later.
   1.647 +    ///
   1.648 +    /// The newly added nodes and edges can be removed
   1.649 +    /// using the restore() function.
   1.650 +    ///
   1.651 +    /// \note After a state is restored, you cannot restore a later state,
   1.652 +    /// i.e. you cannot add the removed nodes and edges again using
   1.653 +    /// another Snapshot instance.
   1.654 +    ///
   1.655 +    /// \warning Node and edge deletions and other modifications
   1.656 +    /// (e.g. changing the end-nodes of edges or contracting nodes)
   1.657 +    /// cannot be restored. These events invalidate the snapshot.
   1.658 +    /// However, the edges and nodes that were added to the graph after
   1.659 +    /// making the current snapshot can be removed without invalidating it.
   1.660 +    class Snapshot {
   1.661 +    protected:
   1.662 +
   1.663 +      typedef Parent::NodeNotifier NodeNotifier;
   1.664 +
   1.665 +      class NodeObserverProxy : public NodeNotifier::ObserverBase {
   1.666 +      public:
   1.667 +
   1.668 +        NodeObserverProxy(Snapshot& _snapshot)
   1.669 +          : snapshot(_snapshot) {}
   1.670 +
   1.671 +        using NodeNotifier::ObserverBase::attach;
   1.672 +        using NodeNotifier::ObserverBase::detach;
   1.673 +        using NodeNotifier::ObserverBase::attached;
   1.674 +
   1.675 +      protected:
   1.676 +
   1.677 +        virtual void add(const Node& node) {
   1.678 +          snapshot.addNode(node);
   1.679 +        }
   1.680 +        virtual void add(const std::vector<Node>& nodes) {
   1.681 +          for (int i = nodes.size() - 1; i >= 0; ++i) {
   1.682 +            snapshot.addNode(nodes[i]);
   1.683 +          }
   1.684 +        }
   1.685 +        virtual void erase(const Node& node) {
   1.686 +          snapshot.eraseNode(node);
   1.687 +        }
   1.688 +        virtual void erase(const std::vector<Node>& nodes) {
   1.689 +          for (int i = 0; i < int(nodes.size()); ++i) {
   1.690 +            snapshot.eraseNode(nodes[i]);
   1.691 +          }
   1.692 +        }
   1.693 +        virtual void build() {
   1.694 +          Node node;
   1.695 +          std::vector<Node> nodes;
   1.696 +          for (notifier()->first(node); node != INVALID;
   1.697 +               notifier()->next(node)) {
   1.698 +            nodes.push_back(node);
   1.699 +          }
   1.700 +          for (int i = nodes.size() - 1; i >= 0; --i) {
   1.701 +            snapshot.addNode(nodes[i]);
   1.702 +          }
   1.703 +        }
   1.704 +        virtual void clear() {
   1.705 +          Node node;
   1.706 +          for (notifier()->first(node); node != INVALID;
   1.707 +               notifier()->next(node)) {
   1.708 +            snapshot.eraseNode(node);
   1.709 +          }
   1.710 +        }
   1.711 +
   1.712 +        Snapshot& snapshot;
   1.713 +      };
   1.714 +
   1.715 +      class EdgeObserverProxy : public EdgeNotifier::ObserverBase {
   1.716 +      public:
   1.717 +
   1.718 +        EdgeObserverProxy(Snapshot& _snapshot)
   1.719 +          : snapshot(_snapshot) {}
   1.720 +
   1.721 +        using EdgeNotifier::ObserverBase::attach;
   1.722 +        using EdgeNotifier::ObserverBase::detach;
   1.723 +        using EdgeNotifier::ObserverBase::attached;
   1.724 +
   1.725 +      protected:
   1.726 +
   1.727 +        virtual void add(const Edge& edge) {
   1.728 +          snapshot.addEdge(edge);
   1.729 +        }
   1.730 +        virtual void add(const std::vector<Edge>& edges) {
   1.731 +          for (int i = edges.size() - 1; i >= 0; ++i) {
   1.732 +            snapshot.addEdge(edges[i]);
   1.733 +          }
   1.734 +        }
   1.735 +        virtual void erase(const Edge& edge) {
   1.736 +          snapshot.eraseEdge(edge);
   1.737 +        }
   1.738 +        virtual void erase(const std::vector<Edge>& edges) {
   1.739 +          for (int i = 0; i < int(edges.size()); ++i) {
   1.740 +            snapshot.eraseEdge(edges[i]);
   1.741 +          }
   1.742 +        }
   1.743 +        virtual void build() {
   1.744 +          Edge edge;
   1.745 +          std::vector<Edge> edges;
   1.746 +          for (notifier()->first(edge); edge != INVALID;
   1.747 +               notifier()->next(edge)) {
   1.748 +            edges.push_back(edge);
   1.749 +          }
   1.750 +          for (int i = edges.size() - 1; i >= 0; --i) {
   1.751 +            snapshot.addEdge(edges[i]);
   1.752 +          }
   1.753 +        }
   1.754 +        virtual void clear() {
   1.755 +          Edge edge;
   1.756 +          for (notifier()->first(edge); edge != INVALID;
   1.757 +               notifier()->next(edge)) {
   1.758 +            snapshot.eraseEdge(edge);
   1.759 +          }
   1.760 +        }
   1.761 +
   1.762 +        Snapshot& snapshot;
   1.763 +      };
   1.764 +
   1.765 +      ListBpGraph *graph;
   1.766 +
   1.767 +      NodeObserverProxy node_observer_proxy;
   1.768 +      EdgeObserverProxy edge_observer_proxy;
   1.769 +
   1.770 +      std::list<Node> added_nodes;
   1.771 +      std::list<Edge> added_edges;
   1.772 +
   1.773 +
   1.774 +      void addNode(const Node& node) {
   1.775 +        added_nodes.push_front(node);
   1.776 +      }
   1.777 +      void eraseNode(const Node& node) {
   1.778 +        std::list<Node>::iterator it =
   1.779 +          std::find(added_nodes.begin(), added_nodes.end(), node);
   1.780 +        if (it == added_nodes.end()) {
   1.781 +          clear();
   1.782 +          edge_observer_proxy.detach();
   1.783 +          throw NodeNotifier::ImmediateDetach();
   1.784 +        } else {
   1.785 +          added_nodes.erase(it);
   1.786 +        }
   1.787 +      }
   1.788 +
   1.789 +      void addEdge(const Edge& edge) {
   1.790 +        added_edges.push_front(edge);
   1.791 +      }
   1.792 +      void eraseEdge(const Edge& edge) {
   1.793 +        std::list<Edge>::iterator it =
   1.794 +          std::find(added_edges.begin(), added_edges.end(), edge);
   1.795 +        if (it == added_edges.end()) {
   1.796 +          clear();
   1.797 +          node_observer_proxy.detach();
   1.798 +          throw EdgeNotifier::ImmediateDetach();
   1.799 +        } else {
   1.800 +          added_edges.erase(it);
   1.801 +        }
   1.802 +      }
   1.803 +
   1.804 +      void attach(ListBpGraph &_graph) {
   1.805 +        graph = &_graph;
   1.806 +        node_observer_proxy.attach(graph->notifier(Node()));
   1.807 +        edge_observer_proxy.attach(graph->notifier(Edge()));
   1.808 +      }
   1.809 +
   1.810 +      void detach() {
   1.811 +        node_observer_proxy.detach();
   1.812 +        edge_observer_proxy.detach();
   1.813 +      }
   1.814 +
   1.815 +      bool attached() const {
   1.816 +        return node_observer_proxy.attached();
   1.817 +      }
   1.818 +
   1.819 +      void clear() {
   1.820 +        added_nodes.clear();
   1.821 +        added_edges.clear();
   1.822 +      }
   1.823 +
   1.824 +    public:
   1.825 +
   1.826 +      /// \brief Default constructor.
   1.827 +      ///
   1.828 +      /// Default constructor.
   1.829 +      /// You have to call save() to actually make a snapshot.
   1.830 +      Snapshot()
   1.831 +        : graph(0), node_observer_proxy(*this),
   1.832 +          edge_observer_proxy(*this) {}
   1.833 +
   1.834 +      /// \brief Constructor that immediately makes a snapshot.
   1.835 +      ///
   1.836 +      /// This constructor immediately makes a snapshot of the given graph.
   1.837 +      Snapshot(ListBpGraph &gr)
   1.838 +        : node_observer_proxy(*this),
   1.839 +          edge_observer_proxy(*this) {
   1.840 +        attach(gr);
   1.841 +      }
   1.842 +
   1.843 +      /// \brief Make a snapshot.
   1.844 +      ///
   1.845 +      /// This function makes a snapshot of the given graph.
   1.846 +      /// It can be called more than once. In case of a repeated
   1.847 +      /// call, the previous snapshot gets lost.
   1.848 +      void save(ListBpGraph &gr) {
   1.849 +        if (attached()) {
   1.850 +          detach();
   1.851 +          clear();
   1.852 +        }
   1.853 +        attach(gr);
   1.854 +      }
   1.855 +
   1.856 +      /// \brief Undo the changes until the last snapshot.
   1.857 +      ///
   1.858 +      /// This function undos the changes until the last snapshot
   1.859 +      /// created by save() or Snapshot(ListBpGraph&).
   1.860 +      ///
   1.861 +      /// \warning This method invalidates the snapshot, i.e. repeated
   1.862 +      /// restoring is not supported unless you call save() again.
   1.863 +      void restore() {
   1.864 +        detach();
   1.865 +        for(std::list<Edge>::iterator it = added_edges.begin();
   1.866 +            it != added_edges.end(); ++it) {
   1.867 +          graph->erase(*it);
   1.868 +        }
   1.869 +        for(std::list<Node>::iterator it = added_nodes.begin();
   1.870 +            it != added_nodes.end(); ++it) {
   1.871 +          graph->erase(*it);
   1.872 +        }
   1.873 +        clear();
   1.874 +      }
   1.875 +
   1.876 +      /// \brief Returns \c true if the snapshot is valid.
   1.877 +      ///
   1.878 +      /// This function returns \c true if the snapshot is valid.
   1.879 +      bool valid() const {
   1.880 +        return attached();
   1.881 +      }
   1.882 +    };
   1.883 +  };
   1.884 +
   1.885 +  /// @}
   1.886  } //namespace lemon
   1.887  
   1.888  
     2.1 --- a/lemon/smart_graph.h	Sun Nov 14 22:48:32 2010 +0100
     2.2 +++ b/lemon/smart_graph.h	Mon Nov 15 09:46:08 2010 +0100
     2.3 @@ -1016,7 +1016,7 @@
     2.4        return nodes[v._id].partition_index;
     2.5      }
     2.6      int blueId(Node v) const {
     2.7 -      LEMON_DEBUG(nodes[v._id].red, "Node has to be blue");
     2.8 +      LEMON_DEBUG(!nodes[v._id].red, "Node has to be blue");
     2.9        return nodes[v._id].partition_index;
    2.10      }
    2.11      static int id(Arc e) { return e._id; }
     3.1 --- a/test/bpgraph_test.cc	Sun Nov 14 22:48:32 2010 +0100
     3.2 +++ b/test/bpgraph_test.cc	Mon Nov 15 09:46:08 2010 +0100
     3.3 @@ -17,7 +17,7 @@
     3.4   */
     3.5  
     3.6  #include <lemon/concepts/bpgraph.h>
     3.7 -//#include <lemon/list_graph.h>
     3.8 +#include <lemon/list_graph.h>
     3.9  #include <lemon/smart_graph.h>
    3.10  #include <lemon/full_graph.h>
    3.11  
    3.12 @@ -107,11 +107,108 @@
    3.13    checkGraphEdgeMap(G);
    3.14  }
    3.15  
    3.16 -template <class Graph>
    3.17 +template <class BpGraph>
    3.18 +void checkBpGraphErase() {
    3.19 +  TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);
    3.20 +
    3.21 +  BpGraph G;
    3.22 +  Node
    3.23 +    n1 = G.addRedNode(), n2 = G.addBlueNode(),
    3.24 +    n3 = G.addBlueNode(), n4 = G.addRedNode();
    3.25 +  Edge
    3.26 +    e1 = G.addEdge(n1, n2), e2 = G.addEdge(n1, n3),
    3.27 +    e3 = G.addEdge(n4, n2), e4 = G.addEdge(n4, n3);
    3.28 +
    3.29 +  // Check edge deletion
    3.30 +  G.erase(e2);
    3.31 +
    3.32 +  checkGraphNodeList(G, 4);
    3.33 +  checkGraphRedNodeList(G, 2);
    3.34 +  checkGraphBlueNodeList(G, 2);
    3.35 +  checkGraphEdgeList(G, 3);
    3.36 +  checkGraphArcList(G, 6);
    3.37 +
    3.38 +  checkGraphIncEdgeArcLists(G, n1, 1);
    3.39 +  checkGraphIncEdgeArcLists(G, n2, 2);
    3.40 +  checkGraphIncEdgeArcLists(G, n3, 1);
    3.41 +  checkGraphIncEdgeArcLists(G, n4, 2);
    3.42 +
    3.43 +  checkGraphConEdgeList(G, 3);
    3.44 +  checkGraphConArcList(G, 6);
    3.45 +
    3.46 +  // Check node deletion
    3.47 +  G.erase(n3);
    3.48 +
    3.49 +  checkGraphNodeList(G, 3);
    3.50 +  checkGraphRedNodeList(G, 2);
    3.51 +  checkGraphBlueNodeList(G, 1);
    3.52 +  checkGraphEdgeList(G, 2);
    3.53 +  checkGraphArcList(G, 4);
    3.54 +
    3.55 +  checkGraphIncEdgeArcLists(G, n1, 1);
    3.56 +  checkGraphIncEdgeArcLists(G, n2, 2);
    3.57 +  checkGraphIncEdgeArcLists(G, n4, 1);
    3.58 +
    3.59 +  checkGraphConEdgeList(G, 2);
    3.60 +  checkGraphConArcList(G, 4);
    3.61 +
    3.62 +}
    3.63 +
    3.64 +template <class BpGraph>
    3.65 +void checkBpGraphAlter() {
    3.66 +  TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);
    3.67 +
    3.68 +  BpGraph G;
    3.69 +  Node
    3.70 +    n1 = G.addRedNode(), n2 = G.addBlueNode(),
    3.71 +    n3 = G.addBlueNode(), n4 = G.addRedNode();
    3.72 +  Edge
    3.73 +    e1 = G.addEdge(n1, n2), e2 = G.addEdge(n1, n3),
    3.74 +    e3 = G.addEdge(n4, n2), e4 = G.addEdge(n4, n3);
    3.75 +
    3.76 +  G.changeRed(e2, n4);
    3.77 +  check(G.redNode(e2) == n4, "Wrong red node");
    3.78 +  check(G.blueNode(e2) == n3, "Wrong blue node");
    3.79 +
    3.80 +  checkGraphNodeList(G, 4);
    3.81 +  checkGraphRedNodeList(G, 2);
    3.82 +  checkGraphBlueNodeList(G, 2);
    3.83 +  checkGraphEdgeList(G, 4);
    3.84 +  checkGraphArcList(G, 8);
    3.85 +
    3.86 +  checkGraphIncEdgeArcLists(G, n1, 1);
    3.87 +  checkGraphIncEdgeArcLists(G, n2, 2);
    3.88 +  checkGraphIncEdgeArcLists(G, n3, 2);
    3.89 +  checkGraphIncEdgeArcLists(G, n4, 3);
    3.90 +
    3.91 +  checkGraphConEdgeList(G, 4);
    3.92 +  checkGraphConArcList(G, 8);
    3.93 +
    3.94 +  G.changeBlue(e2, n2);
    3.95 +  check(G.redNode(e2) == n4, "Wrong red node");
    3.96 +  check(G.blueNode(e2) == n2, "Wrong blue node");
    3.97 +
    3.98 +  checkGraphNodeList(G, 4);
    3.99 +  checkGraphRedNodeList(G, 2);
   3.100 +  checkGraphBlueNodeList(G, 2);
   3.101 +  checkGraphEdgeList(G, 4);
   3.102 +  checkGraphArcList(G, 8);
   3.103 +
   3.104 +  checkGraphIncEdgeArcLists(G, n1, 1);
   3.105 +  checkGraphIncEdgeArcLists(G, n2, 3);
   3.106 +  checkGraphIncEdgeArcLists(G, n3, 1);
   3.107 +  checkGraphIncEdgeArcLists(G, n4, 3);
   3.108 +
   3.109 +  checkGraphConEdgeList(G, 4);
   3.110 +  checkGraphConArcList(G, 8);
   3.111 +}
   3.112 +
   3.113 +
   3.114 +template <class BpGraph>
   3.115  void checkBpGraphSnapshot() {
   3.116 -  TEMPLATE_BPGRAPH_TYPEDEFS(Graph);
   3.117 +  TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);
   3.118  
   3.119 -  Graph G;
   3.120 +  BpGraph G;
   3.121    Node 
   3.122      n1 = G.addRedNode(),
   3.123      n2 = G.addBlueNode(),
   3.124 @@ -126,7 +223,7 @@
   3.125    checkGraphEdgeList(G, 2);
   3.126    checkGraphArcList(G, 4);
   3.127  
   3.128 -  typename Graph::Snapshot snapshot(G);
   3.129 +  typename BpGraph::Snapshot snapshot(G);
   3.130  
   3.131    Node n4 = G.addRedNode();
   3.132    G.addEdge(n4, n2);
   3.133 @@ -190,10 +287,10 @@
   3.134    checkGraphArcList(G, 4);
   3.135  }
   3.136  
   3.137 -template <typename Graph>
   3.138 +template <typename BpGraph>
   3.139  void checkBpGraphValidity() {
   3.140 -  TEMPLATE_GRAPH_TYPEDEFS(Graph);
   3.141 -  Graph g;
   3.142 +  TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);
   3.143 +  BpGraph g;
   3.144  
   3.145    Node
   3.146      n1 = g.addRedNode(),
   3.147 @@ -325,6 +422,13 @@
   3.148  }
   3.149  
   3.150  void checkGraphs() {
   3.151 +  { // Checking ListGraph
   3.152 +    checkBpGraphBuild<ListBpGraph>();
   3.153 +    checkBpGraphErase<ListBpGraph>();
   3.154 +    checkBpGraphAlter<ListBpGraph>();
   3.155 +    checkBpGraphSnapshot<ListBpGraph>();
   3.156 +    checkBpGraphValidity<ListBpGraph>();
   3.157 +  }
   3.158    { // Checking SmartGraph
   3.159      checkBpGraphBuild<SmartBpGraph>();
   3.160      checkBpGraphSnapshot<SmartBpGraph>();