lemon/list_graph.h
author Peter Kovacs <kpeter@inf.elte.hu>
Sat, 17 Feb 2018 23:44:32 +0100
changeset 1421 4fd76139b69e
parent 1337 4add05447ca0
parent 1357 2126945deb6a
child 1432 da87dbdf3daf
permissions -rw-r--r--
Add operator[] to Path structures (#250)
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2013
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #ifndef LEMON_LIST_GRAPH_H
    20 #define LEMON_LIST_GRAPH_H
    21 
    22 ///\ingroup graphs
    23 ///\file
    24 ///\brief ListDigraph and ListGraph classes.
    25 
    26 #include <lemon/core.h>
    27 #include <lemon/error.h>
    28 #include <lemon/bits/graph_extender.h>
    29 
    30 #include <vector>
    31 #include <list>
    32 
    33 namespace lemon {
    34 
    35   class ListDigraph;
    36 
    37   class ListDigraphBase {
    38 
    39   protected:
    40     struct NodeT {
    41       int first_in, first_out;
    42       int prev, next;
    43     };
    44 
    45     struct ArcT {
    46       int target, source;
    47       int prev_in, prev_out;
    48       int next_in, next_out;
    49     };
    50 
    51     std::vector<NodeT> _nodes;
    52 
    53     int first_node;
    54 
    55     int first_free_node;
    56 
    57     std::vector<ArcT> _arcs;
    58 
    59     int first_free_arc;
    60 
    61   public:
    62 
    63     typedef ListDigraphBase Digraph;
    64 
    65     class Node {
    66       friend class ListDigraphBase;
    67       friend class ListDigraph;
    68     protected:
    69 
    70       int id;
    71       explicit Node(int pid) { id = pid;}
    72 
    73     public:
    74       Node() {}
    75       Node (Invalid) { id = -1; }
    76       bool operator==(const Node& node) const {return id == node.id;}
    77       bool operator!=(const Node& node) const {return id != node.id;}
    78       bool operator<(const Node& node) const {return id < node.id;}
    79     };
    80 
    81     class Arc {
    82       friend class ListDigraphBase;
    83       friend class ListDigraph;
    84     protected:
    85 
    86       int id;
    87       explicit Arc(int pid) { id = pid;}
    88 
    89     public:
    90       Arc() {}
    91       Arc (Invalid) { id = -1; }
    92       bool operator==(const Arc& arc) const {return id == arc.id;}
    93       bool operator!=(const Arc& arc) const {return id != arc.id;}
    94       bool operator<(const Arc& arc) const {return id < arc.id;}
    95     };
    96 
    97 
    98 
    99     ListDigraphBase()
   100       : _nodes(), first_node(-1),
   101         first_free_node(-1), _arcs(), first_free_arc(-1) {}
   102 
   103 
   104     int maxNodeId() const { return _nodes.size()-1; }
   105     int maxArcId() const { return _arcs.size()-1; }
   106 
   107     Node source(Arc e) const { return Node(_arcs[e.id].source); }
   108     Node target(Arc e) const { return Node(_arcs[e.id].target); }
   109 
   110 
   111     void first(Node& node) const {
   112       node.id = first_node;
   113     }
   114 
   115     void next(Node& node) const {
   116       node.id = _nodes[node.id].next;
   117     }
   118 
   119 
   120     void first(Arc& arc) const {
   121       int n;
   122       for(n = first_node;
   123           n != -1 && _nodes[n].first_out == -1;
   124           n = _nodes[n].next) {}
   125       arc.id = (n == -1) ? -1 : _nodes[n].first_out;
   126     }
   127 
   128     void next(Arc& arc) const {
   129       if (_arcs[arc.id].next_out != -1) {
   130         arc.id = _arcs[arc.id].next_out;
   131       } else {
   132         int n;
   133         for(n = _nodes[_arcs[arc.id].source].next;
   134             n != -1 && _nodes[n].first_out == -1;
   135             n = _nodes[n].next) {}
   136         arc.id = (n == -1) ? -1 : _nodes[n].first_out;
   137       }
   138     }
   139 
   140     void firstOut(Arc &e, const Node& v) const {
   141       e.id = _nodes[v.id].first_out;
   142     }
   143     void nextOut(Arc &e) const {
   144       e.id=_arcs[e.id].next_out;
   145     }
   146 
   147     void firstIn(Arc &e, const Node& v) const {
   148       e.id = _nodes[v.id].first_in;
   149     }
   150     void nextIn(Arc &e) const {
   151       e.id=_arcs[e.id].next_in;
   152     }
   153 
   154 
   155     static int id(Node v) { return v.id; }
   156     static int id(Arc e) { return e.id; }
   157 
   158     static Node nodeFromId(int id) { return Node(id);}
   159     static Arc arcFromId(int id) { return Arc(id);}
   160 
   161     bool valid(Node n) const {
   162       return n.id >= 0 && n.id < static_cast<int>(_nodes.size()) &&
   163         _nodes[n.id].prev != -2;
   164     }
   165 
   166     bool valid(Arc a) const {
   167       return a.id >= 0 && a.id < static_cast<int>(_arcs.size()) &&
   168         _arcs[a.id].prev_in != -2;
   169     }
   170 
   171     Node addNode() {
   172       int n;
   173 
   174       if(first_free_node==-1) {
   175         n = _nodes.size();
   176         _nodes.push_back(NodeT());
   177       } else {
   178         n = first_free_node;
   179         first_free_node = _nodes[n].next;
   180       }
   181 
   182       _nodes[n].next = first_node;
   183       if(first_node != -1) _nodes[first_node].prev = n;
   184       first_node = n;
   185       _nodes[n].prev = -1;
   186 
   187       _nodes[n].first_in = _nodes[n].first_out = -1;
   188 
   189       return Node(n);
   190     }
   191 
   192     Arc addArc(Node u, Node v) {
   193       int n;
   194 
   195       if (first_free_arc == -1) {
   196         n = _arcs.size();
   197         _arcs.push_back(ArcT());
   198       } else {
   199         n = first_free_arc;
   200         first_free_arc = _arcs[n].next_in;
   201       }
   202 
   203       _arcs[n].source = u.id;
   204       _arcs[n].target = v.id;
   205 
   206       _arcs[n].next_out = _nodes[u.id].first_out;
   207       if(_nodes[u.id].first_out != -1) {
   208         _arcs[_nodes[u.id].first_out].prev_out = n;
   209       }
   210 
   211       _arcs[n].next_in = _nodes[v.id].first_in;
   212       if(_nodes[v.id].first_in != -1) {
   213         _arcs[_nodes[v.id].first_in].prev_in = n;
   214       }
   215 
   216       _arcs[n].prev_in = _arcs[n].prev_out = -1;
   217 
   218       _nodes[u.id].first_out = _nodes[v.id].first_in = n;
   219 
   220       return Arc(n);
   221     }
   222 
   223     void erase(const Node& node) {
   224       int n = node.id;
   225 
   226       if(_nodes[n].next != -1) {
   227         _nodes[_nodes[n].next].prev = _nodes[n].prev;
   228       }
   229 
   230       if(_nodes[n].prev != -1) {
   231         _nodes[_nodes[n].prev].next = _nodes[n].next;
   232       } else {
   233         first_node = _nodes[n].next;
   234       }
   235 
   236       _nodes[n].next = first_free_node;
   237       first_free_node = n;
   238       _nodes[n].prev = -2;
   239 
   240     }
   241 
   242     void erase(const Arc& arc) {
   243       int n = arc.id;
   244 
   245       if(_arcs[n].next_in!=-1) {
   246         _arcs[_arcs[n].next_in].prev_in = _arcs[n].prev_in;
   247       }
   248 
   249       if(_arcs[n].prev_in!=-1) {
   250         _arcs[_arcs[n].prev_in].next_in = _arcs[n].next_in;
   251       } else {
   252         _nodes[_arcs[n].target].first_in = _arcs[n].next_in;
   253       }
   254 
   255 
   256       if(_arcs[n].next_out!=-1) {
   257         _arcs[_arcs[n].next_out].prev_out = _arcs[n].prev_out;
   258       }
   259 
   260       if(_arcs[n].prev_out!=-1) {
   261         _arcs[_arcs[n].prev_out].next_out = _arcs[n].next_out;
   262       } else {
   263         _nodes[_arcs[n].source].first_out = _arcs[n].next_out;
   264       }
   265 
   266       _arcs[n].next_in = first_free_arc;
   267       first_free_arc = n;
   268       _arcs[n].prev_in = -2;
   269     }
   270 
   271     void clear() {
   272       _arcs.clear();
   273       _nodes.clear();
   274       first_node = first_free_node = first_free_arc = -1;
   275     }
   276 
   277   protected:
   278     void changeTarget(Arc e, Node n)
   279     {
   280       if(_arcs[e.id].next_in != -1)
   281         _arcs[_arcs[e.id].next_in].prev_in = _arcs[e.id].prev_in;
   282       if(_arcs[e.id].prev_in != -1)
   283         _arcs[_arcs[e.id].prev_in].next_in = _arcs[e.id].next_in;
   284       else _nodes[_arcs[e.id].target].first_in = _arcs[e.id].next_in;
   285       if (_nodes[n.id].first_in != -1) {
   286         _arcs[_nodes[n.id].first_in].prev_in = e.id;
   287       }
   288       _arcs[e.id].target = n.id;
   289       _arcs[e.id].prev_in = -1;
   290       _arcs[e.id].next_in = _nodes[n.id].first_in;
   291       _nodes[n.id].first_in = e.id;
   292     }
   293     void changeSource(Arc e, Node n)
   294     {
   295       if(_arcs[e.id].next_out != -1)
   296         _arcs[_arcs[e.id].next_out].prev_out = _arcs[e.id].prev_out;
   297       if(_arcs[e.id].prev_out != -1)
   298         _arcs[_arcs[e.id].prev_out].next_out = _arcs[e.id].next_out;
   299       else _nodes[_arcs[e.id].source].first_out = _arcs[e.id].next_out;
   300       if (_nodes[n.id].first_out != -1) {
   301         _arcs[_nodes[n.id].first_out].prev_out = e.id;
   302       }
   303       _arcs[e.id].source = n.id;
   304       _arcs[e.id].prev_out = -1;
   305       _arcs[e.id].next_out = _nodes[n.id].first_out;
   306       _nodes[n.id].first_out = e.id;
   307     }
   308 
   309   };
   310 
   311   typedef DigraphExtender<ListDigraphBase> ExtendedListDigraphBase;
   312 
   313   /// \addtogroup graphs
   314   /// @{
   315 
   316   ///A general directed graph structure.
   317 
   318   ///\ref ListDigraph is a versatile and fast directed graph
   319   ///implementation based on linked lists that are stored in
   320   ///\c std::vector structures.
   321   ///
   322   ///This type fully conforms to the \ref concepts::Digraph "Digraph concept"
   323   ///and it also provides several useful additional functionalities.
   324   ///Most of its member functions and nested classes are documented
   325   ///only in the concept class.
   326   ///
   327   ///This class provides only linear time counting for nodes and arcs.
   328   ///
   329   ///\sa concepts::Digraph
   330   ///\sa ListGraph
   331   class ListDigraph : public ExtendedListDigraphBase {
   332     typedef ExtendedListDigraphBase Parent;
   333 
   334   private:
   335     /// Digraphs are \e not copy constructible. Use DigraphCopy instead.
   336     ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {};
   337     /// \brief Assignment of a digraph to another one is \e not allowed.
   338     /// Use DigraphCopy instead.
   339     void operator=(const ListDigraph &) {}
   340   public:
   341 
   342     /// Constructor
   343 
   344     /// Constructor.
   345     ///
   346     ListDigraph() {}
   347 
   348     ///Add a new node to the digraph.
   349 
   350     ///This function adds a new node to the digraph.
   351     ///\return The new node.
   352     Node addNode() { return Parent::addNode(); }
   353 
   354     ///Add a new arc to the digraph.
   355 
   356     ///This function adds a new arc to the digraph with source node \c s
   357     ///and target node \c t.
   358     ///\return The new arc.
   359     Arc addArc(Node s, Node t) {
   360       return Parent::addArc(s, t);
   361     }
   362 
   363     ///\brief Erase a node from the digraph.
   364     ///
   365     ///This function erases the given node along with its outgoing and
   366     ///incoming arcs from the digraph.
   367     ///
   368     ///\note All iterators referencing the removed node or the connected
   369     ///arcs are invalidated, of course.
   370     void erase(Node n) { Parent::erase(n); }
   371 
   372     ///\brief Erase an arc from the digraph.
   373     ///
   374     ///This function erases the given arc from the digraph.
   375     ///
   376     ///\note All iterators referencing the removed arc are invalidated,
   377     ///of course.
   378     void erase(Arc a) { Parent::erase(a); }
   379 
   380     /// Node validity check
   381 
   382     /// This function gives back \c true if the given node is valid,
   383     /// i.e. it is a real node of the digraph.
   384     ///
   385     /// \warning A removed node could become valid again if new nodes are
   386     /// added to the digraph.
   387     bool valid(Node n) const { return Parent::valid(n); }
   388 
   389     /// Arc validity check
   390 
   391     /// This function gives back \c true if the given arc is valid,
   392     /// i.e. it is a real arc of the digraph.
   393     ///
   394     /// \warning A removed arc could become valid again if new arcs are
   395     /// added to the digraph.
   396     bool valid(Arc a) const { return Parent::valid(a); }
   397 
   398     /// Change the target node of an arc
   399 
   400     /// This function changes the target node of the given arc \c a to \c n.
   401     ///
   402     ///\note \c ArcIt and \c OutArcIt iterators referencing the changed
   403     ///arc remain valid, but \c InArcIt iterators are invalidated.
   404     ///
   405     ///\warning This functionality cannot be used together with the Snapshot
   406     ///feature.
   407     void changeTarget(Arc a, Node n) {
   408       Parent::changeTarget(a,n);
   409     }
   410     /// Change the source node of an arc
   411 
   412     /// This function changes the source node of the given arc \c a to \c n.
   413     ///
   414     ///\note \c InArcIt iterators referencing the changed arc remain
   415     ///valid, but \c ArcIt and \c OutArcIt iterators are invalidated.
   416     ///
   417     ///\warning This functionality cannot be used together with the Snapshot
   418     ///feature.
   419     void changeSource(Arc a, Node n) {
   420       Parent::changeSource(a,n);
   421     }
   422 
   423     /// Reverse the direction of an arc.
   424 
   425     /// This function reverses the direction of the given arc.
   426     ///\note \c ArcIt, \c OutArcIt and \c InArcIt iterators referencing
   427     ///the changed arc are invalidated.
   428     ///
   429     ///\warning This functionality cannot be used together with the Snapshot
   430     ///feature.
   431     void reverseArc(Arc a) {
   432       Node t=target(a);
   433       changeTarget(a,source(a));
   434       changeSource(a,t);
   435     }
   436 
   437     ///Contract two nodes.
   438 
   439     ///This function contracts the given two nodes.
   440     ///Node \c v is removed, but instead of deleting its
   441     ///incident arcs, they are joined to node \c u.
   442     ///If the last parameter \c r is \c true (this is the default value),
   443     ///then the newly created loops are removed.
   444     ///
   445     ///\note The moved arcs are joined to node \c u using changeSource()
   446     ///or changeTarget(), thus \c ArcIt and \c OutArcIt iterators are
   447     ///invalidated for the outgoing arcs of node \c v and \c InArcIt
   448     ///iterators are invalidated for the incoming arcs of \c v.
   449     ///Moreover all iterators referencing node \c v or the removed
   450     ///loops are also invalidated. Other iterators remain valid.
   451     ///
   452     ///\warning This functionality cannot be used together with the Snapshot
   453     ///feature.
   454     void contract(Node u, Node v, bool r = true)
   455     {
   456       for(OutArcIt e(*this,v);e!=INVALID;) {
   457         OutArcIt f=e;
   458         ++f;
   459         if(r && target(e)==u) erase(e);
   460         else changeSource(e,u);
   461         e=f;
   462       }
   463       for(InArcIt e(*this,v);e!=INVALID;) {
   464         InArcIt f=e;
   465         ++f;
   466         if(r && source(e)==u) erase(e);
   467         else changeTarget(e,u);
   468         e=f;
   469       }
   470       erase(v);
   471     }
   472 
   473     ///Split a node.
   474 
   475     ///This function splits the given node. First, a new node is added
   476     ///to the digraph, then the source of each outgoing arc of node \c n
   477     ///is moved to this new node.
   478     ///If the second parameter \c connect is \c true (this is the default
   479     ///value), then a new arc from node \c n to the newly created node
   480     ///is also added.
   481     ///\return The newly created node.
   482     ///
   483     ///\note All iterators remain valid.
   484     ///
   485     ///\warning This functionality cannot be used together with the
   486     ///Snapshot feature.
   487     Node split(Node n, bool connect = true) {
   488       Node b = addNode();
   489       _nodes[b.id].first_out=_nodes[n.id].first_out;
   490       _nodes[n.id].first_out=-1;
   491       for(int i=_nodes[b.id].first_out; i!=-1; i=_arcs[i].next_out) {
   492         _arcs[i].source=b.id;
   493       }
   494       if (connect) addArc(n,b);
   495       return b;
   496     }
   497 
   498     ///Split an arc.
   499 
   500     ///This function splits the given arc. First, a new node \c v is
   501     ///added to the digraph, then the target node of the original arc
   502     ///is set to \c v. Finally, an arc from \c v to the original target
   503     ///is added.
   504     ///\return The newly created node.
   505     ///
   506     ///\note \c InArcIt iterators referencing the original arc are
   507     ///invalidated. Other iterators remain valid.
   508     ///
   509     ///\warning This functionality cannot be used together with the
   510     ///Snapshot feature.
   511     Node split(Arc a) {
   512       Node v = addNode();
   513       addArc(v,target(a));
   514       changeTarget(a,v);
   515       return v;
   516     }
   517 
   518     ///Clear the digraph.
   519 
   520     ///This function erases all nodes and arcs from the digraph.
   521     ///
   522     ///\note All iterators of the digraph are invalidated, of course.
   523     void clear() {
   524       Parent::clear();
   525     }
   526 
   527     /// Reserve memory for nodes.
   528 
   529     /// Using this function, it is possible to avoid superfluous memory
   530     /// allocation: if you know that the digraph you want to build will
   531     /// be large (e.g. it will contain millions of nodes and/or arcs),
   532     /// then it is worth reserving space for this amount before starting
   533     /// to build the digraph.
   534     /// \sa reserveArc()
   535     void reserveNode(int n) { _nodes.reserve(n); };
   536 
   537     /// Reserve memory for arcs.
   538 
   539     /// Using this function, it is possible to avoid superfluous memory
   540     /// allocation: if you know that the digraph you want to build will
   541     /// be large (e.g. it will contain millions of nodes and/or arcs),
   542     /// then it is worth reserving space for this amount before starting
   543     /// to build the digraph.
   544     /// \sa reserveNode()
   545     void reserveArc(int m) { _arcs.reserve(m); };
   546 
   547     /// \brief Class to make a snapshot of the digraph and restore
   548     /// it later.
   549     ///
   550     /// Class to make a snapshot of the digraph and restore it later.
   551     ///
   552     /// The newly added nodes and arcs can be removed using the
   553     /// restore() function.
   554     ///
   555     /// \note After a state is restored, you cannot restore a later state,
   556     /// i.e. you cannot add the removed nodes and arcs again using
   557     /// another Snapshot instance.
   558     ///
   559     /// \warning Node and arc deletions and other modifications (e.g.
   560     /// reversing, contracting, splitting arcs or nodes) cannot be
   561     /// restored. These events invalidate the snapshot.
   562     /// However, the arcs and nodes that were added to the digraph after
   563     /// making the current snapshot can be removed without invalidating it.
   564     class Snapshot {
   565     protected:
   566 
   567       typedef Parent::NodeNotifier NodeNotifier;
   568 
   569       class NodeObserverProxy : public NodeNotifier::ObserverBase {
   570       public:
   571 
   572         NodeObserverProxy(Snapshot& _snapshot)
   573           : snapshot(_snapshot) {}
   574 
   575         using NodeNotifier::ObserverBase::attach;
   576         using NodeNotifier::ObserverBase::detach;
   577         using NodeNotifier::ObserverBase::attached;
   578 
   579       protected:
   580 
   581         virtual void add(const Node& node) {
   582           snapshot.addNode(node);
   583         }
   584         virtual void add(const std::vector<Node>& nodes) {
   585           for (int i = nodes.size() - 1; i >= 0; --i) {
   586             snapshot.addNode(nodes[i]);
   587           }
   588         }
   589         virtual void erase(const Node& node) {
   590           snapshot.eraseNode(node);
   591         }
   592         virtual void erase(const std::vector<Node>& nodes) {
   593           for (int i = 0; i < int(nodes.size()); ++i) {
   594             snapshot.eraseNode(nodes[i]);
   595           }
   596         }
   597         virtual void build() {
   598           Node node;
   599           std::vector<Node> nodes;
   600           for (notifier()->first(node); node != INVALID;
   601                notifier()->next(node)) {
   602             nodes.push_back(node);
   603           }
   604           for (int i = nodes.size() - 1; i >= 0; --i) {
   605             snapshot.addNode(nodes[i]);
   606           }
   607         }
   608         virtual void clear() {
   609           Node node;
   610           for (notifier()->first(node); node != INVALID;
   611                notifier()->next(node)) {
   612             snapshot.eraseNode(node);
   613           }
   614         }
   615 
   616         Snapshot& snapshot;
   617       };
   618 
   619       class ArcObserverProxy : public ArcNotifier::ObserverBase {
   620       public:
   621 
   622         ArcObserverProxy(Snapshot& _snapshot)
   623           : snapshot(_snapshot) {}
   624 
   625         using ArcNotifier::ObserverBase::attach;
   626         using ArcNotifier::ObserverBase::detach;
   627         using ArcNotifier::ObserverBase::attached;
   628 
   629       protected:
   630 
   631         virtual void add(const Arc& arc) {
   632           snapshot.addArc(arc);
   633         }
   634         virtual void add(const std::vector<Arc>& arcs) {
   635           for (int i = arcs.size() - 1; i >= 0; --i) {
   636             snapshot.addArc(arcs[i]);
   637           }
   638         }
   639         virtual void erase(const Arc& arc) {
   640           snapshot.eraseArc(arc);
   641         }
   642         virtual void erase(const std::vector<Arc>& arcs) {
   643           for (int i = 0; i < int(arcs.size()); ++i) {
   644             snapshot.eraseArc(arcs[i]);
   645           }
   646         }
   647         virtual void build() {
   648           Arc arc;
   649           std::vector<Arc> arcs;
   650           for (notifier()->first(arc); arc != INVALID;
   651                notifier()->next(arc)) {
   652             arcs.push_back(arc);
   653           }
   654           for (int i = arcs.size() - 1; i >= 0; --i) {
   655             snapshot.addArc(arcs[i]);
   656           }
   657         }
   658         virtual void clear() {
   659           Arc arc;
   660           for (notifier()->first(arc); arc != INVALID;
   661                notifier()->next(arc)) {
   662             snapshot.eraseArc(arc);
   663           }
   664         }
   665 
   666         Snapshot& snapshot;
   667       };
   668 
   669       ListDigraph *digraph;
   670 
   671       NodeObserverProxy node_observer_proxy;
   672       ArcObserverProxy arc_observer_proxy;
   673 
   674       std::list<Node> added_nodes;
   675       std::list<Arc> added_arcs;
   676 
   677 
   678       void addNode(const Node& node) {
   679         added_nodes.push_front(node);
   680       }
   681       void eraseNode(const Node& node) {
   682         std::list<Node>::iterator it =
   683           std::find(added_nodes.begin(), added_nodes.end(), node);
   684         if (it == added_nodes.end()) {
   685           clear();
   686           arc_observer_proxy.detach();
   687           throw NodeNotifier::ImmediateDetach();
   688         } else {
   689           added_nodes.erase(it);
   690         }
   691       }
   692 
   693       void addArc(const Arc& arc) {
   694         added_arcs.push_front(arc);
   695       }
   696       void eraseArc(const Arc& arc) {
   697         std::list<Arc>::iterator it =
   698           std::find(added_arcs.begin(), added_arcs.end(), arc);
   699         if (it == added_arcs.end()) {
   700           clear();
   701           node_observer_proxy.detach();
   702           throw ArcNotifier::ImmediateDetach();
   703         } else {
   704           added_arcs.erase(it);
   705         }
   706       }
   707 
   708       void attach(ListDigraph &_digraph) {
   709         digraph = &_digraph;
   710         node_observer_proxy.attach(digraph->notifier(Node()));
   711         arc_observer_proxy.attach(digraph->notifier(Arc()));
   712       }
   713 
   714       void detach() {
   715         node_observer_proxy.detach();
   716         arc_observer_proxy.detach();
   717       }
   718 
   719       bool attached() const {
   720         return node_observer_proxy.attached();
   721       }
   722 
   723       void clear() {
   724         added_nodes.clear();
   725         added_arcs.clear();
   726       }
   727 
   728     public:
   729 
   730       /// \brief Default constructor.
   731       ///
   732       /// Default constructor.
   733       /// You have to call save() to actually make a snapshot.
   734       Snapshot()
   735         : digraph(0), node_observer_proxy(*this),
   736           arc_observer_proxy(*this) {}
   737 
   738       /// \brief Constructor that immediately makes a snapshot.
   739       ///
   740       /// This constructor immediately makes a snapshot of the given digraph.
   741       Snapshot(ListDigraph &gr)
   742         : node_observer_proxy(*this),
   743           arc_observer_proxy(*this) {
   744         attach(gr);
   745       }
   746 
   747       /// \brief Make a snapshot.
   748       ///
   749       /// This function makes a snapshot of the given digraph.
   750       /// It can be called more than once. In case of a repeated
   751       /// call, the previous snapshot gets lost.
   752       void save(ListDigraph &gr) {
   753         if (attached()) {
   754           detach();
   755           clear();
   756         }
   757         attach(gr);
   758       }
   759 
   760       /// \brief Undo the changes until the last snapshot.
   761       ///
   762       /// This function undos the changes until the last snapshot
   763       /// created by save() or Snapshot(ListDigraph&).
   764       ///
   765       /// \warning This method invalidates the snapshot, i.e. repeated
   766       /// restoring is not supported unless you call save() again.
   767       void restore() {
   768         detach();
   769         for(std::list<Arc>::iterator it = added_arcs.begin();
   770             it != added_arcs.end(); ++it) {
   771           digraph->erase(*it);
   772         }
   773         for(std::list<Node>::iterator it = added_nodes.begin();
   774             it != added_nodes.end(); ++it) {
   775           digraph->erase(*it);
   776         }
   777         clear();
   778       }
   779 
   780       /// \brief Returns \c true if the snapshot is valid.
   781       ///
   782       /// This function returns \c true if the snapshot is valid.
   783       bool valid() const {
   784         return attached();
   785       }
   786     };
   787 
   788   };
   789 
   790   ///@}
   791 
   792   class ListGraphBase {
   793 
   794   protected:
   795 
   796     struct NodeT {
   797       int first_out;
   798       int prev, next;
   799     };
   800 
   801     struct ArcT {
   802       int target;
   803       int prev_out, next_out;
   804     };
   805 
   806     std::vector<NodeT> _nodes;
   807 
   808     int first_node;
   809 
   810     int first_free_node;
   811 
   812     std::vector<ArcT> _arcs;
   813 
   814     int first_free_arc;
   815 
   816   public:
   817 
   818     typedef ListGraphBase Graph;
   819 
   820     class Node {
   821       friend class ListGraphBase;
   822     protected:
   823 
   824       int id;
   825       explicit Node(int pid) { id = pid;}
   826 
   827     public:
   828       Node() {}
   829       Node (Invalid) { id = -1; }
   830       bool operator==(const Node& node) const {return id == node.id;}
   831       bool operator!=(const Node& node) const {return id != node.id;}
   832       bool operator<(const Node& node) const {return id < node.id;}
   833     };
   834 
   835     class Edge {
   836       friend class ListGraphBase;
   837     protected:
   838 
   839       int id;
   840       explicit Edge(int pid) { id = pid;}
   841 
   842     public:
   843       Edge() {}
   844       Edge (Invalid) { id = -1; }
   845       bool operator==(const Edge& edge) const {return id == edge.id;}
   846       bool operator!=(const Edge& edge) const {return id != edge.id;}
   847       bool operator<(const Edge& edge) const {return id < edge.id;}
   848     };
   849 
   850     class Arc {
   851       friend class ListGraphBase;
   852     protected:
   853 
   854       int id;
   855       explicit Arc(int pid) { id = pid;}
   856 
   857     public:
   858       operator Edge() const {
   859         return id != -1 ? edgeFromId(id / 2) : INVALID;
   860       }
   861 
   862       Arc() {}
   863       Arc (Invalid) { id = -1; }
   864       bool operator==(const Arc& arc) const {return id == arc.id;}
   865       bool operator!=(const Arc& arc) const {return id != arc.id;}
   866       bool operator<(const Arc& arc) const {return id < arc.id;}
   867     };
   868 
   869     ListGraphBase()
   870       : _nodes(), first_node(-1),
   871         first_free_node(-1), _arcs(), first_free_arc(-1) {}
   872 
   873 
   874     int maxNodeId() const { return _nodes.size()-1; }
   875     int maxEdgeId() const { return _arcs.size() / 2 - 1; }
   876     int maxArcId() const { return _arcs.size()-1; }
   877 
   878     Node source(Arc e) const { return Node(_arcs[e.id ^ 1].target); }
   879     Node target(Arc e) const { return Node(_arcs[e.id].target); }
   880 
   881     Node u(Edge e) const { return Node(_arcs[2 * e.id].target); }
   882     Node v(Edge e) const { return Node(_arcs[2 * e.id + 1].target); }
   883 
   884     static bool direction(Arc e) {
   885       return (e.id & 1) == 1;
   886     }
   887 
   888     static Arc direct(Edge e, bool d) {
   889       return Arc(e.id * 2 + (d ? 1 : 0));
   890     }
   891 
   892     void first(Node& node) const {
   893       node.id = first_node;
   894     }
   895 
   896     void next(Node& node) const {
   897       node.id = _nodes[node.id].next;
   898     }
   899 
   900     void first(Arc& e) const {
   901       int n = first_node;
   902       while (n != -1 && _nodes[n].first_out == -1) {
   903         n = _nodes[n].next;
   904       }
   905       e.id = (n == -1) ? -1 : _nodes[n].first_out;
   906     }
   907 
   908     void next(Arc& e) const {
   909       if (_arcs[e.id].next_out != -1) {
   910         e.id = _arcs[e.id].next_out;
   911       } else {
   912         int n = _nodes[_arcs[e.id ^ 1].target].next;
   913         while(n != -1 && _nodes[n].first_out == -1) {
   914           n = _nodes[n].next;
   915         }
   916         e.id = (n == -1) ? -1 : _nodes[n].first_out;
   917       }
   918     }
   919 
   920     void first(Edge& e) const {
   921       int n = first_node;
   922       while (n != -1) {
   923         e.id = _nodes[n].first_out;
   924         while ((e.id & 1) != 1) {
   925           e.id = _arcs[e.id].next_out;
   926         }
   927         if (e.id != -1) {
   928           e.id /= 2;
   929           return;
   930         }
   931         n = _nodes[n].next;
   932       }
   933       e.id = -1;
   934     }
   935 
   936     void next(Edge& e) const {
   937       int n = _arcs[e.id * 2].target;
   938       e.id = _arcs[(e.id * 2) | 1].next_out;
   939       while ((e.id & 1) != 1) {
   940         e.id = _arcs[e.id].next_out;
   941       }
   942       if (e.id != -1) {
   943         e.id /= 2;
   944         return;
   945       }
   946       n = _nodes[n].next;
   947       while (n != -1) {
   948         e.id = _nodes[n].first_out;
   949         while ((e.id & 1) != 1) {
   950           e.id = _arcs[e.id].next_out;
   951         }
   952         if (e.id != -1) {
   953           e.id /= 2;
   954           return;
   955         }
   956         n = _nodes[n].next;
   957       }
   958       e.id = -1;
   959     }
   960 
   961     void firstOut(Arc &e, const Node& v) const {
   962       e.id = _nodes[v.id].first_out;
   963     }
   964     void nextOut(Arc &e) const {
   965       e.id = _arcs[e.id].next_out;
   966     }
   967 
   968     void firstIn(Arc &e, const Node& v) const {
   969       e.id = ((_nodes[v.id].first_out) ^ 1);
   970       if (e.id == -2) e.id = -1;
   971     }
   972     void nextIn(Arc &e) const {
   973       e.id = ((_arcs[e.id ^ 1].next_out) ^ 1);
   974       if (e.id == -2) e.id = -1;
   975     }
   976 
   977     void firstInc(Edge &e, bool& d, const Node& v) const {
   978       int a = _nodes[v.id].first_out;
   979       if (a != -1 ) {
   980         e.id = a / 2;
   981         d = ((a & 1) == 1);
   982       } else {
   983         e.id = -1;
   984         d = true;
   985       }
   986     }
   987     void nextInc(Edge &e, bool& d) const {
   988       int a = (_arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
   989       if (a != -1 ) {
   990         e.id = a / 2;
   991         d = ((a & 1) == 1);
   992       } else {
   993         e.id = -1;
   994         d = true;
   995       }
   996     }
   997 
   998     static int id(Node v) { return v.id; }
   999     static int id(Arc e) { return e.id; }
  1000     static int id(Edge e) { return e.id; }
  1001 
  1002     static Node nodeFromId(int id) { return Node(id);}
  1003     static Arc arcFromId(int id) { return Arc(id);}
  1004     static Edge edgeFromId(int id) { return Edge(id);}
  1005 
  1006     bool valid(Node n) const {
  1007       return n.id >= 0 && n.id < static_cast<int>(_nodes.size()) &&
  1008         _nodes[n.id].prev != -2;
  1009     }
  1010 
  1011     bool valid(Arc a) const {
  1012       return a.id >= 0 && a.id < static_cast<int>(_arcs.size()) &&
  1013         _arcs[a.id].prev_out != -2;
  1014     }
  1015 
  1016     bool valid(Edge e) const {
  1017       return e.id >= 0 && 2 * e.id < static_cast<int>(_arcs.size()) &&
  1018         _arcs[2 * e.id].prev_out != -2;
  1019     }
  1020 
  1021     Node addNode() {
  1022       int n;
  1023 
  1024       if(first_free_node==-1) {
  1025         n = _nodes.size();
  1026         _nodes.push_back(NodeT());
  1027       } else {
  1028         n = first_free_node;
  1029         first_free_node = _nodes[n].next;
  1030       }
  1031 
  1032       _nodes[n].next = first_node;
  1033       if (first_node != -1) _nodes[first_node].prev = n;
  1034       first_node = n;
  1035       _nodes[n].prev = -1;
  1036 
  1037       _nodes[n].first_out = -1;
  1038 
  1039       return Node(n);
  1040     }
  1041 
  1042     Edge addEdge(Node u, Node v) {
  1043       int n;
  1044 
  1045       if (first_free_arc == -1) {
  1046         n = _arcs.size();
  1047         _arcs.push_back(ArcT());
  1048         _arcs.push_back(ArcT());
  1049       } else {
  1050         n = first_free_arc;
  1051         first_free_arc = _arcs[n].next_out;
  1052       }
  1053 
  1054       _arcs[n].target = u.id;
  1055       _arcs[n | 1].target = v.id;
  1056 
  1057       _arcs[n].next_out = _nodes[v.id].first_out;
  1058       if (_nodes[v.id].first_out != -1) {
  1059         _arcs[_nodes[v.id].first_out].prev_out = n;
  1060       }
  1061       _arcs[n].prev_out = -1;
  1062       _nodes[v.id].first_out = n;
  1063 
  1064       _arcs[n | 1].next_out = _nodes[u.id].first_out;
  1065       if (_nodes[u.id].first_out != -1) {
  1066         _arcs[_nodes[u.id].first_out].prev_out = (n | 1);
  1067       }
  1068       _arcs[n | 1].prev_out = -1;
  1069       _nodes[u.id].first_out = (n | 1);
  1070 
  1071       return Edge(n / 2);
  1072     }
  1073 
  1074     void erase(const Node& node) {
  1075       int n = node.id;
  1076 
  1077       if(_nodes[n].next != -1) {
  1078         _nodes[_nodes[n].next].prev = _nodes[n].prev;
  1079       }
  1080 
  1081       if(_nodes[n].prev != -1) {
  1082         _nodes[_nodes[n].prev].next = _nodes[n].next;
  1083       } else {
  1084         first_node = _nodes[n].next;
  1085       }
  1086 
  1087       _nodes[n].next = first_free_node;
  1088       first_free_node = n;
  1089       _nodes[n].prev = -2;
  1090     }
  1091 
  1092     void erase(const Edge& edge) {
  1093       int n = edge.id * 2;
  1094 
  1095       if (_arcs[n].next_out != -1) {
  1096         _arcs[_arcs[n].next_out].prev_out = _arcs[n].prev_out;
  1097       }
  1098 
  1099       if (_arcs[n].prev_out != -1) {
  1100         _arcs[_arcs[n].prev_out].next_out = _arcs[n].next_out;
  1101       } else {
  1102         _nodes[_arcs[n | 1].target].first_out = _arcs[n].next_out;
  1103       }
  1104 
  1105       if (_arcs[n | 1].next_out != -1) {
  1106         _arcs[_arcs[n | 1].next_out].prev_out = _arcs[n | 1].prev_out;
  1107       }
  1108 
  1109       if (_arcs[n | 1].prev_out != -1) {
  1110         _arcs[_arcs[n | 1].prev_out].next_out = _arcs[n | 1].next_out;
  1111       } else {
  1112         _nodes[_arcs[n].target].first_out = _arcs[n | 1].next_out;
  1113       }
  1114 
  1115       _arcs[n].next_out = first_free_arc;
  1116       first_free_arc = n;
  1117       _arcs[n].prev_out = -2;
  1118       _arcs[n | 1].prev_out = -2;
  1119 
  1120     }
  1121 
  1122     void clear() {
  1123       _arcs.clear();
  1124       _nodes.clear();
  1125       first_node = first_free_node = first_free_arc = -1;
  1126     }
  1127 
  1128   protected:
  1129 
  1130     void changeV(Edge e, Node n) {
  1131       if(_arcs[2 * e.id].next_out != -1) {
  1132         _arcs[_arcs[2 * e.id].next_out].prev_out = _arcs[2 * e.id].prev_out;
  1133       }
  1134       if(_arcs[2 * e.id].prev_out != -1) {
  1135         _arcs[_arcs[2 * e.id].prev_out].next_out =
  1136           _arcs[2 * e.id].next_out;
  1137       } else {
  1138         _nodes[_arcs[(2 * e.id) | 1].target].first_out =
  1139           _arcs[2 * e.id].next_out;
  1140       }
  1141 
  1142       if (_nodes[n.id].first_out != -1) {
  1143         _arcs[_nodes[n.id].first_out].prev_out = 2 * e.id;
  1144       }
  1145       _arcs[(2 * e.id) | 1].target = n.id;
  1146       _arcs[2 * e.id].prev_out = -1;
  1147       _arcs[2 * e.id].next_out = _nodes[n.id].first_out;
  1148       _nodes[n.id].first_out = 2 * e.id;
  1149     }
  1150 
  1151     void changeU(Edge e, Node n) {
  1152       if(_arcs[(2 * e.id) | 1].next_out != -1) {
  1153         _arcs[_arcs[(2 * e.id) | 1].next_out].prev_out =
  1154           _arcs[(2 * e.id) | 1].prev_out;
  1155       }
  1156       if(_arcs[(2 * e.id) | 1].prev_out != -1) {
  1157         _arcs[_arcs[(2 * e.id) | 1].prev_out].next_out =
  1158           _arcs[(2 * e.id) | 1].next_out;
  1159       } else {
  1160         _nodes[_arcs[2 * e.id].target].first_out =
  1161           _arcs[(2 * e.id) | 1].next_out;
  1162       }
  1163 
  1164       if (_nodes[n.id].first_out != -1) {
  1165         _arcs[_nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
  1166       }
  1167       _arcs[2 * e.id].target = n.id;
  1168       _arcs[(2 * e.id) | 1].prev_out = -1;
  1169       _arcs[(2 * e.id) | 1].next_out = _nodes[n.id].first_out;
  1170       _nodes[n.id].first_out = ((2 * e.id) | 1);
  1171     }
  1172 
  1173   };
  1174 
  1175   typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
  1176 
  1177 
  1178   /// \addtogroup graphs
  1179   /// @{
  1180 
  1181   ///A general undirected graph structure.
  1182 
  1183   ///\ref ListGraph is a versatile and fast undirected graph
  1184   ///implementation based on linked lists that are stored in
  1185   ///\c std::vector structures.
  1186   ///
  1187   ///This type fully conforms to the \ref concepts::Graph "Graph concept"
  1188   ///and it also provides several useful additional functionalities.
  1189   ///Most of its member functions and nested classes are documented
  1190   ///only in the concept class.
  1191   ///
  1192   ///This class provides only linear time counting for nodes, edges and arcs.
  1193   ///
  1194   ///\sa concepts::Graph
  1195   ///\sa ListDigraph
  1196   class ListGraph : public ExtendedListGraphBase {
  1197     typedef ExtendedListGraphBase Parent;
  1198 
  1199   private:
  1200     /// Graphs are \e not copy constructible. Use GraphCopy instead.
  1201     ListGraph(const ListGraph &) :ExtendedListGraphBase()  {};
  1202     /// \brief Assignment of a graph to another one is \e not allowed.
  1203     /// Use GraphCopy instead.
  1204     void operator=(const ListGraph &) {}
  1205   public:
  1206     /// Constructor
  1207 
  1208     /// Constructor.
  1209     ///
  1210     ListGraph() {}
  1211 
  1212     typedef Parent::IncEdgeIt IncEdgeIt;
  1213 
  1214     /// \brief Add a new node to the graph.
  1215     ///
  1216     /// This function adds a new node to the graph.
  1217     /// \return The new node.
  1218     Node addNode() { return Parent::addNode(); }
  1219 
  1220     /// \brief Add a new edge to the graph.
  1221     ///
  1222     /// This function adds a new edge to the graph between nodes
  1223     /// \c u and \c v with inherent orientation from node \c u to
  1224     /// node \c v.
  1225     /// \return The new edge.
  1226     Edge addEdge(Node u, Node v) {
  1227       return Parent::addEdge(u, v);
  1228     }
  1229 
  1230     ///\brief Erase a node from the graph.
  1231     ///
  1232     /// This function erases the given node along with its incident arcs
  1233     /// from the graph.
  1234     ///
  1235     /// \note All iterators referencing the removed node or the incident
  1236     /// edges are invalidated, of course.
  1237     void erase(Node n) { Parent::erase(n); }
  1238 
  1239     ///\brief Erase an edge from the graph.
  1240     ///
  1241     /// This function erases the given edge from the graph.
  1242     ///
  1243     /// \note All iterators referencing the removed edge are invalidated,
  1244     /// of course.
  1245     void erase(Edge e) { Parent::erase(e); }
  1246     /// Node validity check
  1247 
  1248     /// This function gives back \c true if the given node is valid,
  1249     /// i.e. it is a real node of the graph.
  1250     ///
  1251     /// \warning A removed node could become valid again if new nodes are
  1252     /// added to the graph.
  1253     bool valid(Node n) const { return Parent::valid(n); }
  1254     /// Edge validity check
  1255 
  1256     /// This function gives back \c true if the given edge is valid,
  1257     /// i.e. it is a real edge of the graph.
  1258     ///
  1259     /// \warning A removed edge could become valid again if new edges are
  1260     /// added to the graph.
  1261     bool valid(Edge e) const { return Parent::valid(e); }
  1262     /// Arc validity check
  1263 
  1264     /// This function gives back \c true if the given arc is valid,
  1265     /// i.e. it is a real arc of the graph.
  1266     ///
  1267     /// \warning A removed arc could become valid again if new edges are
  1268     /// added to the graph.
  1269     bool valid(Arc a) const { return Parent::valid(a); }
  1270 
  1271     /// \brief Change the first node of an edge.
  1272     ///
  1273     /// This function changes the first node of the given edge \c e to \c n.
  1274     ///
  1275     ///\note \c EdgeIt and \c ArcIt iterators referencing the
  1276     ///changed edge are invalidated and all other iterators whose
  1277     ///base node is the changed node are also invalidated.
  1278     ///
  1279     ///\warning This functionality cannot be used together with the
  1280     ///Snapshot feature.
  1281     void changeU(Edge e, Node n) {
  1282       Parent::changeU(e,n);
  1283     }
  1284     /// \brief Change the second node of an edge.
  1285     ///
  1286     /// This function changes the second node of the given edge \c e to \c n.
  1287     ///
  1288     ///\note \c EdgeIt iterators referencing the changed edge remain
  1289     ///valid, but \c ArcIt iterators referencing the changed edge and
  1290     ///all other iterators whose base node is the changed node are also
  1291     ///invalidated.
  1292     ///
  1293     ///\warning This functionality cannot be used together with the
  1294     ///Snapshot feature.
  1295     void changeV(Edge e, Node n) {
  1296       Parent::changeV(e,n);
  1297     }
  1298 
  1299     /// \brief Contract two nodes.
  1300     ///
  1301     /// This function contracts the given two nodes.
  1302     /// Node \c b is removed, but instead of deleting
  1303     /// its incident edges, they are joined to node \c a.
  1304     /// If the last parameter \c r is \c true (this is the default value),
  1305     /// then the newly created loops are removed.
  1306     ///
  1307     /// \note The moved edges are joined to node \c a using changeU()
  1308     /// or changeV(), thus all edge and arc iterators whose base node is
  1309     /// \c b are invalidated.
  1310     /// Moreover all iterators referencing node \c b or the removed
  1311     /// loops are also invalidated. Other iterators remain valid.
  1312     ///
  1313     ///\warning This functionality cannot be used together with the
  1314     ///Snapshot feature.
  1315     void contract(Node a, Node b, bool r = true) {
  1316       for(IncEdgeIt e(*this, b); e!=INVALID;) {
  1317         IncEdgeIt f = e; ++f;
  1318         if (r && runningNode(e) == a) {
  1319           erase(e);
  1320         } else if (u(e) == b) {
  1321           changeU(e, a);
  1322         } else {
  1323           changeV(e, a);
  1324         }
  1325         e = f;
  1326       }
  1327       erase(b);
  1328     }
  1329 
  1330     ///Clear the graph.
  1331 
  1332     ///This function erases all nodes and arcs from the graph.
  1333     ///
  1334     ///\note All iterators of the graph are invalidated, of course.
  1335     void clear() {
  1336       Parent::clear();
  1337     }
  1338 
  1339     /// Reserve memory for nodes.
  1340 
  1341     /// Using this function, it is possible to avoid superfluous memory
  1342     /// allocation: if you know that the graph you want to build will
  1343     /// be large (e.g. it will contain millions of nodes and/or edges),
  1344     /// then it is worth reserving space for this amount before starting
  1345     /// to build the graph.
  1346     /// \sa reserveEdge()
  1347     void reserveNode(int n) { _nodes.reserve(n); };
  1348 
  1349     /// Reserve memory for edges.
  1350 
  1351     /// Using this function, it is possible to avoid superfluous memory
  1352     /// allocation: if you know that the graph you want to build will
  1353     /// be large (e.g. it will contain millions of nodes and/or edges),
  1354     /// then it is worth reserving space for this amount before starting
  1355     /// to build the graph.
  1356     /// \sa reserveNode()
  1357     void reserveEdge(int m) { _arcs.reserve(2 * m); };
  1358 
  1359     /// \brief Class to make a snapshot of the graph and restore
  1360     /// it later.
  1361     ///
  1362     /// Class to make a snapshot of the graph and restore it later.
  1363     ///
  1364     /// The newly added nodes and edges can be removed
  1365     /// using the restore() function.
  1366     ///
  1367     /// \note After a state is restored, you cannot restore a later state,
  1368     /// i.e. you cannot add the removed nodes and edges again using
  1369     /// another Snapshot instance.
  1370     ///
  1371     /// \warning Node and edge deletions and other modifications
  1372     /// (e.g. changing the end-nodes of edges or contracting nodes)
  1373     /// cannot be restored. These events invalidate the snapshot.
  1374     /// However, the edges and nodes that were added to the graph after
  1375     /// making the current snapshot can be removed without invalidating it.
  1376     class Snapshot {
  1377     protected:
  1378 
  1379       typedef Parent::NodeNotifier NodeNotifier;
  1380 
  1381       class NodeObserverProxy : public NodeNotifier::ObserverBase {
  1382       public:
  1383 
  1384         NodeObserverProxy(Snapshot& _snapshot)
  1385           : snapshot(_snapshot) {}
  1386 
  1387         using NodeNotifier::ObserverBase::attach;
  1388         using NodeNotifier::ObserverBase::detach;
  1389         using NodeNotifier::ObserverBase::attached;
  1390 
  1391       protected:
  1392 
  1393         virtual void add(const Node& node) {
  1394           snapshot.addNode(node);
  1395         }
  1396         virtual void add(const std::vector<Node>& nodes) {
  1397           for (int i = nodes.size() - 1; i >= 0; --i) {
  1398             snapshot.addNode(nodes[i]);
  1399           }
  1400         }
  1401         virtual void erase(const Node& node) {
  1402           snapshot.eraseNode(node);
  1403         }
  1404         virtual void erase(const std::vector<Node>& nodes) {
  1405           for (int i = 0; i < int(nodes.size()); ++i) {
  1406             snapshot.eraseNode(nodes[i]);
  1407           }
  1408         }
  1409         virtual void build() {
  1410           Node node;
  1411           std::vector<Node> nodes;
  1412           for (notifier()->first(node); node != INVALID;
  1413                notifier()->next(node)) {
  1414             nodes.push_back(node);
  1415           }
  1416           for (int i = nodes.size() - 1; i >= 0; --i) {
  1417             snapshot.addNode(nodes[i]);
  1418           }
  1419         }
  1420         virtual void clear() {
  1421           Node node;
  1422           for (notifier()->first(node); node != INVALID;
  1423                notifier()->next(node)) {
  1424             snapshot.eraseNode(node);
  1425           }
  1426         }
  1427 
  1428         Snapshot& snapshot;
  1429       };
  1430 
  1431       class EdgeObserverProxy : public EdgeNotifier::ObserverBase {
  1432       public:
  1433 
  1434         EdgeObserverProxy(Snapshot& _snapshot)
  1435           : snapshot(_snapshot) {}
  1436 
  1437         using EdgeNotifier::ObserverBase::attach;
  1438         using EdgeNotifier::ObserverBase::detach;
  1439         using EdgeNotifier::ObserverBase::attached;
  1440 
  1441       protected:
  1442 
  1443         virtual void add(const Edge& edge) {
  1444           snapshot.addEdge(edge);
  1445         }
  1446         virtual void add(const std::vector<Edge>& edges) {
  1447           for (int i = edges.size() - 1; i >= 0; --i) {
  1448             snapshot.addEdge(edges[i]);
  1449           }
  1450         }
  1451         virtual void erase(const Edge& edge) {
  1452           snapshot.eraseEdge(edge);
  1453         }
  1454         virtual void erase(const std::vector<Edge>& edges) {
  1455           for (int i = 0; i < int(edges.size()); ++i) {
  1456             snapshot.eraseEdge(edges[i]);
  1457           }
  1458         }
  1459         virtual void build() {
  1460           Edge edge;
  1461           std::vector<Edge> edges;
  1462           for (notifier()->first(edge); edge != INVALID;
  1463                notifier()->next(edge)) {
  1464             edges.push_back(edge);
  1465           }
  1466           for (int i = edges.size() - 1; i >= 0; --i) {
  1467             snapshot.addEdge(edges[i]);
  1468           }
  1469         }
  1470         virtual void clear() {
  1471           Edge edge;
  1472           for (notifier()->first(edge); edge != INVALID;
  1473                notifier()->next(edge)) {
  1474             snapshot.eraseEdge(edge);
  1475           }
  1476         }
  1477 
  1478         Snapshot& snapshot;
  1479       };
  1480 
  1481       ListGraph *graph;
  1482 
  1483       NodeObserverProxy node_observer_proxy;
  1484       EdgeObserverProxy edge_observer_proxy;
  1485 
  1486       std::list<Node> added_nodes;
  1487       std::list<Edge> added_edges;
  1488 
  1489 
  1490       void addNode(const Node& node) {
  1491         added_nodes.push_front(node);
  1492       }
  1493       void eraseNode(const Node& node) {
  1494         std::list<Node>::iterator it =
  1495           std::find(added_nodes.begin(), added_nodes.end(), node);
  1496         if (it == added_nodes.end()) {
  1497           clear();
  1498           edge_observer_proxy.detach();
  1499           throw NodeNotifier::ImmediateDetach();
  1500         } else {
  1501           added_nodes.erase(it);
  1502         }
  1503       }
  1504 
  1505       void addEdge(const Edge& edge) {
  1506         added_edges.push_front(edge);
  1507       }
  1508       void eraseEdge(const Edge& edge) {
  1509         std::list<Edge>::iterator it =
  1510           std::find(added_edges.begin(), added_edges.end(), edge);
  1511         if (it == added_edges.end()) {
  1512           clear();
  1513           node_observer_proxy.detach();
  1514           throw EdgeNotifier::ImmediateDetach();
  1515         } else {
  1516           added_edges.erase(it);
  1517         }
  1518       }
  1519 
  1520       void attach(ListGraph &_graph) {
  1521         graph = &_graph;
  1522         node_observer_proxy.attach(graph->notifier(Node()));
  1523         edge_observer_proxy.attach(graph->notifier(Edge()));
  1524       }
  1525 
  1526       void detach() {
  1527         node_observer_proxy.detach();
  1528         edge_observer_proxy.detach();
  1529       }
  1530 
  1531       bool attached() const {
  1532         return node_observer_proxy.attached();
  1533       }
  1534 
  1535       void clear() {
  1536         added_nodes.clear();
  1537         added_edges.clear();
  1538       }
  1539 
  1540     public:
  1541 
  1542       /// \brief Default constructor.
  1543       ///
  1544       /// Default constructor.
  1545       /// You have to call save() to actually make a snapshot.
  1546       Snapshot()
  1547         : graph(0), node_observer_proxy(*this),
  1548           edge_observer_proxy(*this) {}
  1549 
  1550       /// \brief Constructor that immediately makes a snapshot.
  1551       ///
  1552       /// This constructor immediately makes a snapshot of the given graph.
  1553       Snapshot(ListGraph &gr)
  1554         : node_observer_proxy(*this),
  1555           edge_observer_proxy(*this) {
  1556         attach(gr);
  1557       }
  1558 
  1559       /// \brief Make a snapshot.
  1560       ///
  1561       /// This function makes a snapshot of the given graph.
  1562       /// It can be called more than once. In case of a repeated
  1563       /// call, the previous snapshot gets lost.
  1564       void save(ListGraph &gr) {
  1565         if (attached()) {
  1566           detach();
  1567           clear();
  1568         }
  1569         attach(gr);
  1570       }
  1571 
  1572       /// \brief Undo the changes until the last snapshot.
  1573       ///
  1574       /// This function undos the changes until the last snapshot
  1575       /// created by save() or Snapshot(ListGraph&).
  1576       ///
  1577       /// \warning This method invalidates the snapshot, i.e. repeated
  1578       /// restoring is not supported unless you call save() again.
  1579       void restore() {
  1580         detach();
  1581         for(std::list<Edge>::iterator it = added_edges.begin();
  1582             it != added_edges.end(); ++it) {
  1583           graph->erase(*it);
  1584         }
  1585         for(std::list<Node>::iterator it = added_nodes.begin();
  1586             it != added_nodes.end(); ++it) {
  1587           graph->erase(*it);
  1588         }
  1589         clear();
  1590       }
  1591 
  1592       /// \brief Returns \c true if the snapshot is valid.
  1593       ///
  1594       /// This function returns \c true if the snapshot is valid.
  1595       bool valid() const {
  1596         return attached();
  1597       }
  1598     };
  1599   };
  1600 
  1601   /// @}
  1602 
  1603   class ListBpGraphBase {
  1604 
  1605   protected:
  1606 
  1607     struct NodeT {
  1608       int first_out;
  1609       int prev, next;
  1610       int partition_prev, partition_next;
  1611       int partition_index;
  1612       bool red;
  1613     };
  1614 
  1615     struct ArcT {
  1616       int target;
  1617       int prev_out, next_out;
  1618     };
  1619 
  1620     std::vector<NodeT> _nodes;
  1621 
  1622     int first_node, first_red, first_blue;
  1623     int max_red, max_blue;
  1624 
  1625     int first_free_red, first_free_blue;
  1626 
  1627     std::vector<ArcT> _arcs;
  1628 
  1629     int first_free_arc;
  1630 
  1631   public:
  1632 
  1633     typedef ListBpGraphBase BpGraph;
  1634 
  1635     class Node {
  1636       friend class ListBpGraphBase;
  1637     protected:
  1638 
  1639       int id;
  1640       explicit Node(int pid) { id = pid;}
  1641 
  1642     public:
  1643       Node() {}
  1644       Node (Invalid) { id = -1; }
  1645       bool operator==(const Node& node) const {return id == node.id;}
  1646       bool operator!=(const Node& node) const {return id != node.id;}
  1647       bool operator<(const Node& node) const {return id < node.id;}
  1648     };
  1649 
  1650     class RedNode : public Node {
  1651       friend class ListBpGraphBase;
  1652     protected:
  1653 
  1654       explicit RedNode(int pid) : Node(pid) {}
  1655 
  1656     public:
  1657       RedNode() {}
  1658       RedNode(const RedNode& node) : Node(node) {}
  1659       RedNode(Invalid) : Node(INVALID){}
  1660     };
  1661 
  1662     class BlueNode : public Node {
  1663       friend class ListBpGraphBase;
  1664     protected:
  1665 
  1666       explicit BlueNode(int pid) : Node(pid) {}
  1667 
  1668     public:
  1669       BlueNode() {}
  1670       BlueNode(const BlueNode& node) : Node(node) {}
  1671       BlueNode(Invalid) : Node(INVALID){}
  1672     };
  1673 
  1674     class Edge {
  1675       friend class ListBpGraphBase;
  1676     protected:
  1677 
  1678       int id;
  1679       explicit Edge(int pid) { id = pid;}
  1680 
  1681     public:
  1682       Edge() {}
  1683       Edge (Invalid) { id = -1; }
  1684       bool operator==(const Edge& edge) const {return id == edge.id;}
  1685       bool operator!=(const Edge& edge) const {return id != edge.id;}
  1686       bool operator<(const Edge& edge) const {return id < edge.id;}
  1687     };
  1688 
  1689     class Arc {
  1690       friend class ListBpGraphBase;
  1691     protected:
  1692 
  1693       int id;
  1694       explicit Arc(int pid) { id = pid;}
  1695 
  1696     public:
  1697       operator Edge() const {
  1698         return id != -1 ? edgeFromId(id / 2) : INVALID;
  1699       }
  1700 
  1701       Arc() {}
  1702       Arc (Invalid) { id = -1; }
  1703       bool operator==(const Arc& arc) const {return id == arc.id;}
  1704       bool operator!=(const Arc& arc) const {return id != arc.id;}
  1705       bool operator<(const Arc& arc) const {return id < arc.id;}
  1706     };
  1707 
  1708     ListBpGraphBase()
  1709       : _nodes(), first_node(-1),
  1710         first_red(-1), first_blue(-1),
  1711         max_red(-1), max_blue(-1),
  1712         first_free_red(-1), first_free_blue(-1),
  1713         _arcs(), first_free_arc(-1) {}
  1714 
  1715 
  1716     bool red(Node n) const { return _nodes[n.id].red; }
  1717     bool blue(Node n) const { return !_nodes[n.id].red; }
  1718 
  1719     static RedNode asRedNodeUnsafe(Node n) { return RedNode(n.id); }
  1720     static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n.id); }
  1721 
  1722     int maxNodeId() const { return _nodes.size()-1; }
  1723     int maxRedId() const { return max_red; }
  1724     int maxBlueId() const { return max_blue; }
  1725     int maxEdgeId() const { return _arcs.size() / 2 - 1; }
  1726     int maxArcId() const { return _arcs.size()-1; }
  1727 
  1728     Node source(Arc e) const { return Node(_arcs[e.id ^ 1].target); }
  1729     Node target(Arc e) const { return Node(_arcs[e.id].target); }
  1730 
  1731     RedNode redNode(Edge e) const {
  1732       return RedNode(_arcs[2 * e.id].target);
  1733     }
  1734     BlueNode blueNode(Edge e) const {
  1735       return BlueNode(_arcs[2 * e.id + 1].target);
  1736     }
  1737 
  1738     static bool direction(Arc e) {
  1739       return (e.id & 1) == 1;
  1740     }
  1741 
  1742     static Arc direct(Edge e, bool d) {
  1743       return Arc(e.id * 2 + (d ? 1 : 0));
  1744     }
  1745 
  1746     void first(Node& node) const {
  1747       node.id = first_node;
  1748     }
  1749 
  1750     void next(Node& node) const {
  1751       node.id = _nodes[node.id].next;
  1752     }
  1753 
  1754     void first(RedNode& node) const {
  1755       node.id = first_red;
  1756     }
  1757 
  1758     void next(RedNode& node) const {
  1759       node.id = _nodes[node.id].partition_next;
  1760     }
  1761 
  1762     void first(BlueNode& node) const {
  1763       node.id = first_blue;
  1764     }
  1765 
  1766     void next(BlueNode& node) const {
  1767       node.id = _nodes[node.id].partition_next;
  1768     }
  1769 
  1770     void first(Arc& e) const {
  1771       int n = first_node;
  1772       while (n != -1 && _nodes[n].first_out == -1) {
  1773         n = _nodes[n].next;
  1774       }
  1775       e.id = (n == -1) ? -1 : _nodes[n].first_out;
  1776     }
  1777 
  1778     void next(Arc& e) const {
  1779       if (_arcs[e.id].next_out != -1) {
  1780         e.id = _arcs[e.id].next_out;
  1781       } else {
  1782         int n = _nodes[_arcs[e.id ^ 1].target].next;
  1783         while(n != -1 && _nodes[n].first_out == -1) {
  1784           n = _nodes[n].next;
  1785         }
  1786         e.id = (n == -1) ? -1 : _nodes[n].first_out;
  1787       }
  1788     }
  1789 
  1790     void first(Edge& e) const {
  1791       int n = first_node;
  1792       while (n != -1) {
  1793         e.id = _nodes[n].first_out;
  1794         while ((e.id & 1) != 1) {
  1795           e.id = _arcs[e.id].next_out;
  1796         }
  1797         if (e.id != -1) {
  1798           e.id /= 2;
  1799           return;
  1800         }
  1801         n = _nodes[n].next;
  1802       }
  1803       e.id = -1;
  1804     }
  1805 
  1806     void next(Edge& e) const {
  1807       int n = _arcs[e.id * 2].target;
  1808       e.id = _arcs[(e.id * 2) | 1].next_out;
  1809       while ((e.id & 1) != 1) {
  1810         e.id = _arcs[e.id].next_out;
  1811       }
  1812       if (e.id != -1) {
  1813         e.id /= 2;
  1814         return;
  1815       }
  1816       n = _nodes[n].next;
  1817       while (n != -1) {
  1818         e.id = _nodes[n].first_out;
  1819         while ((e.id & 1) != 1) {
  1820           e.id = _arcs[e.id].next_out;
  1821         }
  1822         if (e.id != -1) {
  1823           e.id /= 2;
  1824           return;
  1825         }
  1826         n = _nodes[n].next;
  1827       }
  1828       e.id = -1;
  1829     }
  1830 
  1831     void firstOut(Arc &e, const Node& v) const {
  1832       e.id = _nodes[v.id].first_out;
  1833     }
  1834     void nextOut(Arc &e) const {
  1835       e.id = _arcs[e.id].next_out;
  1836     }
  1837 
  1838     void firstIn(Arc &e, const Node& v) const {
  1839       e.id = ((_nodes[v.id].first_out) ^ 1);
  1840       if (e.id == -2) e.id = -1;
  1841     }
  1842     void nextIn(Arc &e) const {
  1843       e.id = ((_arcs[e.id ^ 1].next_out) ^ 1);
  1844       if (e.id == -2) e.id = -1;
  1845     }
  1846 
  1847     void firstInc(Edge &e, bool& d, const Node& v) const {
  1848       int a = _nodes[v.id].first_out;
  1849       if (a != -1 ) {
  1850         e.id = a / 2;
  1851         d = ((a & 1) == 1);
  1852       } else {
  1853         e.id = -1;
  1854         d = true;
  1855       }
  1856     }
  1857     void nextInc(Edge &e, bool& d) const {
  1858       int a = (_arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
  1859       if (a != -1 ) {
  1860         e.id = a / 2;
  1861         d = ((a & 1) == 1);
  1862       } else {
  1863         e.id = -1;
  1864         d = true;
  1865       }
  1866     }
  1867 
  1868     static int id(Node v) { return v.id; }
  1869     int id(RedNode v) const { return _nodes[v.id].partition_index; }
  1870     int id(BlueNode v) const { return _nodes[v.id].partition_index; }
  1871     static int id(Arc e) { return e.id; }
  1872     static int id(Edge e) { return e.id; }
  1873 
  1874     static Node nodeFromId(int id) { return Node(id);}
  1875     static Arc arcFromId(int id) { return Arc(id);}
  1876     static Edge edgeFromId(int id) { return Edge(id);}
  1877 
  1878     bool valid(Node n) const {
  1879       return n.id >= 0 && n.id < static_cast<int>(_nodes.size()) &&
  1880         _nodes[n.id].prev != -2;
  1881     }
  1882 
  1883     bool valid(Arc a) const {
  1884       return a.id >= 0 && a.id < static_cast<int>(_arcs.size()) &&
  1885         _arcs[a.id].prev_out != -2;
  1886     }
  1887 
  1888     bool valid(Edge e) const {
  1889       return e.id >= 0 && 2 * e.id < static_cast<int>(_arcs.size()) &&
  1890         _arcs[2 * e.id].prev_out != -2;
  1891     }
  1892 
  1893     RedNode addRedNode() {
  1894       int n;
  1895 
  1896       if(first_free_red==-1) {
  1897         n = _nodes.size();
  1898         _nodes.push_back(NodeT());
  1899         _nodes[n].partition_index = ++max_red;
  1900         _nodes[n].red = true;
  1901       } else {
  1902         n = first_free_red;
  1903         first_free_red = _nodes[n].next;
  1904       }
  1905 
  1906       _nodes[n].next = first_node;
  1907       if (first_node != -1) _nodes[first_node].prev = n;
  1908       first_node = n;
  1909       _nodes[n].prev = -1;
  1910 
  1911       _nodes[n].partition_next = first_red;
  1912       if (first_red != -1) _nodes[first_red].partition_prev = n;
  1913       first_red = n;
  1914       _nodes[n].partition_prev = -1;
  1915 
  1916       _nodes[n].first_out = -1;
  1917 
  1918       return RedNode(n);
  1919     }
  1920 
  1921     BlueNode addBlueNode() {
  1922       int n;
  1923 
  1924       if(first_free_blue==-1) {
  1925         n = _nodes.size();
  1926         _nodes.push_back(NodeT());
  1927         _nodes[n].partition_index = ++max_blue;
  1928         _nodes[n].red = false;
  1929       } else {
  1930         n = first_free_blue;
  1931         first_free_blue = _nodes[n].next;
  1932       }
  1933 
  1934       _nodes[n].next = first_node;
  1935       if (first_node != -1) _nodes[first_node].prev = n;
  1936       first_node = n;
  1937       _nodes[n].prev = -1;
  1938 
  1939       _nodes[n].partition_next = first_blue;
  1940       if (first_blue != -1) _nodes[first_blue].partition_prev = n;
  1941       first_blue = n;
  1942       _nodes[n].partition_prev = -1;
  1943 
  1944       _nodes[n].first_out = -1;
  1945 
  1946       return BlueNode(n);
  1947     }
  1948 
  1949     Edge addEdge(Node u, Node v) {
  1950       int n;
  1951 
  1952       if (first_free_arc == -1) {
  1953         n = _arcs.size();
  1954         _arcs.push_back(ArcT());
  1955         _arcs.push_back(ArcT());
  1956       } else {
  1957         n = first_free_arc;
  1958         first_free_arc = _arcs[n].next_out;
  1959       }
  1960 
  1961       _arcs[n].target = u.id;
  1962       _arcs[n | 1].target = v.id;
  1963 
  1964       _arcs[n].next_out = _nodes[v.id].first_out;
  1965       if (_nodes[v.id].first_out != -1) {
  1966         _arcs[_nodes[v.id].first_out].prev_out = n;
  1967       }
  1968       _arcs[n].prev_out = -1;
  1969       _nodes[v.id].first_out = n;
  1970 
  1971       _arcs[n | 1].next_out = _nodes[u.id].first_out;
  1972       if (_nodes[u.id].first_out != -1) {
  1973         _arcs[_nodes[u.id].first_out].prev_out = (n | 1);
  1974       }
  1975       _arcs[n | 1].prev_out = -1;
  1976       _nodes[u.id].first_out = (n | 1);
  1977 
  1978       return Edge(n / 2);
  1979     }
  1980 
  1981     void erase(const Node& node) {
  1982       int n = node.id;
  1983 
  1984       if(_nodes[n].next != -1) {
  1985         _nodes[_nodes[n].next].prev = _nodes[n].prev;
  1986       }
  1987 
  1988       if(_nodes[n].prev != -1) {
  1989         _nodes[_nodes[n].prev].next = _nodes[n].next;
  1990       } else {
  1991         first_node = _nodes[n].next;
  1992       }
  1993 
  1994       if (_nodes[n].partition_next != -1) {
  1995         _nodes[_nodes[n].partition_next].partition_prev = _nodes[n].partition_prev;
  1996       }
  1997 
  1998       if (_nodes[n].partition_prev != -1) {
  1999         _nodes[_nodes[n].partition_prev].partition_next = _nodes[n].partition_next;
  2000       } else {
  2001         if (_nodes[n].red) {
  2002           first_red = _nodes[n].partition_next;
  2003         } else {
  2004           first_blue = _nodes[n].partition_next;
  2005         }
  2006       }
  2007 
  2008       if (_nodes[n].red) {
  2009         _nodes[n].next = first_free_red;
  2010         first_free_red = n;
  2011       } else {
  2012         _nodes[n].next = first_free_blue;
  2013         first_free_blue = n;
  2014       }
  2015       _nodes[n].prev = -2;
  2016     }
  2017 
  2018     void erase(const Edge& edge) {
  2019       int n = edge.id * 2;
  2020 
  2021       if (_arcs[n].next_out != -1) {
  2022         _arcs[_arcs[n].next_out].prev_out = _arcs[n].prev_out;
  2023       }
  2024 
  2025       if (_arcs[n].prev_out != -1) {
  2026         _arcs[_arcs[n].prev_out].next_out = _arcs[n].next_out;
  2027       } else {
  2028         _nodes[_arcs[n | 1].target].first_out = _arcs[n].next_out;
  2029       }
  2030 
  2031       if (_arcs[n | 1].next_out != -1) {
  2032         _arcs[_arcs[n | 1].next_out].prev_out = _arcs[n | 1].prev_out;
  2033       }
  2034 
  2035       if (_arcs[n | 1].prev_out != -1) {
  2036         _arcs[_arcs[n | 1].prev_out].next_out = _arcs[n | 1].next_out;
  2037       } else {
  2038         _nodes[_arcs[n].target].first_out = _arcs[n | 1].next_out;
  2039       }
  2040 
  2041       _arcs[n].next_out = first_free_arc;
  2042       first_free_arc = n;
  2043       _arcs[n].prev_out = -2;
  2044       _arcs[n | 1].prev_out = -2;
  2045 
  2046     }
  2047 
  2048     void clear() {
  2049       _arcs.clear();
  2050       _nodes.clear();
  2051       first_node = first_free_arc = first_red = first_blue =
  2052         max_red = max_blue = first_free_red = first_free_blue = -1;
  2053     }
  2054 
  2055   protected:
  2056 
  2057     void changeRed(Edge e, RedNode n) {
  2058       if(_arcs[(2 * e.id) | 1].next_out != -1) {
  2059         _arcs[_arcs[(2 * e.id) | 1].next_out].prev_out =
  2060           _arcs[(2 * e.id) | 1].prev_out;
  2061       }
  2062       if(_arcs[(2 * e.id) | 1].prev_out != -1) {
  2063         _arcs[_arcs[(2 * e.id) | 1].prev_out].next_out =
  2064           _arcs[(2 * e.id) | 1].next_out;
  2065       } else {
  2066         _nodes[_arcs[2 * e.id].target].first_out =
  2067           _arcs[(2 * e.id) | 1].next_out;
  2068       }
  2069 
  2070       if (_nodes[n.id].first_out != -1) {
  2071         _arcs[_nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
  2072       }
  2073       _arcs[2 * e.id].target = n.id;
  2074       _arcs[(2 * e.id) | 1].prev_out = -1;
  2075       _arcs[(2 * e.id) | 1].next_out = _nodes[n.id].first_out;
  2076       _nodes[n.id].first_out = ((2 * e.id) | 1);
  2077     }
  2078 
  2079     void changeBlue(Edge e, BlueNode n) {
  2080        if(_arcs[2 * e.id].next_out != -1) {
  2081         _arcs[_arcs[2 * e.id].next_out].prev_out = _arcs[2 * e.id].prev_out;
  2082       }
  2083       if(_arcs[2 * e.id].prev_out != -1) {
  2084         _arcs[_arcs[2 * e.id].prev_out].next_out =
  2085           _arcs[2 * e.id].next_out;
  2086       } else {
  2087         _nodes[_arcs[(2 * e.id) | 1].target].first_out =
  2088           _arcs[2 * e.id].next_out;
  2089       }
  2090 
  2091       if (_nodes[n.id].first_out != -1) {
  2092         _arcs[_nodes[n.id].first_out].prev_out = 2 * e.id;
  2093       }
  2094       _arcs[(2 * e.id) | 1].target = n.id;
  2095       _arcs[2 * e.id].prev_out = -1;
  2096       _arcs[2 * e.id].next_out = _nodes[n.id].first_out;
  2097       _nodes[n.id].first_out = 2 * e.id;
  2098     }
  2099 
  2100   };
  2101 
  2102   typedef BpGraphExtender<ListBpGraphBase> ExtendedListBpGraphBase;
  2103 
  2104 
  2105   /// \addtogroup graphs
  2106   /// @{
  2107 
  2108   ///A general undirected graph structure.
  2109 
  2110   ///\ref ListBpGraph is a versatile and fast undirected graph
  2111   ///implementation based on linked lists that are stored in
  2112   ///\c std::vector structures.
  2113   ///
  2114   ///This type fully conforms to the \ref concepts::BpGraph "BpGraph concept"
  2115   ///and it also provides several useful additional functionalities.
  2116   ///Most of its member functions and nested classes are documented
  2117   ///only in the concept class.
  2118   ///
  2119   ///This class provides only linear time counting for nodes, edges and arcs.
  2120   ///
  2121   ///\sa concepts::BpGraph
  2122   ///\sa ListDigraph
  2123   class ListBpGraph : public ExtendedListBpGraphBase {
  2124     typedef ExtendedListBpGraphBase Parent;
  2125 
  2126   private:
  2127     /// BpGraphs are \e not copy constructible. Use BpGraphCopy instead.
  2128     ListBpGraph(const ListBpGraph &) :ExtendedListBpGraphBase()  {};
  2129     /// \brief Assignment of a graph to another one is \e not allowed.
  2130     /// Use BpGraphCopy instead.
  2131     void operator=(const ListBpGraph &) {}
  2132   public:
  2133     /// Constructor
  2134 
  2135     /// Constructor.
  2136     ///
  2137     ListBpGraph() {}
  2138 
  2139     typedef Parent::IncEdgeIt IncEdgeIt;
  2140 
  2141     /// \brief Add a new red node to the graph.
  2142     ///
  2143     /// This function adds a red new node to the graph.
  2144     /// \return The new node.
  2145     RedNode addRedNode() { return Parent::addRedNode(); }
  2146 
  2147     /// \brief Add a new blue node to the graph.
  2148     ///
  2149     /// This function adds a blue new node to the graph.
  2150     /// \return The new node.
  2151     BlueNode addBlueNode() { return Parent::addBlueNode(); }
  2152 
  2153     /// \brief Add a new edge to the graph.
  2154     ///
  2155     /// This function adds a new edge to the graph between nodes
  2156     /// \c u and \c v with inherent orientation from node \c u to
  2157     /// node \c v.
  2158     /// \return The new edge.
  2159     Edge addEdge(RedNode u, BlueNode v) {
  2160       return Parent::addEdge(u, v);
  2161     }
  2162     Edge addEdge(BlueNode v, RedNode u) {
  2163       return Parent::addEdge(u, v);
  2164     }
  2165 
  2166     ///\brief Erase a node from the graph.
  2167     ///
  2168     /// This function erases the given node along with its incident arcs
  2169     /// from the graph.
  2170     ///
  2171     /// \note All iterators referencing the removed node or the incident
  2172     /// edges are invalidated, of course.
  2173     void erase(Node n) { Parent::erase(n); }
  2174 
  2175     ///\brief Erase an edge from the graph.
  2176     ///
  2177     /// This function erases the given edge from the graph.
  2178     ///
  2179     /// \note All iterators referencing the removed edge are invalidated,
  2180     /// of course.
  2181     void erase(Edge e) { Parent::erase(e); }
  2182     /// Node validity check
  2183 
  2184     /// This function gives back \c true if the given node is valid,
  2185     /// i.e. it is a real node of the graph.
  2186     ///
  2187     /// \warning A removed node could become valid again if new nodes are
  2188     /// added to the graph.
  2189     bool valid(Node n) const { return Parent::valid(n); }
  2190     /// Edge validity check
  2191 
  2192     /// This function gives back \c true if the given edge is valid,
  2193     /// i.e. it is a real edge of the graph.
  2194     ///
  2195     /// \warning A removed edge could become valid again if new edges are
  2196     /// added to the graph.
  2197     bool valid(Edge e) const { return Parent::valid(e); }
  2198     /// Arc validity check
  2199 
  2200     /// This function gives back \c true if the given arc is valid,
  2201     /// i.e. it is a real arc of the graph.
  2202     ///
  2203     /// \warning A removed arc could become valid again if new edges are
  2204     /// added to the graph.
  2205     bool valid(Arc a) const { return Parent::valid(a); }
  2206 
  2207     /// \brief Change the red node of an edge.
  2208     ///
  2209     /// This function changes the red node of the given edge \c e to \c n.
  2210     ///
  2211     ///\note \c EdgeIt and \c ArcIt iterators referencing the
  2212     ///changed edge are invalidated and all other iterators whose
  2213     ///base node is the changed node are also invalidated.
  2214     ///
  2215     ///\warning This functionality cannot be used together with the
  2216     ///Snapshot feature.
  2217     void changeRed(Edge e, RedNode n) {
  2218       Parent::changeRed(e, n);
  2219     }
  2220     /// \brief Change the blue node of an edge.
  2221     ///
  2222     /// This function changes the blue node of the given edge \c e to \c n.
  2223     ///
  2224     ///\note \c EdgeIt iterators referencing the changed edge remain
  2225     ///valid, but \c ArcIt iterators referencing the changed edge and
  2226     ///all other iterators whose base node is the changed node are also
  2227     ///invalidated.
  2228     ///
  2229     ///\warning This functionality cannot be used together with the
  2230     ///Snapshot feature.
  2231     void changeBlue(Edge e, BlueNode n) {
  2232       Parent::changeBlue(e, n);
  2233     }
  2234 
  2235     ///Clear the graph.
  2236 
  2237     ///This function erases all nodes and arcs from the graph.
  2238     ///
  2239     ///\note All iterators of the graph are invalidated, of course.
  2240     void clear() {
  2241       Parent::clear();
  2242     }
  2243 
  2244     /// Reserve memory for nodes.
  2245 
  2246     /// Using this function, it is possible to avoid superfluous memory
  2247     /// allocation: if you know that the graph you want to build will
  2248     /// be large (e.g. it will contain millions of nodes and/or edges),
  2249     /// then it is worth reserving space for this amount before starting
  2250     /// to build the graph.
  2251     /// \sa reserveEdge()
  2252     void reserveNode(int n) { _nodes.reserve(n); };
  2253 
  2254     /// Reserve memory for edges.
  2255 
  2256     /// Using this function, it is possible to avoid superfluous memory
  2257     /// allocation: if you know that the graph you want to build will
  2258     /// be large (e.g. it will contain millions of nodes and/or edges),
  2259     /// then it is worth reserving space for this amount before starting
  2260     /// to build the graph.
  2261     /// \sa reserveNode()
  2262     void reserveEdge(int m) { _arcs.reserve(2 * m); };
  2263 
  2264     /// \brief Class to make a snapshot of the graph and restore
  2265     /// it later.
  2266     ///
  2267     /// Class to make a snapshot of the graph and restore it later.
  2268     ///
  2269     /// The newly added nodes and edges can be removed
  2270     /// using the restore() function.
  2271     ///
  2272     /// \note After a state is restored, you cannot restore a later state,
  2273     /// i.e. you cannot add the removed nodes and edges again using
  2274     /// another Snapshot instance.
  2275     ///
  2276     /// \warning Node and edge deletions and other modifications
  2277     /// (e.g. changing the end-nodes of edges or contracting nodes)
  2278     /// cannot be restored. These events invalidate the snapshot.
  2279     /// However, the edges and nodes that were added to the graph after
  2280     /// making the current snapshot can be removed without invalidating it.
  2281     class Snapshot {
  2282     protected:
  2283 
  2284       typedef Parent::NodeNotifier NodeNotifier;
  2285 
  2286       class NodeObserverProxy : public NodeNotifier::ObserverBase {
  2287       public:
  2288 
  2289         NodeObserverProxy(Snapshot& _snapshot)
  2290           : snapshot(_snapshot) {}
  2291 
  2292         using NodeNotifier::ObserverBase::attach;
  2293         using NodeNotifier::ObserverBase::detach;
  2294         using NodeNotifier::ObserverBase::attached;
  2295 
  2296       protected:
  2297 
  2298         virtual void add(const Node& node) {
  2299           snapshot.addNode(node);
  2300         }
  2301         virtual void add(const std::vector<Node>& nodes) {
  2302           for (int i = nodes.size() - 1; i >= 0; --i) {
  2303             snapshot.addNode(nodes[i]);
  2304           }
  2305         }
  2306         virtual void erase(const Node& node) {
  2307           snapshot.eraseNode(node);
  2308         }
  2309         virtual void erase(const std::vector<Node>& nodes) {
  2310           for (int i = 0; i < int(nodes.size()); ++i) {
  2311             snapshot.eraseNode(nodes[i]);
  2312           }
  2313         }
  2314         virtual void build() {
  2315           Node node;
  2316           std::vector<Node> nodes;
  2317           for (notifier()->first(node); node != INVALID;
  2318                notifier()->next(node)) {
  2319             nodes.push_back(node);
  2320           }
  2321           for (int i = nodes.size() - 1; i >= 0; --i) {
  2322             snapshot.addNode(nodes[i]);
  2323           }
  2324         }
  2325         virtual void clear() {
  2326           Node node;
  2327           for (notifier()->first(node); node != INVALID;
  2328                notifier()->next(node)) {
  2329             snapshot.eraseNode(node);
  2330           }
  2331         }
  2332 
  2333         Snapshot& snapshot;
  2334       };
  2335 
  2336       class EdgeObserverProxy : public EdgeNotifier::ObserverBase {
  2337       public:
  2338 
  2339         EdgeObserverProxy(Snapshot& _snapshot)
  2340           : snapshot(_snapshot) {}
  2341 
  2342         using EdgeNotifier::ObserverBase::attach;
  2343         using EdgeNotifier::ObserverBase::detach;
  2344         using EdgeNotifier::ObserverBase::attached;
  2345 
  2346       protected:
  2347 
  2348         virtual void add(const Edge& edge) {
  2349           snapshot.addEdge(edge);
  2350         }
  2351         virtual void add(const std::vector<Edge>& edges) {
  2352           for (int i = edges.size() - 1; i >= 0; --i) {
  2353             snapshot.addEdge(edges[i]);
  2354           }
  2355         }
  2356         virtual void erase(const Edge& edge) {
  2357           snapshot.eraseEdge(edge);
  2358         }
  2359         virtual void erase(const std::vector<Edge>& edges) {
  2360           for (int i = 0; i < int(edges.size()); ++i) {
  2361             snapshot.eraseEdge(edges[i]);
  2362           }
  2363         }
  2364         virtual void build() {
  2365           Edge edge;
  2366           std::vector<Edge> edges;
  2367           for (notifier()->first(edge); edge != INVALID;
  2368                notifier()->next(edge)) {
  2369             edges.push_back(edge);
  2370           }
  2371           for (int i = edges.size() - 1; i >= 0; --i) {
  2372             snapshot.addEdge(edges[i]);
  2373           }
  2374         }
  2375         virtual void clear() {
  2376           Edge edge;
  2377           for (notifier()->first(edge); edge != INVALID;
  2378                notifier()->next(edge)) {
  2379             snapshot.eraseEdge(edge);
  2380           }
  2381         }
  2382 
  2383         Snapshot& snapshot;
  2384       };
  2385 
  2386       ListBpGraph *graph;
  2387 
  2388       NodeObserverProxy node_observer_proxy;
  2389       EdgeObserverProxy edge_observer_proxy;
  2390 
  2391       std::list<Node> added_nodes;
  2392       std::list<Edge> added_edges;
  2393 
  2394 
  2395       void addNode(const Node& node) {
  2396         added_nodes.push_front(node);
  2397       }
  2398       void eraseNode(const Node& node) {
  2399         std::list<Node>::iterator it =
  2400           std::find(added_nodes.begin(), added_nodes.end(), node);
  2401         if (it == added_nodes.end()) {
  2402           clear();
  2403           edge_observer_proxy.detach();
  2404           throw NodeNotifier::ImmediateDetach();
  2405         } else {
  2406           added_nodes.erase(it);
  2407         }
  2408       }
  2409 
  2410       void addEdge(const Edge& edge) {
  2411         added_edges.push_front(edge);
  2412       }
  2413       void eraseEdge(const Edge& edge) {
  2414         std::list<Edge>::iterator it =
  2415           std::find(added_edges.begin(), added_edges.end(), edge);
  2416         if (it == added_edges.end()) {
  2417           clear();
  2418           node_observer_proxy.detach();
  2419           throw EdgeNotifier::ImmediateDetach();
  2420         } else {
  2421           added_edges.erase(it);
  2422         }
  2423       }
  2424 
  2425       void attach(ListBpGraph &_graph) {
  2426         graph = &_graph;
  2427         node_observer_proxy.attach(graph->notifier(Node()));
  2428         edge_observer_proxy.attach(graph->notifier(Edge()));
  2429       }
  2430 
  2431       void detach() {
  2432         node_observer_proxy.detach();
  2433         edge_observer_proxy.detach();
  2434       }
  2435 
  2436       bool attached() const {
  2437         return node_observer_proxy.attached();
  2438       }
  2439 
  2440       void clear() {
  2441         added_nodes.clear();
  2442         added_edges.clear();
  2443       }
  2444 
  2445     public:
  2446 
  2447       /// \brief Default constructor.
  2448       ///
  2449       /// Default constructor.
  2450       /// You have to call save() to actually make a snapshot.
  2451       Snapshot()
  2452         : graph(0), node_observer_proxy(*this),
  2453           edge_observer_proxy(*this) {}
  2454 
  2455       /// \brief Constructor that immediately makes a snapshot.
  2456       ///
  2457       /// This constructor immediately makes a snapshot of the given graph.
  2458       Snapshot(ListBpGraph &gr)
  2459         : node_observer_proxy(*this),
  2460           edge_observer_proxy(*this) {
  2461         attach(gr);
  2462       }
  2463 
  2464       /// \brief Make a snapshot.
  2465       ///
  2466       /// This function makes a snapshot of the given graph.
  2467       /// It can be called more than once. In case of a repeated
  2468       /// call, the previous snapshot gets lost.
  2469       void save(ListBpGraph &gr) {
  2470         if (attached()) {
  2471           detach();
  2472           clear();
  2473         }
  2474         attach(gr);
  2475       }
  2476 
  2477       /// \brief Undo the changes until the last snapshot.
  2478       ///
  2479       /// This function undos the changes until the last snapshot
  2480       /// created by save() or Snapshot(ListBpGraph&).
  2481       ///
  2482       /// \warning This method invalidates the snapshot, i.e. repeated
  2483       /// restoring is not supported unless you call save() again.
  2484       void restore() {
  2485         detach();
  2486         for(std::list<Edge>::iterator it = added_edges.begin();
  2487             it != added_edges.end(); ++it) {
  2488           graph->erase(*it);
  2489         }
  2490         for(std::list<Node>::iterator it = added_nodes.begin();
  2491             it != added_nodes.end(); ++it) {
  2492           graph->erase(*it);
  2493         }
  2494         clear();
  2495       }
  2496 
  2497       /// \brief Returns \c true if the snapshot is valid.
  2498       ///
  2499       /// This function returns \c true if the snapshot is valid.
  2500       bool valid() const {
  2501         return attached();
  2502       }
  2503     };
  2504   };
  2505 
  2506   /// @}
  2507 } //namespace lemon
  2508 
  2509 
  2510 #endif