Merge
authorAlpar Juttner <alpar@cs.elte.hu>
Fri, 22 May 2015 17:44:29 +0200
changeset 1356138714057145
parent 1347 0900cfe4a84d
parent 1355 81f70097df81
child 1357 2126945deb6a
Merge
lemon/list_graph.h
     1.1 --- a/lemon/list_graph.h	Wed May 06 16:01:26 2015 +0200
     1.2 +++ b/lemon/list_graph.h	Fri May 22 17:44:29 2015 +0200
     1.3 @@ -582,6 +582,1723 @@
     1.4            snapshot.addNode(node);
     1.5          }
     1.6          virtual void add(const std::vector<Node>& nodes) {
     1.7 +          for (int i = nodes.size() - 1; i >= 0; --i) {
     1.8 +            snapshot.addNode(nodes[i]);
     1.9 +          }
    1.10 +        }
    1.11 +        virtual void erase(const Node& node) {
    1.12 +          snapshot.eraseNode(node);
    1.13 +        }
    1.14 +        virtual void erase(const std::vector<Node>& nodes) {
    1.15 +          for (int i = 0; i < int(nodes.size()); ++i) {
    1.16 +            snapshot.eraseNode(nodes[i]);
    1.17 +          }
    1.18 +        }
    1.19 +        virtual void build() {
    1.20 +          Node node;
    1.21 +          std::vector<Node> nodes;
    1.22 +          for (notifier()->first(node); node != INVALID;
    1.23 +               notifier()->next(node)) {
    1.24 +            nodes.push_back(node);
    1.25 +          }
    1.26 +          for (int i = nodes.size() - 1; i >= 0; --i) {
    1.27 +            snapshot.addNode(nodes[i]);
    1.28 +          }
    1.29 +        }
    1.30 +        virtual void clear() {
    1.31 +          Node node;
    1.32 +          for (notifier()->first(node); node != INVALID;
    1.33 +               notifier()->next(node)) {
    1.34 +            snapshot.eraseNode(node);
    1.35 +          }
    1.36 +        }
    1.37 +
    1.38 +        Snapshot& snapshot;
    1.39 +      };
    1.40 +
    1.41 +      class ArcObserverProxy : public ArcNotifier::ObserverBase {
    1.42 +      public:
    1.43 +
    1.44 +        ArcObserverProxy(Snapshot& _snapshot)
    1.45 +          : snapshot(_snapshot) {}
    1.46 +
    1.47 +        using ArcNotifier::ObserverBase::attach;
    1.48 +        using ArcNotifier::ObserverBase::detach;
    1.49 +        using ArcNotifier::ObserverBase::attached;
    1.50 +
    1.51 +      protected:
    1.52 +
    1.53 +        virtual void add(const Arc& arc) {
    1.54 +          snapshot.addArc(arc);
    1.55 +        }
    1.56 +        virtual void add(const std::vector<Arc>& arcs) {
    1.57 +          for (int i = arcs.size() - 1; i >= 0; --i) {
    1.58 +            snapshot.addArc(arcs[i]);
    1.59 +          }
    1.60 +        }
    1.61 +        virtual void erase(const Arc& arc) {
    1.62 +          snapshot.eraseArc(arc);
    1.63 +        }
    1.64 +        virtual void erase(const std::vector<Arc>& arcs) {
    1.65 +          for (int i = 0; i < int(arcs.size()); ++i) {
    1.66 +            snapshot.eraseArc(arcs[i]);
    1.67 +          }
    1.68 +        }
    1.69 +        virtual void build() {
    1.70 +          Arc arc;
    1.71 +          std::vector<Arc> arcs;
    1.72 +          for (notifier()->first(arc); arc != INVALID;
    1.73 +               notifier()->next(arc)) {
    1.74 +            arcs.push_back(arc);
    1.75 +          }
    1.76 +          for (int i = arcs.size() - 1; i >= 0; --i) {
    1.77 +            snapshot.addArc(arcs[i]);
    1.78 +          }
    1.79 +        }
    1.80 +        virtual void clear() {
    1.81 +          Arc arc;
    1.82 +          for (notifier()->first(arc); arc != INVALID;
    1.83 +               notifier()->next(arc)) {
    1.84 +            snapshot.eraseArc(arc);
    1.85 +          }
    1.86 +        }
    1.87 +
    1.88 +        Snapshot& snapshot;
    1.89 +      };
    1.90 +
    1.91 +      ListDigraph *digraph;
    1.92 +
    1.93 +      NodeObserverProxy node_observer_proxy;
    1.94 +      ArcObserverProxy arc_observer_proxy;
    1.95 +
    1.96 +      std::list<Node> added_nodes;
    1.97 +      std::list<Arc> added_arcs;
    1.98 +
    1.99 +
   1.100 +      void addNode(const Node& node) {
   1.101 +        added_nodes.push_front(node);
   1.102 +      }
   1.103 +      void eraseNode(const Node& node) {
   1.104 +        std::list<Node>::iterator it =
   1.105 +          std::find(added_nodes.begin(), added_nodes.end(), node);
   1.106 +        if (it == added_nodes.end()) {
   1.107 +          clear();
   1.108 +          arc_observer_proxy.detach();
   1.109 +          throw NodeNotifier::ImmediateDetach();
   1.110 +        } else {
   1.111 +          added_nodes.erase(it);
   1.112 +        }
   1.113 +      }
   1.114 +
   1.115 +      void addArc(const Arc& arc) {
   1.116 +        added_arcs.push_front(arc);
   1.117 +      }
   1.118 +      void eraseArc(const Arc& arc) {
   1.119 +        std::list<Arc>::iterator it =
   1.120 +          std::find(added_arcs.begin(), added_arcs.end(), arc);
   1.121 +        if (it == added_arcs.end()) {
   1.122 +          clear();
   1.123 +          node_observer_proxy.detach();
   1.124 +          throw ArcNotifier::ImmediateDetach();
   1.125 +        } else {
   1.126 +          added_arcs.erase(it);
   1.127 +        }
   1.128 +      }
   1.129 +
   1.130 +      void attach(ListDigraph &_digraph) {
   1.131 +        digraph = &_digraph;
   1.132 +        node_observer_proxy.attach(digraph->notifier(Node()));
   1.133 +        arc_observer_proxy.attach(digraph->notifier(Arc()));
   1.134 +      }
   1.135 +
   1.136 +      void detach() {
   1.137 +        node_observer_proxy.detach();
   1.138 +        arc_observer_proxy.detach();
   1.139 +      }
   1.140 +
   1.141 +      bool attached() const {
   1.142 +        return node_observer_proxy.attached();
   1.143 +      }
   1.144 +
   1.145 +      void clear() {
   1.146 +        added_nodes.clear();
   1.147 +        added_arcs.clear();
   1.148 +      }
   1.149 +
   1.150 +    public:
   1.151 +
   1.152 +      /// \brief Default constructor.
   1.153 +      ///
   1.154 +      /// Default constructor.
   1.155 +      /// You have to call save() to actually make a snapshot.
   1.156 +      Snapshot()
   1.157 +        : digraph(0), node_observer_proxy(*this),
   1.158 +          arc_observer_proxy(*this) {}
   1.159 +
   1.160 +      /// \brief Constructor that immediately makes a snapshot.
   1.161 +      ///
   1.162 +      /// This constructor immediately makes a snapshot of the given digraph.
   1.163 +      Snapshot(ListDigraph &gr)
   1.164 +        : node_observer_proxy(*this),
   1.165 +          arc_observer_proxy(*this) {
   1.166 +        attach(gr);
   1.167 +      }
   1.168 +
   1.169 +      /// \brief Make a snapshot.
   1.170 +      ///
   1.171 +      /// This function makes a snapshot of the given digraph.
   1.172 +      /// It can be called more than once. In case of a repeated
   1.173 +      /// call, the previous snapshot gets lost.
   1.174 +      void save(ListDigraph &gr) {
   1.175 +        if (attached()) {
   1.176 +          detach();
   1.177 +          clear();
   1.178 +        }
   1.179 +        attach(gr);
   1.180 +      }
   1.181 +
   1.182 +      /// \brief Undo the changes until the last snapshot.
   1.183 +      ///
   1.184 +      /// This function undos the changes until the last snapshot
   1.185 +      /// created by save() or Snapshot(ListDigraph&).
   1.186 +      ///
   1.187 +      /// \warning This method invalidates the snapshot, i.e. repeated
   1.188 +      /// restoring is not supported unless you call save() again.
   1.189 +      void restore() {
   1.190 +        detach();
   1.191 +        for(std::list<Arc>::iterator it = added_arcs.begin();
   1.192 +            it != added_arcs.end(); ++it) {
   1.193 +          digraph->erase(*it);
   1.194 +        }
   1.195 +        for(std::list<Node>::iterator it = added_nodes.begin();
   1.196 +            it != added_nodes.end(); ++it) {
   1.197 +          digraph->erase(*it);
   1.198 +        }
   1.199 +        clear();
   1.200 +      }
   1.201 +
   1.202 +      /// \brief Returns \c true if the snapshot is valid.
   1.203 +      ///
   1.204 +      /// This function returns \c true if the snapshot is valid.
   1.205 +      bool valid() const {
   1.206 +        return attached();
   1.207 +      }
   1.208 +    };
   1.209 +
   1.210 +  };
   1.211 +
   1.212 +  ///@}
   1.213 +
   1.214 +  class ListGraphBase {
   1.215 +
   1.216 +  protected:
   1.217 +
   1.218 +    struct NodeT {
   1.219 +      int first_out;
   1.220 +      int prev, next;
   1.221 +    };
   1.222 +
   1.223 +    struct ArcT {
   1.224 +      int target;
   1.225 +      int prev_out, next_out;
   1.226 +    };
   1.227 +
   1.228 +    std::vector<NodeT> nodes;
   1.229 +
   1.230 +    int first_node;
   1.231 +
   1.232 +    int first_free_node;
   1.233 +
   1.234 +    std::vector<ArcT> arcs;
   1.235 +
   1.236 +    int first_free_arc;
   1.237 +
   1.238 +  public:
   1.239 +
   1.240 +    typedef ListGraphBase Graph;
   1.241 +
   1.242 +    class Node {
   1.243 +      friend class ListGraphBase;
   1.244 +    protected:
   1.245 +
   1.246 +      int id;
   1.247 +      explicit Node(int pid) { id = pid;}
   1.248 +
   1.249 +    public:
   1.250 +      Node() {}
   1.251 +      Node (Invalid) { id = -1; }
   1.252 +      bool operator==(const Node& node) const {return id == node.id;}
   1.253 +      bool operator!=(const Node& node) const {return id != node.id;}
   1.254 +      bool operator<(const Node& node) const {return id < node.id;}
   1.255 +    };
   1.256 +
   1.257 +    class Edge {
   1.258 +      friend class ListGraphBase;
   1.259 +    protected:
   1.260 +
   1.261 +      int id;
   1.262 +      explicit Edge(int pid) { id = pid;}
   1.263 +
   1.264 +    public:
   1.265 +      Edge() {}
   1.266 +      Edge (Invalid) { id = -1; }
   1.267 +      bool operator==(const Edge& edge) const {return id == edge.id;}
   1.268 +      bool operator!=(const Edge& edge) const {return id != edge.id;}
   1.269 +      bool operator<(const Edge& edge) const {return id < edge.id;}
   1.270 +    };
   1.271 +
   1.272 +    class Arc {
   1.273 +      friend class ListGraphBase;
   1.274 +    protected:
   1.275 +
   1.276 +      int id;
   1.277 +      explicit Arc(int pid) { id = pid;}
   1.278 +
   1.279 +    public:
   1.280 +      operator Edge() const {
   1.281 +        return id != -1 ? edgeFromId(id / 2) : INVALID;
   1.282 +      }
   1.283 +
   1.284 +      Arc() {}
   1.285 +      Arc (Invalid) { id = -1; }
   1.286 +      bool operator==(const Arc& arc) const {return id == arc.id;}
   1.287 +      bool operator!=(const Arc& arc) const {return id != arc.id;}
   1.288 +      bool operator<(const Arc& arc) const {return id < arc.id;}
   1.289 +    };
   1.290 +
   1.291 +    ListGraphBase()
   1.292 +      : nodes(), first_node(-1),
   1.293 +        first_free_node(-1), arcs(), first_free_arc(-1) {}
   1.294 +
   1.295 +
   1.296 +    int maxNodeId() const { return nodes.size()-1; }
   1.297 +    int maxEdgeId() const { return arcs.size() / 2 - 1; }
   1.298 +    int maxArcId() const { return arcs.size()-1; }
   1.299 +
   1.300 +    Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); }
   1.301 +    Node target(Arc e) const { return Node(arcs[e.id].target); }
   1.302 +
   1.303 +    Node u(Edge e) const { return Node(arcs[2 * e.id].target); }
   1.304 +    Node v(Edge e) const { return Node(arcs[2 * e.id + 1].target); }
   1.305 +
   1.306 +    static bool direction(Arc e) {
   1.307 +      return (e.id & 1) == 1;
   1.308 +    }
   1.309 +
   1.310 +    static Arc direct(Edge e, bool d) {
   1.311 +      return Arc(e.id * 2 + (d ? 1 : 0));
   1.312 +    }
   1.313 +
   1.314 +    void first(Node& node) const {
   1.315 +      node.id = first_node;
   1.316 +    }
   1.317 +
   1.318 +    void next(Node& node) const {
   1.319 +      node.id = nodes[node.id].next;
   1.320 +    }
   1.321 +
   1.322 +    void first(Arc& e) const {
   1.323 +      int n = first_node;
   1.324 +      while (n != -1 && nodes[n].first_out == -1) {
   1.325 +        n = nodes[n].next;
   1.326 +      }
   1.327 +      e.id = (n == -1) ? -1 : nodes[n].first_out;
   1.328 +    }
   1.329 +
   1.330 +    void next(Arc& e) const {
   1.331 +      if (arcs[e.id].next_out != -1) {
   1.332 +        e.id = arcs[e.id].next_out;
   1.333 +      } else {
   1.334 +        int n = nodes[arcs[e.id ^ 1].target].next;
   1.335 +        while(n != -1 && nodes[n].first_out == -1) {
   1.336 +          n = nodes[n].next;
   1.337 +        }
   1.338 +        e.id = (n == -1) ? -1 : nodes[n].first_out;
   1.339 +      }
   1.340 +    }
   1.341 +
   1.342 +    void first(Edge& e) const {
   1.343 +      int n = first_node;
   1.344 +      while (n != -1) {
   1.345 +        e.id = nodes[n].first_out;
   1.346 +        while ((e.id & 1) != 1) {
   1.347 +          e.id = arcs[e.id].next_out;
   1.348 +        }
   1.349 +        if (e.id != -1) {
   1.350 +          e.id /= 2;
   1.351 +          return;
   1.352 +        }
   1.353 +        n = nodes[n].next;
   1.354 +      }
   1.355 +      e.id = -1;
   1.356 +    }
   1.357 +
   1.358 +    void next(Edge& e) const {
   1.359 +      int n = arcs[e.id * 2].target;
   1.360 +      e.id = arcs[(e.id * 2) | 1].next_out;
   1.361 +      while ((e.id & 1) != 1) {
   1.362 +        e.id = arcs[e.id].next_out;
   1.363 +      }
   1.364 +      if (e.id != -1) {
   1.365 +        e.id /= 2;
   1.366 +        return;
   1.367 +      }
   1.368 +      n = nodes[n].next;
   1.369 +      while (n != -1) {
   1.370 +        e.id = nodes[n].first_out;
   1.371 +        while ((e.id & 1) != 1) {
   1.372 +          e.id = arcs[e.id].next_out;
   1.373 +        }
   1.374 +        if (e.id != -1) {
   1.375 +          e.id /= 2;
   1.376 +          return;
   1.377 +        }
   1.378 +        n = nodes[n].next;
   1.379 +      }
   1.380 +      e.id = -1;
   1.381 +    }
   1.382 +
   1.383 +    void firstOut(Arc &e, const Node& v) const {
   1.384 +      e.id = nodes[v.id].first_out;
   1.385 +    }
   1.386 +    void nextOut(Arc &e) const {
   1.387 +      e.id = arcs[e.id].next_out;
   1.388 +    }
   1.389 +
   1.390 +    void firstIn(Arc &e, const Node& v) const {
   1.391 +      e.id = ((nodes[v.id].first_out) ^ 1);
   1.392 +      if (e.id == -2) e.id = -1;
   1.393 +    }
   1.394 +    void nextIn(Arc &e) const {
   1.395 +      e.id = ((arcs[e.id ^ 1].next_out) ^ 1);
   1.396 +      if (e.id == -2) e.id = -1;
   1.397 +    }
   1.398 +
   1.399 +    void firstInc(Edge &e, bool& d, const Node& v) const {
   1.400 +      int a = nodes[v.id].first_out;
   1.401 +      if (a != -1 ) {
   1.402 +        e.id = a / 2;
   1.403 +        d = ((a & 1) == 1);
   1.404 +      } else {
   1.405 +        e.id = -1;
   1.406 +        d = true;
   1.407 +      }
   1.408 +    }
   1.409 +    void nextInc(Edge &e, bool& d) const {
   1.410 +      int a = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
   1.411 +      if (a != -1 ) {
   1.412 +        e.id = a / 2;
   1.413 +        d = ((a & 1) == 1);
   1.414 +      } else {
   1.415 +        e.id = -1;
   1.416 +        d = true;
   1.417 +      }
   1.418 +    }
   1.419 +
   1.420 +    static int id(Node v) { return v.id; }
   1.421 +    static int id(Arc e) { return e.id; }
   1.422 +    static int id(Edge e) { return e.id; }
   1.423 +
   1.424 +    static Node nodeFromId(int id) { return Node(id);}
   1.425 +    static Arc arcFromId(int id) { return Arc(id);}
   1.426 +    static Edge edgeFromId(int id) { return Edge(id);}
   1.427 +
   1.428 +    bool valid(Node n) const {
   1.429 +      return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
   1.430 +        nodes[n.id].prev != -2;
   1.431 +    }
   1.432 +
   1.433 +    bool valid(Arc a) const {
   1.434 +      return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
   1.435 +        arcs[a.id].prev_out != -2;
   1.436 +    }
   1.437 +
   1.438 +    bool valid(Edge e) const {
   1.439 +      return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) &&
   1.440 +        arcs[2 * e.id].prev_out != -2;
   1.441 +    }
   1.442 +
   1.443 +    Node addNode() {
   1.444 +      int n;
   1.445 +
   1.446 +      if(first_free_node==-1) {
   1.447 +        n = nodes.size();
   1.448 +        nodes.push_back(NodeT());
   1.449 +      } else {
   1.450 +        n = first_free_node;
   1.451 +        first_free_node = nodes[n].next;
   1.452 +      }
   1.453 +
   1.454 +      nodes[n].next = first_node;
   1.455 +      if (first_node != -1) nodes[first_node].prev = n;
   1.456 +      first_node = n;
   1.457 +      nodes[n].prev = -1;
   1.458 +
   1.459 +      nodes[n].first_out = -1;
   1.460 +
   1.461 +      return Node(n);
   1.462 +    }
   1.463 +
   1.464 +    Edge addEdge(Node u, Node v) {
   1.465 +      int n;
   1.466 +
   1.467 +      if (first_free_arc == -1) {
   1.468 +        n = arcs.size();
   1.469 +        arcs.push_back(ArcT());
   1.470 +        arcs.push_back(ArcT());
   1.471 +      } else {
   1.472 +        n = first_free_arc;
   1.473 +        first_free_arc = arcs[n].next_out;
   1.474 +      }
   1.475 +
   1.476 +      arcs[n].target = u.id;
   1.477 +      arcs[n | 1].target = v.id;
   1.478 +
   1.479 +      arcs[n].next_out = nodes[v.id].first_out;
   1.480 +      if (nodes[v.id].first_out != -1) {
   1.481 +        arcs[nodes[v.id].first_out].prev_out = n;
   1.482 +      }
   1.483 +      arcs[n].prev_out = -1;
   1.484 +      nodes[v.id].first_out = n;
   1.485 +
   1.486 +      arcs[n | 1].next_out = nodes[u.id].first_out;
   1.487 +      if (nodes[u.id].first_out != -1) {
   1.488 +        arcs[nodes[u.id].first_out].prev_out = (n | 1);
   1.489 +      }
   1.490 +      arcs[n | 1].prev_out = -1;
   1.491 +      nodes[u.id].first_out = (n | 1);
   1.492 +
   1.493 +      return Edge(n / 2);
   1.494 +    }
   1.495 +
   1.496 +    void erase(const Node& node) {
   1.497 +      int n = node.id;
   1.498 +
   1.499 +      if(nodes[n].next != -1) {
   1.500 +        nodes[nodes[n].next].prev = nodes[n].prev;
   1.501 +      }
   1.502 +
   1.503 +      if(nodes[n].prev != -1) {
   1.504 +        nodes[nodes[n].prev].next = nodes[n].next;
   1.505 +      } else {
   1.506 +        first_node = nodes[n].next;
   1.507 +      }
   1.508 +
   1.509 +      nodes[n].next = first_free_node;
   1.510 +      first_free_node = n;
   1.511 +      nodes[n].prev = -2;
   1.512 +    }
   1.513 +
   1.514 +    void erase(const Edge& edge) {
   1.515 +      int n = edge.id * 2;
   1.516 +
   1.517 +      if (arcs[n].next_out != -1) {
   1.518 +        arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
   1.519 +      }
   1.520 +
   1.521 +      if (arcs[n].prev_out != -1) {
   1.522 +        arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
   1.523 +      } else {
   1.524 +        nodes[arcs[n | 1].target].first_out = arcs[n].next_out;
   1.525 +      }
   1.526 +
   1.527 +      if (arcs[n | 1].next_out != -1) {
   1.528 +        arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
   1.529 +      }
   1.530 +
   1.531 +      if (arcs[n | 1].prev_out != -1) {
   1.532 +        arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
   1.533 +      } else {
   1.534 +        nodes[arcs[n].target].first_out = arcs[n | 1].next_out;
   1.535 +      }
   1.536 +
   1.537 +      arcs[n].next_out = first_free_arc;
   1.538 +      first_free_arc = n;
   1.539 +      arcs[n].prev_out = -2;
   1.540 +      arcs[n | 1].prev_out = -2;
   1.541 +
   1.542 +    }
   1.543 +
   1.544 +    void clear() {
   1.545 +      arcs.clear();
   1.546 +      nodes.clear();
   1.547 +      first_node = first_free_node = first_free_arc = -1;
   1.548 +    }
   1.549 +
   1.550 +  protected:
   1.551 +
   1.552 +    void changeV(Edge e, Node n) {
   1.553 +      if(arcs[2 * e.id].next_out != -1) {
   1.554 +        arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
   1.555 +      }
   1.556 +      if(arcs[2 * e.id].prev_out != -1) {
   1.557 +        arcs[arcs[2 * e.id].prev_out].next_out =
   1.558 +          arcs[2 * e.id].next_out;
   1.559 +      } else {
   1.560 +        nodes[arcs[(2 * e.id) | 1].target].first_out =
   1.561 +          arcs[2 * e.id].next_out;
   1.562 +      }
   1.563 +
   1.564 +      if (nodes[n.id].first_out != -1) {
   1.565 +        arcs[nodes[n.id].first_out].prev_out = 2 * e.id;
   1.566 +      }
   1.567 +      arcs[(2 * e.id) | 1].target = n.id;
   1.568 +      arcs[2 * e.id].prev_out = -1;
   1.569 +      arcs[2 * e.id].next_out = nodes[n.id].first_out;
   1.570 +      nodes[n.id].first_out = 2 * e.id;
   1.571 +    }
   1.572 +
   1.573 +    void changeU(Edge e, Node n) {
   1.574 +      if(arcs[(2 * e.id) | 1].next_out != -1) {
   1.575 +        arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
   1.576 +          arcs[(2 * e.id) | 1].prev_out;
   1.577 +      }
   1.578 +      if(arcs[(2 * e.id) | 1].prev_out != -1) {
   1.579 +        arcs[arcs[(2 * e.id) | 1].prev_out].next_out =
   1.580 +          arcs[(2 * e.id) | 1].next_out;
   1.581 +      } else {
   1.582 +        nodes[arcs[2 * e.id].target].first_out =
   1.583 +          arcs[(2 * e.id) | 1].next_out;
   1.584 +      }
   1.585 +
   1.586 +      if (nodes[n.id].first_out != -1) {
   1.587 +        arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
   1.588 +      }
   1.589 +      arcs[2 * e.id].target = n.id;
   1.590 +      arcs[(2 * e.id) | 1].prev_out = -1;
   1.591 +      arcs[(2 * e.id) | 1].next_out = nodes[n.id].first_out;
   1.592 +      nodes[n.id].first_out = ((2 * e.id) | 1);
   1.593 +    }
   1.594 +
   1.595 +  };
   1.596 +
   1.597 +  typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
   1.598 +
   1.599 +
   1.600 +  /// \addtogroup graphs
   1.601 +  /// @{
   1.602 +
   1.603 +  ///A general undirected graph structure.
   1.604 +
   1.605 +  ///\ref ListGraph is a versatile and fast undirected graph
   1.606 +  ///implementation based on linked lists that are stored in
   1.607 +  ///\c std::vector structures.
   1.608 +  ///
   1.609 +  ///This type fully conforms to the \ref concepts::Graph "Graph concept"
   1.610 +  ///and it also provides several useful additional functionalities.
   1.611 +  ///Most of its member functions and nested classes are documented
   1.612 +  ///only in the concept class.
   1.613 +  ///
   1.614 +  ///This class provides only linear time counting for nodes, edges and arcs.
   1.615 +  ///
   1.616 +  ///\sa concepts::Graph
   1.617 +  ///\sa ListDigraph
   1.618 +  class ListGraph : public ExtendedListGraphBase {
   1.619 +    typedef ExtendedListGraphBase Parent;
   1.620 +
   1.621 +  private:
   1.622 +    /// Graphs are \e not copy constructible. Use GraphCopy instead.
   1.623 +    ListGraph(const ListGraph &) :ExtendedListGraphBase()  {};
   1.624 +    /// \brief Assignment of a graph to another one is \e not allowed.
   1.625 +    /// Use GraphCopy instead.
   1.626 +    void operator=(const ListGraph &) {}
   1.627 +  public:
   1.628 +    /// Constructor
   1.629 +
   1.630 +    /// Constructor.
   1.631 +    ///
   1.632 +    ListGraph() {}
   1.633 +
   1.634 +    typedef Parent::OutArcIt IncEdgeIt;
   1.635 +
   1.636 +    /// \brief Add a new node to the graph.
   1.637 +    ///
   1.638 +    /// This function adds a new node to the graph.
   1.639 +    /// \return The new node.
   1.640 +    Node addNode() { return Parent::addNode(); }
   1.641 +
   1.642 +    /// \brief Add a new edge to the graph.
   1.643 +    ///
   1.644 +    /// This function adds a new edge to the graph between nodes
   1.645 +    /// \c u and \c v with inherent orientation from node \c u to
   1.646 +    /// node \c v.
   1.647 +    /// \return The new edge.
   1.648 +    Edge addEdge(Node u, Node v) {
   1.649 +      return Parent::addEdge(u, v);
   1.650 +    }
   1.651 +
   1.652 +    ///\brief Erase a node from the graph.
   1.653 +    ///
   1.654 +    /// This function erases the given node along with its incident arcs
   1.655 +    /// from the graph.
   1.656 +    ///
   1.657 +    /// \note All iterators referencing the removed node or the incident
   1.658 +    /// edges are invalidated, of course.
   1.659 +    void erase(Node n) { Parent::erase(n); }
   1.660 +
   1.661 +    ///\brief Erase an edge from the graph.
   1.662 +    ///
   1.663 +    /// This function erases the given edge from the graph.
   1.664 +    ///
   1.665 +    /// \note All iterators referencing the removed edge are invalidated,
   1.666 +    /// of course.
   1.667 +    void erase(Edge e) { Parent::erase(e); }
   1.668 +    /// Node validity check
   1.669 +
   1.670 +    /// This function gives back \c true if the given node is valid,
   1.671 +    /// i.e. it is a real node of the graph.
   1.672 +    ///
   1.673 +    /// \warning A removed node could become valid again if new nodes are
   1.674 +    /// added to the graph.
   1.675 +    bool valid(Node n) const { return Parent::valid(n); }
   1.676 +    /// Edge validity check
   1.677 +
   1.678 +    /// This function gives back \c true if the given edge is valid,
   1.679 +    /// i.e. it is a real edge of the graph.
   1.680 +    ///
   1.681 +    /// \warning A removed edge could become valid again if new edges are
   1.682 +    /// added to the graph.
   1.683 +    bool valid(Edge e) const { return Parent::valid(e); }
   1.684 +    /// Arc validity check
   1.685 +
   1.686 +    /// This function gives back \c true if the given arc is valid,
   1.687 +    /// i.e. it is a real arc of the graph.
   1.688 +    ///
   1.689 +    /// \warning A removed arc could become valid again if new edges are
   1.690 +    /// added to the graph.
   1.691 +    bool valid(Arc a) const { return Parent::valid(a); }
   1.692 +
   1.693 +    /// \brief Change the first node of an edge.
   1.694 +    ///
   1.695 +    /// This function changes the first node of the given edge \c e to \c n.
   1.696 +    ///
   1.697 +    ///\note \c EdgeIt and \c ArcIt iterators referencing the
   1.698 +    ///changed edge are invalidated and all other iterators whose
   1.699 +    ///base node is the changed node are also invalidated.
   1.700 +    ///
   1.701 +    ///\warning This functionality cannot be used together with the
   1.702 +    ///Snapshot feature.
   1.703 +    void changeU(Edge e, Node n) {
   1.704 +      Parent::changeU(e,n);
   1.705 +    }
   1.706 +    /// \brief Change the second node of an edge.
   1.707 +    ///
   1.708 +    /// This function changes the second node of the given edge \c e to \c n.
   1.709 +    ///
   1.710 +    ///\note \c EdgeIt iterators referencing the changed edge remain
   1.711 +    ///valid, but \c ArcIt iterators referencing the changed edge and
   1.712 +    ///all other iterators whose base node is the changed node are also
   1.713 +    ///invalidated.
   1.714 +    ///
   1.715 +    ///\warning This functionality cannot be used together with the
   1.716 +    ///Snapshot feature.
   1.717 +    void changeV(Edge e, Node n) {
   1.718 +      Parent::changeV(e,n);
   1.719 +    }
   1.720 +
   1.721 +    /// \brief Contract two nodes.
   1.722 +    ///
   1.723 +    /// This function contracts the given two nodes.
   1.724 +    /// Node \c b is removed, but instead of deleting
   1.725 +    /// its incident edges, they are joined to node \c a.
   1.726 +    /// If the last parameter \c r is \c true (this is the default value),
   1.727 +    /// then the newly created loops are removed.
   1.728 +    ///
   1.729 +    /// \note The moved edges are joined to node \c a using changeU()
   1.730 +    /// or changeV(), thus all edge and arc iterators whose base node is
   1.731 +    /// \c b are invalidated.
   1.732 +    /// Moreover all iterators referencing node \c b or the removed
   1.733 +    /// loops are also invalidated. Other iterators remain valid.
   1.734 +    ///
   1.735 +    ///\warning This functionality cannot be used together with the
   1.736 +    ///Snapshot feature.
   1.737 +    void contract(Node a, Node b, bool r = true) {
   1.738 +      for(IncEdgeIt e(*this, b); e!=INVALID;) {
   1.739 +        IncEdgeIt f = e; ++f;
   1.740 +        if (r && runningNode(e) == a) {
   1.741 +          erase(e);
   1.742 +        } else if (u(e) == b) {
   1.743 +          changeU(e, a);
   1.744 +        } else {
   1.745 +          changeV(e, a);
   1.746 +        }
   1.747 +        e = f;
   1.748 +      }
   1.749 +      erase(b);
   1.750 +    }
   1.751 +
   1.752 +    ///Clear the graph.
   1.753 +
   1.754 +    ///This function erases all nodes and arcs from the graph.
   1.755 +    ///
   1.756 +    ///\note All iterators of the graph are invalidated, of course.
   1.757 +    void clear() {
   1.758 +      Parent::clear();
   1.759 +    }
   1.760 +
   1.761 +    /// Reserve memory for nodes.
   1.762 +
   1.763 +    /// Using this function, it is possible to avoid superfluous memory
   1.764 +    /// allocation: if you know that the graph you want to build will
   1.765 +    /// be large (e.g. it will contain millions of nodes and/or edges),
   1.766 +    /// then it is worth reserving space for this amount before starting
   1.767 +    /// to build the graph.
   1.768 +    /// \sa reserveEdge()
   1.769 +    void reserveNode(int n) { nodes.reserve(n); };
   1.770 +
   1.771 +    /// Reserve memory for edges.
   1.772 +
   1.773 +    /// Using this function, it is possible to avoid superfluous memory
   1.774 +    /// allocation: if you know that the graph you want to build will
   1.775 +    /// be large (e.g. it will contain millions of nodes and/or edges),
   1.776 +    /// then it is worth reserving space for this amount before starting
   1.777 +    /// to build the graph.
   1.778 +    /// \sa reserveNode()
   1.779 +    void reserveEdge(int m) { arcs.reserve(2 * m); };
   1.780 +
   1.781 +    /// \brief Class to make a snapshot of the graph and restore
   1.782 +    /// it later.
   1.783 +    ///
   1.784 +    /// Class to make a snapshot of the graph and restore it later.
   1.785 +    ///
   1.786 +    /// The newly added nodes and edges can be removed
   1.787 +    /// using the restore() function.
   1.788 +    ///
   1.789 +    /// \note After a state is restored, you cannot restore a later state,
   1.790 +    /// i.e. you cannot add the removed nodes and edges again using
   1.791 +    /// another Snapshot instance.
   1.792 +    ///
   1.793 +    /// \warning Node and edge deletions and other modifications
   1.794 +    /// (e.g. changing the end-nodes of edges or contracting nodes)
   1.795 +    /// cannot be restored. These events invalidate the snapshot.
   1.796 +    /// However, the edges and nodes that were added to the graph after
   1.797 +    /// making the current snapshot can be removed without invalidating it.
   1.798 +    class Snapshot {
   1.799 +    protected:
   1.800 +
   1.801 +      typedef Parent::NodeNotifier NodeNotifier;
   1.802 +
   1.803 +      class NodeObserverProxy : public NodeNotifier::ObserverBase {
   1.804 +      public:
   1.805 +
   1.806 +        NodeObserverProxy(Snapshot& _snapshot)
   1.807 +          : snapshot(_snapshot) {}
   1.808 +
   1.809 +        using NodeNotifier::ObserverBase::attach;
   1.810 +        using NodeNotifier::ObserverBase::detach;
   1.811 +        using NodeNotifier::ObserverBase::attached;
   1.812 +
   1.813 +      protected:
   1.814 +
   1.815 +        virtual void add(const Node& node) {
   1.816 +          snapshot.addNode(node);
   1.817 +        }
   1.818 +        virtual void add(const std::vector<Node>& nodes) {
   1.819 +          for (int i = nodes.size() - 1; i >= 0; --i) {
   1.820 +            snapshot.addNode(nodes[i]);
   1.821 +          }
   1.822 +        }
   1.823 +        virtual void erase(const Node& node) {
   1.824 +          snapshot.eraseNode(node);
   1.825 +        }
   1.826 +        virtual void erase(const std::vector<Node>& nodes) {
   1.827 +          for (int i = 0; i < int(nodes.size()); ++i) {
   1.828 +            snapshot.eraseNode(nodes[i]);
   1.829 +          }
   1.830 +        }
   1.831 +        virtual void build() {
   1.832 +          Node node;
   1.833 +          std::vector<Node> nodes;
   1.834 +          for (notifier()->first(node); node != INVALID;
   1.835 +               notifier()->next(node)) {
   1.836 +            nodes.push_back(node);
   1.837 +          }
   1.838 +          for (int i = nodes.size() - 1; i >= 0; --i) {
   1.839 +            snapshot.addNode(nodes[i]);
   1.840 +          }
   1.841 +        }
   1.842 +        virtual void clear() {
   1.843 +          Node node;
   1.844 +          for (notifier()->first(node); node != INVALID;
   1.845 +               notifier()->next(node)) {
   1.846 +            snapshot.eraseNode(node);
   1.847 +          }
   1.848 +        }
   1.849 +
   1.850 +        Snapshot& snapshot;
   1.851 +      };
   1.852 +
   1.853 +      class EdgeObserverProxy : public EdgeNotifier::ObserverBase {
   1.854 +      public:
   1.855 +
   1.856 +        EdgeObserverProxy(Snapshot& _snapshot)
   1.857 +          : snapshot(_snapshot) {}
   1.858 +
   1.859 +        using EdgeNotifier::ObserverBase::attach;
   1.860 +        using EdgeNotifier::ObserverBase::detach;
   1.861 +        using EdgeNotifier::ObserverBase::attached;
   1.862 +
   1.863 +      protected:
   1.864 +
   1.865 +        virtual void add(const Edge& edge) {
   1.866 +          snapshot.addEdge(edge);
   1.867 +        }
   1.868 +        virtual void add(const std::vector<Edge>& edges) {
   1.869 +          for (int i = edges.size() - 1; i >= 0; --i) {
   1.870 +            snapshot.addEdge(edges[i]);
   1.871 +          }
   1.872 +        }
   1.873 +        virtual void erase(const Edge& edge) {
   1.874 +          snapshot.eraseEdge(edge);
   1.875 +        }
   1.876 +        virtual void erase(const std::vector<Edge>& edges) {
   1.877 +          for (int i = 0; i < int(edges.size()); ++i) {
   1.878 +            snapshot.eraseEdge(edges[i]);
   1.879 +          }
   1.880 +        }
   1.881 +        virtual void build() {
   1.882 +          Edge edge;
   1.883 +          std::vector<Edge> edges;
   1.884 +          for (notifier()->first(edge); edge != INVALID;
   1.885 +               notifier()->next(edge)) {
   1.886 +            edges.push_back(edge);
   1.887 +          }
   1.888 +          for (int i = edges.size() - 1; i >= 0; --i) {
   1.889 +            snapshot.addEdge(edges[i]);
   1.890 +          }
   1.891 +        }
   1.892 +        virtual void clear() {
   1.893 +          Edge edge;
   1.894 +          for (notifier()->first(edge); edge != INVALID;
   1.895 +               notifier()->next(edge)) {
   1.896 +            snapshot.eraseEdge(edge);
   1.897 +          }
   1.898 +        }
   1.899 +
   1.900 +        Snapshot& snapshot;
   1.901 +      };
   1.902 +
   1.903 +      ListGraph *graph;
   1.904 +
   1.905 +      NodeObserverProxy node_observer_proxy;
   1.906 +      EdgeObserverProxy edge_observer_proxy;
   1.907 +
   1.908 +      std::list<Node> added_nodes;
   1.909 +      std::list<Edge> added_edges;
   1.910 +
   1.911 +
   1.912 +      void addNode(const Node& node) {
   1.913 +        added_nodes.push_front(node);
   1.914 +      }
   1.915 +      void eraseNode(const Node& node) {
   1.916 +        std::list<Node>::iterator it =
   1.917 +          std::find(added_nodes.begin(), added_nodes.end(), node);
   1.918 +        if (it == added_nodes.end()) {
   1.919 +          clear();
   1.920 +          edge_observer_proxy.detach();
   1.921 +          throw NodeNotifier::ImmediateDetach();
   1.922 +        } else {
   1.923 +          added_nodes.erase(it);
   1.924 +        }
   1.925 +      }
   1.926 +
   1.927 +      void addEdge(const Edge& edge) {
   1.928 +        added_edges.push_front(edge);
   1.929 +      }
   1.930 +      void eraseEdge(const Edge& edge) {
   1.931 +        std::list<Edge>::iterator it =
   1.932 +          std::find(added_edges.begin(), added_edges.end(), edge);
   1.933 +        if (it == added_edges.end()) {
   1.934 +          clear();
   1.935 +          node_observer_proxy.detach();
   1.936 +          throw EdgeNotifier::ImmediateDetach();
   1.937 +        } else {
   1.938 +          added_edges.erase(it);
   1.939 +        }
   1.940 +      }
   1.941 +
   1.942 +      void attach(ListGraph &_graph) {
   1.943 +        graph = &_graph;
   1.944 +        node_observer_proxy.attach(graph->notifier(Node()));
   1.945 +        edge_observer_proxy.attach(graph->notifier(Edge()));
   1.946 +      }
   1.947 +
   1.948 +      void detach() {
   1.949 +        node_observer_proxy.detach();
   1.950 +        edge_observer_proxy.detach();
   1.951 +      }
   1.952 +
   1.953 +      bool attached() const {
   1.954 +        return node_observer_proxy.attached();
   1.955 +      }
   1.956 +
   1.957 +      void clear() {
   1.958 +        added_nodes.clear();
   1.959 +        added_edges.clear();
   1.960 +      }
   1.961 +
   1.962 +    public:
   1.963 +
   1.964 +      /// \brief Default constructor.
   1.965 +      ///
   1.966 +      /// Default constructor.
   1.967 +      /// You have to call save() to actually make a snapshot.
   1.968 +      Snapshot()
   1.969 +        : graph(0), node_observer_proxy(*this),
   1.970 +          edge_observer_proxy(*this) {}
   1.971 +
   1.972 +      /// \brief Constructor that immediately makes a snapshot.
   1.973 +      ///
   1.974 +      /// This constructor immediately makes a snapshot of the given graph.
   1.975 +      Snapshot(ListGraph &gr)
   1.976 +        : node_observer_proxy(*this),
   1.977 +          edge_observer_proxy(*this) {
   1.978 +        attach(gr);
   1.979 +      }
   1.980 +
   1.981 +      /// \brief Make a snapshot.
   1.982 +      ///
   1.983 +      /// This function makes a snapshot of the given graph.
   1.984 +      /// It can be called more than once. In case of a repeated
   1.985 +      /// call, the previous snapshot gets lost.
   1.986 +      void save(ListGraph &gr) {
   1.987 +        if (attached()) {
   1.988 +          detach();
   1.989 +          clear();
   1.990 +        }
   1.991 +        attach(gr);
   1.992 +      }
   1.993 +
   1.994 +      /// \brief Undo the changes until the last snapshot.
   1.995 +      ///
   1.996 +      /// This function undos the changes until the last snapshot
   1.997 +      /// created by save() or Snapshot(ListGraph&).
   1.998 +      ///
   1.999 +      /// \warning This method invalidates the snapshot, i.e. repeated
  1.1000 +      /// restoring is not supported unless you call save() again.
  1.1001 +      void restore() {
  1.1002 +        detach();
  1.1003 +        for(std::list<Edge>::iterator it = added_edges.begin();
  1.1004 +            it != added_edges.end(); ++it) {
  1.1005 +          graph->erase(*it);
  1.1006 +        }
  1.1007 +        for(std::list<Node>::iterator it = added_nodes.begin();
  1.1008 +            it != added_nodes.end(); ++it) {
  1.1009 +          graph->erase(*it);
  1.1010 +        }
  1.1011 +        clear();
  1.1012 +      }
  1.1013 +
  1.1014 +      /// \brief Returns \c true if the snapshot is valid.
  1.1015 +      ///
  1.1016 +      /// This function returns \c true if the snapshot is valid.
  1.1017 +      bool valid() const {
  1.1018 +        return attached();
  1.1019 +      }
  1.1020 +    };
  1.1021 +  };
  1.1022 +
  1.1023 +  /// @}
  1.1024 +
  1.1025 +  class ListBpGraphBase {
  1.1026 +
  1.1027 +  protected:
  1.1028 +
  1.1029 +    struct NodeT {
  1.1030 +      int first_out;
  1.1031 +      int prev, next;
  1.1032 +      int partition_prev, partition_next;
  1.1033 +      int partition_index;
  1.1034 +      bool red;
  1.1035 +    };
  1.1036 +
  1.1037 +    struct ArcT {
  1.1038 +      int target;
  1.1039 +      int prev_out, next_out;
  1.1040 +    };
  1.1041 +
  1.1042 +    std::vector<NodeT> nodes;
  1.1043 +
  1.1044 +    int first_node, first_red, first_blue;
  1.1045 +    int max_red, max_blue;
  1.1046 +
  1.1047 +    int first_free_red, first_free_blue;
  1.1048 +
  1.1049 +    std::vector<ArcT> arcs;
  1.1050 +
  1.1051 +    int first_free_arc;
  1.1052 +
  1.1053 +  public:
  1.1054 +
  1.1055 +    typedef ListBpGraphBase BpGraph;
  1.1056 +
  1.1057 +    class Node {
  1.1058 +      friend class ListBpGraphBase;
  1.1059 +    protected:
  1.1060 +
  1.1061 +      int id;
  1.1062 +      explicit Node(int pid) { id = pid;}
  1.1063 +
  1.1064 +    public:
  1.1065 +      Node() {}
  1.1066 +      Node (Invalid) { id = -1; }
  1.1067 +      bool operator==(const Node& node) const {return id == node.id;}
  1.1068 +      bool operator!=(const Node& node) const {return id != node.id;}
  1.1069 +      bool operator<(const Node& node) const {return id < node.id;}
  1.1070 +    };
  1.1071 +
  1.1072 +    class RedNode : public Node {
  1.1073 +      friend class ListBpGraphBase;
  1.1074 +    protected:
  1.1075 +
  1.1076 +      explicit RedNode(int pid) : Node(pid) {}
  1.1077 +
  1.1078 +    public:
  1.1079 +      RedNode() {}
  1.1080 +      RedNode(const RedNode& node) : Node(node) {}
  1.1081 +      RedNode(Invalid) : Node(INVALID){}
  1.1082 +    };
  1.1083 +
  1.1084 +    class BlueNode : public Node {
  1.1085 +      friend class ListBpGraphBase;
  1.1086 +    protected:
  1.1087 +
  1.1088 +      explicit BlueNode(int pid) : Node(pid) {}
  1.1089 +
  1.1090 +    public:
  1.1091 +      BlueNode() {}
  1.1092 +      BlueNode(const BlueNode& node) : Node(node) {}
  1.1093 +      BlueNode(Invalid) : Node(INVALID){}
  1.1094 +    };
  1.1095 +
  1.1096 +    class Edge {
  1.1097 +      friend class ListBpGraphBase;
  1.1098 +    protected:
  1.1099 +
  1.1100 +      int id;
  1.1101 +      explicit Edge(int pid) { id = pid;}
  1.1102 +
  1.1103 +    public:
  1.1104 +      Edge() {}
  1.1105 +      Edge (Invalid) { id = -1; }
  1.1106 +      bool operator==(const Edge& edge) const {return id == edge.id;}
  1.1107 +      bool operator!=(const Edge& edge) const {return id != edge.id;}
  1.1108 +      bool operator<(const Edge& edge) const {return id < edge.id;}
  1.1109 +    };
  1.1110 +
  1.1111 +    class Arc {
  1.1112 +      friend class ListBpGraphBase;
  1.1113 +    protected:
  1.1114 +
  1.1115 +      int id;
  1.1116 +      explicit Arc(int pid) { id = pid;}
  1.1117 +
  1.1118 +    public:
  1.1119 +      operator Edge() const {
  1.1120 +        return id != -1 ? edgeFromId(id / 2) : INVALID;
  1.1121 +      }
  1.1122 +
  1.1123 +      Arc() {}
  1.1124 +      Arc (Invalid) { id = -1; }
  1.1125 +      bool operator==(const Arc& arc) const {return id == arc.id;}
  1.1126 +      bool operator!=(const Arc& arc) const {return id != arc.id;}
  1.1127 +      bool operator<(const Arc& arc) const {return id < arc.id;}
  1.1128 +    };
  1.1129 +
  1.1130 +    ListBpGraphBase()
  1.1131 +      : nodes(), first_node(-1),
  1.1132 +        first_red(-1), first_blue(-1),
  1.1133 +        max_red(-1), max_blue(-1),
  1.1134 +        first_free_red(-1), first_free_blue(-1),
  1.1135 +        arcs(), first_free_arc(-1) {}
  1.1136 +
  1.1137 +
  1.1138 +    bool red(Node n) const { return nodes[n.id].red; }
  1.1139 +    bool blue(Node n) const { return !nodes[n.id].red; }
  1.1140 +
  1.1141 +    static RedNode asRedNodeUnsafe(Node n) { return RedNode(n.id); }
  1.1142 +    static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n.id); }
  1.1143 +
  1.1144 +    int maxNodeId() const { return nodes.size()-1; }
  1.1145 +    int maxRedId() const { return max_red; }
  1.1146 +    int maxBlueId() const { return max_blue; }
  1.1147 +    int maxEdgeId() const { return arcs.size() / 2 - 1; }
  1.1148 +    int maxArcId() const { return arcs.size()-1; }
  1.1149 +
  1.1150 +    Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); }
  1.1151 +    Node target(Arc e) const { return Node(arcs[e.id].target); }
  1.1152 +
  1.1153 +    RedNode redNode(Edge e) const {
  1.1154 +      return RedNode(arcs[2 * e.id].target);
  1.1155 +    }
  1.1156 +    BlueNode blueNode(Edge e) const {
  1.1157 +      return BlueNode(arcs[2 * e.id + 1].target);
  1.1158 +    }
  1.1159 +
  1.1160 +    static bool direction(Arc e) {
  1.1161 +      return (e.id & 1) == 1;
  1.1162 +    }
  1.1163 +
  1.1164 +    static Arc direct(Edge e, bool d) {
  1.1165 +      return Arc(e.id * 2 + (d ? 1 : 0));
  1.1166 +    }
  1.1167 +
  1.1168 +    void first(Node& node) const {
  1.1169 +      node.id = first_node;
  1.1170 +    }
  1.1171 +
  1.1172 +    void next(Node& node) const {
  1.1173 +      node.id = nodes[node.id].next;
  1.1174 +    }
  1.1175 +
  1.1176 +    void first(RedNode& node) const {
  1.1177 +      node.id = first_red;
  1.1178 +    }
  1.1179 +
  1.1180 +    void next(RedNode& node) const {
  1.1181 +      node.id = nodes[node.id].partition_next;
  1.1182 +    }
  1.1183 +
  1.1184 +    void first(BlueNode& node) const {
  1.1185 +      node.id = first_blue;
  1.1186 +    }
  1.1187 +
  1.1188 +    void next(BlueNode& node) const {
  1.1189 +      node.id = nodes[node.id].partition_next;
  1.1190 +    }
  1.1191 +
  1.1192 +    void first(Arc& e) const {
  1.1193 +      int n = first_node;
  1.1194 +      while (n != -1 && nodes[n].first_out == -1) {
  1.1195 +        n = nodes[n].next;
  1.1196 +      }
  1.1197 +      e.id = (n == -1) ? -1 : nodes[n].first_out;
  1.1198 +    }
  1.1199 +
  1.1200 +    void next(Arc& e) const {
  1.1201 +      if (arcs[e.id].next_out != -1) {
  1.1202 +        e.id = arcs[e.id].next_out;
  1.1203 +      } else {
  1.1204 +        int n = nodes[arcs[e.id ^ 1].target].next;
  1.1205 +        while(n != -1 && nodes[n].first_out == -1) {
  1.1206 +          n = nodes[n].next;
  1.1207 +        }
  1.1208 +        e.id = (n == -1) ? -1 : nodes[n].first_out;
  1.1209 +      }
  1.1210 +    }
  1.1211 +
  1.1212 +    void first(Edge& e) const {
  1.1213 +      int n = first_node;
  1.1214 +      while (n != -1) {
  1.1215 +        e.id = nodes[n].first_out;
  1.1216 +        while ((e.id & 1) != 1) {
  1.1217 +          e.id = arcs[e.id].next_out;
  1.1218 +        }
  1.1219 +        if (e.id != -1) {
  1.1220 +          e.id /= 2;
  1.1221 +          return;
  1.1222 +        }
  1.1223 +        n = nodes[n].next;
  1.1224 +      }
  1.1225 +      e.id = -1;
  1.1226 +    }
  1.1227 +
  1.1228 +    void next(Edge& e) const {
  1.1229 +      int n = arcs[e.id * 2].target;
  1.1230 +      e.id = arcs[(e.id * 2) | 1].next_out;
  1.1231 +      while ((e.id & 1) != 1) {
  1.1232 +        e.id = arcs[e.id].next_out;
  1.1233 +      }
  1.1234 +      if (e.id != -1) {
  1.1235 +        e.id /= 2;
  1.1236 +        return;
  1.1237 +      }
  1.1238 +      n = nodes[n].next;
  1.1239 +      while (n != -1) {
  1.1240 +        e.id = nodes[n].first_out;
  1.1241 +        while ((e.id & 1) != 1) {
  1.1242 +          e.id = arcs[e.id].next_out;
  1.1243 +        }
  1.1244 +        if (e.id != -1) {
  1.1245 +          e.id /= 2;
  1.1246 +          return;
  1.1247 +        }
  1.1248 +        n = nodes[n].next;
  1.1249 +      }
  1.1250 +      e.id = -1;
  1.1251 +    }
  1.1252 +
  1.1253 +    void firstOut(Arc &e, const Node& v) const {
  1.1254 +      e.id = nodes[v.id].first_out;
  1.1255 +    }
  1.1256 +    void nextOut(Arc &e) const {
  1.1257 +      e.id = arcs[e.id].next_out;
  1.1258 +    }
  1.1259 +
  1.1260 +    void firstIn(Arc &e, const Node& v) const {
  1.1261 +      e.id = ((nodes[v.id].first_out) ^ 1);
  1.1262 +      if (e.id == -2) e.id = -1;
  1.1263 +    }
  1.1264 +    void nextIn(Arc &e) const {
  1.1265 +      e.id = ((arcs[e.id ^ 1].next_out) ^ 1);
  1.1266 +      if (e.id == -2) e.id = -1;
  1.1267 +    }
  1.1268 +
  1.1269 +    void firstInc(Edge &e, bool& d, const Node& v) const {
  1.1270 +      int a = nodes[v.id].first_out;
  1.1271 +      if (a != -1 ) {
  1.1272 +        e.id = a / 2;
  1.1273 +        d = ((a & 1) == 1);
  1.1274 +      } else {
  1.1275 +        e.id = -1;
  1.1276 +        d = true;
  1.1277 +      }
  1.1278 +    }
  1.1279 +    void nextInc(Edge &e, bool& d) const {
  1.1280 +      int a = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
  1.1281 +      if (a != -1 ) {
  1.1282 +        e.id = a / 2;
  1.1283 +        d = ((a & 1) == 1);
  1.1284 +      } else {
  1.1285 +        e.id = -1;
  1.1286 +        d = true;
  1.1287 +      }
  1.1288 +    }
  1.1289 +
  1.1290 +    static int id(Node v) { return v.id; }
  1.1291 +    int id(RedNode v) const { return nodes[v.id].partition_index; }
  1.1292 +    int id(BlueNode v) const { return nodes[v.id].partition_index; }
  1.1293 +    static int id(Arc e) { return e.id; }
  1.1294 +    static int id(Edge e) { return e.id; }
  1.1295 +
  1.1296 +    static Node nodeFromId(int id) { return Node(id);}
  1.1297 +    static Arc arcFromId(int id) { return Arc(id);}
  1.1298 +    static Edge edgeFromId(int id) { return Edge(id);}
  1.1299 +
  1.1300 +    bool valid(Node n) const {
  1.1301 +      return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
  1.1302 +        nodes[n.id].prev != -2;
  1.1303 +    }
  1.1304 +
  1.1305 +    bool valid(Arc a) const {
  1.1306 +      return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
  1.1307 +        arcs[a.id].prev_out != -2;
  1.1308 +    }
  1.1309 +
  1.1310 +    bool valid(Edge e) const {
  1.1311 +      return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) &&
  1.1312 +        arcs[2 * e.id].prev_out != -2;
  1.1313 +    }
  1.1314 +
  1.1315 +    RedNode addRedNode() {
  1.1316 +      int n;
  1.1317 +
  1.1318 +      if(first_free_red==-1) {
  1.1319 +        n = nodes.size();
  1.1320 +        nodes.push_back(NodeT());
  1.1321 +        nodes[n].partition_index = ++max_red;
  1.1322 +        nodes[n].red = true;
  1.1323 +      } else {
  1.1324 +        n = first_free_red;
  1.1325 +        first_free_red = nodes[n].next;
  1.1326 +      }
  1.1327 +
  1.1328 +      nodes[n].next = first_node;
  1.1329 +      if (first_node != -1) nodes[first_node].prev = n;
  1.1330 +      first_node = n;
  1.1331 +      nodes[n].prev = -1;
  1.1332 +
  1.1333 +      nodes[n].partition_next = first_red;
  1.1334 +      if (first_red != -1) nodes[first_red].partition_prev = n;
  1.1335 +      first_red = n;
  1.1336 +      nodes[n].partition_prev = -1;
  1.1337 +
  1.1338 +      nodes[n].first_out = -1;
  1.1339 +
  1.1340 +      return RedNode(n);
  1.1341 +    }
  1.1342 +
  1.1343 +    BlueNode addBlueNode() {
  1.1344 +      int n;
  1.1345 +
  1.1346 +      if(first_free_blue==-1) {
  1.1347 +        n = nodes.size();
  1.1348 +        nodes.push_back(NodeT());
  1.1349 +        nodes[n].partition_index = ++max_blue;
  1.1350 +        nodes[n].red = false;
  1.1351 +      } else {
  1.1352 +        n = first_free_blue;
  1.1353 +        first_free_blue = nodes[n].next;
  1.1354 +      }
  1.1355 +
  1.1356 +      nodes[n].next = first_node;
  1.1357 +      if (first_node != -1) nodes[first_node].prev = n;
  1.1358 +      first_node = n;
  1.1359 +      nodes[n].prev = -1;
  1.1360 +
  1.1361 +      nodes[n].partition_next = first_blue;
  1.1362 +      if (first_blue != -1) nodes[first_blue].partition_prev = n;
  1.1363 +      first_blue = n;
  1.1364 +      nodes[n].partition_prev = -1;
  1.1365 +
  1.1366 +      nodes[n].first_out = -1;
  1.1367 +
  1.1368 +      return BlueNode(n);
  1.1369 +    }
  1.1370 +
  1.1371 +    Edge addEdge(Node u, Node v) {
  1.1372 +      int n;
  1.1373 +
  1.1374 +      if (first_free_arc == -1) {
  1.1375 +        n = arcs.size();
  1.1376 +        arcs.push_back(ArcT());
  1.1377 +        arcs.push_back(ArcT());
  1.1378 +      } else {
  1.1379 +        n = first_free_arc;
  1.1380 +        first_free_arc = arcs[n].next_out;
  1.1381 +      }
  1.1382 +
  1.1383 +      arcs[n].target = u.id;
  1.1384 +      arcs[n | 1].target = v.id;
  1.1385 +
  1.1386 +      arcs[n].next_out = nodes[v.id].first_out;
  1.1387 +      if (nodes[v.id].first_out != -1) {
  1.1388 +        arcs[nodes[v.id].first_out].prev_out = n;
  1.1389 +      }
  1.1390 +      arcs[n].prev_out = -1;
  1.1391 +      nodes[v.id].first_out = n;
  1.1392 +
  1.1393 +      arcs[n | 1].next_out = nodes[u.id].first_out;
  1.1394 +      if (nodes[u.id].first_out != -1) {
  1.1395 +        arcs[nodes[u.id].first_out].prev_out = (n | 1);
  1.1396 +      }
  1.1397 +      arcs[n | 1].prev_out = -1;
  1.1398 +      nodes[u.id].first_out = (n | 1);
  1.1399 +
  1.1400 +      return Edge(n / 2);
  1.1401 +    }
  1.1402 +
  1.1403 +    void erase(const Node& node) {
  1.1404 +      int n = node.id;
  1.1405 +
  1.1406 +      if(nodes[n].next != -1) {
  1.1407 +        nodes[nodes[n].next].prev = nodes[n].prev;
  1.1408 +      }
  1.1409 +
  1.1410 +      if(nodes[n].prev != -1) {
  1.1411 +        nodes[nodes[n].prev].next = nodes[n].next;
  1.1412 +      } else {
  1.1413 +        first_node = nodes[n].next;
  1.1414 +      }
  1.1415 +
  1.1416 +      if (nodes[n].partition_next != -1) {
  1.1417 +        nodes[nodes[n].partition_next].partition_prev = nodes[n].partition_prev;
  1.1418 +      }
  1.1419 +
  1.1420 +      if (nodes[n].partition_prev != -1) {
  1.1421 +        nodes[nodes[n].partition_prev].partition_next = nodes[n].partition_next;
  1.1422 +      } else {
  1.1423 +        if (nodes[n].red) {
  1.1424 +          first_red = nodes[n].partition_next;
  1.1425 +        } else {
  1.1426 +          first_blue = nodes[n].partition_next;
  1.1427 +        }
  1.1428 +      }
  1.1429 +
  1.1430 +      if (nodes[n].red) {
  1.1431 +        nodes[n].next = first_free_red;
  1.1432 +        first_free_red = n;
  1.1433 +      } else {
  1.1434 +        nodes[n].next = first_free_blue;
  1.1435 +        first_free_blue = n;
  1.1436 +      }
  1.1437 +      nodes[n].prev = -2;
  1.1438 +    }
  1.1439 +
  1.1440 +    void erase(const Edge& edge) {
  1.1441 +      int n = edge.id * 2;
  1.1442 +
  1.1443 +      if (arcs[n].next_out != -1) {
  1.1444 +        arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
  1.1445 +      }
  1.1446 +
  1.1447 +      if (arcs[n].prev_out != -1) {
  1.1448 +        arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
  1.1449 +      } else {
  1.1450 +        nodes[arcs[n | 1].target].first_out = arcs[n].next_out;
  1.1451 +      }
  1.1452 +
  1.1453 +      if (arcs[n | 1].next_out != -1) {
  1.1454 +        arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
  1.1455 +      }
  1.1456 +
  1.1457 +      if (arcs[n | 1].prev_out != -1) {
  1.1458 +        arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
  1.1459 +      } else {
  1.1460 +        nodes[arcs[n].target].first_out = arcs[n | 1].next_out;
  1.1461 +      }
  1.1462 +
  1.1463 +      arcs[n].next_out = first_free_arc;
  1.1464 +      first_free_arc = n;
  1.1465 +      arcs[n].prev_out = -2;
  1.1466 +      arcs[n | 1].prev_out = -2;
  1.1467 +
  1.1468 +    }
  1.1469 +
  1.1470 +    void clear() {
  1.1471 +      arcs.clear();
  1.1472 +      nodes.clear();
  1.1473 +      first_node = first_free_arc = first_red = first_blue =
  1.1474 +        max_red = max_blue = first_free_red = first_free_blue = -1;
  1.1475 +    }
  1.1476 +
  1.1477 +  protected:
  1.1478 +
  1.1479 +    void changeRed(Edge e, RedNode n) {
  1.1480 +      if(arcs[(2 * e.id) | 1].next_out != -1) {
  1.1481 +        arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
  1.1482 +          arcs[(2 * e.id) | 1].prev_out;
  1.1483 +      }
  1.1484 +      if(arcs[(2 * e.id) | 1].prev_out != -1) {
  1.1485 +        arcs[arcs[(2 * e.id) | 1].prev_out].next_out =
  1.1486 +          arcs[(2 * e.id) | 1].next_out;
  1.1487 +      } else {
  1.1488 +        nodes[arcs[2 * e.id].target].first_out =
  1.1489 +          arcs[(2 * e.id) | 1].next_out;
  1.1490 +      }
  1.1491 +
  1.1492 +      if (nodes[n.id].first_out != -1) {
  1.1493 +        arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
  1.1494 +      }
  1.1495 +      arcs[2 * e.id].target = n.id;
  1.1496 +      arcs[(2 * e.id) | 1].prev_out = -1;
  1.1497 +      arcs[(2 * e.id) | 1].next_out = nodes[n.id].first_out;
  1.1498 +      nodes[n.id].first_out = ((2 * e.id) | 1);
  1.1499 +    }
  1.1500 +
  1.1501 +    void changeBlue(Edge e, BlueNode n) {
  1.1502 +       if(arcs[2 * e.id].next_out != -1) {
  1.1503 +        arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
  1.1504 +      }
  1.1505 +      if(arcs[2 * e.id].prev_out != -1) {
  1.1506 +        arcs[arcs[2 * e.id].prev_out].next_out =
  1.1507 +          arcs[2 * e.id].next_out;
  1.1508 +      } else {
  1.1509 +        nodes[arcs[(2 * e.id) | 1].target].first_out =
  1.1510 +          arcs[2 * e.id].next_out;
  1.1511 +      }
  1.1512 +
  1.1513 +      if (nodes[n.id].first_out != -1) {
  1.1514 +        arcs[nodes[n.id].first_out].prev_out = 2 * e.id;
  1.1515 +      }
  1.1516 +      arcs[(2 * e.id) | 1].target = n.id;
  1.1517 +      arcs[2 * e.id].prev_out = -1;
  1.1518 +      arcs[2 * e.id].next_out = nodes[n.id].first_out;
  1.1519 +      nodes[n.id].first_out = 2 * e.id;
  1.1520 +    }
  1.1521 +
  1.1522 +  };
  1.1523 +
  1.1524 +  typedef BpGraphExtender<ListBpGraphBase> ExtendedListBpGraphBase;
  1.1525 +
  1.1526 +
  1.1527 +  /// \addtogroup graphs
  1.1528 +  /// @{
  1.1529 +
  1.1530 +  ///A general undirected graph structure.
  1.1531 +
  1.1532 +  ///\ref ListBpGraph is a versatile and fast undirected graph
  1.1533 +  ///implementation based on linked lists that are stored in
  1.1534 +  ///\c std::vector structures.
  1.1535 +  ///
  1.1536 +  ///This type fully conforms to the \ref concepts::BpGraph "BpGraph concept"
  1.1537 +  ///and it also provides several useful additional functionalities.
  1.1538 +  ///Most of its member functions and nested classes are documented
  1.1539 +  ///only in the concept class.
  1.1540 +  ///
  1.1541 +  ///This class provides only linear time counting for nodes, edges and arcs.
  1.1542 +  ///
  1.1543 +  ///\sa concepts::BpGraph
  1.1544 +  ///\sa ListDigraph
  1.1545 +  class ListBpGraph : public ExtendedListBpGraphBase {
  1.1546 +    typedef ExtendedListBpGraphBase Parent;
  1.1547 +
  1.1548 +  private:
  1.1549 +    /// BpGraphs are \e not copy constructible. Use BpGraphCopy instead.
  1.1550 +    ListBpGraph(const ListBpGraph &) :ExtendedListBpGraphBase()  {};
  1.1551 +    /// \brief Assignment of a graph to another one is \e not allowed.
  1.1552 +    /// Use BpGraphCopy instead.
  1.1553 +    void operator=(const ListBpGraph &) {}
  1.1554 +  public:
  1.1555 +    /// Constructor
  1.1556 +
  1.1557 +    /// Constructor.
  1.1558 +    ///
  1.1559 +    ListBpGraph() {}
  1.1560 +
  1.1561 +    typedef Parent::OutArcIt IncEdgeIt;
  1.1562 +
  1.1563 +    /// \brief Add a new red node to the graph.
  1.1564 +    ///
  1.1565 +    /// This function adds a red new node to the graph.
  1.1566 +    /// \return The new node.
  1.1567 +    RedNode addRedNode() { return Parent::addRedNode(); }
  1.1568 +
  1.1569 +    /// \brief Add a new blue node to the graph.
  1.1570 +    ///
  1.1571 +    /// This function adds a blue new node to the graph.
  1.1572 +    /// \return The new node.
  1.1573 +    BlueNode addBlueNode() { return Parent::addBlueNode(); }
  1.1574 +
  1.1575 +    /// \brief Add a new edge to the graph.
  1.1576 +    ///
  1.1577 +    /// This function adds a new edge to the graph between nodes
  1.1578 +    /// \c u and \c v with inherent orientation from node \c u to
  1.1579 +    /// node \c v.
  1.1580 +    /// \return The new edge.
  1.1581 +    Edge addEdge(RedNode u, BlueNode v) {
  1.1582 +      return Parent::addEdge(u, v);
  1.1583 +    }
  1.1584 +    Edge addEdge(BlueNode v, RedNode u) {
  1.1585 +      return Parent::addEdge(u, v);
  1.1586 +    }
  1.1587 +
  1.1588 +    ///\brief Erase a node from the graph.
  1.1589 +    ///
  1.1590 +    /// This function erases the given node along with its incident arcs
  1.1591 +    /// from the graph.
  1.1592 +    ///
  1.1593 +    /// \note All iterators referencing the removed node or the incident
  1.1594 +    /// edges are invalidated, of course.
  1.1595 +    void erase(Node n) { Parent::erase(n); }
  1.1596 +
  1.1597 +    ///\brief Erase an edge from the graph.
  1.1598 +    ///
  1.1599 +    /// This function erases the given edge from the graph.
  1.1600 +    ///
  1.1601 +    /// \note All iterators referencing the removed edge are invalidated,
  1.1602 +    /// of course.
  1.1603 +    void erase(Edge e) { Parent::erase(e); }
  1.1604 +    /// Node validity check
  1.1605 +
  1.1606 +    /// This function gives back \c true if the given node is valid,
  1.1607 +    /// i.e. it is a real node of the graph.
  1.1608 +    ///
  1.1609 +    /// \warning A removed node could become valid again if new nodes are
  1.1610 +    /// added to the graph.
  1.1611 +    bool valid(Node n) const { return Parent::valid(n); }
  1.1612 +    /// Edge validity check
  1.1613 +
  1.1614 +    /// This function gives back \c true if the given edge is valid,
  1.1615 +    /// i.e. it is a real edge of the graph.
  1.1616 +    ///
  1.1617 +    /// \warning A removed edge could become valid again if new edges are
  1.1618 +    /// added to the graph.
  1.1619 +    bool valid(Edge e) const { return Parent::valid(e); }
  1.1620 +    /// Arc validity check
  1.1621 +
  1.1622 +    /// This function gives back \c true if the given arc is valid,
  1.1623 +    /// i.e. it is a real arc of the graph.
  1.1624 +    ///
  1.1625 +    /// \warning A removed arc could become valid again if new edges are
  1.1626 +    /// added to the graph.
  1.1627 +    bool valid(Arc a) const { return Parent::valid(a); }
  1.1628 +
  1.1629 +    /// \brief Change the red node of an edge.
  1.1630 +    ///
  1.1631 +    /// This function changes the red node of the given edge \c e to \c n.
  1.1632 +    ///
  1.1633 +    ///\note \c EdgeIt and \c ArcIt iterators referencing the
  1.1634 +    ///changed edge are invalidated and all other iterators whose
  1.1635 +    ///base node is the changed node are also invalidated.
  1.1636 +    ///
  1.1637 +    ///\warning This functionality cannot be used together with the
  1.1638 +    ///Snapshot feature.
  1.1639 +    void changeRed(Edge e, RedNode n) {
  1.1640 +      Parent::changeRed(e, n);
  1.1641 +    }
  1.1642 +    /// \brief Change the blue node of an edge.
  1.1643 +    ///
  1.1644 +    /// This function changes the blue node of the given edge \c e to \c n.
  1.1645 +    ///
  1.1646 +    ///\note \c EdgeIt iterators referencing the changed edge remain
  1.1647 +    ///valid, but \c ArcIt iterators referencing the changed edge and
  1.1648 +    ///all other iterators whose base node is the changed node are also
  1.1649 +    ///invalidated.
  1.1650 +    ///
  1.1651 +    ///\warning This functionality cannot be used together with the
  1.1652 +    ///Snapshot feature.
  1.1653 +    void changeBlue(Edge e, BlueNode n) {
  1.1654 +      Parent::changeBlue(e, n);
  1.1655 +    }
  1.1656 +
  1.1657 +    ///Clear the graph.
  1.1658 +
  1.1659 +    ///This function erases all nodes and arcs from the graph.
  1.1660 +    ///
  1.1661 +    ///\note All iterators of the graph are invalidated, of course.
  1.1662 +    void clear() {
  1.1663 +      Parent::clear();
  1.1664 +    }
  1.1665 +
  1.1666 +    /// Reserve memory for nodes.
  1.1667 +
  1.1668 +    /// Using this function, it is possible to avoid superfluous memory
  1.1669 +    /// allocation: if you know that the graph you want to build will
  1.1670 +    /// be large (e.g. it will contain millions of nodes and/or edges),
  1.1671 +    /// then it is worth reserving space for this amount before starting
  1.1672 +    /// to build the graph.
  1.1673 +    /// \sa reserveEdge()
  1.1674 +    void reserveNode(int n) { nodes.reserve(n); };
  1.1675 +
  1.1676 +    /// Reserve memory for edges.
  1.1677 +
  1.1678 +    /// Using this function, it is possible to avoid superfluous memory
  1.1679 +    /// allocation: if you know that the graph you want to build will
  1.1680 +    /// be large (e.g. it will contain millions of nodes and/or edges),
  1.1681 +    /// then it is worth reserving space for this amount before starting
  1.1682 +    /// to build the graph.
  1.1683 +    /// \sa reserveNode()
  1.1684 +    void reserveEdge(int m) { arcs.reserve(2 * m); };
  1.1685 +
  1.1686 +    /// \brief Class to make a snapshot of the graph and restore
  1.1687 +    /// it later.
  1.1688 +    ///
  1.1689 +    /// Class to make a snapshot of the graph and restore it later.
  1.1690 +    ///
  1.1691 +    /// The newly added nodes and edges can be removed
  1.1692 +    /// using the restore() function.
  1.1693 +    ///
  1.1694 +    /// \note After a state is restored, you cannot restore a later state,
  1.1695 +    /// i.e. you cannot add the removed nodes and edges again using
  1.1696 +    /// another Snapshot instance.
  1.1697 +    ///
  1.1698 +    /// \warning Node and edge deletions and other modifications
  1.1699 +    /// (e.g. changing the end-nodes of edges or contracting nodes)
  1.1700 +    /// cannot be restored. These events invalidate the snapshot.
  1.1701 +    /// However, the edges and nodes that were added to the graph after
  1.1702 +    /// making the current snapshot can be removed without invalidating it.
  1.1703 +    class Snapshot {
  1.1704 +    protected:
  1.1705 +
  1.1706 +      typedef Parent::NodeNotifier NodeNotifier;
  1.1707 +
  1.1708 +      class NodeObserverProxy : public NodeNotifier::ObserverBase {
  1.1709 +      public:
  1.1710 +
  1.1711 +        NodeObserverProxy(Snapshot& _snapshot)
  1.1712 +          : snapshot(_snapshot) {}
  1.1713 +
  1.1714 +        using NodeNotifier::ObserverBase::attach;
  1.1715 +        using NodeNotifier::ObserverBase::detach;
  1.1716 +        using NodeNotifier::ObserverBase::attached;
  1.1717 +
  1.1718 +      protected:
  1.1719 +
  1.1720 +        virtual void add(const Node& node) {
  1.1721 +          snapshot.addNode(node);
  1.1722 +        }
  1.1723 +        virtual void add(const std::vector<Node>& nodes) {
  1.1724            for (int i = nodes.size() - 1; i >= 0; ++i) {
  1.1725              snapshot.addNode(nodes[i]);
  1.1726            }
  1.1727 @@ -616,818 +2333,6 @@
  1.1728          Snapshot& snapshot;
  1.1729        };
  1.1730  
  1.1731 -      class ArcObserverProxy : public ArcNotifier::ObserverBase {
  1.1732 -      public:
  1.1733 -
  1.1734 -        ArcObserverProxy(Snapshot& _snapshot)
  1.1735 -          : snapshot(_snapshot) {}
  1.1736 -
  1.1737 -        using ArcNotifier::ObserverBase::attach;
  1.1738 -        using ArcNotifier::ObserverBase::detach;
  1.1739 -        using ArcNotifier::ObserverBase::attached;
  1.1740 -
  1.1741 -      protected:
  1.1742 -
  1.1743 -        virtual void add(const Arc& arc) {
  1.1744 -          snapshot.addArc(arc);
  1.1745 -        }
  1.1746 -        virtual void add(const std::vector<Arc>& arcs) {
  1.1747 -          for (int i = arcs.size() - 1; i >= 0; ++i) {
  1.1748 -            snapshot.addArc(arcs[i]);
  1.1749 -          }
  1.1750 -        }
  1.1751 -        virtual void erase(const Arc& arc) {
  1.1752 -          snapshot.eraseArc(arc);
  1.1753 -        }
  1.1754 -        virtual void erase(const std::vector<Arc>& arcs) {
  1.1755 -          for (int i = 0; i < int(arcs.size()); ++i) {
  1.1756 -            snapshot.eraseArc(arcs[i]);
  1.1757 -          }
  1.1758 -        }
  1.1759 -        virtual void build() {
  1.1760 -          Arc arc;
  1.1761 -          std::vector<Arc> arcs;
  1.1762 -          for (notifier()->first(arc); arc != INVALID;
  1.1763 -               notifier()->next(arc)) {
  1.1764 -            arcs.push_back(arc);
  1.1765 -          }
  1.1766 -          for (int i = arcs.size() - 1; i >= 0; --i) {
  1.1767 -            snapshot.addArc(arcs[i]);
  1.1768 -          }
  1.1769 -        }
  1.1770 -        virtual void clear() {
  1.1771 -          Arc arc;
  1.1772 -          for (notifier()->first(arc); arc != INVALID;
  1.1773 -               notifier()->next(arc)) {
  1.1774 -            snapshot.eraseArc(arc);
  1.1775 -          }
  1.1776 -        }
  1.1777 -
  1.1778 -        Snapshot& snapshot;
  1.1779 -      };
  1.1780 -
  1.1781 -      ListDigraph *digraph;
  1.1782 -
  1.1783 -      NodeObserverProxy node_observer_proxy;
  1.1784 -      ArcObserverProxy arc_observer_proxy;
  1.1785 -
  1.1786 -      std::list<Node> added_nodes;
  1.1787 -      std::list<Arc> added_arcs;
  1.1788 -
  1.1789 -
  1.1790 -      void addNode(const Node& node) {
  1.1791 -        added_nodes.push_front(node);
  1.1792 -      }
  1.1793 -      void eraseNode(const Node& node) {
  1.1794 -        std::list<Node>::iterator it =
  1.1795 -          std::find(added_nodes.begin(), added_nodes.end(), node);
  1.1796 -        if (it == added_nodes.end()) {
  1.1797 -          clear();
  1.1798 -          arc_observer_proxy.detach();
  1.1799 -          throw NodeNotifier::ImmediateDetach();
  1.1800 -        } else {
  1.1801 -          added_nodes.erase(it);
  1.1802 -        }
  1.1803 -      }
  1.1804 -
  1.1805 -      void addArc(const Arc& arc) {
  1.1806 -        added_arcs.push_front(arc);
  1.1807 -      }
  1.1808 -      void eraseArc(const Arc& arc) {
  1.1809 -        std::list<Arc>::iterator it =
  1.1810 -          std::find(added_arcs.begin(), added_arcs.end(), arc);
  1.1811 -        if (it == added_arcs.end()) {
  1.1812 -          clear();
  1.1813 -          node_observer_proxy.detach();
  1.1814 -          throw ArcNotifier::ImmediateDetach();
  1.1815 -        } else {
  1.1816 -          added_arcs.erase(it);
  1.1817 -        }
  1.1818 -      }
  1.1819 -
  1.1820 -      void attach(ListDigraph &_digraph) {
  1.1821 -        digraph = &_digraph;
  1.1822 -        node_observer_proxy.attach(digraph->notifier(Node()));
  1.1823 -        arc_observer_proxy.attach(digraph->notifier(Arc()));
  1.1824 -      }
  1.1825 -
  1.1826 -      void detach() {
  1.1827 -        node_observer_proxy.detach();
  1.1828 -        arc_observer_proxy.detach();
  1.1829 -      }
  1.1830 -
  1.1831 -      bool attached() const {
  1.1832 -        return node_observer_proxy.attached();
  1.1833 -      }
  1.1834 -
  1.1835 -      void clear() {
  1.1836 -        added_nodes.clear();
  1.1837 -        added_arcs.clear();
  1.1838 -      }
  1.1839 -
  1.1840 -    public:
  1.1841 -
  1.1842 -      /// \brief Default constructor.
  1.1843 -      ///
  1.1844 -      /// Default constructor.
  1.1845 -      /// You have to call save() to actually make a snapshot.
  1.1846 -      Snapshot()
  1.1847 -        : digraph(0), node_observer_proxy(*this),
  1.1848 -          arc_observer_proxy(*this) {}
  1.1849 -
  1.1850 -      /// \brief Constructor that immediately makes a snapshot.
  1.1851 -      ///
  1.1852 -      /// This constructor immediately makes a snapshot of the given digraph.
  1.1853 -      Snapshot(ListDigraph &gr)
  1.1854 -        : node_observer_proxy(*this),
  1.1855 -          arc_observer_proxy(*this) {
  1.1856 -        attach(gr);
  1.1857 -      }
  1.1858 -
  1.1859 -      /// \brief Make a snapshot.
  1.1860 -      ///
  1.1861 -      /// This function makes a snapshot of the given digraph.
  1.1862 -      /// It can be called more than once. In case of a repeated
  1.1863 -      /// call, the previous snapshot gets lost.
  1.1864 -      void save(ListDigraph &gr) {
  1.1865 -        if (attached()) {
  1.1866 -          detach();
  1.1867 -          clear();
  1.1868 -        }
  1.1869 -        attach(gr);
  1.1870 -      }
  1.1871 -
  1.1872 -      /// \brief Undo the changes until the last snapshot.
  1.1873 -      ///
  1.1874 -      /// This function undos the changes until the last snapshot
  1.1875 -      /// created by save() or Snapshot(ListDigraph&).
  1.1876 -      ///
  1.1877 -      /// \warning This method invalidates the snapshot, i.e. repeated
  1.1878 -      /// restoring is not supported unless you call save() again.
  1.1879 -      void restore() {
  1.1880 -        detach();
  1.1881 -        for(std::list<Arc>::iterator it = added_arcs.begin();
  1.1882 -            it != added_arcs.end(); ++it) {
  1.1883 -          digraph->erase(*it);
  1.1884 -        }
  1.1885 -        for(std::list<Node>::iterator it = added_nodes.begin();
  1.1886 -            it != added_nodes.end(); ++it) {
  1.1887 -          digraph->erase(*it);
  1.1888 -        }
  1.1889 -        clear();
  1.1890 -      }
  1.1891 -
  1.1892 -      /// \brief Returns \c true if the snapshot is valid.
  1.1893 -      ///
  1.1894 -      /// This function returns \c true if the snapshot is valid.
  1.1895 -      bool valid() const {
  1.1896 -        return attached();
  1.1897 -      }
  1.1898 -    };
  1.1899 -
  1.1900 -  };
  1.1901 -
  1.1902 -  ///@}
  1.1903 -
  1.1904 -  class ListGraphBase {
  1.1905 -
  1.1906 -  protected:
  1.1907 -
  1.1908 -    struct NodeT {
  1.1909 -      int first_out;
  1.1910 -      int prev, next;
  1.1911 -    };
  1.1912 -
  1.1913 -    struct ArcT {
  1.1914 -      int target;
  1.1915 -      int prev_out, next_out;
  1.1916 -    };
  1.1917 -
  1.1918 -    std::vector<NodeT> nodes;
  1.1919 -
  1.1920 -    int first_node;
  1.1921 -
  1.1922 -    int first_free_node;
  1.1923 -
  1.1924 -    std::vector<ArcT> arcs;
  1.1925 -
  1.1926 -    int first_free_arc;
  1.1927 -
  1.1928 -  public:
  1.1929 -
  1.1930 -    typedef ListGraphBase Graph;
  1.1931 -
  1.1932 -    class Node {
  1.1933 -      friend class ListGraphBase;
  1.1934 -    protected:
  1.1935 -
  1.1936 -      int id;
  1.1937 -      explicit Node(int pid) { id = pid;}
  1.1938 -
  1.1939 -    public:
  1.1940 -      Node() {}
  1.1941 -      Node (Invalid) { id = -1; }
  1.1942 -      bool operator==(const Node& node) const {return id == node.id;}
  1.1943 -      bool operator!=(const Node& node) const {return id != node.id;}
  1.1944 -      bool operator<(const Node& node) const {return id < node.id;}
  1.1945 -    };
  1.1946 -
  1.1947 -    class Edge {
  1.1948 -      friend class ListGraphBase;
  1.1949 -    protected:
  1.1950 -
  1.1951 -      int id;
  1.1952 -      explicit Edge(int pid) { id = pid;}
  1.1953 -
  1.1954 -    public:
  1.1955 -      Edge() {}
  1.1956 -      Edge (Invalid) { id = -1; }
  1.1957 -      bool operator==(const Edge& edge) const {return id == edge.id;}
  1.1958 -      bool operator!=(const Edge& edge) const {return id != edge.id;}
  1.1959 -      bool operator<(const Edge& edge) const {return id < edge.id;}
  1.1960 -    };
  1.1961 -
  1.1962 -    class Arc {
  1.1963 -      friend class ListGraphBase;
  1.1964 -    protected:
  1.1965 -
  1.1966 -      int id;
  1.1967 -      explicit Arc(int pid) { id = pid;}
  1.1968 -
  1.1969 -    public:
  1.1970 -      operator Edge() const {
  1.1971 -        return id != -1 ? edgeFromId(id / 2) : INVALID;
  1.1972 -      }
  1.1973 -
  1.1974 -      Arc() {}
  1.1975 -      Arc (Invalid) { id = -1; }
  1.1976 -      bool operator==(const Arc& arc) const {return id == arc.id;}
  1.1977 -      bool operator!=(const Arc& arc) const {return id != arc.id;}
  1.1978 -      bool operator<(const Arc& arc) const {return id < arc.id;}
  1.1979 -    };
  1.1980 -
  1.1981 -    ListGraphBase()
  1.1982 -      : nodes(), first_node(-1),
  1.1983 -        first_free_node(-1), arcs(), first_free_arc(-1) {}
  1.1984 -
  1.1985 -
  1.1986 -    int maxNodeId() const { return nodes.size()-1; }
  1.1987 -    int maxEdgeId() const { return arcs.size() / 2 - 1; }
  1.1988 -    int maxArcId() const { return arcs.size()-1; }
  1.1989 -
  1.1990 -    Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); }
  1.1991 -    Node target(Arc e) const { return Node(arcs[e.id].target); }
  1.1992 -
  1.1993 -    Node u(Edge e) const { return Node(arcs[2 * e.id].target); }
  1.1994 -    Node v(Edge e) const { return Node(arcs[2 * e.id + 1].target); }
  1.1995 -
  1.1996 -    static bool direction(Arc e) {
  1.1997 -      return (e.id & 1) == 1;
  1.1998 -    }
  1.1999 -
  1.2000 -    static Arc direct(Edge e, bool d) {
  1.2001 -      return Arc(e.id * 2 + (d ? 1 : 0));
  1.2002 -    }
  1.2003 -
  1.2004 -    void first(Node& node) const {
  1.2005 -      node.id = first_node;
  1.2006 -    }
  1.2007 -
  1.2008 -    void next(Node& node) const {
  1.2009 -      node.id = nodes[node.id].next;
  1.2010 -    }
  1.2011 -
  1.2012 -    void first(Arc& e) const {
  1.2013 -      int n = first_node;
  1.2014 -      while (n != -1 && nodes[n].first_out == -1) {
  1.2015 -        n = nodes[n].next;
  1.2016 -      }
  1.2017 -      e.id = (n == -1) ? -1 : nodes[n].first_out;
  1.2018 -    }
  1.2019 -
  1.2020 -    void next(Arc& e) const {
  1.2021 -      if (arcs[e.id].next_out != -1) {
  1.2022 -        e.id = arcs[e.id].next_out;
  1.2023 -      } else {
  1.2024 -        int n = nodes[arcs[e.id ^ 1].target].next;
  1.2025 -        while(n != -1 && nodes[n].first_out == -1) {
  1.2026 -          n = nodes[n].next;
  1.2027 -        }
  1.2028 -        e.id = (n == -1) ? -1 : nodes[n].first_out;
  1.2029 -      }
  1.2030 -    }
  1.2031 -
  1.2032 -    void first(Edge& e) const {
  1.2033 -      int n = first_node;
  1.2034 -      while (n != -1) {
  1.2035 -        e.id = nodes[n].first_out;
  1.2036 -        while ((e.id & 1) != 1) {
  1.2037 -          e.id = arcs[e.id].next_out;
  1.2038 -        }
  1.2039 -        if (e.id != -1) {
  1.2040 -          e.id /= 2;
  1.2041 -          return;
  1.2042 -        }
  1.2043 -        n = nodes[n].next;
  1.2044 -      }
  1.2045 -      e.id = -1;
  1.2046 -    }
  1.2047 -
  1.2048 -    void next(Edge& e) const {
  1.2049 -      int n = arcs[e.id * 2].target;
  1.2050 -      e.id = arcs[(e.id * 2) | 1].next_out;
  1.2051 -      while ((e.id & 1) != 1) {
  1.2052 -        e.id = arcs[e.id].next_out;
  1.2053 -      }
  1.2054 -      if (e.id != -1) {
  1.2055 -        e.id /= 2;
  1.2056 -        return;
  1.2057 -      }
  1.2058 -      n = nodes[n].next;
  1.2059 -      while (n != -1) {
  1.2060 -        e.id = nodes[n].first_out;
  1.2061 -        while ((e.id & 1) != 1) {
  1.2062 -          e.id = arcs[e.id].next_out;
  1.2063 -        }
  1.2064 -        if (e.id != -1) {
  1.2065 -          e.id /= 2;
  1.2066 -          return;
  1.2067 -        }
  1.2068 -        n = nodes[n].next;
  1.2069 -      }
  1.2070 -      e.id = -1;
  1.2071 -    }
  1.2072 -
  1.2073 -    void firstOut(Arc &e, const Node& v) const {
  1.2074 -      e.id = nodes[v.id].first_out;
  1.2075 -    }
  1.2076 -    void nextOut(Arc &e) const {
  1.2077 -      e.id = arcs[e.id].next_out;
  1.2078 -    }
  1.2079 -
  1.2080 -    void firstIn(Arc &e, const Node& v) const {
  1.2081 -      e.id = ((nodes[v.id].first_out) ^ 1);
  1.2082 -      if (e.id == -2) e.id = -1;
  1.2083 -    }
  1.2084 -    void nextIn(Arc &e) const {
  1.2085 -      e.id = ((arcs[e.id ^ 1].next_out) ^ 1);
  1.2086 -      if (e.id == -2) e.id = -1;
  1.2087 -    }
  1.2088 -
  1.2089 -    void firstInc(Edge &e, bool& d, const Node& v) const {
  1.2090 -      int a = nodes[v.id].first_out;
  1.2091 -      if (a != -1 ) {
  1.2092 -        e.id = a / 2;
  1.2093 -        d = ((a & 1) == 1);
  1.2094 -      } else {
  1.2095 -        e.id = -1;
  1.2096 -        d = true;
  1.2097 -      }
  1.2098 -    }
  1.2099 -    void nextInc(Edge &e, bool& d) const {
  1.2100 -      int a = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
  1.2101 -      if (a != -1 ) {
  1.2102 -        e.id = a / 2;
  1.2103 -        d = ((a & 1) == 1);
  1.2104 -      } else {
  1.2105 -        e.id = -1;
  1.2106 -        d = true;
  1.2107 -      }
  1.2108 -    }
  1.2109 -
  1.2110 -    static int id(Node v) { return v.id; }
  1.2111 -    static int id(Arc e) { return e.id; }
  1.2112 -    static int id(Edge e) { return e.id; }
  1.2113 -
  1.2114 -    static Node nodeFromId(int id) { return Node(id);}
  1.2115 -    static Arc arcFromId(int id) { return Arc(id);}
  1.2116 -    static Edge edgeFromId(int id) { return Edge(id);}
  1.2117 -
  1.2118 -    bool valid(Node n) const {
  1.2119 -      return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
  1.2120 -        nodes[n.id].prev != -2;
  1.2121 -    }
  1.2122 -
  1.2123 -    bool valid(Arc a) const {
  1.2124 -      return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
  1.2125 -        arcs[a.id].prev_out != -2;
  1.2126 -    }
  1.2127 -
  1.2128 -    bool valid(Edge e) const {
  1.2129 -      return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) &&
  1.2130 -        arcs[2 * e.id].prev_out != -2;
  1.2131 -    }
  1.2132 -
  1.2133 -    Node addNode() {
  1.2134 -      int n;
  1.2135 -
  1.2136 -      if(first_free_node==-1) {
  1.2137 -        n = nodes.size();
  1.2138 -        nodes.push_back(NodeT());
  1.2139 -      } else {
  1.2140 -        n = first_free_node;
  1.2141 -        first_free_node = nodes[n].next;
  1.2142 -      }
  1.2143 -
  1.2144 -      nodes[n].next = first_node;
  1.2145 -      if (first_node != -1) nodes[first_node].prev = n;
  1.2146 -      first_node = n;
  1.2147 -      nodes[n].prev = -1;
  1.2148 -
  1.2149 -      nodes[n].first_out = -1;
  1.2150 -
  1.2151 -      return Node(n);
  1.2152 -    }
  1.2153 -
  1.2154 -    Edge addEdge(Node u, Node v) {
  1.2155 -      int n;
  1.2156 -
  1.2157 -      if (first_free_arc == -1) {
  1.2158 -        n = arcs.size();
  1.2159 -        arcs.push_back(ArcT());
  1.2160 -        arcs.push_back(ArcT());
  1.2161 -      } else {
  1.2162 -        n = first_free_arc;
  1.2163 -        first_free_arc = arcs[n].next_out;
  1.2164 -      }
  1.2165 -
  1.2166 -      arcs[n].target = u.id;
  1.2167 -      arcs[n | 1].target = v.id;
  1.2168 -
  1.2169 -      arcs[n].next_out = nodes[v.id].first_out;
  1.2170 -      if (nodes[v.id].first_out != -1) {
  1.2171 -        arcs[nodes[v.id].first_out].prev_out = n;
  1.2172 -      }
  1.2173 -      arcs[n].prev_out = -1;
  1.2174 -      nodes[v.id].first_out = n;
  1.2175 -
  1.2176 -      arcs[n | 1].next_out = nodes[u.id].first_out;
  1.2177 -      if (nodes[u.id].first_out != -1) {
  1.2178 -        arcs[nodes[u.id].first_out].prev_out = (n | 1);
  1.2179 -      }
  1.2180 -      arcs[n | 1].prev_out = -1;
  1.2181 -      nodes[u.id].first_out = (n | 1);
  1.2182 -
  1.2183 -      return Edge(n / 2);
  1.2184 -    }
  1.2185 -
  1.2186 -    void erase(const Node& node) {
  1.2187 -      int n = node.id;
  1.2188 -
  1.2189 -      if(nodes[n].next != -1) {
  1.2190 -        nodes[nodes[n].next].prev = nodes[n].prev;
  1.2191 -      }
  1.2192 -
  1.2193 -      if(nodes[n].prev != -1) {
  1.2194 -        nodes[nodes[n].prev].next = nodes[n].next;
  1.2195 -      } else {
  1.2196 -        first_node = nodes[n].next;
  1.2197 -      }
  1.2198 -
  1.2199 -      nodes[n].next = first_free_node;
  1.2200 -      first_free_node = n;
  1.2201 -      nodes[n].prev = -2;
  1.2202 -    }
  1.2203 -
  1.2204 -    void erase(const Edge& edge) {
  1.2205 -      int n = edge.id * 2;
  1.2206 -
  1.2207 -      if (arcs[n].next_out != -1) {
  1.2208 -        arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
  1.2209 -      }
  1.2210 -
  1.2211 -      if (arcs[n].prev_out != -1) {
  1.2212 -        arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
  1.2213 -      } else {
  1.2214 -        nodes[arcs[n | 1].target].first_out = arcs[n].next_out;
  1.2215 -      }
  1.2216 -
  1.2217 -      if (arcs[n | 1].next_out != -1) {
  1.2218 -        arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
  1.2219 -      }
  1.2220 -
  1.2221 -      if (arcs[n | 1].prev_out != -1) {
  1.2222 -        arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
  1.2223 -      } else {
  1.2224 -        nodes[arcs[n].target].first_out = arcs[n | 1].next_out;
  1.2225 -      }
  1.2226 -
  1.2227 -      arcs[n].next_out = first_free_arc;
  1.2228 -      first_free_arc = n;
  1.2229 -      arcs[n].prev_out = -2;
  1.2230 -      arcs[n | 1].prev_out = -2;
  1.2231 -
  1.2232 -    }
  1.2233 -
  1.2234 -    void clear() {
  1.2235 -      arcs.clear();
  1.2236 -      nodes.clear();
  1.2237 -      first_node = first_free_node = first_free_arc = -1;
  1.2238 -    }
  1.2239 -
  1.2240 -  protected:
  1.2241 -
  1.2242 -    void changeV(Edge e, Node n) {
  1.2243 -      if(arcs[2 * e.id].next_out != -1) {
  1.2244 -        arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
  1.2245 -      }
  1.2246 -      if(arcs[2 * e.id].prev_out != -1) {
  1.2247 -        arcs[arcs[2 * e.id].prev_out].next_out =
  1.2248 -          arcs[2 * e.id].next_out;
  1.2249 -      } else {
  1.2250 -        nodes[arcs[(2 * e.id) | 1].target].first_out =
  1.2251 -          arcs[2 * e.id].next_out;
  1.2252 -      }
  1.2253 -
  1.2254 -      if (nodes[n.id].first_out != -1) {
  1.2255 -        arcs[nodes[n.id].first_out].prev_out = 2 * e.id;
  1.2256 -      }
  1.2257 -      arcs[(2 * e.id) | 1].target = n.id;
  1.2258 -      arcs[2 * e.id].prev_out = -1;
  1.2259 -      arcs[2 * e.id].next_out = nodes[n.id].first_out;
  1.2260 -      nodes[n.id].first_out = 2 * e.id;
  1.2261 -    }
  1.2262 -
  1.2263 -    void changeU(Edge e, Node n) {
  1.2264 -      if(arcs[(2 * e.id) | 1].next_out != -1) {
  1.2265 -        arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
  1.2266 -          arcs[(2 * e.id) | 1].prev_out;
  1.2267 -      }
  1.2268 -      if(arcs[(2 * e.id) | 1].prev_out != -1) {
  1.2269 -        arcs[arcs[(2 * e.id) | 1].prev_out].next_out =
  1.2270 -          arcs[(2 * e.id) | 1].next_out;
  1.2271 -      } else {
  1.2272 -        nodes[arcs[2 * e.id].target].first_out =
  1.2273 -          arcs[(2 * e.id) | 1].next_out;
  1.2274 -      }
  1.2275 -
  1.2276 -      if (nodes[n.id].first_out != -1) {
  1.2277 -        arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
  1.2278 -      }
  1.2279 -      arcs[2 * e.id].target = n.id;
  1.2280 -      arcs[(2 * e.id) | 1].prev_out = -1;
  1.2281 -      arcs[(2 * e.id) | 1].next_out = nodes[n.id].first_out;
  1.2282 -      nodes[n.id].first_out = ((2 * e.id) | 1);
  1.2283 -    }
  1.2284 -
  1.2285 -  };
  1.2286 -
  1.2287 -  typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
  1.2288 -
  1.2289 -
  1.2290 -  /// \addtogroup graphs
  1.2291 -  /// @{
  1.2292 -
  1.2293 -  ///A general undirected graph structure.
  1.2294 -
  1.2295 -  ///\ref ListGraph is a versatile and fast undirected graph
  1.2296 -  ///implementation based on linked lists that are stored in
  1.2297 -  ///\c std::vector structures.
  1.2298 -  ///
  1.2299 -  ///This type fully conforms to the \ref concepts::Graph "Graph concept"
  1.2300 -  ///and it also provides several useful additional functionalities.
  1.2301 -  ///Most of its member functions and nested classes are documented
  1.2302 -  ///only in the concept class.
  1.2303 -  ///
  1.2304 -  ///This class provides only linear time counting for nodes, edges and arcs.
  1.2305 -  ///
  1.2306 -  ///\sa concepts::Graph
  1.2307 -  ///\sa ListDigraph
  1.2308 -  class ListGraph : public ExtendedListGraphBase {
  1.2309 -    typedef ExtendedListGraphBase Parent;
  1.2310 -
  1.2311 -  private:
  1.2312 -    /// Graphs are \e not copy constructible. Use GraphCopy instead.
  1.2313 -    ListGraph(const ListGraph &) :ExtendedListGraphBase()  {};
  1.2314 -    /// \brief Assignment of a graph to another one is \e not allowed.
  1.2315 -    /// Use GraphCopy instead.
  1.2316 -    void operator=(const ListGraph &) {}
  1.2317 -  public:
  1.2318 -    /// Constructor
  1.2319 -
  1.2320 -    /// Constructor.
  1.2321 -    ///
  1.2322 -    ListGraph() {}
  1.2323 -
  1.2324 -    typedef Parent::OutArcIt IncEdgeIt;
  1.2325 -
  1.2326 -    /// \brief Add a new node to the graph.
  1.2327 -    ///
  1.2328 -    /// This function adds a new node to the graph.
  1.2329 -    /// \return The new node.
  1.2330 -    Node addNode() { return Parent::addNode(); }
  1.2331 -
  1.2332 -    /// \brief Add a new edge to the graph.
  1.2333 -    ///
  1.2334 -    /// This function adds a new edge to the graph between nodes
  1.2335 -    /// \c u and \c v with inherent orientation from node \c u to
  1.2336 -    /// node \c v.
  1.2337 -    /// \return The new edge.
  1.2338 -    Edge addEdge(Node u, Node v) {
  1.2339 -      return Parent::addEdge(u, v);
  1.2340 -    }
  1.2341 -
  1.2342 -    ///\brief Erase a node from the graph.
  1.2343 -    ///
  1.2344 -    /// This function erases the given node along with its incident arcs
  1.2345 -    /// from the graph.
  1.2346 -    ///
  1.2347 -    /// \note All iterators referencing the removed node or the incident
  1.2348 -    /// edges are invalidated, of course.
  1.2349 -    void erase(Node n) { Parent::erase(n); }
  1.2350 -
  1.2351 -    ///\brief Erase an edge from the graph.
  1.2352 -    ///
  1.2353 -    /// This function erases the given edge from the graph.
  1.2354 -    ///
  1.2355 -    /// \note All iterators referencing the removed edge are invalidated,
  1.2356 -    /// of course.
  1.2357 -    void erase(Edge e) { Parent::erase(e); }
  1.2358 -    /// Node validity check
  1.2359 -
  1.2360 -    /// This function gives back \c true if the given node is valid,
  1.2361 -    /// i.e. it is a real node of the graph.
  1.2362 -    ///
  1.2363 -    /// \warning A removed node could become valid again if new nodes are
  1.2364 -    /// added to the graph.
  1.2365 -    bool valid(Node n) const { return Parent::valid(n); }
  1.2366 -    /// Edge validity check
  1.2367 -
  1.2368 -    /// This function gives back \c true if the given edge is valid,
  1.2369 -    /// i.e. it is a real edge of the graph.
  1.2370 -    ///
  1.2371 -    /// \warning A removed edge could become valid again if new edges are
  1.2372 -    /// added to the graph.
  1.2373 -    bool valid(Edge e) const { return Parent::valid(e); }
  1.2374 -    /// Arc validity check
  1.2375 -
  1.2376 -    /// This function gives back \c true if the given arc is valid,
  1.2377 -    /// i.e. it is a real arc of the graph.
  1.2378 -    ///
  1.2379 -    /// \warning A removed arc could become valid again if new edges are
  1.2380 -    /// added to the graph.
  1.2381 -    bool valid(Arc a) const { return Parent::valid(a); }
  1.2382 -
  1.2383 -    /// \brief Change the first node of an edge.
  1.2384 -    ///
  1.2385 -    /// This function changes the first node of the given edge \c e to \c n.
  1.2386 -    ///
  1.2387 -    ///\note \c EdgeIt and \c ArcIt iterators referencing the
  1.2388 -    ///changed edge are invalidated and all other iterators whose
  1.2389 -    ///base node is the changed node are also invalidated.
  1.2390 -    ///
  1.2391 -    ///\warning This functionality cannot be used together with the
  1.2392 -    ///Snapshot feature.
  1.2393 -    void changeU(Edge e, Node n) {
  1.2394 -      Parent::changeU(e,n);
  1.2395 -    }
  1.2396 -    /// \brief Change the second node of an edge.
  1.2397 -    ///
  1.2398 -    /// This function changes the second node of the given edge \c e to \c n.
  1.2399 -    ///
  1.2400 -    ///\note \c EdgeIt iterators referencing the changed edge remain
  1.2401 -    ///valid, but \c ArcIt iterators referencing the changed edge and
  1.2402 -    ///all other iterators whose base node is the changed node are also
  1.2403 -    ///invalidated.
  1.2404 -    ///
  1.2405 -    ///\warning This functionality cannot be used together with the
  1.2406 -    ///Snapshot feature.
  1.2407 -    void changeV(Edge e, Node n) {
  1.2408 -      Parent::changeV(e,n);
  1.2409 -    }
  1.2410 -
  1.2411 -    /// \brief Contract two nodes.
  1.2412 -    ///
  1.2413 -    /// This function contracts the given two nodes.
  1.2414 -    /// Node \c b is removed, but instead of deleting
  1.2415 -    /// its incident edges, they are joined to node \c a.
  1.2416 -    /// If the last parameter \c r is \c true (this is the default value),
  1.2417 -    /// then the newly created loops are removed.
  1.2418 -    ///
  1.2419 -    /// \note The moved edges are joined to node \c a using changeU()
  1.2420 -    /// or changeV(), thus all edge and arc iterators whose base node is
  1.2421 -    /// \c b are invalidated.
  1.2422 -    /// Moreover all iterators referencing node \c b or the removed
  1.2423 -    /// loops are also invalidated. Other iterators remain valid.
  1.2424 -    ///
  1.2425 -    ///\warning This functionality cannot be used together with the
  1.2426 -    ///Snapshot feature.
  1.2427 -    void contract(Node a, Node b, bool r = true) {
  1.2428 -      for(IncEdgeIt e(*this, b); e!=INVALID;) {
  1.2429 -        IncEdgeIt f = e; ++f;
  1.2430 -        if (r && runningNode(e) == a) {
  1.2431 -          erase(e);
  1.2432 -        } else if (u(e) == b) {
  1.2433 -          changeU(e, a);
  1.2434 -        } else {
  1.2435 -          changeV(e, a);
  1.2436 -        }
  1.2437 -        e = f;
  1.2438 -      }
  1.2439 -      erase(b);
  1.2440 -    }
  1.2441 -
  1.2442 -    ///Clear the graph.
  1.2443 -
  1.2444 -    ///This function erases all nodes and arcs from the graph.
  1.2445 -    ///
  1.2446 -    ///\note All iterators of the graph are invalidated, of course.
  1.2447 -    void clear() {
  1.2448 -      Parent::clear();
  1.2449 -    }
  1.2450 -
  1.2451 -    /// Reserve memory for nodes.
  1.2452 -
  1.2453 -    /// Using this function, it is possible to avoid superfluous memory
  1.2454 -    /// allocation: if you know that the graph you want to build will
  1.2455 -    /// be large (e.g. it will contain millions of nodes and/or edges),
  1.2456 -    /// then it is worth reserving space for this amount before starting
  1.2457 -    /// to build the graph.
  1.2458 -    /// \sa reserveEdge()
  1.2459 -    void reserveNode(int n) { nodes.reserve(n); };
  1.2460 -
  1.2461 -    /// Reserve memory for edges.
  1.2462 -
  1.2463 -    /// Using this function, it is possible to avoid superfluous memory
  1.2464 -    /// allocation: if you know that the graph you want to build will
  1.2465 -    /// be large (e.g. it will contain millions of nodes and/or edges),
  1.2466 -    /// then it is worth reserving space for this amount before starting
  1.2467 -    /// to build the graph.
  1.2468 -    /// \sa reserveNode()
  1.2469 -    void reserveEdge(int m) { arcs.reserve(2 * m); };
  1.2470 -
  1.2471 -    /// \brief Class to make a snapshot of the graph and restore
  1.2472 -    /// it later.
  1.2473 -    ///
  1.2474 -    /// Class to make a snapshot of the graph and restore it later.
  1.2475 -    ///
  1.2476 -    /// The newly added nodes and edges can be removed
  1.2477 -    /// using the restore() function.
  1.2478 -    ///
  1.2479 -    /// \note After a state is restored, you cannot restore a later state,
  1.2480 -    /// i.e. you cannot add the removed nodes and edges again using
  1.2481 -    /// another Snapshot instance.
  1.2482 -    ///
  1.2483 -    /// \warning Node and edge deletions and other modifications
  1.2484 -    /// (e.g. changing the end-nodes of edges or contracting nodes)
  1.2485 -    /// cannot be restored. These events invalidate the snapshot.
  1.2486 -    /// However, the edges and nodes that were added to the graph after
  1.2487 -    /// making the current snapshot can be removed without invalidating it.
  1.2488 -    class Snapshot {
  1.2489 -    protected:
  1.2490 -
  1.2491 -      typedef Parent::NodeNotifier NodeNotifier;
  1.2492 -
  1.2493 -      class NodeObserverProxy : public NodeNotifier::ObserverBase {
  1.2494 -      public:
  1.2495 -
  1.2496 -        NodeObserverProxy(Snapshot& _snapshot)
  1.2497 -          : snapshot(_snapshot) {}
  1.2498 -
  1.2499 -        using NodeNotifier::ObserverBase::attach;
  1.2500 -        using NodeNotifier::ObserverBase::detach;
  1.2501 -        using NodeNotifier::ObserverBase::attached;
  1.2502 -
  1.2503 -      protected:
  1.2504 -
  1.2505 -        virtual void add(const Node& node) {
  1.2506 -          snapshot.addNode(node);
  1.2507 -        }
  1.2508 -        virtual void add(const std::vector<Node>& nodes) {
  1.2509 -          for (int i = nodes.size() - 1; i >= 0; ++i) {
  1.2510 -            snapshot.addNode(nodes[i]);
  1.2511 -          }
  1.2512 -        }
  1.2513 -        virtual void erase(const Node& node) {
  1.2514 -          snapshot.eraseNode(node);
  1.2515 -        }
  1.2516 -        virtual void erase(const std::vector<Node>& nodes) {
  1.2517 -          for (int i = 0; i < int(nodes.size()); ++i) {
  1.2518 -            snapshot.eraseNode(nodes[i]);
  1.2519 -          }
  1.2520 -        }
  1.2521 -        virtual void build() {
  1.2522 -          Node node;
  1.2523 -          std::vector<Node> nodes;
  1.2524 -          for (notifier()->first(node); node != INVALID;
  1.2525 -               notifier()->next(node)) {
  1.2526 -            nodes.push_back(node);
  1.2527 -          }
  1.2528 -          for (int i = nodes.size() - 1; i >= 0; --i) {
  1.2529 -            snapshot.addNode(nodes[i]);
  1.2530 -          }
  1.2531 -        }
  1.2532 -        virtual void clear() {
  1.2533 -          Node node;
  1.2534 -          for (notifier()->first(node); node != INVALID;
  1.2535 -               notifier()->next(node)) {
  1.2536 -            snapshot.eraseNode(node);
  1.2537 -          }
  1.2538 -        }
  1.2539 -
  1.2540 -        Snapshot& snapshot;
  1.2541 -      };
  1.2542 -
  1.2543        class EdgeObserverProxy : public EdgeNotifier::ObserverBase {
  1.2544        public:
  1.2545  
  1.2546 @@ -1478,911 +2383,6 @@
  1.2547          Snapshot& snapshot;
  1.2548        };
  1.2549  
  1.2550 -      ListGraph *graph;
  1.2551 -
  1.2552 -      NodeObserverProxy node_observer_proxy;
  1.2553 -      EdgeObserverProxy edge_observer_proxy;
  1.2554 -
  1.2555 -      std::list<Node> added_nodes;
  1.2556 -      std::list<Edge> added_edges;
  1.2557 -
  1.2558 -
  1.2559 -      void addNode(const Node& node) {
  1.2560 -        added_nodes.push_front(node);
  1.2561 -      }
  1.2562 -      void eraseNode(const Node& node) {
  1.2563 -        std::list<Node>::iterator it =
  1.2564 -          std::find(added_nodes.begin(), added_nodes.end(), node);
  1.2565 -        if (it == added_nodes.end()) {
  1.2566 -          clear();
  1.2567 -          edge_observer_proxy.detach();
  1.2568 -          throw NodeNotifier::ImmediateDetach();
  1.2569 -        } else {
  1.2570 -          added_nodes.erase(it);
  1.2571 -        }
  1.2572 -      }
  1.2573 -
  1.2574 -      void addEdge(const Edge& edge) {
  1.2575 -        added_edges.push_front(edge);
  1.2576 -      }
  1.2577 -      void eraseEdge(const Edge& edge) {
  1.2578 -        std::list<Edge>::iterator it =
  1.2579 -          std::find(added_edges.begin(), added_edges.end(), edge);
  1.2580 -        if (it == added_edges.end()) {
  1.2581 -          clear();
  1.2582 -          node_observer_proxy.detach();
  1.2583 -          throw EdgeNotifier::ImmediateDetach();
  1.2584 -        } else {
  1.2585 -          added_edges.erase(it);
  1.2586 -        }
  1.2587 -      }
  1.2588 -
  1.2589 -      void attach(ListGraph &_graph) {
  1.2590 -        graph = &_graph;
  1.2591 -        node_observer_proxy.attach(graph->notifier(Node()));
  1.2592 -        edge_observer_proxy.attach(graph->notifier(Edge()));
  1.2593 -      }
  1.2594 -
  1.2595 -      void detach() {
  1.2596 -        node_observer_proxy.detach();
  1.2597 -        edge_observer_proxy.detach();
  1.2598 -      }
  1.2599 -
  1.2600 -      bool attached() const {
  1.2601 -        return node_observer_proxy.attached();
  1.2602 -      }
  1.2603 -
  1.2604 -      void clear() {
  1.2605 -        added_nodes.clear();
  1.2606 -        added_edges.clear();
  1.2607 -      }
  1.2608 -
  1.2609 -    public:
  1.2610 -
  1.2611 -      /// \brief Default constructor.
  1.2612 -      ///
  1.2613 -      /// Default constructor.
  1.2614 -      /// You have to call save() to actually make a snapshot.
  1.2615 -      Snapshot()
  1.2616 -        : graph(0), node_observer_proxy(*this),
  1.2617 -          edge_observer_proxy(*this) {}
  1.2618 -
  1.2619 -      /// \brief Constructor that immediately makes a snapshot.
  1.2620 -      ///
  1.2621 -      /// This constructor immediately makes a snapshot of the given graph.
  1.2622 -      Snapshot(ListGraph &gr)
  1.2623 -        : node_observer_proxy(*this),
  1.2624 -          edge_observer_proxy(*this) {
  1.2625 -        attach(gr);
  1.2626 -      }
  1.2627 -
  1.2628 -      /// \brief Make a snapshot.
  1.2629 -      ///
  1.2630 -      /// This function makes a snapshot of the given graph.
  1.2631 -      /// It can be called more than once. In case of a repeated
  1.2632 -      /// call, the previous snapshot gets lost.
  1.2633 -      void save(ListGraph &gr) {
  1.2634 -        if (attached()) {
  1.2635 -          detach();
  1.2636 -          clear();
  1.2637 -        }
  1.2638 -        attach(gr);
  1.2639 -      }
  1.2640 -
  1.2641 -      /// \brief Undo the changes until the last snapshot.
  1.2642 -      ///
  1.2643 -      /// This function undos the changes until the last snapshot
  1.2644 -      /// created by save() or Snapshot(ListGraph&).
  1.2645 -      ///
  1.2646 -      /// \warning This method invalidates the snapshot, i.e. repeated
  1.2647 -      /// restoring is not supported unless you call save() again.
  1.2648 -      void restore() {
  1.2649 -        detach();
  1.2650 -        for(std::list<Edge>::iterator it = added_edges.begin();
  1.2651 -            it != added_edges.end(); ++it) {
  1.2652 -          graph->erase(*it);
  1.2653 -        }
  1.2654 -        for(std::list<Node>::iterator it = added_nodes.begin();
  1.2655 -            it != added_nodes.end(); ++it) {
  1.2656 -          graph->erase(*it);
  1.2657 -        }
  1.2658 -        clear();
  1.2659 -      }
  1.2660 -
  1.2661 -      /// \brief Returns \c true if the snapshot is valid.
  1.2662 -      ///
  1.2663 -      /// This function returns \c true if the snapshot is valid.
  1.2664 -      bool valid() const {
  1.2665 -        return attached();
  1.2666 -      }
  1.2667 -    };
  1.2668 -  };
  1.2669 -
  1.2670 -  /// @}
  1.2671 -
  1.2672 -  class ListBpGraphBase {
  1.2673 -
  1.2674 -  protected:
  1.2675 -
  1.2676 -    struct NodeT {
  1.2677 -      int first_out;
  1.2678 -      int prev, next;
  1.2679 -      int partition_prev, partition_next;
  1.2680 -      int partition_index;
  1.2681 -      bool red;
  1.2682 -    };
  1.2683 -
  1.2684 -    struct ArcT {
  1.2685 -      int target;
  1.2686 -      int prev_out, next_out;
  1.2687 -    };
  1.2688 -
  1.2689 -    std::vector<NodeT> nodes;
  1.2690 -
  1.2691 -    int first_node, first_red, first_blue;
  1.2692 -    int max_red, max_blue;
  1.2693 -
  1.2694 -    int first_free_red, first_free_blue;
  1.2695 -
  1.2696 -    std::vector<ArcT> arcs;
  1.2697 -
  1.2698 -    int first_free_arc;
  1.2699 -
  1.2700 -  public:
  1.2701 -
  1.2702 -    typedef ListBpGraphBase BpGraph;
  1.2703 -
  1.2704 -    class Node {
  1.2705 -      friend class ListBpGraphBase;
  1.2706 -    protected:
  1.2707 -
  1.2708 -      int id;
  1.2709 -      explicit Node(int pid) { id = pid;}
  1.2710 -
  1.2711 -    public:
  1.2712 -      Node() {}
  1.2713 -      Node (Invalid) { id = -1; }
  1.2714 -      bool operator==(const Node& node) const {return id == node.id;}
  1.2715 -      bool operator!=(const Node& node) const {return id != node.id;}
  1.2716 -      bool operator<(const Node& node) const {return id < node.id;}
  1.2717 -    };
  1.2718 -
  1.2719 -    class RedNode : public Node {
  1.2720 -      friend class ListBpGraphBase;
  1.2721 -    protected:
  1.2722 -
  1.2723 -      explicit RedNode(int pid) : Node(pid) {}
  1.2724 -
  1.2725 -    public:
  1.2726 -      RedNode() {}
  1.2727 -      RedNode(const RedNode& node) : Node(node) {}
  1.2728 -      RedNode(Invalid) : Node(INVALID){}
  1.2729 -    };
  1.2730 -
  1.2731 -    class BlueNode : public Node {
  1.2732 -      friend class ListBpGraphBase;
  1.2733 -    protected:
  1.2734 -
  1.2735 -      explicit BlueNode(int pid) : Node(pid) {}
  1.2736 -
  1.2737 -    public:
  1.2738 -      BlueNode() {}
  1.2739 -      BlueNode(const BlueNode& node) : Node(node) {}
  1.2740 -      BlueNode(Invalid) : Node(INVALID){}
  1.2741 -    };
  1.2742 -
  1.2743 -    class Edge {
  1.2744 -      friend class ListBpGraphBase;
  1.2745 -    protected:
  1.2746 -
  1.2747 -      int id;
  1.2748 -      explicit Edge(int pid) { id = pid;}
  1.2749 -
  1.2750 -    public:
  1.2751 -      Edge() {}
  1.2752 -      Edge (Invalid) { id = -1; }
  1.2753 -      bool operator==(const Edge& edge) const {return id == edge.id;}
  1.2754 -      bool operator!=(const Edge& edge) const {return id != edge.id;}
  1.2755 -      bool operator<(const Edge& edge) const {return id < edge.id;}
  1.2756 -    };
  1.2757 -
  1.2758 -    class Arc {
  1.2759 -      friend class ListBpGraphBase;
  1.2760 -    protected:
  1.2761 -
  1.2762 -      int id;
  1.2763 -      explicit Arc(int pid) { id = pid;}
  1.2764 -
  1.2765 -    public:
  1.2766 -      operator Edge() const {
  1.2767 -        return id != -1 ? edgeFromId(id / 2) : INVALID;
  1.2768 -      }
  1.2769 -
  1.2770 -      Arc() {}
  1.2771 -      Arc (Invalid) { id = -1; }
  1.2772 -      bool operator==(const Arc& arc) const {return id == arc.id;}
  1.2773 -      bool operator!=(const Arc& arc) const {return id != arc.id;}
  1.2774 -      bool operator<(const Arc& arc) const {return id < arc.id;}
  1.2775 -    };
  1.2776 -
  1.2777 -    ListBpGraphBase()
  1.2778 -      : nodes(), first_node(-1),
  1.2779 -        first_red(-1), first_blue(-1),
  1.2780 -        max_red(-1), max_blue(-1),
  1.2781 -        first_free_red(-1), first_free_blue(-1),
  1.2782 -        arcs(), first_free_arc(-1) {}
  1.2783 -
  1.2784 -
  1.2785 -    bool red(Node n) const { return nodes[n.id].red; }
  1.2786 -    bool blue(Node n) const { return !nodes[n.id].red; }
  1.2787 -
  1.2788 -    static RedNode asRedNodeUnsafe(Node n) { return RedNode(n.id); }
  1.2789 -    static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n.id); }
  1.2790 -
  1.2791 -    int maxNodeId() const { return nodes.size()-1; }
  1.2792 -    int maxRedId() const { return max_red; }
  1.2793 -    int maxBlueId() const { return max_blue; }
  1.2794 -    int maxEdgeId() const { return arcs.size() / 2 - 1; }
  1.2795 -    int maxArcId() const { return arcs.size()-1; }
  1.2796 -
  1.2797 -    Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); }
  1.2798 -    Node target(Arc e) const { return Node(arcs[e.id].target); }
  1.2799 -
  1.2800 -    RedNode redNode(Edge e) const {
  1.2801 -      return RedNode(arcs[2 * e.id].target);
  1.2802 -    }
  1.2803 -    BlueNode blueNode(Edge e) const {
  1.2804 -      return BlueNode(arcs[2 * e.id + 1].target);
  1.2805 -    }
  1.2806 -
  1.2807 -    static bool direction(Arc e) {
  1.2808 -      return (e.id & 1) == 1;
  1.2809 -    }
  1.2810 -
  1.2811 -    static Arc direct(Edge e, bool d) {
  1.2812 -      return Arc(e.id * 2 + (d ? 1 : 0));
  1.2813 -    }
  1.2814 -
  1.2815 -    void first(Node& node) const {
  1.2816 -      node.id = first_node;
  1.2817 -    }
  1.2818 -
  1.2819 -    void next(Node& node) const {
  1.2820 -      node.id = nodes[node.id].next;
  1.2821 -    }
  1.2822 -
  1.2823 -    void first(RedNode& node) const {
  1.2824 -      node.id = first_red;
  1.2825 -    }
  1.2826 -
  1.2827 -    void next(RedNode& node) const {
  1.2828 -      node.id = nodes[node.id].partition_next;
  1.2829 -    }
  1.2830 -
  1.2831 -    void first(BlueNode& node) const {
  1.2832 -      node.id = first_blue;
  1.2833 -    }
  1.2834 -
  1.2835 -    void next(BlueNode& node) const {
  1.2836 -      node.id = nodes[node.id].partition_next;
  1.2837 -    }
  1.2838 -
  1.2839 -    void first(Arc& e) const {
  1.2840 -      int n = first_node;
  1.2841 -      while (n != -1 && nodes[n].first_out == -1) {
  1.2842 -        n = nodes[n].next;
  1.2843 -      }
  1.2844 -      e.id = (n == -1) ? -1 : nodes[n].first_out;
  1.2845 -    }
  1.2846 -
  1.2847 -    void next(Arc& e) const {
  1.2848 -      if (arcs[e.id].next_out != -1) {
  1.2849 -        e.id = arcs[e.id].next_out;
  1.2850 -      } else {
  1.2851 -        int n = nodes[arcs[e.id ^ 1].target].next;
  1.2852 -        while(n != -1 && nodes[n].first_out == -1) {
  1.2853 -          n = nodes[n].next;
  1.2854 -        }
  1.2855 -        e.id = (n == -1) ? -1 : nodes[n].first_out;
  1.2856 -      }
  1.2857 -    }
  1.2858 -
  1.2859 -    void first(Edge& e) const {
  1.2860 -      int n = first_node;
  1.2861 -      while (n != -1) {
  1.2862 -        e.id = nodes[n].first_out;
  1.2863 -        while ((e.id & 1) != 1) {
  1.2864 -          e.id = arcs[e.id].next_out;
  1.2865 -        }
  1.2866 -        if (e.id != -1) {
  1.2867 -          e.id /= 2;
  1.2868 -          return;
  1.2869 -        }
  1.2870 -        n = nodes[n].next;
  1.2871 -      }
  1.2872 -      e.id = -1;
  1.2873 -    }
  1.2874 -
  1.2875 -    void next(Edge& e) const {
  1.2876 -      int n = arcs[e.id * 2].target;
  1.2877 -      e.id = arcs[(e.id * 2) | 1].next_out;
  1.2878 -      while ((e.id & 1) != 1) {
  1.2879 -        e.id = arcs[e.id].next_out;
  1.2880 -      }
  1.2881 -      if (e.id != -1) {
  1.2882 -        e.id /= 2;
  1.2883 -        return;
  1.2884 -      }
  1.2885 -      n = nodes[n].next;
  1.2886 -      while (n != -1) {
  1.2887 -        e.id = nodes[n].first_out;
  1.2888 -        while ((e.id & 1) != 1) {
  1.2889 -          e.id = arcs[e.id].next_out;
  1.2890 -        }
  1.2891 -        if (e.id != -1) {
  1.2892 -          e.id /= 2;
  1.2893 -          return;
  1.2894 -        }
  1.2895 -        n = nodes[n].next;
  1.2896 -      }
  1.2897 -      e.id = -1;
  1.2898 -    }
  1.2899 -
  1.2900 -    void firstOut(Arc &e, const Node& v) const {
  1.2901 -      e.id = nodes[v.id].first_out;
  1.2902 -    }
  1.2903 -    void nextOut(Arc &e) const {
  1.2904 -      e.id = arcs[e.id].next_out;
  1.2905 -    }
  1.2906 -
  1.2907 -    void firstIn(Arc &e, const Node& v) const {
  1.2908 -      e.id = ((nodes[v.id].first_out) ^ 1);
  1.2909 -      if (e.id == -2) e.id = -1;
  1.2910 -    }
  1.2911 -    void nextIn(Arc &e) const {
  1.2912 -      e.id = ((arcs[e.id ^ 1].next_out) ^ 1);
  1.2913 -      if (e.id == -2) e.id = -1;
  1.2914 -    }
  1.2915 -
  1.2916 -    void firstInc(Edge &e, bool& d, const Node& v) const {
  1.2917 -      int a = nodes[v.id].first_out;
  1.2918 -      if (a != -1 ) {
  1.2919 -        e.id = a / 2;
  1.2920 -        d = ((a & 1) == 1);
  1.2921 -      } else {
  1.2922 -        e.id = -1;
  1.2923 -        d = true;
  1.2924 -      }
  1.2925 -    }
  1.2926 -    void nextInc(Edge &e, bool& d) const {
  1.2927 -      int a = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
  1.2928 -      if (a != -1 ) {
  1.2929 -        e.id = a / 2;
  1.2930 -        d = ((a & 1) == 1);
  1.2931 -      } else {
  1.2932 -        e.id = -1;
  1.2933 -        d = true;
  1.2934 -      }
  1.2935 -    }
  1.2936 -
  1.2937 -    static int id(Node v) { return v.id; }
  1.2938 -    int id(RedNode v) const { return nodes[v.id].partition_index; }
  1.2939 -    int id(BlueNode v) const { return nodes[v.id].partition_index; }
  1.2940 -    static int id(Arc e) { return e.id; }
  1.2941 -    static int id(Edge e) { return e.id; }
  1.2942 -
  1.2943 -    static Node nodeFromId(int id) { return Node(id);}
  1.2944 -    static Arc arcFromId(int id) { return Arc(id);}
  1.2945 -    static Edge edgeFromId(int id) { return Edge(id);}
  1.2946 -
  1.2947 -    bool valid(Node n) const {
  1.2948 -      return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
  1.2949 -        nodes[n.id].prev != -2;
  1.2950 -    }
  1.2951 -
  1.2952 -    bool valid(Arc a) const {
  1.2953 -      return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
  1.2954 -        arcs[a.id].prev_out != -2;
  1.2955 -    }
  1.2956 -
  1.2957 -    bool valid(Edge e) const {
  1.2958 -      return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) &&
  1.2959 -        arcs[2 * e.id].prev_out != -2;
  1.2960 -    }
  1.2961 -
  1.2962 -    RedNode addRedNode() {
  1.2963 -      int n;
  1.2964 -
  1.2965 -      if(first_free_red==-1) {
  1.2966 -        n = nodes.size();
  1.2967 -        nodes.push_back(NodeT());
  1.2968 -        nodes[n].partition_index = ++max_red;
  1.2969 -        nodes[n].red = true;
  1.2970 -      } else {
  1.2971 -        n = first_free_red;
  1.2972 -        first_free_red = nodes[n].next;
  1.2973 -      }
  1.2974 -
  1.2975 -      nodes[n].next = first_node;
  1.2976 -      if (first_node != -1) nodes[first_node].prev = n;
  1.2977 -      first_node = n;
  1.2978 -      nodes[n].prev = -1;
  1.2979 -
  1.2980 -      nodes[n].partition_next = first_red;
  1.2981 -      if (first_red != -1) nodes[first_red].partition_prev = n;
  1.2982 -      first_red = n;
  1.2983 -      nodes[n].partition_prev = -1;
  1.2984 -
  1.2985 -      nodes[n].first_out = -1;
  1.2986 -
  1.2987 -      return RedNode(n);
  1.2988 -    }
  1.2989 -
  1.2990 -    BlueNode addBlueNode() {
  1.2991 -      int n;
  1.2992 -
  1.2993 -      if(first_free_blue==-1) {
  1.2994 -        n = nodes.size();
  1.2995 -        nodes.push_back(NodeT());
  1.2996 -        nodes[n].partition_index = ++max_blue;
  1.2997 -        nodes[n].red = false;
  1.2998 -      } else {
  1.2999 -        n = first_free_blue;
  1.3000 -        first_free_blue = nodes[n].next;
  1.3001 -      }
  1.3002 -
  1.3003 -      nodes[n].next = first_node;
  1.3004 -      if (first_node != -1) nodes[first_node].prev = n;
  1.3005 -      first_node = n;
  1.3006 -      nodes[n].prev = -1;
  1.3007 -
  1.3008 -      nodes[n].partition_next = first_blue;
  1.3009 -      if (first_blue != -1) nodes[first_blue].partition_prev = n;
  1.3010 -      first_blue = n;
  1.3011 -      nodes[n].partition_prev = -1;
  1.3012 -
  1.3013 -      nodes[n].first_out = -1;
  1.3014 -
  1.3015 -      return BlueNode(n);
  1.3016 -    }
  1.3017 -
  1.3018 -    Edge addEdge(Node u, Node v) {
  1.3019 -      int n;
  1.3020 -
  1.3021 -      if (first_free_arc == -1) {
  1.3022 -        n = arcs.size();
  1.3023 -        arcs.push_back(ArcT());
  1.3024 -        arcs.push_back(ArcT());
  1.3025 -      } else {
  1.3026 -        n = first_free_arc;
  1.3027 -        first_free_arc = arcs[n].next_out;
  1.3028 -      }
  1.3029 -
  1.3030 -      arcs[n].target = u.id;
  1.3031 -      arcs[n | 1].target = v.id;
  1.3032 -
  1.3033 -      arcs[n].next_out = nodes[v.id].first_out;
  1.3034 -      if (nodes[v.id].first_out != -1) {
  1.3035 -        arcs[nodes[v.id].first_out].prev_out = n;
  1.3036 -      }
  1.3037 -      arcs[n].prev_out = -1;
  1.3038 -      nodes[v.id].first_out = n;
  1.3039 -
  1.3040 -      arcs[n | 1].next_out = nodes[u.id].first_out;
  1.3041 -      if (nodes[u.id].first_out != -1) {
  1.3042 -        arcs[nodes[u.id].first_out].prev_out = (n | 1);
  1.3043 -      }
  1.3044 -      arcs[n | 1].prev_out = -1;
  1.3045 -      nodes[u.id].first_out = (n | 1);
  1.3046 -
  1.3047 -      return Edge(n / 2);
  1.3048 -    }
  1.3049 -
  1.3050 -    void erase(const Node& node) {
  1.3051 -      int n = node.id;
  1.3052 -
  1.3053 -      if(nodes[n].next != -1) {
  1.3054 -        nodes[nodes[n].next].prev = nodes[n].prev;
  1.3055 -      }
  1.3056 -
  1.3057 -      if(nodes[n].prev != -1) {
  1.3058 -        nodes[nodes[n].prev].next = nodes[n].next;
  1.3059 -      } else {
  1.3060 -        first_node = nodes[n].next;
  1.3061 -      }
  1.3062 -
  1.3063 -      if (nodes[n].partition_next != -1) {
  1.3064 -        nodes[nodes[n].partition_next].partition_prev = nodes[n].partition_prev;
  1.3065 -      }
  1.3066 -
  1.3067 -      if (nodes[n].partition_prev != -1) {
  1.3068 -        nodes[nodes[n].partition_prev].partition_next = nodes[n].partition_next;
  1.3069 -      } else {
  1.3070 -        if (nodes[n].red) {
  1.3071 -          first_red = nodes[n].partition_next;
  1.3072 -        } else {
  1.3073 -          first_blue = nodes[n].partition_next;
  1.3074 -        }
  1.3075 -      }
  1.3076 -
  1.3077 -      if (nodes[n].red) {
  1.3078 -        nodes[n].next = first_free_red;
  1.3079 -        first_free_red = n;
  1.3080 -      } else {
  1.3081 -        nodes[n].next = first_free_blue;
  1.3082 -        first_free_blue = n;
  1.3083 -      }
  1.3084 -      nodes[n].prev = -2;
  1.3085 -    }
  1.3086 -
  1.3087 -    void erase(const Edge& edge) {
  1.3088 -      int n = edge.id * 2;
  1.3089 -
  1.3090 -      if (arcs[n].next_out != -1) {
  1.3091 -        arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
  1.3092 -      }
  1.3093 -
  1.3094 -      if (arcs[n].prev_out != -1) {
  1.3095 -        arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
  1.3096 -      } else {
  1.3097 -        nodes[arcs[n | 1].target].first_out = arcs[n].next_out;
  1.3098 -      }
  1.3099 -
  1.3100 -      if (arcs[n | 1].next_out != -1) {
  1.3101 -        arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
  1.3102 -      }
  1.3103 -
  1.3104 -      if (arcs[n | 1].prev_out != -1) {
  1.3105 -        arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
  1.3106 -      } else {
  1.3107 -        nodes[arcs[n].target].first_out = arcs[n | 1].next_out;
  1.3108 -      }
  1.3109 -
  1.3110 -      arcs[n].next_out = first_free_arc;
  1.3111 -      first_free_arc = n;
  1.3112 -      arcs[n].prev_out = -2;
  1.3113 -      arcs[n | 1].prev_out = -2;
  1.3114 -
  1.3115 -    }
  1.3116 -
  1.3117 -    void clear() {
  1.3118 -      arcs.clear();
  1.3119 -      nodes.clear();
  1.3120 -      first_node = first_free_arc = first_red = first_blue =
  1.3121 -        max_red = max_blue = first_free_red = first_free_blue = -1;
  1.3122 -    }
  1.3123 -
  1.3124 -  protected:
  1.3125 -
  1.3126 -    void changeRed(Edge e, RedNode n) {
  1.3127 -      if(arcs[(2 * e.id) | 1].next_out != -1) {
  1.3128 -        arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
  1.3129 -          arcs[(2 * e.id) | 1].prev_out;
  1.3130 -      }
  1.3131 -      if(arcs[(2 * e.id) | 1].prev_out != -1) {
  1.3132 -        arcs[arcs[(2 * e.id) | 1].prev_out].next_out =
  1.3133 -          arcs[(2 * e.id) | 1].next_out;
  1.3134 -      } else {
  1.3135 -        nodes[arcs[2 * e.id].target].first_out =
  1.3136 -          arcs[(2 * e.id) | 1].next_out;
  1.3137 -      }
  1.3138 -
  1.3139 -      if (nodes[n.id].first_out != -1) {
  1.3140 -        arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
  1.3141 -      }
  1.3142 -      arcs[2 * e.id].target = n.id;
  1.3143 -      arcs[(2 * e.id) | 1].prev_out = -1;
  1.3144 -      arcs[(2 * e.id) | 1].next_out = nodes[n.id].first_out;
  1.3145 -      nodes[n.id].first_out = ((2 * e.id) | 1);
  1.3146 -    }
  1.3147 -
  1.3148 -    void changeBlue(Edge e, BlueNode n) {
  1.3149 -       if(arcs[2 * e.id].next_out != -1) {
  1.3150 -        arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
  1.3151 -      }
  1.3152 -      if(arcs[2 * e.id].prev_out != -1) {
  1.3153 -        arcs[arcs[2 * e.id].prev_out].next_out =
  1.3154 -          arcs[2 * e.id].next_out;
  1.3155 -      } else {
  1.3156 -        nodes[arcs[(2 * e.id) | 1].target].first_out =
  1.3157 -          arcs[2 * e.id].next_out;
  1.3158 -      }
  1.3159 -
  1.3160 -      if (nodes[n.id].first_out != -1) {
  1.3161 -        arcs[nodes[n.id].first_out].prev_out = 2 * e.id;
  1.3162 -      }
  1.3163 -      arcs[(2 * e.id) | 1].target = n.id;
  1.3164 -      arcs[2 * e.id].prev_out = -1;
  1.3165 -      arcs[2 * e.id].next_out = nodes[n.id].first_out;
  1.3166 -      nodes[n.id].first_out = 2 * e.id;
  1.3167 -    }
  1.3168 -
  1.3169 -  };
  1.3170 -
  1.3171 -  typedef BpGraphExtender<ListBpGraphBase> ExtendedListBpGraphBase;
  1.3172 -
  1.3173 -
  1.3174 -  /// \addtogroup graphs
  1.3175 -  /// @{
  1.3176 -
  1.3177 -  ///A general undirected graph structure.
  1.3178 -
  1.3179 -  ///\ref ListBpGraph is a versatile and fast undirected graph
  1.3180 -  ///implementation based on linked lists that are stored in
  1.3181 -  ///\c std::vector structures.
  1.3182 -  ///
  1.3183 -  ///This type fully conforms to the \ref concepts::BpGraph "BpGraph concept"
  1.3184 -  ///and it also provides several useful additional functionalities.
  1.3185 -  ///Most of its member functions and nested classes are documented
  1.3186 -  ///only in the concept class.
  1.3187 -  ///
  1.3188 -  ///This class provides only linear time counting for nodes, edges and arcs.
  1.3189 -  ///
  1.3190 -  ///\sa concepts::BpGraph
  1.3191 -  ///\sa ListDigraph
  1.3192 -  class ListBpGraph : public ExtendedListBpGraphBase {
  1.3193 -    typedef ExtendedListBpGraphBase Parent;
  1.3194 -
  1.3195 -  private:
  1.3196 -    /// BpGraphs are \e not copy constructible. Use BpGraphCopy instead.
  1.3197 -    ListBpGraph(const ListBpGraph &) :ExtendedListBpGraphBase()  {};
  1.3198 -    /// \brief Assignment of a graph to another one is \e not allowed.
  1.3199 -    /// Use BpGraphCopy instead.
  1.3200 -    void operator=(const ListBpGraph &) {}
  1.3201 -  public:
  1.3202 -    /// Constructor
  1.3203 -
  1.3204 -    /// Constructor.
  1.3205 -    ///
  1.3206 -    ListBpGraph() {}
  1.3207 -
  1.3208 -    typedef Parent::OutArcIt IncEdgeIt;
  1.3209 -
  1.3210 -    /// \brief Add a new red node to the graph.
  1.3211 -    ///
  1.3212 -    /// This function adds a red new node to the graph.
  1.3213 -    /// \return The new node.
  1.3214 -    RedNode addRedNode() { return Parent::addRedNode(); }
  1.3215 -
  1.3216 -    /// \brief Add a new blue node to the graph.
  1.3217 -    ///
  1.3218 -    /// This function adds a blue new node to the graph.
  1.3219 -    /// \return The new node.
  1.3220 -    BlueNode addBlueNode() { return Parent::addBlueNode(); }
  1.3221 -
  1.3222 -    /// \brief Add a new edge to the graph.
  1.3223 -    ///
  1.3224 -    /// This function adds a new edge to the graph between nodes
  1.3225 -    /// \c u and \c v with inherent orientation from node \c u to
  1.3226 -    /// node \c v.
  1.3227 -    /// \return The new edge.
  1.3228 -    Edge addEdge(RedNode u, BlueNode v) {
  1.3229 -      return Parent::addEdge(u, v);
  1.3230 -    }
  1.3231 -    Edge addEdge(BlueNode v, RedNode u) {
  1.3232 -      return Parent::addEdge(u, v);
  1.3233 -    }
  1.3234 -
  1.3235 -    ///\brief Erase a node from the graph.
  1.3236 -    ///
  1.3237 -    /// This function erases the given node along with its incident arcs
  1.3238 -    /// from the graph.
  1.3239 -    ///
  1.3240 -    /// \note All iterators referencing the removed node or the incident
  1.3241 -    /// edges are invalidated, of course.
  1.3242 -    void erase(Node n) { Parent::erase(n); }
  1.3243 -
  1.3244 -    ///\brief Erase an edge from the graph.
  1.3245 -    ///
  1.3246 -    /// This function erases the given edge from the graph.
  1.3247 -    ///
  1.3248 -    /// \note All iterators referencing the removed edge are invalidated,
  1.3249 -    /// of course.
  1.3250 -    void erase(Edge e) { Parent::erase(e); }
  1.3251 -    /// Node validity check
  1.3252 -
  1.3253 -    /// This function gives back \c true if the given node is valid,
  1.3254 -    /// i.e. it is a real node of the graph.
  1.3255 -    ///
  1.3256 -    /// \warning A removed node could become valid again if new nodes are
  1.3257 -    /// added to the graph.
  1.3258 -    bool valid(Node n) const { return Parent::valid(n); }
  1.3259 -    /// Edge validity check
  1.3260 -
  1.3261 -    /// This function gives back \c true if the given edge is valid,
  1.3262 -    /// i.e. it is a real edge of the graph.
  1.3263 -    ///
  1.3264 -    /// \warning A removed edge could become valid again if new edges are
  1.3265 -    /// added to the graph.
  1.3266 -    bool valid(Edge e) const { return Parent::valid(e); }
  1.3267 -    /// Arc validity check
  1.3268 -
  1.3269 -    /// This function gives back \c true if the given arc is valid,
  1.3270 -    /// i.e. it is a real arc of the graph.
  1.3271 -    ///
  1.3272 -    /// \warning A removed arc could become valid again if new edges are
  1.3273 -    /// added to the graph.
  1.3274 -    bool valid(Arc a) const { return Parent::valid(a); }
  1.3275 -
  1.3276 -    /// \brief Change the red node of an edge.
  1.3277 -    ///
  1.3278 -    /// This function changes the red node of the given edge \c e to \c n.
  1.3279 -    ///
  1.3280 -    ///\note \c EdgeIt and \c ArcIt iterators referencing the
  1.3281 -    ///changed edge are invalidated and all other iterators whose
  1.3282 -    ///base node is the changed node are also invalidated.
  1.3283 -    ///
  1.3284 -    ///\warning This functionality cannot be used together with the
  1.3285 -    ///Snapshot feature.
  1.3286 -    void changeRed(Edge e, RedNode n) {
  1.3287 -      Parent::changeRed(e, n);
  1.3288 -    }
  1.3289 -    /// \brief Change the blue node of an edge.
  1.3290 -    ///
  1.3291 -    /// This function changes the blue node of the given edge \c e to \c n.
  1.3292 -    ///
  1.3293 -    ///\note \c EdgeIt iterators referencing the changed edge remain
  1.3294 -    ///valid, but \c ArcIt iterators referencing the changed edge and
  1.3295 -    ///all other iterators whose base node is the changed node are also
  1.3296 -    ///invalidated.
  1.3297 -    ///
  1.3298 -    ///\warning This functionality cannot be used together with the
  1.3299 -    ///Snapshot feature.
  1.3300 -    void changeBlue(Edge e, BlueNode n) {
  1.3301 -      Parent::changeBlue(e, n);
  1.3302 -    }
  1.3303 -
  1.3304 -    ///Clear the graph.
  1.3305 -
  1.3306 -    ///This function erases all nodes and arcs from the graph.
  1.3307 -    ///
  1.3308 -    ///\note All iterators of the graph are invalidated, of course.
  1.3309 -    void clear() {
  1.3310 -      Parent::clear();
  1.3311 -    }
  1.3312 -
  1.3313 -    /// Reserve memory for nodes.
  1.3314 -
  1.3315 -    /// Using this function, it is possible to avoid superfluous memory
  1.3316 -    /// allocation: if you know that the graph you want to build will
  1.3317 -    /// be large (e.g. it will contain millions of nodes and/or edges),
  1.3318 -    /// then it is worth reserving space for this amount before starting
  1.3319 -    /// to build the graph.
  1.3320 -    /// \sa reserveEdge()
  1.3321 -    void reserveNode(int n) { nodes.reserve(n); };
  1.3322 -
  1.3323 -    /// Reserve memory for edges.
  1.3324 -
  1.3325 -    /// Using this function, it is possible to avoid superfluous memory
  1.3326 -    /// allocation: if you know that the graph you want to build will
  1.3327 -    /// be large (e.g. it will contain millions of nodes and/or edges),
  1.3328 -    /// then it is worth reserving space for this amount before starting
  1.3329 -    /// to build the graph.
  1.3330 -    /// \sa reserveNode()
  1.3331 -    void reserveEdge(int m) { arcs.reserve(2 * m); };
  1.3332 -
  1.3333 -    /// \brief Class to make a snapshot of the graph and restore
  1.3334 -    /// it later.
  1.3335 -    ///
  1.3336 -    /// Class to make a snapshot of the graph and restore it later.
  1.3337 -    ///
  1.3338 -    /// The newly added nodes and edges can be removed
  1.3339 -    /// using the restore() function.
  1.3340 -    ///
  1.3341 -    /// \note After a state is restored, you cannot restore a later state,
  1.3342 -    /// i.e. you cannot add the removed nodes and edges again using
  1.3343 -    /// another Snapshot instance.
  1.3344 -    ///
  1.3345 -    /// \warning Node and edge deletions and other modifications
  1.3346 -    /// (e.g. changing the end-nodes of edges or contracting nodes)
  1.3347 -    /// cannot be restored. These events invalidate the snapshot.
  1.3348 -    /// However, the edges and nodes that were added to the graph after
  1.3349 -    /// making the current snapshot can be removed without invalidating it.
  1.3350 -    class Snapshot {
  1.3351 -    protected:
  1.3352 -
  1.3353 -      typedef Parent::NodeNotifier NodeNotifier;
  1.3354 -
  1.3355 -      class NodeObserverProxy : public NodeNotifier::ObserverBase {
  1.3356 -      public:
  1.3357 -
  1.3358 -        NodeObserverProxy(Snapshot& _snapshot)
  1.3359 -          : snapshot(_snapshot) {}
  1.3360 -
  1.3361 -        using NodeNotifier::ObserverBase::attach;
  1.3362 -        using NodeNotifier::ObserverBase::detach;
  1.3363 -        using NodeNotifier::ObserverBase::attached;
  1.3364 -
  1.3365 -      protected:
  1.3366 -
  1.3367 -        virtual void add(const Node& node) {
  1.3368 -          snapshot.addNode(node);
  1.3369 -        }
  1.3370 -        virtual void add(const std::vector<Node>& nodes) {
  1.3371 -          for (int i = nodes.size() - 1; i >= 0; ++i) {
  1.3372 -            snapshot.addNode(nodes[i]);
  1.3373 -          }
  1.3374 -        }
  1.3375 -        virtual void erase(const Node& node) {
  1.3376 -          snapshot.eraseNode(node);
  1.3377 -        }
  1.3378 -        virtual void erase(const std::vector<Node>& nodes) {
  1.3379 -          for (int i = 0; i < int(nodes.size()); ++i) {
  1.3380 -            snapshot.eraseNode(nodes[i]);
  1.3381 -          }
  1.3382 -        }
  1.3383 -        virtual void build() {
  1.3384 -          Node node;
  1.3385 -          std::vector<Node> nodes;
  1.3386 -          for (notifier()->first(node); node != INVALID;
  1.3387 -               notifier()->next(node)) {
  1.3388 -            nodes.push_back(node);
  1.3389 -          }
  1.3390 -          for (int i = nodes.size() - 1; i >= 0; --i) {
  1.3391 -            snapshot.addNode(nodes[i]);
  1.3392 -          }
  1.3393 -        }
  1.3394 -        virtual void clear() {
  1.3395 -          Node node;
  1.3396 -          for (notifier()->first(node); node != INVALID;
  1.3397 -               notifier()->next(node)) {
  1.3398 -            snapshot.eraseNode(node);
  1.3399 -          }
  1.3400 -        }
  1.3401 -
  1.3402 -        Snapshot& snapshot;
  1.3403 -      };
  1.3404 -
  1.3405 -      class EdgeObserverProxy : public EdgeNotifier::ObserverBase {
  1.3406 -      public:
  1.3407 -
  1.3408 -        EdgeObserverProxy(Snapshot& _snapshot)
  1.3409 -          : snapshot(_snapshot) {}
  1.3410 -
  1.3411 -        using EdgeNotifier::ObserverBase::attach;
  1.3412 -        using EdgeNotifier::ObserverBase::detach;
  1.3413 -        using EdgeNotifier::ObserverBase::attached;
  1.3414 -
  1.3415 -      protected:
  1.3416 -
  1.3417 -        virtual void add(const Edge& edge) {
  1.3418 -          snapshot.addEdge(edge);
  1.3419 -        }
  1.3420 -        virtual void add(const std::vector<Edge>& edges) {
  1.3421 -          for (int i = edges.size() - 1; i >= 0; ++i) {
  1.3422 -            snapshot.addEdge(edges[i]);
  1.3423 -          }
  1.3424 -        }
  1.3425 -        virtual void erase(const Edge& edge) {
  1.3426 -          snapshot.eraseEdge(edge);
  1.3427 -        }
  1.3428 -        virtual void erase(const std::vector<Edge>& edges) {
  1.3429 -          for (int i = 0; i < int(edges.size()); ++i) {
  1.3430 -            snapshot.eraseEdge(edges[i]);
  1.3431 -          }
  1.3432 -        }
  1.3433 -        virtual void build() {
  1.3434 -          Edge edge;
  1.3435 -          std::vector<Edge> edges;
  1.3436 -          for (notifier()->first(edge); edge != INVALID;
  1.3437 -               notifier()->next(edge)) {
  1.3438 -            edges.push_back(edge);
  1.3439 -          }
  1.3440 -          for (int i = edges.size() - 1; i >= 0; --i) {
  1.3441 -            snapshot.addEdge(edges[i]);
  1.3442 -          }
  1.3443 -        }
  1.3444 -        virtual void clear() {
  1.3445 -          Edge edge;
  1.3446 -          for (notifier()->first(edge); edge != INVALID;
  1.3447 -               notifier()->next(edge)) {
  1.3448 -            snapshot.eraseEdge(edge);
  1.3449 -          }
  1.3450 -        }
  1.3451 -
  1.3452 -        Snapshot& snapshot;
  1.3453 -      };
  1.3454 -
  1.3455        ListBpGraph *graph;
  1.3456  
  1.3457        NodeObserverProxy node_observer_proxy;