lemon/list_graph.h
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 09 Feb 2010 23:29:51 +0100
changeset 823 a7e93de12cbd
parent 787 c2230649a493
parent 786 e20173729589
child 877 141f9c0db4a3
permissions -rw-r--r--
Add a warning about huge capacities in Preflow (#319)
     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-2009
     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 incomming 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::OutArcIt 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 } //namespace lemon
  1603 
  1604 
  1605 #endif