lemon/list_graph.h
author Alpar Juttner <alpar@cs.elte.hu>
Fri, 29 Feb 2008 11:01:39 +0000
changeset 103 b68a7e348e00
parent 57 c1acf0018c0a
child 149 2f7ae34e1333
permissions -rw-r--r--
Port kruskal() and UnionFind from svn -r3468

The class type interface of Kruskal has not been ported yet
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2008
     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, ListGraph classes.
    25 
    26 #include <lemon/bits/graph_extender.h>
    27 
    28 #include <vector>
    29 #include <list>
    30 
    31 namespace lemon {
    32 
    33   class ListDigraphBase {
    34 
    35   protected:
    36     struct NodeT {
    37       int first_in, first_out;
    38       int prev, next;
    39     };
    40  
    41     struct ArcT {
    42       int target, source;
    43       int prev_in, prev_out;
    44       int next_in, next_out;
    45     };
    46 
    47     std::vector<NodeT> nodes;
    48 
    49     int first_node;
    50 
    51     int first_free_node;
    52 
    53     std::vector<ArcT> arcs;
    54 
    55     int first_free_arc;
    56     
    57   public:
    58     
    59     typedef ListDigraphBase Digraph;
    60     
    61     class Node {
    62       friend class ListDigraphBase;
    63     protected:
    64 
    65       int id;
    66       explicit Node(int pid) { id = pid;}
    67 
    68     public:
    69       Node() {}
    70       Node (Invalid) { id = -1; }
    71       bool operator==(const Node& node) const {return id == node.id;}
    72       bool operator!=(const Node& node) const {return id != node.id;}
    73       bool operator<(const Node& node) const {return id < node.id;}
    74     };
    75 
    76     class Arc {
    77       friend class ListDigraphBase;
    78     protected:
    79 
    80       int id;
    81       explicit Arc(int pid) { id = pid;}
    82 
    83     public:
    84       Arc() {}
    85       Arc (Invalid) { id = -1; }
    86       bool operator==(const Arc& arc) const {return id == arc.id;}
    87       bool operator!=(const Arc& arc) const {return id != arc.id;}
    88       bool operator<(const Arc& arc) const {return id < arc.id;}
    89     };
    90 
    91 
    92 
    93     ListDigraphBase()
    94       : nodes(), first_node(-1),
    95 	first_free_node(-1), arcs(), first_free_arc(-1) {}
    96 
    97     
    98     int maxNodeId() const { return nodes.size()-1; } 
    99     int maxArcId() const { return arcs.size()-1; }
   100 
   101     Node source(Arc e) const { return Node(arcs[e.id].source); }
   102     Node target(Arc e) const { return Node(arcs[e.id].target); }
   103 
   104 
   105     void first(Node& node) const { 
   106       node.id = first_node;
   107     }
   108 
   109     void next(Node& node) const {
   110       node.id = nodes[node.id].next;
   111     }
   112 
   113 
   114     void first(Arc& arc) const { 
   115       int n;
   116       for(n = first_node; 
   117 	  n!=-1 && nodes[n].first_in == -1; 
   118 	  n = nodes[n].next);
   119       arc.id = (n == -1) ? -1 : nodes[n].first_in;
   120     }
   121 
   122     void next(Arc& arc) const {
   123       if (arcs[arc.id].next_in != -1) {
   124 	arc.id = arcs[arc.id].next_in;
   125       } else {
   126 	int n;
   127 	for(n = nodes[arcs[arc.id].target].next;
   128 	  n!=-1 && nodes[n].first_in == -1; 
   129 	  n = nodes[n].next);
   130 	arc.id = (n == -1) ? -1 : nodes[n].first_in;
   131       }      
   132     }
   133 
   134     void firstOut(Arc &e, const Node& v) const {
   135       e.id = nodes[v.id].first_out;
   136     }
   137     void nextOut(Arc &e) const {
   138       e.id=arcs[e.id].next_out;
   139     }
   140 
   141     void firstIn(Arc &e, const Node& v) const {
   142       e.id = nodes[v.id].first_in;
   143     }
   144     void nextIn(Arc &e) const {
   145       e.id=arcs[e.id].next_in;
   146     }
   147 
   148     
   149     static int id(Node v) { return v.id; }
   150     static int id(Arc e) { return e.id; }
   151 
   152     static Node nodeFromId(int id) { return Node(id);}
   153     static Arc arcFromId(int id) { return Arc(id);}
   154 
   155     Node addNode() {     
   156       int n;
   157       
   158       if(first_free_node==-1) {
   159 	n = nodes.size();
   160 	nodes.push_back(NodeT());
   161       } else {
   162 	n = first_free_node;
   163 	first_free_node = nodes[n].next;
   164       }
   165       
   166       nodes[n].next = first_node;
   167       if(first_node != -1) nodes[first_node].prev = n;
   168       first_node = n;
   169       nodes[n].prev = -1;
   170       
   171       nodes[n].first_in = nodes[n].first_out = -1;
   172       
   173       return Node(n);
   174     }
   175     
   176     Arc addArc(Node u, Node v) {
   177       int n;      
   178 
   179       if (first_free_arc == -1) {
   180 	n = arcs.size();
   181 	arcs.push_back(ArcT());
   182       } else {
   183 	n = first_free_arc;
   184 	first_free_arc = arcs[n].next_in;
   185       }
   186       
   187       arcs[n].source = u.id; 
   188       arcs[n].target = v.id;
   189 
   190       arcs[n].next_out = nodes[u.id].first_out;
   191       if(nodes[u.id].first_out != -1) {
   192 	arcs[nodes[u.id].first_out].prev_out = n;
   193       }
   194       
   195       arcs[n].next_in = nodes[v.id].first_in;
   196       if(nodes[v.id].first_in != -1) {
   197 	arcs[nodes[v.id].first_in].prev_in = n;
   198       }
   199       
   200       arcs[n].prev_in = arcs[n].prev_out = -1;
   201 	
   202       nodes[u.id].first_out = nodes[v.id].first_in = n;
   203 
   204       return Arc(n);
   205     }
   206     
   207     void erase(const Node& node) {
   208       int n = node.id;
   209       
   210       if(nodes[n].next != -1) {
   211 	nodes[nodes[n].next].prev = nodes[n].prev;
   212       }
   213       
   214       if(nodes[n].prev != -1) {
   215 	nodes[nodes[n].prev].next = nodes[n].next;
   216       } else {
   217 	first_node = nodes[n].next;
   218       }
   219       
   220       nodes[n].next = first_free_node;
   221       first_free_node = n;
   222 
   223     }
   224     
   225     void erase(const Arc& arc) {
   226       int n = arc.id;
   227       
   228       if(arcs[n].next_in!=-1) {
   229 	arcs[arcs[n].next_in].prev_in = arcs[n].prev_in;
   230       }
   231 
   232       if(arcs[n].prev_in!=-1) {
   233 	arcs[arcs[n].prev_in].next_in = arcs[n].next_in;
   234       } else {
   235 	nodes[arcs[n].target].first_in = arcs[n].next_in;
   236       }
   237 
   238       
   239       if(arcs[n].next_out!=-1) {
   240 	arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
   241       } 
   242 
   243       if(arcs[n].prev_out!=-1) {
   244 	arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
   245       } else {
   246 	nodes[arcs[n].source].first_out = arcs[n].next_out;
   247       }
   248       
   249       arcs[n].next_in = first_free_arc;
   250       first_free_arc = n;      
   251 
   252     }
   253 
   254     void clear() {
   255       arcs.clear();
   256       nodes.clear();
   257       first_node = first_free_node = first_free_arc = -1;
   258     }
   259 
   260   protected:
   261     void changeTarget(Arc e, Node n) 
   262     {
   263       if(arcs[e.id].next_in != -1)
   264 	arcs[arcs[e.id].next_in].prev_in = arcs[e.id].prev_in;
   265       if(arcs[e.id].prev_in != -1)
   266 	arcs[arcs[e.id].prev_in].next_in = arcs[e.id].next_in;
   267       else nodes[arcs[e.id].target].first_in = arcs[e.id].next_in;
   268       if (nodes[n.id].first_in != -1) {
   269 	arcs[nodes[n.id].first_in].prev_in = e.id;
   270       }
   271       arcs[e.id].target = n.id;
   272       arcs[e.id].prev_in = -1;
   273       arcs[e.id].next_in = nodes[n.id].first_in;
   274       nodes[n.id].first_in = e.id;
   275     }
   276     void changeSource(Arc e, Node n) 
   277     {
   278       if(arcs[e.id].next_out != -1)
   279 	arcs[arcs[e.id].next_out].prev_out = arcs[e.id].prev_out;
   280       if(arcs[e.id].prev_out != -1)
   281 	arcs[arcs[e.id].prev_out].next_out = arcs[e.id].next_out;
   282       else nodes[arcs[e.id].source].first_out = arcs[e.id].next_out;
   283       if (nodes[n.id].first_out != -1) {
   284 	arcs[nodes[n.id].first_out].prev_out = e.id;
   285       }
   286       arcs[e.id].source = n.id;
   287       arcs[e.id].prev_out = -1;
   288       arcs[e.id].next_out = nodes[n.id].first_out;
   289       nodes[n.id].first_out = e.id;
   290     }
   291 
   292   };
   293 
   294   typedef DigraphExtender<ListDigraphBase> ExtendedListDigraphBase;
   295 
   296   /// \addtogroup graphs
   297   /// @{
   298 
   299   ///A general directed graph structure. 
   300 
   301   ///\ref ListDigraph is a simple and fast <em>directed graph</em> 
   302   ///implementation based on static linked lists that are stored in 
   303   ///\c std::vector structures.   
   304   ///
   305   ///It conforms to the \ref concepts::Digraph "Digraph concept" and it
   306   ///also provides several useful additional functionalities.
   307   ///Most of the member functions and nested classes are documented
   308   ///only in the concept class.
   309   ///
   310   ///An important extra feature of this digraph implementation is that
   311   ///its maps are real \ref concepts::ReferenceMap "reference map"s.
   312   ///
   313   ///\sa concepts::Digraph
   314 
   315   class ListDigraph : public ExtendedListDigraphBase {
   316   private:
   317     ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
   318     
   319     ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
   320     ///
   321     ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {};
   322     ///\brief Assignment of ListDigraph to another one is \e not allowed.
   323     ///Use copyDigraph() instead.
   324 
   325     ///Assignment of ListDigraph to another one is \e not allowed.
   326     ///Use copyDigraph() instead.
   327     void operator=(const ListDigraph &) {}
   328   public:
   329 
   330     typedef ExtendedListDigraphBase Parent;
   331 
   332     /// Constructor
   333     
   334     /// Constructor.
   335     ///
   336     ListDigraph() {}
   337 
   338     ///Add a new node to the digraph.
   339     
   340     ///Add a new node to the digraph.
   341     ///\return the new node.
   342     Node addNode() { return Parent::addNode(); }
   343 
   344     ///Add a new arc to the digraph.
   345     
   346     ///Add a new arc to the digraph with source node \c s
   347     ///and target node \c t.
   348     ///\return the new arc.
   349     Arc addArc(const Node& s, const Node& t) { 
   350       return Parent::addArc(s, t); 
   351     }
   352 
   353     /// Change the target of \c e to \c n
   354 
   355     /// Change the target of \c e to \c n
   356     ///
   357     ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing
   358     ///the changed arc remain valid. However <tt>InArcIt</tt>s are
   359     ///invalidated.
   360     ///
   361     ///\warning This functionality cannot be used together with the Snapshot
   362     ///feature.
   363     void changeTarget(Arc e, Node n) { 
   364       Parent::changeTarget(e,n); 
   365     }
   366     /// Change the source of \c e to \c n
   367 
   368     /// Change the source of \c e to \c n
   369     ///
   370     ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s referencing
   371     ///the changed arc remain valid. However <tt>OutArcIt</tt>s are
   372     ///invalidated.
   373     ///
   374     ///\warning This functionality cannot be used together with the Snapshot
   375     ///feature.
   376     void changeSource(Arc e, Node n) { 
   377       Parent::changeSource(e,n);
   378     }
   379 
   380     /// Invert the direction of an arc.
   381 
   382     ///\note The <tt>ArcIt</tt>s referencing the changed arc remain
   383     ///valid. However <tt>OutArcIt</tt>s and <tt>InArcIt</tt>s are
   384     ///invalidated.
   385     ///
   386     ///\warning This functionality cannot be used together with the Snapshot
   387     ///feature.
   388     void reverseArc(Arc e) {
   389       Node t=target(e);
   390       changeTarget(e,source(e));
   391       changeSource(e,t);
   392     }
   393 
   394     /// Reserve memory for nodes.
   395 
   396     /// Using this function it is possible to avoid the superfluous memory
   397     /// allocation: if you know that the digraph you want to build will
   398     /// be very large (e.g. it will contain millions of nodes and/or arcs)
   399     /// then it is worth reserving space for this amount before starting
   400     /// to build the digraph.
   401     /// \sa reserveArc
   402     void reserveNode(int n) { nodes.reserve(n); };
   403 
   404     /// Reserve memory for arcs.
   405 
   406     /// Using this function it is possible to avoid the superfluous memory
   407     /// allocation: if you know that the digraph you want to build will
   408     /// be very large (e.g. it will contain millions of nodes and/or arcs)
   409     /// then it is worth reserving space for this amount before starting
   410     /// to build the digraph.
   411     /// \sa reserveNode
   412     void reserveArc(int m) { arcs.reserve(m); };
   413 
   414     ///Contract two nodes.
   415 
   416     ///This function contracts two nodes.
   417     ///Node \p b will be removed but instead of deleting
   418     ///incident arcs, they will be joined to \p a.
   419     ///The last parameter \p r controls whether to remove loops. \c true
   420     ///means that loops will be removed.
   421     ///
   422     ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
   423     ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s
   424     ///may be invalidated.
   425     ///
   426     ///\warning This functionality cannot be used together with the Snapshot
   427     ///feature.
   428     void contract(Node a, Node b, bool r = true) 
   429     {
   430       for(OutArcIt e(*this,b);e!=INVALID;) {
   431 	OutArcIt f=e;
   432 	++f;
   433 	if(r && target(e)==a) erase(e);
   434 	else changeSource(e,a);
   435 	e=f;
   436       }
   437       for(InArcIt e(*this,b);e!=INVALID;) {
   438 	InArcIt f=e;
   439 	++f;
   440 	if(r && source(e)==a) erase(e);
   441 	else changeTarget(e,a);
   442 	e=f;
   443       }
   444       erase(b);
   445     }
   446 
   447     ///Split a node.
   448 
   449     ///This function splits a node. First a new node is added to the digraph,
   450     ///then the source of each outgoing arc of \c n is moved to this new node.
   451     ///If \c connect is \c true (this is the default value), then a new arc
   452     ///from \c n to the newly created node is also added.
   453     ///\return The newly created node.
   454     ///
   455     ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
   456     ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s may
   457     ///be invalidated.  
   458     ///
   459     ///\warning This functionality cannot be used together with the
   460     ///Snapshot feature.
   461     ///
   462     ///\todo It could be implemented in a bit faster way.
   463     Node split(Node n, bool connect = true) {
   464       Node b = addNode();
   465       for(OutArcIt e(*this,n);e!=INVALID;) {
   466  	OutArcIt f=e;
   467 	++f;
   468 	changeSource(e,b);
   469 	e=f;
   470       }
   471       if (connect) addArc(n,b);
   472       return b;
   473     }
   474       
   475     ///Split an arc.
   476 
   477     ///This function splits an arc. First a new node \c b is added to
   478     ///the digraph, then the original arc is re-targeted to \c
   479     ///b. Finally an arc from \c b to the original target is added.
   480     ///
   481     ///\return The newly created node.
   482     ///
   483     ///\warning This functionality cannot be used together with the
   484     ///Snapshot feature.
   485     Node split(Arc e) {
   486       Node b = addNode();
   487       addArc(b,target(e));
   488       changeTarget(e,b);
   489       return b;
   490     }
   491       
   492     /// \brief Class to make a snapshot of the digraph and restore
   493     /// it later.
   494     ///
   495     /// Class to make a snapshot of the digraph and restore it later.
   496     ///
   497     /// The newly added nodes and arcs can be removed using the
   498     /// restore() function.
   499     ///
   500     /// \warning Arc and node deletions and other modifications (e.g.
   501     /// contracting, splitting, reversing arcs or nodes) cannot be 
   502     /// restored. These events invalidate the snapshot. 
   503     class Snapshot {
   504     protected:
   505 
   506       typedef Parent::NodeNotifier NodeNotifier;
   507 
   508       class NodeObserverProxy : public NodeNotifier::ObserverBase {
   509       public:
   510 
   511         NodeObserverProxy(Snapshot& _snapshot)
   512           : snapshot(_snapshot) {}
   513 
   514         using NodeNotifier::ObserverBase::attach;
   515         using NodeNotifier::ObserverBase::detach;
   516         using NodeNotifier::ObserverBase::attached;
   517         
   518       protected:
   519         
   520         virtual void add(const Node& node) {
   521           snapshot.addNode(node);
   522         }
   523         virtual void add(const std::vector<Node>& nodes) {
   524           for (int i = nodes.size() - 1; i >= 0; ++i) {
   525             snapshot.addNode(nodes[i]);
   526           }
   527         }
   528         virtual void erase(const Node& node) {
   529           snapshot.eraseNode(node);
   530         }
   531         virtual void erase(const std::vector<Node>& nodes) {
   532           for (int i = 0; i < int(nodes.size()); ++i) {
   533             snapshot.eraseNode(nodes[i]);
   534           }
   535         }
   536         virtual void build() {
   537           Node node;
   538           std::vector<Node> nodes;
   539           for (notifier()->first(node); node != INVALID; 
   540                notifier()->next(node)) {
   541             nodes.push_back(node);
   542           }
   543           for (int i = nodes.size() - 1; i >= 0; --i) {
   544             snapshot.addNode(nodes[i]);
   545           }
   546         }
   547         virtual void clear() {
   548           Node node;
   549           for (notifier()->first(node); node != INVALID; 
   550                notifier()->next(node)) {
   551             snapshot.eraseNode(node);
   552           }
   553         }
   554 
   555         Snapshot& snapshot;
   556       };
   557 
   558       class ArcObserverProxy : public ArcNotifier::ObserverBase {
   559       public:
   560 
   561         ArcObserverProxy(Snapshot& _snapshot)
   562           : snapshot(_snapshot) {}
   563 
   564         using ArcNotifier::ObserverBase::attach;
   565         using ArcNotifier::ObserverBase::detach;
   566         using ArcNotifier::ObserverBase::attached;
   567         
   568       protected:
   569 
   570         virtual void add(const Arc& arc) {
   571           snapshot.addArc(arc);
   572         }
   573         virtual void add(const std::vector<Arc>& arcs) {
   574           for (int i = arcs.size() - 1; i >= 0; ++i) {
   575             snapshot.addArc(arcs[i]);
   576           }
   577         }
   578         virtual void erase(const Arc& arc) {
   579           snapshot.eraseArc(arc);
   580         }
   581         virtual void erase(const std::vector<Arc>& arcs) {
   582           for (int i = 0; i < int(arcs.size()); ++i) {
   583             snapshot.eraseArc(arcs[i]);
   584           }
   585         }
   586         virtual void build() {
   587           Arc arc;
   588           std::vector<Arc> arcs;
   589           for (notifier()->first(arc); arc != INVALID; 
   590                notifier()->next(arc)) {
   591             arcs.push_back(arc);
   592           }
   593           for (int i = arcs.size() - 1; i >= 0; --i) {
   594             snapshot.addArc(arcs[i]);
   595           }
   596         }
   597         virtual void clear() {
   598           Arc arc;
   599           for (notifier()->first(arc); arc != INVALID; 
   600                notifier()->next(arc)) {
   601             snapshot.eraseArc(arc);
   602           }
   603         }
   604 
   605         Snapshot& snapshot;
   606       };
   607       
   608       ListDigraph *digraph;
   609 
   610       NodeObserverProxy node_observer_proxy;
   611       ArcObserverProxy arc_observer_proxy;
   612 
   613       std::list<Node> added_nodes;
   614       std::list<Arc> added_arcs;
   615 
   616 
   617       void addNode(const Node& node) {
   618         added_nodes.push_front(node);        
   619       }
   620       void eraseNode(const Node& node) {
   621         std::list<Node>::iterator it = 
   622           std::find(added_nodes.begin(), added_nodes.end(), node);
   623         if (it == added_nodes.end()) {
   624           clear();
   625           arc_observer_proxy.detach();
   626           throw NodeNotifier::ImmediateDetach();
   627         } else {
   628           added_nodes.erase(it);
   629         }
   630       }
   631 
   632       void addArc(const Arc& arc) {
   633         added_arcs.push_front(arc);        
   634       }
   635       void eraseArc(const Arc& arc) {
   636         std::list<Arc>::iterator it = 
   637           std::find(added_arcs.begin(), added_arcs.end(), arc);
   638         if (it == added_arcs.end()) {
   639           clear();
   640           node_observer_proxy.detach(); 
   641           throw ArcNotifier::ImmediateDetach();
   642         } else {
   643           added_arcs.erase(it);
   644         }        
   645       }
   646 
   647       void attach(ListDigraph &_digraph) {
   648 	digraph = &_digraph;
   649 	node_observer_proxy.attach(digraph->notifier(Node()));
   650         arc_observer_proxy.attach(digraph->notifier(Arc()));
   651       }
   652             
   653       void detach() {
   654 	node_observer_proxy.detach();
   655 	arc_observer_proxy.detach();
   656       }
   657 
   658       bool attached() const {
   659         return node_observer_proxy.attached();
   660       }
   661 
   662       void clear() {
   663         added_nodes.clear();
   664         added_arcs.clear();        
   665       }
   666 
   667     public:
   668 
   669       /// \brief Default constructor.
   670       ///
   671       /// Default constructor.
   672       /// To actually make a snapshot you must call save().
   673       Snapshot() 
   674         : digraph(0), node_observer_proxy(*this), 
   675           arc_observer_proxy(*this) {}
   676       
   677       /// \brief Constructor that immediately makes a snapshot.
   678       ///      
   679       /// This constructor immediately makes a snapshot of the digraph.
   680       /// \param _digraph The digraph we make a snapshot of.
   681       Snapshot(ListDigraph &_digraph) 
   682         : node_observer_proxy(*this), 
   683           arc_observer_proxy(*this) {
   684 	attach(_digraph);
   685       }
   686       
   687       /// \brief Make a snapshot.
   688       ///
   689       /// Make a snapshot of the digraph.
   690       ///
   691       /// This function can be called more than once. In case of a repeated
   692       /// call, the previous snapshot gets lost.
   693       /// \param _digraph The digraph we make the snapshot of.
   694       void save(ListDigraph &_digraph) {
   695         if (attached()) {
   696           detach();
   697           clear();
   698         }
   699         attach(_digraph);
   700       }
   701       
   702       /// \brief Undo the changes until the last snapshot.
   703       // 
   704       /// Undo the changes until the last snapshot created by save().
   705       void restore() {
   706 	detach();
   707 	for(std::list<Arc>::iterator it = added_arcs.begin(); 
   708             it != added_arcs.end(); ++it) {
   709 	  digraph->erase(*it);
   710 	}
   711 	for(std::list<Node>::iterator it = added_nodes.begin(); 
   712             it != added_nodes.end(); ++it) {
   713 	  digraph->erase(*it);
   714 	}
   715         clear();
   716       }
   717 
   718       /// \brief Gives back true when the snapshot is valid.
   719       ///
   720       /// Gives back true when the snapshot is valid.
   721       bool valid() const {
   722         return attached();
   723       }
   724     };
   725     
   726   };
   727 
   728   ///@}
   729 
   730   class ListGraphBase {
   731 
   732   protected:
   733 
   734     struct NodeT {
   735       int first_out;
   736       int prev, next;
   737     };
   738  
   739     struct ArcT {
   740       int target;
   741       int prev_out, next_out;
   742     };
   743 
   744     std::vector<NodeT> nodes;
   745 
   746     int first_node;
   747 
   748     int first_free_node;
   749 
   750     std::vector<ArcT> arcs;
   751 
   752     int first_free_arc;
   753     
   754   public:
   755     
   756     typedef ListGraphBase Digraph;
   757 
   758     class Node;
   759     class Arc;
   760     class Edge;
   761     
   762     class Node {
   763       friend class ListGraphBase;
   764     protected:
   765 
   766       int id;
   767       explicit Node(int pid) { id = pid;}
   768 
   769     public:
   770       Node() {}
   771       Node (Invalid) { id = -1; }
   772       bool operator==(const Node& node) const {return id == node.id;}
   773       bool operator!=(const Node& node) const {return id != node.id;}
   774       bool operator<(const Node& node) const {return id < node.id;}
   775     };
   776 
   777     class Edge {
   778       friend class ListGraphBase;
   779     protected:
   780 
   781       int id;
   782       explicit Edge(int pid) { id = pid;}
   783 
   784     public:
   785       Edge() {}
   786       Edge (Invalid) { id = -1; }
   787       bool operator==(const Edge& edge) const {return id == edge.id;}
   788       bool operator!=(const Edge& edge) const {return id != edge.id;}
   789       bool operator<(const Edge& edge) const {return id < edge.id;}
   790     };
   791 
   792     class Arc {
   793       friend class ListGraphBase;
   794     protected:
   795 
   796       int id;
   797       explicit Arc(int pid) { id = pid;}
   798 
   799     public:
   800       operator Edge() const { return edgeFromId(id / 2); }
   801 
   802       Arc() {}
   803       Arc (Invalid) { id = -1; }
   804       bool operator==(const Arc& arc) const {return id == arc.id;}
   805       bool operator!=(const Arc& arc) const {return id != arc.id;}
   806       bool operator<(const Arc& arc) const {return id < arc.id;}
   807     };
   808 
   809 
   810 
   811     ListGraphBase()
   812       : nodes(), first_node(-1),
   813 	first_free_node(-1), arcs(), first_free_arc(-1) {}
   814 
   815     
   816     int maxNodeId() const { return nodes.size()-1; } 
   817     int maxEdgeId() const { return arcs.size() / 2 - 1; }
   818     int maxArcId() const { return arcs.size()-1; }
   819 
   820     Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); }
   821     Node target(Arc e) const { return Node(arcs[e.id].target); }
   822 
   823     Node u(Edge e) const { return Node(arcs[2 * e.id].target); }
   824     Node v(Edge e) const { return Node(arcs[2 * e.id + 1].target); }
   825 
   826     static bool direction(Arc e) {
   827       return (e.id & 1) == 1;
   828     }
   829 
   830     static Arc direct(Edge e, bool d) {
   831       return Arc(e.id * 2 + (d ? 1 : 0));
   832     }
   833 
   834     void first(Node& node) const { 
   835       node.id = first_node;
   836     }
   837 
   838     void next(Node& node) const {
   839       node.id = nodes[node.id].next;
   840     }
   841 
   842     void first(Arc& e) const { 
   843       int n = first_node;
   844       while (n != -1 && nodes[n].first_out == -1) {
   845         n = nodes[n].next;
   846       }
   847       e.id = (n == -1) ? -1 : nodes[n].first_out;
   848     }
   849 
   850     void next(Arc& e) const {
   851       if (arcs[e.id].next_out != -1) {
   852 	e.id = arcs[e.id].next_out;
   853       } else {
   854 	int n = nodes[arcs[e.id ^ 1].target].next;
   855         while(n != -1 && nodes[n].first_out == -1) {
   856           n = nodes[n].next;
   857         }
   858 	e.id = (n == -1) ? -1 : nodes[n].first_out;
   859       }      
   860     }
   861 
   862     void first(Edge& e) const { 
   863       int n = first_node;
   864       while (n != -1) {
   865         e.id = nodes[n].first_out;
   866         while ((e.id & 1) != 1) {
   867           e.id = arcs[e.id].next_out;
   868         }
   869         if (e.id != -1) {
   870           e.id /= 2;
   871           return;
   872         } 
   873         n = nodes[n].next;
   874       }
   875       e.id = -1;
   876     }
   877 
   878     void next(Edge& e) const {
   879       int n = arcs[e.id * 2].target;
   880       e.id = arcs[(e.id * 2) | 1].next_out;
   881       while ((e.id & 1) != 1) {
   882         e.id = arcs[e.id].next_out;
   883       }
   884       if (e.id != -1) {
   885         e.id /= 2;
   886         return;
   887       } 
   888       n = nodes[n].next;
   889       while (n != -1) {
   890         e.id = nodes[n].first_out;
   891         while ((e.id & 1) != 1) {
   892           e.id = arcs[e.id].next_out;
   893         }
   894         if (e.id != -1) {
   895           e.id /= 2;
   896           return;
   897         } 
   898         n = nodes[n].next;
   899       }
   900       e.id = -1;
   901     }
   902 
   903     void firstOut(Arc &e, const Node& v) const {
   904       e.id = nodes[v.id].first_out;
   905     }
   906     void nextOut(Arc &e) const {
   907       e.id = arcs[e.id].next_out;
   908     }
   909 
   910     void firstIn(Arc &e, const Node& v) const {
   911       e.id = ((nodes[v.id].first_out) ^ 1);
   912       if (e.id == -2) e.id = -1;
   913     }
   914     void nextIn(Arc &e) const {
   915       e.id = ((arcs[e.id ^ 1].next_out) ^ 1);
   916       if (e.id == -2) e.id = -1;
   917     }
   918 
   919     void firstInc(Edge &e, bool& d, const Node& v) const {
   920       int a = nodes[v.id].first_out;
   921       if (a != -1 ) {
   922         e.id = a / 2;
   923         d = ((a & 1) == 1);
   924       } else {
   925         e.id = -1;
   926         d = true;
   927       }
   928     }
   929     void nextInc(Edge &e, bool& d) const {
   930       int a = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
   931       if (a != -1 ) {
   932         e.id = a / 2;
   933         d = ((a & 1) == 1);
   934       } else {
   935         e.id = -1;
   936         d = true;
   937       }
   938     }
   939     
   940     static int id(Node v) { return v.id; }
   941     static int id(Arc e) { return e.id; }
   942     static int id(Edge e) { return e.id; }
   943 
   944     static Node nodeFromId(int id) { return Node(id);}
   945     static Arc arcFromId(int id) { return Arc(id);}
   946     static Edge edgeFromId(int id) { return Edge(id);}
   947 
   948     Node addNode() {     
   949       int n;
   950       
   951       if(first_free_node==-1) {
   952 	n = nodes.size();
   953 	nodes.push_back(NodeT());
   954       } else {
   955 	n = first_free_node;
   956 	first_free_node = nodes[n].next;
   957       }
   958       
   959       nodes[n].next = first_node;
   960       if (first_node != -1) nodes[first_node].prev = n;
   961       first_node = n;
   962       nodes[n].prev = -1;
   963       
   964       nodes[n].first_out = -1;
   965       
   966       return Node(n);
   967     }
   968     
   969     Edge addEdge(Node u, Node v) {
   970       int n;      
   971 
   972       if (first_free_arc == -1) {
   973 	n = arcs.size();
   974 	arcs.push_back(ArcT());
   975 	arcs.push_back(ArcT());
   976       } else {
   977 	n = first_free_arc;
   978 	first_free_arc = arcs[n].next_out;
   979       }
   980       
   981       arcs[n].target = u.id;
   982       arcs[n | 1].target = v.id;
   983 
   984       arcs[n].next_out = nodes[v.id].first_out;
   985       if (nodes[v.id].first_out != -1) {
   986 	arcs[nodes[v.id].first_out].prev_out = n;
   987       }      
   988       arcs[n].prev_out = -1;
   989       nodes[v.id].first_out = n;
   990       
   991       arcs[n | 1].next_out = nodes[u.id].first_out;
   992       if (nodes[u.id].first_out != -1) {
   993 	arcs[nodes[u.id].first_out].prev_out = (n | 1);
   994       }
   995       arcs[n | 1].prev_out = -1;      
   996       nodes[u.id].first_out = (n | 1);
   997 
   998       return Edge(n / 2);
   999     }
  1000     
  1001     void erase(const Node& node) {
  1002       int n = node.id;
  1003       
  1004       if(nodes[n].next != -1) {
  1005 	nodes[nodes[n].next].prev = nodes[n].prev;
  1006       }
  1007       
  1008       if(nodes[n].prev != -1) {
  1009 	nodes[nodes[n].prev].next = nodes[n].next;
  1010       } else {
  1011 	first_node = nodes[n].next;
  1012       }
  1013       
  1014       nodes[n].next = first_free_node;
  1015       first_free_node = n;
  1016 
  1017     }
  1018     
  1019     void erase(const Edge& edge) {
  1020       int n = edge.id * 2;
  1021       
  1022       if (arcs[n].next_out != -1) {
  1023 	arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
  1024       } 
  1025 
  1026       if (arcs[n].prev_out != -1) {
  1027 	arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
  1028       } else {
  1029 	nodes[arcs[n | 1].target].first_out = arcs[n].next_out;
  1030       }
  1031 
  1032       if (arcs[n | 1].next_out != -1) {
  1033 	arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
  1034       } 
  1035 
  1036       if (arcs[n | 1].prev_out != -1) {
  1037 	arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
  1038       } else {
  1039 	nodes[arcs[n].target].first_out = arcs[n | 1].next_out;
  1040       }
  1041       
  1042       arcs[n].next_out = first_free_arc;
  1043       first_free_arc = n;      
  1044 
  1045     }
  1046 
  1047     void clear() {
  1048       arcs.clear();
  1049       nodes.clear();
  1050       first_node = first_free_node = first_free_arc = -1;
  1051     }
  1052 
  1053   protected:
  1054 
  1055     void changeTarget(Edge e, Node n) {
  1056       if(arcs[2 * e.id].next_out != -1) {
  1057 	arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
  1058       }
  1059       if(arcs[2 * e.id].prev_out != -1) {
  1060 	arcs[arcs[2 * e.id].prev_out].next_out = 
  1061           arcs[2 * e.id].next_out;
  1062       } else {
  1063         nodes[arcs[(2 * e.id) | 1].target].first_out = 
  1064           arcs[2 * e.id].next_out;
  1065       }
  1066 
  1067       if (nodes[n.id].first_out != -1) {
  1068 	arcs[nodes[n.id].first_out].prev_out = 2 * e.id;
  1069       }
  1070       arcs[(2 * e.id) | 1].target = n.id;
  1071       arcs[2 * e.id].prev_out = -1;
  1072       arcs[2 * e.id].next_out = nodes[n.id].first_out;
  1073       nodes[n.id].first_out = 2 * e.id;
  1074     }
  1075 
  1076     void changeSource(Edge e, Node n) {
  1077       if(arcs[(2 * e.id) | 1].next_out != -1) {
  1078 	arcs[arcs[(2 * e.id) | 1].next_out].prev_out = 
  1079           arcs[(2 * e.id) | 1].prev_out;
  1080       }
  1081       if(arcs[(2 * e.id) | 1].prev_out != -1) {
  1082 	arcs[arcs[(2 * e.id) | 1].prev_out].next_out = 
  1083           arcs[(2 * e.id) | 1].next_out;
  1084       } else {
  1085         nodes[arcs[2 * e.id].target].first_out = 
  1086           arcs[(2 * e.id) | 1].next_out;
  1087       }
  1088 
  1089       if (nodes[n.id].first_out != -1) {
  1090 	arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
  1091       }
  1092       arcs[2 * e.id].target = n.id;
  1093       arcs[(2 * e.id) | 1].prev_out = -1;
  1094       arcs[(2 * e.id) | 1].next_out = nodes[n.id].first_out;
  1095       nodes[n.id].first_out = ((2 * e.id) | 1);
  1096     }
  1097 
  1098   };
  1099 
  1100   typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
  1101 
  1102 
  1103   /// \addtogroup graphs
  1104   /// @{
  1105 
  1106   ///A general undirected graph structure.
  1107 
  1108   ///\ref ListGraph is a simple and fast <em>undirected graph</em> 
  1109   ///implementation based on static linked lists that are stored in 
  1110   ///\c std::vector structures. 
  1111   ///
  1112   ///It conforms to the \ref concepts::Graph "Graph concept" and it
  1113   ///also provides several useful additional functionalities.
  1114   ///Most of the member functions and nested classes are documented
  1115   ///only in the concept class.
  1116   ///
  1117   ///An important extra feature of this graph implementation is that
  1118   ///its maps are real \ref concepts::ReferenceMap "reference map"s.
  1119   ///
  1120   ///\sa concepts::Graph
  1121 
  1122   class ListGraph : public ExtendedListGraphBase {
  1123   private:
  1124     ///ListGraph is \e not copy constructible. Use copyGraph() instead.
  1125 
  1126     ///ListGraph is \e not copy constructible. Use copyGraph() instead.
  1127     ///
  1128     ListGraph(const ListGraph &) :ExtendedListGraphBase()  {};
  1129     ///\brief Assignment of ListGraph to another one is \e not allowed.
  1130     ///Use copyGraph() instead.
  1131 
  1132     ///Assignment of ListGraph to another one is \e not allowed.
  1133     ///Use copyGraph() instead.
  1134     void operator=(const ListGraph &) {}
  1135   public:
  1136     /// Constructor
  1137     
  1138     /// Constructor.
  1139     ///
  1140     ListGraph() {}
  1141 
  1142     typedef ExtendedListGraphBase Parent;
  1143 
  1144     typedef Parent::OutArcIt IncEdgeIt;
  1145 
  1146     /// \brief Add a new node to the graph.
  1147     ///
  1148     /// Add a new node to the graph.
  1149     /// \return the new node.
  1150     Node addNode() { return Parent::addNode(); }
  1151 
  1152     /// \brief Add a new edge to the graph.
  1153     ///
  1154     /// Add a new edge to the graph with source node \c s
  1155     /// and target node \c t.
  1156     /// \return the new edge.
  1157     Edge addEdge(const Node& s, const Node& t) { 
  1158       return Parent::addEdge(s, t); 
  1159     }
  1160     /// \brief Change the source of \c e to \c n
  1161     ///
  1162     /// This function changes the source of \c e to \c n.
  1163     ///
  1164     ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s
  1165     ///referencing the changed arc remain
  1166     ///valid. However <tt>OutArcIt</tt>s are invalidated.
  1167     ///
  1168     ///\warning This functionality cannot be used together with the
  1169     ///Snapshot feature.
  1170     void changeSource(Edge e, Node n) { 
  1171       Parent::changeSource(e,n); 
  1172     }    
  1173     /// \brief Change the target of \c e to \c n
  1174     ///
  1175     /// This function changes the target of \c e to \c n.
  1176     ///
  1177     /// \note The <tt>ArcIt</tt>s referencing the changed arc remain
  1178     /// valid. However the other iterators may be invalidated.
  1179     ///
  1180     ///\warning This functionality cannot be used together with the
  1181     ///Snapshot feature.
  1182     void changeTarget(Edge e, Node n) { 
  1183       Parent::changeTarget(e,n); 
  1184     }
  1185     /// \brief Change the source of \c e to \c n
  1186     ///
  1187     /// This function changes the source of \c e to \c n. 
  1188     /// It also changes the proper node of the represented edge.
  1189     ///
  1190     ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s
  1191     ///referencing the changed arc remain
  1192     ///valid. However <tt>OutArcIt</tt>s are invalidated.
  1193     ///
  1194     ///\warning This functionality cannot be used together with the
  1195     ///Snapshot feature.
  1196     void changeSource(Arc e, Node n) { 
  1197       if (Parent::direction(e)) {
  1198         Parent::changeSource(e,n);
  1199       } else {
  1200         Parent::changeTarget(e,n);
  1201       } 
  1202     }
  1203     /// \brief Change the target of \c e to \c n
  1204     ///
  1205     /// This function changes the target of \c e to \c n. 
  1206     /// It also changes the proper node of the represented edge.
  1207     ///
  1208     ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s
  1209     ///referencing the changed arc remain
  1210     ///valid. However <tt>InArcIt</tt>s are invalidated.
  1211     ///
  1212     ///\warning This functionality cannot be used together with the
  1213     ///Snapshot feature.
  1214     void changeTarget(Arc e, Node n) { 
  1215       if (Parent::direction(e)) {
  1216         Parent::changeTarget(e,n);
  1217       } else {
  1218         Parent::changeSource(e,n);
  1219       } 
  1220     }
  1221     /// \brief Contract two nodes.
  1222     ///
  1223     /// This function contracts two nodes.
  1224     /// Node \p b will be removed but instead of deleting
  1225     /// its neighboring arcs, they will be joined to \p a.
  1226     /// The last parameter \p r controls whether to remove loops. \c true
  1227     /// means that loops will be removed.
  1228     ///
  1229     /// \note The <tt>ArcIt</tt>s referencing a moved arc remain
  1230     /// valid.
  1231     ///
  1232     ///\warning This functionality cannot be used together with the
  1233     ///Snapshot feature.
  1234     void contract(Node a, Node b, bool r = true) {
  1235       for(IncEdgeIt e(*this, b); e!=INVALID;) {
  1236 	IncEdgeIt f = e; ++f;
  1237 	if (r && runningNode(e) == a) {
  1238 	  erase(e);
  1239 	} else if (source(e) == b) {
  1240 	  changeSource(e, a);
  1241 	} else {
  1242 	  changeTarget(e, a);
  1243 	}
  1244 	e = f;
  1245       }
  1246       erase(b);
  1247     }
  1248 
  1249 
  1250     /// \brief Class to make a snapshot of the graph and restore
  1251     /// it later.
  1252     ///
  1253     /// Class to make a snapshot of the graph and restore it later.
  1254     ///
  1255     /// The newly added nodes and edges can be removed
  1256     /// using the restore() function.
  1257     ///
  1258     /// \warning Edge and node deletions and other modifications
  1259     /// (e.g. changing nodes of edges, contracting nodes) cannot be 
  1260     /// restored. These events invalidate the snapshot.
  1261     class Snapshot {
  1262     protected:
  1263 
  1264       typedef Parent::NodeNotifier NodeNotifier;
  1265 
  1266       class NodeObserverProxy : public NodeNotifier::ObserverBase {
  1267       public:
  1268 
  1269         NodeObserverProxy(Snapshot& _snapshot)
  1270           : snapshot(_snapshot) {}
  1271 
  1272         using NodeNotifier::ObserverBase::attach;
  1273         using NodeNotifier::ObserverBase::detach;
  1274         using NodeNotifier::ObserverBase::attached;
  1275         
  1276       protected:
  1277         
  1278         virtual void add(const Node& node) {
  1279           snapshot.addNode(node);
  1280         }
  1281         virtual void add(const std::vector<Node>& nodes) {
  1282           for (int i = nodes.size() - 1; i >= 0; ++i) {
  1283             snapshot.addNode(nodes[i]);
  1284           }
  1285         }
  1286         virtual void erase(const Node& node) {
  1287           snapshot.eraseNode(node);
  1288         }
  1289         virtual void erase(const std::vector<Node>& nodes) {
  1290           for (int i = 0; i < int(nodes.size()); ++i) {
  1291             snapshot.eraseNode(nodes[i]);
  1292           }
  1293         }
  1294         virtual void build() {
  1295           Node node;
  1296           std::vector<Node> nodes;
  1297           for (notifier()->first(node); node != INVALID; 
  1298                notifier()->next(node)) {
  1299             nodes.push_back(node);
  1300           }
  1301           for (int i = nodes.size() - 1; i >= 0; --i) {
  1302             snapshot.addNode(nodes[i]);
  1303           }
  1304         }
  1305         virtual void clear() {
  1306           Node node;
  1307           for (notifier()->first(node); node != INVALID; 
  1308                notifier()->next(node)) {
  1309             snapshot.eraseNode(node);
  1310           }
  1311         }
  1312 
  1313         Snapshot& snapshot;
  1314       };
  1315 
  1316       class EdgeObserverProxy : public EdgeNotifier::ObserverBase {
  1317       public:
  1318 
  1319         EdgeObserverProxy(Snapshot& _snapshot)
  1320           : snapshot(_snapshot) {}
  1321 
  1322         using EdgeNotifier::ObserverBase::attach;
  1323         using EdgeNotifier::ObserverBase::detach;
  1324         using EdgeNotifier::ObserverBase::attached;
  1325         
  1326       protected:
  1327 
  1328         virtual void add(const Edge& edge) {
  1329           snapshot.addEdge(edge);
  1330         }
  1331         virtual void add(const std::vector<Edge>& edges) {
  1332           for (int i = edges.size() - 1; i >= 0; ++i) {
  1333             snapshot.addEdge(edges[i]);
  1334           }
  1335         }
  1336         virtual void erase(const Edge& edge) {
  1337           snapshot.eraseEdge(edge);
  1338         }
  1339         virtual void erase(const std::vector<Edge>& edges) {
  1340           for (int i = 0; i < int(edges.size()); ++i) {
  1341             snapshot.eraseEdge(edges[i]);
  1342           }
  1343         }
  1344         virtual void build() {
  1345           Edge edge;
  1346           std::vector<Edge> edges;
  1347           for (notifier()->first(edge); edge != INVALID; 
  1348                notifier()->next(edge)) {
  1349             edges.push_back(edge);
  1350           }
  1351           for (int i = edges.size() - 1; i >= 0; --i) {
  1352             snapshot.addEdge(edges[i]);
  1353           }
  1354         }
  1355         virtual void clear() {
  1356           Edge edge;
  1357           for (notifier()->first(edge); edge != INVALID; 
  1358                notifier()->next(edge)) {
  1359             snapshot.eraseEdge(edge);
  1360           }
  1361         }
  1362 
  1363         Snapshot& snapshot;
  1364       };
  1365 
  1366       ListGraph *graph;
  1367 
  1368       NodeObserverProxy node_observer_proxy;
  1369       EdgeObserverProxy edge_observer_proxy;
  1370 
  1371       std::list<Node> added_nodes;
  1372       std::list<Edge> added_edges;
  1373 
  1374 
  1375       void addNode(const Node& node) {
  1376         added_nodes.push_front(node);        
  1377       }
  1378       void eraseNode(const Node& node) {
  1379         std::list<Node>::iterator it = 
  1380           std::find(added_nodes.begin(), added_nodes.end(), node);
  1381         if (it == added_nodes.end()) {
  1382           clear();
  1383           edge_observer_proxy.detach();
  1384           throw NodeNotifier::ImmediateDetach();
  1385         } else {
  1386           added_nodes.erase(it);
  1387         }
  1388       }
  1389 
  1390       void addEdge(const Edge& edge) {
  1391         added_edges.push_front(edge);        
  1392       }
  1393       void eraseEdge(const Edge& edge) {
  1394         std::list<Edge>::iterator it = 
  1395           std::find(added_edges.begin(), added_edges.end(), edge);
  1396         if (it == added_edges.end()) {
  1397           clear();
  1398           node_observer_proxy.detach();
  1399           throw EdgeNotifier::ImmediateDetach();
  1400         } else {
  1401           added_edges.erase(it);
  1402         }
  1403       }
  1404 
  1405       void attach(ListGraph &_graph) {
  1406 	graph = &_graph;
  1407 	node_observer_proxy.attach(graph->notifier(Node()));
  1408         edge_observer_proxy.attach(graph->notifier(Edge()));
  1409       }
  1410             
  1411       void detach() {
  1412 	node_observer_proxy.detach();
  1413 	edge_observer_proxy.detach();
  1414       }
  1415 
  1416       bool attached() const {
  1417         return node_observer_proxy.attached();
  1418       }
  1419 
  1420       void clear() {
  1421         added_nodes.clear();
  1422         added_edges.clear();        
  1423       }
  1424 
  1425     public:
  1426 
  1427       /// \brief Default constructor.
  1428       ///
  1429       /// Default constructor.
  1430       /// To actually make a snapshot you must call save().
  1431       Snapshot() 
  1432         : graph(0), node_observer_proxy(*this), 
  1433           edge_observer_proxy(*this) {}
  1434       
  1435       /// \brief Constructor that immediately makes a snapshot.
  1436       ///      
  1437       /// This constructor immediately makes a snapshot of the graph.
  1438       /// \param _graph The graph we make a snapshot of.
  1439       Snapshot(ListGraph &_graph) 
  1440         : node_observer_proxy(*this), 
  1441           edge_observer_proxy(*this) {
  1442 	attach(_graph);
  1443       }
  1444       
  1445       /// \brief Make a snapshot.
  1446       ///
  1447       /// Make a snapshot of the graph.
  1448       ///
  1449       /// This function can be called more than once. In case of a repeated
  1450       /// call, the previous snapshot gets lost.
  1451       /// \param _graph The graph we make the snapshot of.
  1452       void save(ListGraph &_graph) {
  1453         if (attached()) {
  1454           detach();
  1455           clear();
  1456         }
  1457         attach(_graph);
  1458       }
  1459       
  1460       /// \brief Undo the changes until the last snapshot.
  1461       // 
  1462       /// Undo the changes until the last snapshot created by save().
  1463       void restore() {
  1464 	detach();
  1465 	for(std::list<Edge>::iterator it = added_edges.begin(); 
  1466             it != added_edges.end(); ++it) {
  1467 	  graph->erase(*it);
  1468 	}
  1469 	for(std::list<Node>::iterator it = added_nodes.begin(); 
  1470             it != added_nodes.end(); ++it) {
  1471 	  graph->erase(*it);
  1472 	}
  1473         clear();
  1474       }
  1475 
  1476       /// \brief Gives back true when the snapshot is valid.
  1477       ///
  1478       /// Gives back true when the snapshot is valid.
  1479       bool valid() const {
  1480         return attached();
  1481       }
  1482     };
  1483   };
  1484   
  1485   /// @}  
  1486 } //namespace lemon
  1487   
  1488 
  1489 #endif