lemon/list_graph.h
author Balazs Dezso <deba@inf.elte.hu>
Fri, 11 Jul 2008 15:01:49 +0200
changeset 203 215bfc30b14f
parent 149 2f7ae34e1333
child 209 765619b7cbb2
permissions -rw-r--r--
Cleaning of heap test and bug fix in heap concept check (ticket #100)

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