lemon/list_graph.h
changeset 59 4ab73d92f0fb
parent 39 0a01d811071f
child 73 c56b7389dc78
equal deleted inserted replaced
1:0f58732904a6 2:c534af49375c
    14  * express or implied, and with no claim as to its suitability for any
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    15  * purpose.
    16  *
    16  *
    17  */
    17  */
    18 
    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