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