lemon/list_graph.h
author deba
Fri, 06 Apr 2007 22:50:27 +0000
changeset 2417 113d381c9160
parent 2386 81b47fc5c444
child 2456 717a5134ddeb
permissions -rw-r--r--
Parameter reordering

Patch from Kovacs Peter
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2007
     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 ListGraph, ListUGraph classes.
    25 
    26 #include <lemon/bits/base_extender.h>
    27 #include <lemon/bits/graph_extender.h>
    28 
    29 #include <lemon/error.h>
    30 
    31 #include <vector>
    32 #include <list>
    33 
    34 namespace lemon {
    35 
    36   class ListGraphBase {
    37 
    38   protected:
    39     struct NodeT {
    40       int first_in, first_out;
    41       int prev, next;
    42     };
    43  
    44     struct EdgeT {
    45       int target, source;
    46       int prev_in, prev_out;
    47       int next_in, next_out;
    48     };
    49 
    50     std::vector<NodeT> nodes;
    51 
    52     int first_node;
    53 
    54     int first_free_node;
    55 
    56     std::vector<EdgeT> edges;
    57 
    58     int first_free_edge;
    59     
    60   public:
    61     
    62     typedef ListGraphBase Graph;
    63     
    64     class Node {
    65       friend class ListGraphBase;
    66     protected:
    67 
    68       int id;
    69       explicit Node(int pid) { id = pid;}
    70 
    71     public:
    72       Node() {}
    73       Node (Invalid) { id = -1; }
    74       bool operator==(const Node& node) const {return id == node.id;}
    75       bool operator!=(const Node& node) const {return id != node.id;}
    76       bool operator<(const Node& node) const {return id < node.id;}
    77     };
    78 
    79     class Edge {
    80       friend class ListGraphBase;
    81     protected:
    82 
    83       int id;
    84       explicit Edge(int pid) { id = pid;}
    85 
    86     public:
    87       Edge() {}
    88       Edge (Invalid) { id = -1; }
    89       bool operator==(const Edge& edge) const {return id == edge.id;}
    90       bool operator!=(const Edge& edge) const {return id != edge.id;}
    91       bool operator<(const Edge& edge) const {return id < edge.id;}
    92     };
    93 
    94 
    95 
    96     ListGraphBase()
    97       : nodes(), first_node(-1),
    98 	first_free_node(-1), edges(), first_free_edge(-1) {}
    99 
   100     
   101     int maxNodeId() const { return nodes.size()-1; } 
   102     int maxEdgeId() const { return edges.size()-1; }
   103 
   104     Node source(Edge e) const { return Node(edges[e.id].source); }
   105     Node target(Edge e) const { return Node(edges[e.id].target); }
   106 
   107 
   108     void first(Node& node) const { 
   109       node.id = first_node;
   110     }
   111 
   112     void next(Node& node) const {
   113       node.id = nodes[node.id].next;
   114     }
   115 
   116 
   117     void first(Edge& e) const { 
   118       int n;
   119       for(n = first_node; 
   120 	  n!=-1 && nodes[n].first_in == -1; 
   121 	  n = nodes[n].next);
   122       e.id = (n == -1) ? -1 : nodes[n].first_in;
   123     }
   124 
   125     void next(Edge& edge) const {
   126       if (edges[edge.id].next_in != -1) {
   127 	edge.id = edges[edge.id].next_in;
   128       } else {
   129 	int n;
   130 	for(n = nodes[edges[edge.id].target].next;
   131 	  n!=-1 && nodes[n].first_in == -1; 
   132 	  n = nodes[n].next);
   133 	edge.id = (n == -1) ? -1 : nodes[n].first_in;
   134       }      
   135     }
   136 
   137     void firstOut(Edge &e, const Node& v) const {
   138       e.id = nodes[v.id].first_out;
   139     }
   140     void nextOut(Edge &e) const {
   141       e.id=edges[e.id].next_out;
   142     }
   143 
   144     void firstIn(Edge &e, const Node& v) const {
   145       e.id = nodes[v.id].first_in;
   146     }
   147     void nextIn(Edge &e) const {
   148       e.id=edges[e.id].next_in;
   149     }
   150 
   151     
   152     static int id(Node v) { return v.id; }
   153     static int id(Edge e) { return e.id; }
   154 
   155     static Node nodeFromId(int id) { return Node(id);}
   156     static Edge edgeFromId(int id) { return Edge(id);}
   157 
   158     Node addNode() {     
   159       int n;
   160       
   161       if(first_free_node==-1) {
   162 	n = nodes.size();
   163 	nodes.push_back(NodeT());
   164       } else {
   165 	n = first_free_node;
   166 	first_free_node = nodes[n].next;
   167       }
   168       
   169       nodes[n].next = first_node;
   170       if(first_node != -1) nodes[first_node].prev = n;
   171       first_node = n;
   172       nodes[n].prev = -1;
   173       
   174       nodes[n].first_in = nodes[n].first_out = -1;
   175       
   176       return Node(n);
   177     }
   178     
   179     Edge addEdge(Node u, Node v) {
   180       int n;      
   181 
   182       if (first_free_edge == -1) {
   183 	n = edges.size();
   184 	edges.push_back(EdgeT());
   185       } else {
   186 	n = first_free_edge;
   187 	first_free_edge = edges[n].next_in;
   188       }
   189       
   190       edges[n].source = u.id; 
   191       edges[n].target = v.id;
   192 
   193       edges[n].next_out = nodes[u.id].first_out;
   194       if(nodes[u.id].first_out != -1) {
   195 	edges[nodes[u.id].first_out].prev_out = n;
   196       }
   197       
   198       edges[n].next_in = nodes[v.id].first_in;
   199       if(nodes[v.id].first_in != -1) {
   200 	edges[nodes[v.id].first_in].prev_in = n;
   201       }
   202       
   203       edges[n].prev_in = edges[n].prev_out = -1;
   204 	
   205       nodes[u.id].first_out = nodes[v.id].first_in = n;
   206 
   207       return Edge(n);
   208     }
   209     
   210     void erase(const Node& node) {
   211       int n = node.id;
   212       
   213       if(nodes[n].next != -1) {
   214 	nodes[nodes[n].next].prev = nodes[n].prev;
   215       }
   216       
   217       if(nodes[n].prev != -1) {
   218 	nodes[nodes[n].prev].next = nodes[n].next;
   219       } else {
   220 	first_node = nodes[n].next;
   221       }
   222       
   223       nodes[n].next = first_free_node;
   224       first_free_node = n;
   225 
   226     }
   227     
   228     void erase(const Edge& edge) {
   229       int n = edge.id;
   230       
   231       if(edges[n].next_in!=-1) {
   232 	edges[edges[n].next_in].prev_in = edges[n].prev_in;
   233       }
   234 
   235       if(edges[n].prev_in!=-1) {
   236 	edges[edges[n].prev_in].next_in = edges[n].next_in;
   237       } else {
   238 	nodes[edges[n].target].first_in = edges[n].next_in;
   239       }
   240 
   241       
   242       if(edges[n].next_out!=-1) {
   243 	edges[edges[n].next_out].prev_out = edges[n].prev_out;
   244       } 
   245 
   246       if(edges[n].prev_out!=-1) {
   247 	edges[edges[n].prev_out].next_out = edges[n].next_out;
   248       } else {
   249 	nodes[edges[n].source].first_out = edges[n].next_out;
   250       }
   251       
   252       edges[n].next_in = first_free_edge;
   253       first_free_edge = n;      
   254 
   255     }
   256 
   257     void clear() {
   258       edges.clear();
   259       nodes.clear();
   260       first_node = first_free_node = first_free_edge = -1;
   261     }
   262 
   263   protected:
   264     void changeTarget(Edge e, Node n) 
   265     {
   266       if(edges[e.id].next_in != -1)
   267 	edges[edges[e.id].next_in].prev_in = edges[e.id].prev_in;
   268       if(edges[e.id].prev_in != -1)
   269 	edges[edges[e.id].prev_in].next_in = edges[e.id].next_in;
   270       else nodes[edges[e.id].target].first_in = edges[e.id].next_in;
   271       if (nodes[n.id].first_in != -1) {
   272 	edges[nodes[n.id].first_in].prev_in = e.id;
   273       }
   274       edges[e.id].target = n.id;
   275       edges[e.id].prev_in = -1;
   276       edges[e.id].next_in = nodes[n.id].first_in;
   277       nodes[n.id].first_in = e.id;
   278     }
   279     void changeSource(Edge e, Node n) 
   280     {
   281       if(edges[e.id].next_out != -1)
   282 	edges[edges[e.id].next_out].prev_out = edges[e.id].prev_out;
   283       if(edges[e.id].prev_out != -1)
   284 	edges[edges[e.id].prev_out].next_out = edges[e.id].next_out;
   285       else nodes[edges[e.id].source].first_out = edges[e.id].next_out;
   286       if (nodes[n.id].first_out != -1) {
   287 	edges[nodes[n.id].first_out].prev_out = e.id;
   288       }
   289       edges[e.id].source = n.id;
   290       edges[e.id].prev_out = -1;
   291       edges[e.id].next_out = nodes[n.id].first_out;
   292       nodes[n.id].first_out = e.id;
   293     }
   294 
   295   };
   296 
   297   typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
   298 
   299   /// \addtogroup graphs
   300   /// @{
   301 
   302   ///A list graph class.
   303 
   304   ///This is a simple and fast graph implementation.
   305   ///
   306   ///It conforms to the \ref concepts::Graph "Graph concept" and it
   307   ///also provides several additional useful extra functionalities.
   308   ///The most of the member functions and nested classes are
   309   ///documented only in the concept class.
   310   ///
   311   ///An important extra feature of this graph implementation is that
   312   ///its maps are real \ref concepts::ReferenceMap "reference map"s.
   313   ///
   314   ///\sa concepts::Graph.
   315 
   316   class ListGraph : public ExtendedListGraphBase {
   317   private:
   318     ///ListGraph is \e not copy constructible. Use GraphCopy() instead.
   319     
   320     ///ListGraph is \e not copy constructible. Use GraphCopy() instead.
   321     ///
   322     ListGraph(const ListGraph &) :ExtendedListGraphBase() {};
   323     ///\brief Assignment of ListGraph to another one is \e not allowed.
   324     ///Use GraphCopy() instead.
   325 
   326     ///Assignment of ListGraph to another one is \e not allowed.
   327     ///Use GraphCopy() instead.
   328     void operator=(const ListGraph &) {}
   329   public:
   330 
   331     typedef ExtendedListGraphBase Parent;
   332 
   333     /// Constructor
   334     
   335     /// Constructor.
   336     ///
   337     ListGraph() {}
   338 
   339     ///Add a new node to the graph.
   340     
   341     /// \return the new node.
   342     ///
   343     Node addNode() { return Parent::addNode(); }
   344 
   345     ///Add a new edge to the graph.
   346     
   347     ///Add a new edge to the graph with source node \c s
   348     ///and target node \c t.
   349     ///\return the new edge.
   350     Edge addEdge(const Node& s, const Node& t) { 
   351       return Parent::addEdge(s, t); 
   352     }
   353 
   354     /// Changes the target of \c e to \c n
   355 
   356     /// Changes the target of \c e to \c n
   357     ///
   358     ///\note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s referencing
   359     ///the changed edge remain valid. However <tt>InEdgeIt</tt>s are
   360     ///invalidated.
   361     ///\warning This functionality cannot be used together with the Snapshot
   362     ///feature.
   363     void changeTarget(Edge e, Node n) { 
   364       Parent::changeTarget(e,n); 
   365     }
   366     /// Changes the source of \c e to \c n
   367 
   368     /// Changes the source of \c e to \c n
   369     ///
   370     ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s referencing
   371     ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are
   372     ///invalidated.
   373     ///\warning This functionality cannot be used together with the Snapshot
   374     ///feature.
   375     void changeSource(Edge e, Node n) { 
   376       Parent::changeSource(e,n);
   377     }
   378 
   379     /// Invert the direction of an edge.
   380 
   381     ///\note The <tt>EdgeIt</tt>s referencing the changed edge remain
   382     ///valid. However <tt>OutEdgeIt</tt>s and <tt>InEdgeIt</tt>s are
   383     ///invalidated.
   384     ///\warning This functionality cannot be used together with the Snapshot
   385     ///feature.
   386     void reverseEdge(Edge e) {
   387       Node t=target(e);
   388       changeTarget(e,source(e));
   389       changeSource(e,t);
   390     }
   391 
   392     /// \brief Using this it is possible to avoid the superfluous memory
   393     /// allocation.
   394 
   395     ///Using this it is possible to avoid the superfluous memory
   396     ///allocation: if you know that the graph you want to build will
   397     ///contain at least 10 million nodes then it is worth reserving
   398     ///space for this amount before starting to build the graph.
   399     void reserveNode(int n) { nodes.reserve(n); };
   400 
   401     /// \brief Using this it is possible to avoid the superfluous memory
   402     /// allocation.
   403 
   404     ///Using this it is possible to avoid the superfluous memory
   405     ///allocation: see the \ref reserveNode function.
   406     void reserveEdge(int n) { edges.reserve(n); };
   407 
   408 
   409     ///Contract two nodes.
   410 
   411     ///This function contracts two nodes.
   412     ///
   413     ///Node \p b will be removed but instead of deleting
   414     ///incident edges, they will be joined to \p a.
   415     ///The last parameter \p r controls whether to remove loops. \c true
   416     ///means that loops will be removed.
   417     ///
   418     ///\note The <tt>EdgeIt</tt>s
   419     ///referencing a moved edge remain
   420     ///valid. However <tt>InEdgeIt</tt>s and <tt>OutEdgeIt</tt>s
   421     ///may be invalidated.
   422     ///\warning This functionality cannot be used together with the Snapshot
   423     ///feature.
   424     void contract(Node a, Node b, bool r = true) 
   425     {
   426       for(OutEdgeIt e(*this,b);e!=INVALID;) {
   427 	OutEdgeIt f=e;
   428 	++f;
   429 	if(r && target(e)==a) erase(e);
   430 	else changeSource(e,a);
   431 	e=f;
   432       }
   433       for(InEdgeIt e(*this,b);e!=INVALID;) {
   434 	InEdgeIt f=e;
   435 	++f;
   436 	if(r && source(e)==a) erase(e);
   437 	else changeTarget(e,a);
   438 	e=f;
   439       }
   440       erase(b);
   441     }
   442 
   443     ///Split a node.
   444 
   445     ///This function splits a node. First a new node is added to the graph,
   446     ///then the source of each outgoing edge of \c n is moved to this new node.
   447     ///If \c connect is \c true (this is the default value), then a new edge
   448     ///from \c n to the newly created node is also added.
   449     ///\return The newly created node.
   450     ///
   451     ///\note The <tt>EdgeIt</tt>s referencing a moved edge remain
   452     ///valid. However <tt>InEdgeIt</tt>s and <tt>OutEdgeIt</tt>s may
   453     ///be invalidated.  
   454     ///
   455     ///\warning This functionality cannot be used together with the
   456     ///Snapshot feature.  \todo It could be implemented in a bit
   457     ///faster way.
   458     Node split(Node n, bool connect = true) {
   459       Node b = addNode();
   460       for(OutEdgeIt e(*this,n);e!=INVALID;) {
   461  	OutEdgeIt f=e;
   462 	++f;
   463 	changeSource(e,b);
   464 	e=f;
   465       }
   466       if (connect) addEdge(n,b);
   467       return b;
   468     }
   469       
   470     ///Split an edge.
   471 
   472     ///This function splits an edge. First a new node \c b is added to
   473     ///the graph, then the original edge is re-targeted to \c
   474     ///b. Finally an edge from \c b to the original target is added.
   475     ///\return The newly created node.  
   476     ///\warning This functionality
   477     ///cannot be used together with the Snapshot feature.
   478     Node split(Edge e) {
   479       Node b = addNode();
   480       addEdge(b,target(e));
   481       changeTarget(e,b);
   482       return b;
   483     }
   484       
   485     /// \brief Class to make a snapshot of the graph and restore
   486     /// to it later.
   487     ///
   488     /// Class to make a snapshot of the graph and to restore it
   489     /// later.
   490     ///
   491     /// The newly added nodes and edges can be removed using the
   492     /// restore() function.
   493     ///
   494     /// \warning Edge and node deletions cannot be restored. This
   495     /// events invalidate the snapshot. 
   496     class Snapshot {
   497     protected:
   498 
   499       typedef Parent::NodeNotifier NodeNotifier;
   500 
   501       class NodeObserverProxy : public NodeNotifier::ObserverBase {
   502       public:
   503 
   504         NodeObserverProxy(Snapshot& _snapshot)
   505           : snapshot(_snapshot) {}
   506 
   507         using NodeNotifier::ObserverBase::attach;
   508         using NodeNotifier::ObserverBase::detach;
   509         using NodeNotifier::ObserverBase::attached;
   510         
   511       protected:
   512         
   513         virtual void add(const Node& node) {
   514           snapshot.addNode(node);
   515         }
   516         virtual void add(const std::vector<Node>& nodes) {
   517           for (int i = nodes.size() - 1; i >= 0; ++i) {
   518             snapshot.addNode(nodes[i]);
   519           }
   520         }
   521         virtual void erase(const Node& node) {
   522           snapshot.eraseNode(node);
   523         }
   524         virtual void erase(const std::vector<Node>& nodes) {
   525           for (int i = 0; i < int(nodes.size()); ++i) {
   526             snapshot.eraseNode(nodes[i]);
   527           }
   528         }
   529         virtual void build() {
   530           Node node;
   531           std::vector<Node> nodes;
   532           for (notifier()->first(node); node != INVALID; 
   533                notifier()->next(node)) {
   534             nodes.push_back(node);
   535           }
   536           for (int i = nodes.size() - 1; i >= 0; --i) {
   537             snapshot.addNode(nodes[i]);
   538           }
   539         }
   540         virtual void clear() {
   541           Node node;
   542           for (notifier()->first(node); node != INVALID; 
   543                notifier()->next(node)) {
   544             snapshot.eraseNode(node);
   545           }
   546         }
   547 
   548         Snapshot& snapshot;
   549       };
   550 
   551       class EdgeObserverProxy : public EdgeNotifier::ObserverBase {
   552       public:
   553 
   554         EdgeObserverProxy(Snapshot& _snapshot)
   555           : snapshot(_snapshot) {}
   556 
   557         using EdgeNotifier::ObserverBase::attach;
   558         using EdgeNotifier::ObserverBase::detach;
   559         using EdgeNotifier::ObserverBase::attached;
   560         
   561       protected:
   562 
   563         virtual void add(const Edge& edge) {
   564           snapshot.addEdge(edge);
   565         }
   566         virtual void add(const std::vector<Edge>& edges) {
   567           for (int i = edges.size() - 1; i >= 0; ++i) {
   568             snapshot.addEdge(edges[i]);
   569           }
   570         }
   571         virtual void erase(const Edge& edge) {
   572           snapshot.eraseEdge(edge);
   573         }
   574         virtual void erase(const std::vector<Edge>& edges) {
   575           for (int i = 0; i < int(edges.size()); ++i) {
   576             snapshot.eraseEdge(edges[i]);
   577           }
   578         }
   579         virtual void build() {
   580           Edge edge;
   581           std::vector<Edge> edges;
   582           for (notifier()->first(edge); edge != INVALID; 
   583                notifier()->next(edge)) {
   584             edges.push_back(edge);
   585           }
   586           for (int i = edges.size() - 1; i >= 0; --i) {
   587             snapshot.addEdge(edges[i]);
   588           }
   589         }
   590         virtual void clear() {
   591           Edge edge;
   592           for (notifier()->first(edge); edge != INVALID; 
   593                notifier()->next(edge)) {
   594             snapshot.eraseEdge(edge);
   595           }
   596         }
   597 
   598         Snapshot& snapshot;
   599       };
   600       
   601       ListGraph *graph;
   602 
   603       NodeObserverProxy node_observer_proxy;
   604       EdgeObserverProxy edge_observer_proxy;
   605 
   606       std::list<Node> added_nodes;
   607       std::list<Edge> added_edges;
   608 
   609 
   610       void addNode(const Node& node) {
   611         added_nodes.push_front(node);        
   612       }
   613       void eraseNode(const Node& node) {
   614         std::list<Node>::iterator it = 
   615           std::find(added_nodes.begin(), added_nodes.end(), node);
   616         if (it == added_nodes.end()) {
   617           clear();
   618           edge_observer_proxy.detach();
   619           throw NodeNotifier::ImmediateDetach();
   620         } else {
   621           added_nodes.erase(it);
   622         }
   623       }
   624 
   625       void addEdge(const Edge& edge) {
   626         added_edges.push_front(edge);        
   627       }
   628       void eraseEdge(const Edge& edge) {
   629         std::list<Edge>::iterator it = 
   630           std::find(added_edges.begin(), added_edges.end(), edge);
   631         if (it == added_edges.end()) {
   632           clear();
   633           node_observer_proxy.detach(); 
   634           throw EdgeNotifier::ImmediateDetach();
   635         } else {
   636           added_edges.erase(it);
   637         }        
   638       }
   639 
   640       void attach(ListGraph &_graph) {
   641 	graph = &_graph;
   642 	node_observer_proxy.attach(graph->notifier(Node()));
   643         edge_observer_proxy.attach(graph->notifier(Edge()));
   644       }
   645             
   646       void detach() {
   647 	node_observer_proxy.detach();
   648 	edge_observer_proxy.detach();
   649       }
   650 
   651       bool attached() const {
   652         return node_observer_proxy.attached();
   653       }
   654 
   655       void clear() {
   656         added_nodes.clear();
   657         added_edges.clear();        
   658       }
   659 
   660     public:
   661 
   662       /// \brief Default constructor.
   663       ///
   664       /// Default constructor.
   665       /// To actually make a snapshot you must call save().
   666       Snapshot() 
   667         : graph(0), node_observer_proxy(*this), 
   668           edge_observer_proxy(*this) {}
   669       
   670       /// \brief Constructor that immediately makes a snapshot.
   671       ///      
   672       /// This constructor immediately makes a snapshot of the graph.
   673       /// \param _graph The graph we make a snapshot of.
   674       Snapshot(ListGraph &_graph) 
   675         : node_observer_proxy(*this), 
   676           edge_observer_proxy(*this) {
   677 	attach(_graph);
   678       }
   679       
   680       /// \brief Make a snapshot.
   681       ///
   682       /// Make a snapshot of the graph.
   683       ///
   684       /// This function can be called more than once. In case of a repeated
   685       /// call, the previous snapshot gets lost.
   686       /// \param _graph The graph we make the snapshot of.
   687       void save(ListGraph &_graph) {
   688         if (attached()) {
   689           detach();
   690           clear();
   691         }
   692         attach(_graph);
   693       }
   694       
   695       /// \brief Undo the changes until the last snapshot.
   696       // 
   697       /// Undo the changes until the last snapshot created by save().
   698       void restore() {
   699 	detach();
   700 	for(std::list<Edge>::iterator it = added_edges.begin(); 
   701             it != added_edges.end(); ++it) {
   702 	  graph->erase(*it);
   703 	}
   704 	for(std::list<Node>::iterator it = added_nodes.begin(); 
   705             it != added_nodes.end(); ++it) {
   706 	  graph->erase(*it);
   707 	}
   708         clear();
   709       }
   710 
   711       /// \brief Gives back true when the snapshot is valid.
   712       ///
   713       /// Gives back true when the snapshot is valid.
   714       bool valid() const {
   715         return attached();
   716       }
   717     };
   718     
   719   };
   720 
   721   ///@}
   722 
   723   class ListUGraphBase {
   724 
   725   protected:
   726 
   727     struct NodeT {
   728       int first_out;
   729       int prev, next;
   730     };
   731  
   732     struct EdgeT {
   733       int target;
   734       int prev_out, next_out;
   735     };
   736 
   737     std::vector<NodeT> nodes;
   738 
   739     int first_node;
   740 
   741     int first_free_node;
   742 
   743     std::vector<EdgeT> edges;
   744 
   745     int first_free_edge;
   746     
   747   public:
   748     
   749     typedef ListUGraphBase Graph;
   750 
   751     class Node;
   752     class Edge;
   753     class UEdge;
   754     
   755     class Node {
   756       friend class ListUGraphBase;
   757     protected:
   758 
   759       int id;
   760       explicit Node(int pid) { id = pid;}
   761 
   762     public:
   763       Node() {}
   764       Node (Invalid) { id = -1; }
   765       bool operator==(const Node& node) const {return id == node.id;}
   766       bool operator!=(const Node& node) const {return id != node.id;}
   767       bool operator<(const Node& node) const {return id < node.id;}
   768     };
   769 
   770     class UEdge {
   771       friend class ListUGraphBase;
   772     protected:
   773 
   774       int id;
   775       explicit UEdge(int pid) { id = pid;}
   776 
   777     public:
   778       UEdge() {}
   779       UEdge (Invalid) { id = -1; }
   780       bool operator==(const UEdge& edge) const {return id == edge.id;}
   781       bool operator!=(const UEdge& edge) const {return id != edge.id;}
   782       bool operator<(const UEdge& edge) const {return id < edge.id;}
   783     };
   784 
   785     class Edge {
   786       friend class ListUGraphBase;
   787     protected:
   788 
   789       int id;
   790       explicit Edge(int pid) { id = pid;}
   791 
   792     public:
   793       operator UEdge() const { return uEdgeFromId(id / 2); }
   794 
   795       Edge() {}
   796       Edge (Invalid) { id = -1; }
   797       bool operator==(const Edge& edge) const {return id == edge.id;}
   798       bool operator!=(const Edge& edge) const {return id != edge.id;}
   799       bool operator<(const Edge& edge) const {return id < edge.id;}
   800     };
   801 
   802 
   803 
   804     ListUGraphBase()
   805       : nodes(), first_node(-1),
   806 	first_free_node(-1), edges(), first_free_edge(-1) {}
   807 
   808     
   809     int maxNodeId() const { return nodes.size()-1; } 
   810     int maxUEdgeId() const { return edges.size() / 2 - 1; }
   811     int maxEdgeId() const { return edges.size()-1; }
   812 
   813     Node source(Edge e) const { return Node(edges[e.id ^ 1].target); }
   814     Node target(Edge e) const { return Node(edges[e.id].target); }
   815 
   816     Node source(UEdge e) const { return Node(edges[2 * e.id].target); }
   817     Node target(UEdge e) const { return Node(edges[2 * e.id + 1].target); }
   818 
   819     static bool direction(Edge e) {
   820       return (e.id & 1) == 1;
   821     }
   822 
   823     static Edge direct(UEdge e, bool d) {
   824       return Edge(e.id * 2 + (d ? 1 : 0));
   825     }
   826 
   827     void first(Node& node) const { 
   828       node.id = first_node;
   829     }
   830 
   831     void next(Node& node) const {
   832       node.id = nodes[node.id].next;
   833     }
   834 
   835     void first(Edge& e) const { 
   836       int n = first_node;
   837       while (n != -1 && nodes[n].first_out == -1) {
   838         n = nodes[n].next;
   839       }
   840       e.id = (n == -1) ? -1 : nodes[n].first_out;
   841     }
   842 
   843     void next(Edge& e) const {
   844       if (edges[e.id].next_out != -1) {
   845 	e.id = edges[e.id].next_out;
   846       } else {
   847 	int n = nodes[edges[e.id ^ 1].target].next;
   848         while(n != -1 && nodes[n].first_out == -1) {
   849           n = nodes[n].next;
   850         }
   851 	e.id = (n == -1) ? -1 : nodes[n].first_out;
   852       }      
   853     }
   854 
   855     void first(UEdge& e) const { 
   856       int n = first_node;
   857       while (n != -1) {
   858         e.id = nodes[n].first_out;
   859         while ((e.id & 1) != 1) {
   860           e.id = edges[e.id].next_out;
   861         }
   862         if (e.id != -1) {
   863           e.id /= 2;
   864           return;
   865         } 
   866         n = nodes[n].next;
   867       }
   868       e.id = -1;
   869     }
   870 
   871     void next(UEdge& e) const {
   872       int n = edges[e.id * 2].target;
   873       e.id = edges[(e.id * 2) | 1].next_out;
   874       while ((e.id & 1) != 1) {
   875         e.id = edges[e.id].next_out;
   876       }
   877       if (e.id != -1) {
   878         e.id /= 2;
   879         return;
   880       } 
   881       n = nodes[n].next;
   882       while (n != -1) {
   883         e.id = nodes[n].first_out;
   884         while ((e.id & 1) != 1) {
   885           e.id = edges[e.id].next_out;
   886         }
   887         if (e.id != -1) {
   888           e.id /= 2;
   889           return;
   890         } 
   891         n = nodes[n].next;
   892       }
   893       e.id = -1;
   894     }
   895 
   896     void firstOut(Edge &e, const Node& v) const {
   897       e.id = nodes[v.id].first_out;
   898     }
   899     void nextOut(Edge &e) const {
   900       e.id = edges[e.id].next_out;
   901     }
   902 
   903     void firstIn(Edge &e, const Node& v) const {
   904       e.id = ((nodes[v.id].first_out) ^ 1);
   905       if (e.id == -2) e.id = -1;
   906     }
   907     void nextIn(Edge &e) const {
   908       e.id = ((edges[e.id ^ 1].next_out) ^ 1);
   909       if (e.id == -2) e.id = -1;
   910     }
   911 
   912     void firstInc(UEdge &e, bool& d, const Node& v) const {
   913       int de = nodes[v.id].first_out;
   914       if (de != -1 ) {
   915         e.id = de / 2;
   916         d = ((de & 1) == 1);
   917       } else {
   918         e.id = -1;
   919         d = true;
   920       }
   921     }
   922     void nextInc(UEdge &e, bool& d) const {
   923       int de = (edges[(e.id * 2) | (d ? 1 : 0)].next_out);
   924       if (de != -1 ) {
   925         e.id = de / 2;
   926         d = ((de & 1) == 1);
   927       } else {
   928         e.id = -1;
   929         d = true;
   930       }
   931     }
   932     
   933     static int id(Node v) { return v.id; }
   934     static int id(Edge e) { return e.id; }
   935     static int id(UEdge e) { return e.id; }
   936 
   937     static Node nodeFromId(int id) { return Node(id);}
   938     static Edge edgeFromId(int id) { return Edge(id);}
   939     static UEdge uEdgeFromId(int id) { return UEdge(id);}
   940 
   941     Node addNode() {     
   942       int n;
   943       
   944       if(first_free_node==-1) {
   945 	n = nodes.size();
   946 	nodes.push_back(NodeT());
   947       } else {
   948 	n = first_free_node;
   949 	first_free_node = nodes[n].next;
   950       }
   951       
   952       nodes[n].next = first_node;
   953       if (first_node != -1) nodes[first_node].prev = n;
   954       first_node = n;
   955       nodes[n].prev = -1;
   956       
   957       nodes[n].first_out = -1;
   958       
   959       return Node(n);
   960     }
   961     
   962     UEdge addEdge(Node u, Node v) {
   963       int n;      
   964 
   965       if (first_free_edge == -1) {
   966 	n = edges.size();
   967 	edges.push_back(EdgeT());
   968 	edges.push_back(EdgeT());
   969       } else {
   970 	n = first_free_edge;
   971 	first_free_edge = edges[n].next_out;
   972       }
   973       
   974       edges[n].target = u.id;
   975       edges[n | 1].target = v.id;
   976 
   977       edges[n].next_out = nodes[v.id].first_out;
   978       edges[n | 1].next_out = nodes[u.id].first_out;
   979       if (nodes[v.id].first_out != -1) {
   980 	edges[nodes[v.id].first_out].prev_out = n;
   981       }
   982       if (nodes[u.id].first_out != -1) {
   983 	edges[nodes[u.id].first_out].prev_out = (n | 1);
   984       }
   985       
   986       edges[n].prev_out = edges[n | 1].prev_out = -1;
   987 	
   988       nodes[v.id].first_out = n;
   989       nodes[u.id].first_out = (n | 1);
   990 
   991       return UEdge(n / 2);
   992     }
   993     
   994     void erase(const Node& node) {
   995       int n = node.id;
   996       
   997       if(nodes[n].next != -1) {
   998 	nodes[nodes[n].next].prev = nodes[n].prev;
   999       }
  1000       
  1001       if(nodes[n].prev != -1) {
  1002 	nodes[nodes[n].prev].next = nodes[n].next;
  1003       } else {
  1004 	first_node = nodes[n].next;
  1005       }
  1006       
  1007       nodes[n].next = first_free_node;
  1008       first_free_node = n;
  1009 
  1010     }
  1011     
  1012     void erase(const UEdge& edge) {
  1013       int n = edge.id * 2;
  1014       
  1015       if (edges[n].next_out != -1) {
  1016 	edges[edges[n].next_out].prev_out = edges[n].prev_out;
  1017       } 
  1018 
  1019       if (edges[n].prev_out != -1) {
  1020 	edges[edges[n].prev_out].next_out = edges[n].next_out;
  1021       } else {
  1022 	nodes[edges[n | 1].target].first_out = edges[n].next_out;
  1023       }
  1024 
  1025       if (edges[n | 1].next_out != -1) {
  1026 	edges[edges[n | 1].next_out].prev_out = edges[n | 1].prev_out;
  1027       } 
  1028 
  1029       if (edges[n | 1].prev_out != -1) {
  1030 	edges[edges[n | 1].prev_out].next_out = edges[n | 1].next_out;
  1031       } else {
  1032 	nodes[edges[n].target].first_out = edges[n | 1].next_out;
  1033       }
  1034       
  1035       edges[n].next_out = first_free_edge;
  1036       first_free_edge = n;      
  1037 
  1038     }
  1039 
  1040     void clear() {
  1041       edges.clear();
  1042       nodes.clear();
  1043       first_node = first_free_node = first_free_edge = -1;
  1044     }
  1045 
  1046   protected:
  1047 
  1048     void changeTarget(UEdge e, Node n) {
  1049       if(edges[2 * e.id].next_out != -1) {
  1050 	edges[edges[2 * e.id].next_out].prev_out = edges[2 * e.id].prev_out;
  1051       }
  1052       if(edges[2 * e.id].prev_out != -1) {
  1053 	edges[edges[2 * e.id].prev_out].next_out = 
  1054           edges[2 * e.id].next_out;
  1055       } else {
  1056         nodes[edges[(2 * e.id) | 1].target].first_out = 
  1057           edges[2 * e.id].next_out;
  1058       }
  1059 
  1060       if (nodes[n.id].first_out != -1) {
  1061 	edges[nodes[n.id].first_out].prev_out = 2 * e.id;
  1062       }
  1063       edges[(2 * e.id) | 1].target = n.id;
  1064       edges[2 * e.id].prev_out = -1;
  1065       edges[2 * e.id].next_out = nodes[n.id].first_out;
  1066       nodes[n.id].first_out = 2 * e.id;
  1067     }
  1068 
  1069     void changeSource(UEdge e, Node n) {
  1070       if(edges[(2 * e.id) | 1].next_out != -1) {
  1071 	edges[edges[(2 * e.id) | 1].next_out].prev_out = 
  1072           edges[(2 * e.id) | 1].prev_out;
  1073       }
  1074       if(edges[(2 * e.id) | 1].prev_out != -1) {
  1075 	edges[edges[(2 * e.id) | 1].prev_out].next_out = 
  1076           edges[(2 * e.id) | 1].next_out;
  1077       } else {
  1078         nodes[edges[2 * e.id].target].first_out = 
  1079           edges[(2 * e.id) | 1].next_out;
  1080       }
  1081 
  1082       if (nodes[n.id].first_out != -1) {
  1083 	edges[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
  1084       }
  1085       edges[2 * e.id].target = n.id;
  1086       edges[(2 * e.id) | 1].prev_out = -1;
  1087       edges[(2 * e.id) | 1].next_out = nodes[n.id].first_out;
  1088       nodes[n.id].first_out = ((2 * e.id) | 1);
  1089     }
  1090 
  1091   };
  1092 
  1093 //   typedef UGraphExtender<UndirGraphExtender<ListGraphBase> > 
  1094 //   ExtendedListUGraphBase;
  1095 
  1096   typedef UGraphExtender<ListUGraphBase> ExtendedListUGraphBase;
  1097 
  1098 
  1099 
  1100   /// \addtogroup graphs
  1101   /// @{
  1102 
  1103   ///An undirected list graph class.
  1104 
  1105   ///This is a simple and fast undirected graph implementation.
  1106   ///
  1107   ///An important extra feature of this graph implementation is that
  1108   ///its maps are real \ref concepts::ReferenceMap "reference map"s.
  1109   ///
  1110   ///It conforms to the
  1111   ///\ref concepts::UGraph "UGraph concept".
  1112   ///
  1113   ///\sa concepts::UGraph.
  1114   ///
  1115   class ListUGraph : public ExtendedListUGraphBase {
  1116   private:
  1117     ///ListUGraph is \e not copy constructible. Use UGraphCopy() instead.
  1118 
  1119     ///ListUGraph is \e not copy constructible. Use UGraphCopy() instead.
  1120     ///
  1121     ListUGraph(const ListUGraph &) :ExtendedListUGraphBase()  {};
  1122     ///\brief Assignment of ListUGraph to another one is \e not allowed.
  1123     ///Use UGraphCopy() instead.
  1124 
  1125     ///Assignment of ListUGraph to another one is \e not allowed.
  1126     ///Use UGraphCopy() instead.
  1127     void operator=(const ListUGraph &) {}
  1128   public:
  1129     /// Constructor
  1130     
  1131     /// Constructor.
  1132     ///
  1133     ListUGraph() {}
  1134 
  1135     typedef ExtendedListUGraphBase Parent;
  1136 
  1137     typedef Parent::OutEdgeIt IncEdgeIt;
  1138 
  1139     /// \brief Add a new node to the graph.
  1140     ///
  1141     /// \return the new node.
  1142     ///
  1143     Node addNode() { return Parent::addNode(); }
  1144 
  1145     /// \brief Add a new edge to the graph.
  1146     ///
  1147     /// Add a new edge to the graph with source node \c s
  1148     /// and target node \c t.
  1149     /// \return the new undirected edge.
  1150     UEdge addEdge(const Node& s, const Node& t) { 
  1151       return Parent::addEdge(s, t); 
  1152     }
  1153     /// \brief Changes the source of \c e to \c n
  1154     ///
  1155     /// Changes the source of \c e to \c n
  1156     ///
  1157     ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s
  1158     ///referencing the changed edge remain
  1159     ///valid. However <tt>OutEdgeIt</tt>s are invalidated.
  1160     void changeSource(UEdge e, Node n) { 
  1161       Parent::changeSource(e,n); 
  1162     }    
  1163     /// \brief Changes the target of \c e to \c n
  1164     ///
  1165     /// Changes the target of \c e to \c n
  1166     ///
  1167     /// \note The <tt>EdgeIt</tt>s referencing the changed edge remain
  1168     /// valid. However the other iterators may be invalidated.
  1169     void changeTarget(UEdge e, Node n) { 
  1170       Parent::changeTarget(e,n); 
  1171     }
  1172     /// \brief Changes the source of \c e to \c n
  1173     ///
  1174     /// Changes the source of \c e to \c n. It changes the proper
  1175     /// node of the represented undirected edge.
  1176     ///
  1177     ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s
  1178     ///referencing the changed edge remain
  1179     ///valid. However <tt>OutEdgeIt</tt>s are invalidated.
  1180     void changeSource(Edge e, Node n) { 
  1181       if (Parent::direction(e)) {
  1182         Parent::changeSource(e,n);
  1183       } else {
  1184         Parent::changeTarget(e,n);
  1185       } 
  1186     }
  1187     /// \brief Changes the target of \c e to \c n
  1188     ///
  1189     /// Changes the target of \c e to \c n. It changes the proper
  1190     /// node of the represented undirected edge.
  1191     ///
  1192     ///\note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
  1193     ///referencing the changed edge remain
  1194     ///valid. However <tt>InEdgeIt</tt>s are invalidated.
  1195     void changeTarget(Edge e, Node n) { 
  1196       if (Parent::direction(e)) {
  1197         Parent::changeTarget(e,n);
  1198       } else {
  1199         Parent::changeSource(e,n);
  1200       } 
  1201     }
  1202     /// \brief Contract two nodes.
  1203     ///
  1204     /// This function contracts two nodes.
  1205     ///
  1206     /// Node \p b will be removed but instead of deleting
  1207     /// its neighboring edges, they will be joined to \p a.
  1208     /// The last parameter \p r controls whether to remove loops. \c true
  1209     /// means that loops will be removed.
  1210     ///
  1211     /// \note The <tt>EdgeIt</tt>s referencing a moved edge remain
  1212     /// valid.
  1213     void contract(Node a, Node b, bool r = true) {
  1214       for(IncEdgeIt e(*this, b); e!=INVALID;) {
  1215 	IncEdgeIt f = e; ++f;
  1216 	if (r && runningNode(e) == a) {
  1217 	  erase(e);
  1218 	} else if (source(e) == b) {
  1219 	  changeSource(e, a);
  1220 	} else {
  1221 	  changeTarget(e, a);
  1222 	}
  1223 	e = f;
  1224       }
  1225       erase(b);
  1226     }
  1227 
  1228 
  1229     /// \brief Class to make a snapshot of the graph and restore
  1230     /// to it later.
  1231     ///
  1232     /// Class to make a snapshot of the graph and to restore it
  1233     /// later.
  1234     ///
  1235     /// The newly added nodes and undirected edges can be removed
  1236     /// using the restore() function.
  1237     ///
  1238     /// \warning Edge and node deletions cannot be restored. This
  1239     /// events invalidate the snapshot. 
  1240     class Snapshot {
  1241     protected:
  1242 
  1243       typedef Parent::NodeNotifier NodeNotifier;
  1244 
  1245       class NodeObserverProxy : public NodeNotifier::ObserverBase {
  1246       public:
  1247 
  1248         NodeObserverProxy(Snapshot& _snapshot)
  1249           : snapshot(_snapshot) {}
  1250 
  1251         using NodeNotifier::ObserverBase::attach;
  1252         using NodeNotifier::ObserverBase::detach;
  1253         using NodeNotifier::ObserverBase::attached;
  1254         
  1255       protected:
  1256         
  1257         virtual void add(const Node& node) {
  1258           snapshot.addNode(node);
  1259         }
  1260         virtual void add(const std::vector<Node>& nodes) {
  1261           for (int i = nodes.size() - 1; i >= 0; ++i) {
  1262             snapshot.addNode(nodes[i]);
  1263           }
  1264         }
  1265         virtual void erase(const Node& node) {
  1266           snapshot.eraseNode(node);
  1267         }
  1268         virtual void erase(const std::vector<Node>& nodes) {
  1269           for (int i = 0; i < int(nodes.size()); ++i) {
  1270             snapshot.eraseNode(nodes[i]);
  1271           }
  1272         }
  1273         virtual void build() {
  1274           Node node;
  1275           std::vector<Node> nodes;
  1276           for (notifier()->first(node); node != INVALID; 
  1277                notifier()->next(node)) {
  1278             nodes.push_back(node);
  1279           }
  1280           for (int i = nodes.size() - 1; i >= 0; --i) {
  1281             snapshot.addNode(nodes[i]);
  1282           }
  1283         }
  1284         virtual void clear() {
  1285           Node node;
  1286           for (notifier()->first(node); node != INVALID; 
  1287                notifier()->next(node)) {
  1288             snapshot.eraseNode(node);
  1289           }
  1290         }
  1291 
  1292         Snapshot& snapshot;
  1293       };
  1294 
  1295       class UEdgeObserverProxy : public UEdgeNotifier::ObserverBase {
  1296       public:
  1297 
  1298         UEdgeObserverProxy(Snapshot& _snapshot)
  1299           : snapshot(_snapshot) {}
  1300 
  1301         using UEdgeNotifier::ObserverBase::attach;
  1302         using UEdgeNotifier::ObserverBase::detach;
  1303         using UEdgeNotifier::ObserverBase::attached;
  1304         
  1305       protected:
  1306 
  1307         virtual void add(const UEdge& edge) {
  1308           snapshot.addUEdge(edge);
  1309         }
  1310         virtual void add(const std::vector<UEdge>& edges) {
  1311           for (int i = edges.size() - 1; i >= 0; ++i) {
  1312             snapshot.addUEdge(edges[i]);
  1313           }
  1314         }
  1315         virtual void erase(const UEdge& edge) {
  1316           snapshot.eraseUEdge(edge);
  1317         }
  1318         virtual void erase(const std::vector<UEdge>& edges) {
  1319           for (int i = 0; i < int(edges.size()); ++i) {
  1320             snapshot.eraseUEdge(edges[i]);
  1321           }
  1322         }
  1323         virtual void build() {
  1324           UEdge edge;
  1325           std::vector<UEdge> edges;
  1326           for (notifier()->first(edge); edge != INVALID; 
  1327                notifier()->next(edge)) {
  1328             edges.push_back(edge);
  1329           }
  1330           for (int i = edges.size() - 1; i >= 0; --i) {
  1331             snapshot.addUEdge(edges[i]);
  1332           }
  1333         }
  1334         virtual void clear() {
  1335           UEdge edge;
  1336           for (notifier()->first(edge); edge != INVALID; 
  1337                notifier()->next(edge)) {
  1338             snapshot.eraseUEdge(edge);
  1339           }
  1340         }
  1341 
  1342         Snapshot& snapshot;
  1343       };
  1344       
  1345       ListUGraph *graph;
  1346 
  1347       NodeObserverProxy node_observer_proxy;
  1348       UEdgeObserverProxy edge_observer_proxy;
  1349 
  1350       std::list<Node> added_nodes;
  1351       std::list<UEdge> added_edges;
  1352 
  1353 
  1354       void addNode(const Node& node) {
  1355         added_nodes.push_front(node);        
  1356       }
  1357       void eraseNode(const Node& node) {
  1358         std::list<Node>::iterator it = 
  1359           std::find(added_nodes.begin(), added_nodes.end(), node);
  1360         if (it == added_nodes.end()) {
  1361           clear();
  1362           edge_observer_proxy.detach();
  1363           throw NodeNotifier::ImmediateDetach();
  1364         } else {
  1365           added_nodes.erase(it);
  1366         }
  1367       }
  1368 
  1369       void addUEdge(const UEdge& edge) {
  1370         added_edges.push_front(edge);        
  1371       }
  1372       void eraseUEdge(const UEdge& edge) {
  1373         std::list<UEdge>::iterator it = 
  1374           std::find(added_edges.begin(), added_edges.end(), edge);
  1375         if (it == added_edges.end()) {
  1376           clear();
  1377           node_observer_proxy.detach();
  1378           throw UEdgeNotifier::ImmediateDetach();
  1379         } else {
  1380           added_edges.erase(it);
  1381         }        
  1382       }
  1383 
  1384       void attach(ListUGraph &_graph) {
  1385 	graph = &_graph;
  1386 	node_observer_proxy.attach(graph->notifier(Node()));
  1387         edge_observer_proxy.attach(graph->notifier(UEdge()));
  1388       }
  1389             
  1390       void detach() {
  1391 	node_observer_proxy.detach();
  1392 	edge_observer_proxy.detach();
  1393       }
  1394 
  1395       bool attached() const {
  1396         return node_observer_proxy.attached();
  1397       }
  1398 
  1399       void clear() {
  1400         added_nodes.clear();
  1401         added_edges.clear();        
  1402       }
  1403 
  1404     public:
  1405 
  1406       /// \brief Default constructor.
  1407       ///
  1408       /// Default constructor.
  1409       /// To actually make a snapshot you must call save().
  1410       Snapshot() 
  1411         : graph(0), node_observer_proxy(*this), 
  1412           edge_observer_proxy(*this) {}
  1413       
  1414       /// \brief Constructor that immediately makes a snapshot.
  1415       ///      
  1416       /// This constructor immediately makes a snapshot of the graph.
  1417       /// \param _graph The graph we make a snapshot of.
  1418       Snapshot(ListUGraph &_graph) 
  1419         : node_observer_proxy(*this), 
  1420           edge_observer_proxy(*this) {
  1421 	attach(_graph);
  1422       }
  1423       
  1424       /// \brief Make a snapshot.
  1425       ///
  1426       /// Make a snapshot of the graph.
  1427       ///
  1428       /// This function can be called more than once. In case of a repeated
  1429       /// call, the previous snapshot gets lost.
  1430       /// \param _graph The graph we make the snapshot of.
  1431       void save(ListUGraph &_graph) {
  1432         if (attached()) {
  1433           detach();
  1434           clear();
  1435         }
  1436         attach(_graph);
  1437       }
  1438       
  1439       /// \brief Undo the changes until the last snapshot.
  1440       // 
  1441       /// Undo the changes until the last snapshot created by save().
  1442       void restore() {
  1443 	detach();
  1444 	for(std::list<UEdge>::iterator it = added_edges.begin(); 
  1445             it != added_edges.end(); ++it) {
  1446 	  graph->erase(*it);
  1447 	}
  1448 	for(std::list<Node>::iterator it = added_nodes.begin(); 
  1449             it != added_nodes.end(); ++it) {
  1450 	  graph->erase(*it);
  1451 	}
  1452         clear();
  1453       }
  1454 
  1455       /// \brief Gives back true when the snapshot is valid.
  1456       ///
  1457       /// Gives back true when the snapshot is valid.
  1458       bool valid() const {
  1459         return attached();
  1460       }
  1461     };
  1462   };
  1463 
  1464 
  1465   class ListBpUGraphBase {
  1466   public:
  1467 
  1468     class NodeSetError : public LogicError {
  1469     public:
  1470       virtual const char* what() const throw() { 
  1471 	return "lemon::ListBpUGraph::NodeSetError";
  1472       }
  1473     };
  1474 
  1475   protected:
  1476 
  1477     struct NodeT {
  1478       int first_edge, prev, next;
  1479     };
  1480 
  1481     struct UEdgeT {
  1482       int aNode, prev_out, next_out;
  1483       int bNode, prev_in, next_in;
  1484     };
  1485 
  1486     std::vector<NodeT> aNodes;
  1487     std::vector<NodeT> bNodes;
  1488 
  1489     std::vector<UEdgeT> edges;
  1490 
  1491     int first_anode;
  1492     int first_free_anode;
  1493 
  1494     int first_bnode;
  1495     int first_free_bnode;
  1496 
  1497     int first_free_edge;
  1498 
  1499   public:
  1500   
  1501     class Node {
  1502       friend class ListBpUGraphBase;
  1503     protected:
  1504       int id;
  1505 
  1506       explicit Node(int _id) : id(_id) {}
  1507     public:
  1508       Node() {}
  1509       Node(Invalid) { id = -1; }
  1510       bool operator==(const Node i) const {return id==i.id;}
  1511       bool operator!=(const Node i) const {return id!=i.id;}
  1512       bool operator<(const Node i) const {return id<i.id;}
  1513     };
  1514 
  1515     class UEdge {
  1516       friend class ListBpUGraphBase;
  1517     protected:
  1518       int id;
  1519 
  1520       explicit UEdge(int _id) { id = _id;}
  1521     public:
  1522       UEdge() {}
  1523       UEdge (Invalid) { id = -1; }
  1524       bool operator==(const UEdge i) const {return id==i.id;}
  1525       bool operator!=(const UEdge i) const {return id!=i.id;}
  1526       bool operator<(const UEdge i) const {return id<i.id;}
  1527     };
  1528 
  1529     ListBpUGraphBase()
  1530       : first_anode(-1), first_free_anode(-1),
  1531         first_bnode(-1), first_free_bnode(-1),
  1532         first_free_edge(-1) {}
  1533 
  1534     void firstANode(Node& node) const {
  1535       node.id = first_anode != -1 ? (first_anode << 1) : -1;
  1536     }
  1537     void nextANode(Node& node) const {
  1538       node.id = aNodes[node.id >> 1].next;
  1539     }
  1540 
  1541     void firstBNode(Node& node) const {
  1542       node.id = first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
  1543     }
  1544     void nextBNode(Node& node) const {
  1545       node.id = bNodes[node.id >> 1].next;
  1546     }
  1547 
  1548     void first(Node& node) const {
  1549       if (first_anode != -1) {
  1550         node.id = (first_anode << 1);
  1551       } else if (first_bnode != -1) {
  1552         node.id = (first_bnode << 1) + 1;
  1553       } else {
  1554         node.id = -1;
  1555       }
  1556     }
  1557     void next(Node& node) const {
  1558       if (aNode(node)) {
  1559         node.id = aNodes[node.id >> 1].next;
  1560         if (node.id == -1) {
  1561           if (first_bnode != -1) {
  1562             node.id = (first_bnode << 1) + 1;
  1563           }
  1564         }
  1565       } else {
  1566         node.id = bNodes[node.id >> 1].next;
  1567       }
  1568     }
  1569   
  1570     void first(UEdge& edge) const {
  1571       int aid = first_anode;
  1572       while (aid != -1 && aNodes[aid].first_edge == -1) {
  1573         aid = aNodes[aid].next != -1 ? 
  1574           aNodes[aid].next >> 1 : -1;
  1575       }
  1576       if (aid != -1) {
  1577         edge.id = aNodes[aid].first_edge;
  1578       } else {
  1579         edge.id = -1;
  1580       }
  1581     }
  1582     void next(UEdge& edge) const {
  1583       int aid = edges[edge.id].aNode >> 1;
  1584       edge.id = edges[edge.id].next_out;
  1585       if (edge.id == -1) {
  1586         aid = aNodes[aid].next != -1 ? 
  1587           aNodes[aid].next >> 1 : -1;
  1588         while (aid != -1 && aNodes[aid].first_edge == -1) {
  1589           aid = aNodes[aid].next != -1 ? 
  1590           aNodes[aid].next >> 1 : -1;
  1591         }
  1592         if (aid != -1) {
  1593           edge.id = aNodes[aid].first_edge;
  1594         } else {
  1595           edge.id = -1;
  1596         }
  1597       }
  1598     }
  1599 
  1600     void firstFromANode(UEdge& edge, const Node& node) const {
  1601       LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
  1602       edge.id = aNodes[node.id >> 1].first_edge;
  1603     }
  1604     void nextFromANode(UEdge& edge) const {
  1605       edge.id = edges[edge.id].next_out;
  1606     }
  1607 
  1608     void firstFromBNode(UEdge& edge, const Node& node) const {
  1609       LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
  1610       edge.id = bNodes[node.id >> 1].first_edge;
  1611     }
  1612     void nextFromBNode(UEdge& edge) const {
  1613       edge.id = edges[edge.id].next_in;
  1614     }
  1615 
  1616     static int id(const Node& node) {
  1617       return node.id;
  1618     }
  1619     static Node nodeFromId(int id) {
  1620       return Node(id);
  1621     }
  1622     int maxNodeId() const {
  1623       return aNodes.size() > bNodes.size() ?
  1624 	aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
  1625     }
  1626   
  1627     static int id(const UEdge& edge) {
  1628       return edge.id;
  1629     }
  1630     static UEdge uEdgeFromId(int id) {
  1631       return UEdge(id);
  1632     }
  1633     int maxUEdgeId() const {
  1634       return edges.size();
  1635     }
  1636   
  1637     static int aNodeId(const Node& node) {
  1638       return node.id >> 1;
  1639     }
  1640     static Node nodeFromANodeId(int id) {
  1641       return Node(id << 1);
  1642     }
  1643     int maxANodeId() const {
  1644       return aNodes.size();
  1645     }
  1646 
  1647     static int bNodeId(const Node& node) {
  1648       return node.id >> 1;
  1649     }
  1650     static Node nodeFromBNodeId(int id) {
  1651       return Node((id << 1) + 1);
  1652     }
  1653     int maxBNodeId() const {
  1654       return bNodes.size();
  1655     }
  1656 
  1657     Node aNode(const UEdge& edge) const {
  1658       return Node(edges[edge.id].aNode);
  1659     }
  1660     Node bNode(const UEdge& edge) const {
  1661       return Node(edges[edge.id].bNode);
  1662     }
  1663 
  1664     static bool aNode(const Node& node) {
  1665       return (node.id & 1) == 0;
  1666     }
  1667 
  1668     static bool bNode(const Node& node) {
  1669       return (node.id & 1) == 1;
  1670     }
  1671 
  1672     Node addANode() {
  1673       int aid;
  1674       if (first_free_anode == -1) {
  1675         aid = aNodes.size();
  1676         aNodes.push_back(NodeT());
  1677       } else {
  1678         aid = first_free_anode;
  1679         first_free_anode = aNodes[first_free_anode].next;
  1680       }
  1681       if (first_anode != -1) {
  1682         aNodes[aid].next = first_anode << 1;
  1683         aNodes[first_anode].prev = aid << 1;
  1684       } else {
  1685         aNodes[aid].next = -1;
  1686       }
  1687       aNodes[aid].prev = -1;
  1688       first_anode = aid;
  1689       aNodes[aid].first_edge = -1;
  1690       return Node(aid << 1);
  1691     }
  1692 
  1693     Node addBNode() {
  1694       int bid;
  1695       if (first_free_bnode == -1) {
  1696         bid = bNodes.size();
  1697         bNodes.push_back(NodeT());
  1698       } else {
  1699         bid = first_free_bnode;
  1700         first_free_bnode = bNodes[first_free_bnode].next;
  1701       }
  1702       if (first_bnode != -1) {
  1703         bNodes[bid].next = (first_bnode << 1) + 1;
  1704         bNodes[first_bnode].prev = (bid << 1) + 1;
  1705       } else {
  1706         bNodes[bid].next = -1;
  1707       }
  1708       bNodes[bid].prev = -1;
  1709       first_bnode = bid;
  1710       bNodes[bid].first_edge = -1;
  1711       return Node((bid << 1) + 1);
  1712     }
  1713 
  1714     UEdge addEdge(const Node& source, const Node& target) {
  1715       LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
  1716       int edgeId;
  1717       if (first_free_edge != -1) {
  1718         edgeId = first_free_edge;
  1719         first_free_edge = edges[edgeId].next_out;
  1720       } else {
  1721         edgeId = edges.size();
  1722         edges.push_back(UEdgeT());
  1723       }
  1724       if ((source.id & 1) == 0) {
  1725 	edges[edgeId].aNode = source.id;
  1726 	edges[edgeId].bNode = target.id;
  1727       } else {
  1728 	edges[edgeId].aNode = target.id;
  1729 	edges[edgeId].bNode = source.id;
  1730       }
  1731       edges[edgeId].next_out = aNodes[edges[edgeId].aNode >> 1].first_edge;
  1732       edges[edgeId].prev_out = -1;
  1733       if (aNodes[edges[edgeId].aNode >> 1].first_edge != -1) {
  1734         edges[aNodes[edges[edgeId].aNode >> 1].first_edge].prev_out = edgeId;
  1735       }
  1736       aNodes[edges[edgeId].aNode >> 1].first_edge = edgeId;
  1737       edges[edgeId].next_in = bNodes[edges[edgeId].bNode >> 1].first_edge;
  1738       edges[edgeId].prev_in = -1;
  1739       if (bNodes[edges[edgeId].bNode >> 1].first_edge != -1) {
  1740         edges[bNodes[edges[edgeId].bNode >> 1].first_edge].prev_in = edgeId;
  1741       }
  1742       bNodes[edges[edgeId].bNode >> 1].first_edge = edgeId;
  1743       return UEdge(edgeId);
  1744     }
  1745 
  1746     void erase(const Node& node) {
  1747       if (aNode(node)) {
  1748         int aid = node.id >> 1;
  1749         if (aNodes[aid].prev != -1) {
  1750           aNodes[aNodes[aid].prev >> 1].next = aNodes[aid].next;
  1751         } else {
  1752           first_anode = 
  1753             aNodes[aid].next != -1 ? aNodes[aid].next >> 1 : -1;
  1754         }
  1755         if (aNodes[aid].next != -1) {
  1756           aNodes[aNodes[aid].next >> 1].prev = aNodes[aid].prev;
  1757         }
  1758         aNodes[aid].next = first_free_anode;
  1759         first_free_anode = aid;
  1760       } else {
  1761         int bid = node.id >> 1;
  1762         if (bNodes[bid].prev != -1) {
  1763           bNodes[bNodes[bid].prev >> 1].next = bNodes[bid].next;
  1764         } else {
  1765           first_bnode = 
  1766             bNodes[bid].next != -1 ? bNodes[bid].next >> 1 : -1;
  1767         }
  1768         if (bNodes[bid].next != -1) {
  1769           bNodes[bNodes[bid].next >> 1].prev = bNodes[bid].prev;
  1770         }
  1771         bNodes[bid].next = first_free_bnode;
  1772         first_free_bnode = bid;
  1773       }
  1774     }
  1775 
  1776     void erase(const UEdge& edge) {
  1777 
  1778       if (edges[edge.id].prev_out != -1) {
  1779         edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
  1780       } else {
  1781         aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out;
  1782       }
  1783       if (edges[edge.id].next_out != -1) {
  1784         edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;
  1785       }
  1786 
  1787       if (edges[edge.id].prev_in != -1) {
  1788         edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
  1789       } else {
  1790         bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in;
  1791       }
  1792       if (edges[edge.id].next_in != -1) {
  1793         edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;
  1794       }
  1795 
  1796       edges[edge.id].next_out = first_free_edge;
  1797       first_free_edge = edge.id;
  1798     }
  1799  
  1800     void clear() {
  1801       aNodes.clear();
  1802       bNodes.clear();
  1803       edges.clear();
  1804       first_anode = -1;
  1805       first_free_anode = -1;
  1806       first_bnode = -1;
  1807       first_free_bnode = -1;
  1808       first_free_edge = -1;
  1809     }
  1810 
  1811     void changeANode(const UEdge& edge, const Node& node) {
  1812       LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
  1813       if (edges[edge.id].prev_out != -1) {
  1814         edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
  1815       } else {
  1816         aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out;
  1817       }
  1818       if (edges[edge.id].next_out != -1) {
  1819         edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;  
  1820       }
  1821       if (aNodes[node.id >> 1].first_edge != -1) {
  1822         edges[aNodes[node.id >> 1].first_edge].prev_out = edge.id;
  1823       }
  1824       edges[edge.id].prev_out = -1;
  1825       edges[edge.id].next_out = aNodes[node.id >> 1].first_edge;
  1826       aNodes[node.id >> 1].first_edge = edge.id;
  1827       edges[edge.id].aNode = node.id;
  1828     } 
  1829 
  1830     void changeBNode(const UEdge& edge, const Node& node) {
  1831       LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
  1832       if (edges[edge.id].prev_in != -1) {
  1833         edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
  1834       } else {
  1835         bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in;
  1836       }
  1837       if (edges[edge.id].next_in != -1) {
  1838         edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;  
  1839       }
  1840       if (bNodes[node.id >> 1].first_edge != -1) {
  1841         edges[bNodes[node.id >> 1].first_edge].prev_in = edge.id;
  1842       }
  1843       edges[edge.id].prev_in = -1;
  1844       edges[edge.id].next_in = bNodes[node.id >> 1].first_edge;
  1845       bNodes[node.id >> 1].first_edge = edge.id;
  1846       edges[edge.id].bNode = node.id;
  1847     } 
  1848 
  1849   };
  1850 
  1851 
  1852   typedef BpUGraphExtender<BidirBpUGraphExtender<ListBpUGraphBase> > 
  1853   ExtendedListBpUGraphBase;
  1854 
  1855   /// \ingroup graphs
  1856   ///
  1857   /// \brief A smart bipartite undirected graph class.
  1858   ///
  1859   /// This is a bipartite undirected graph implementation.
  1860   /// It is conforms to the \ref concepts::BpUGraph "BpUGraph concept".
  1861   ///
  1862   ///An important extra feature of this graph implementation is that
  1863   ///its maps are real \ref concepts::ReferenceMap "reference map"s.
  1864   ///
  1865   /// \sa concepts::BpUGraph.
  1866   ///
  1867   class ListBpUGraph : public ExtendedListBpUGraphBase {
  1868     /// \brief ListBpUGraph is \e not copy constructible.
  1869     ///
  1870     ///ListBpUGraph is \e not copy constructible.
  1871     ListBpUGraph(const ListBpUGraph &) :ExtendedListBpUGraphBase()  {};
  1872     /// \brief Assignment of ListBpUGraph to another one is \e not
  1873     /// allowed.
  1874     ///
  1875     /// Assignment of ListBpUGraph to another one is \e not allowed.
  1876     void operator=(const ListBpUGraph &) {}
  1877   public:
  1878     /// \brief Constructor
  1879     ///    
  1880     /// Constructor.
  1881     ///
  1882     ListBpUGraph() {}
  1883 
  1884     typedef ExtendedListBpUGraphBase Parent;
  1885     /// \brief Add a new ANode to the graph.
  1886     ///
  1887     /// \return the new node.
  1888     ///
  1889     Node addANode() { return Parent::addANode(); }
  1890 
  1891     /// \brief Add a new BNode to the graph.
  1892     ///
  1893     /// \return the new node.
  1894     ///
  1895     Node addBNode() { return Parent::addBNode(); }
  1896 
  1897     /// \brief Add a new edge to the graph.
  1898     ///
  1899     /// Add a new edge to the graph with an ANode and a BNode.
  1900     /// \return the new undirected edge.
  1901     UEdge addEdge(const Node& s, const Node& t) { 
  1902       return Parent::addEdge(s, t); 
  1903     }
  1904 
  1905     /// \brief Changes the ANode of \c e to \c n
  1906     ///
  1907     /// Changes the ANode of \c e to \c n
  1908     ///
  1909     ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s referencing
  1910     ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are
  1911     ///invalidated.
  1912     void changeANode(UEdge e, Node n) { 
  1913       Parent::changeANode(e,n); 
  1914     }
  1915 
  1916     /// \brief Changes the BNode of \c e to \c n
  1917     ///
  1918     /// Changes the BNode of \c e to \c n
  1919     ///
  1920     /// \note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
  1921     /// referencing the changed edge remain
  1922     /// valid. However <tt>InEdgeIt</tt>s are invalidated.
  1923     void changeBNode(UEdge e, Node n) { 
  1924       Parent::changeBNode(e,n); 
  1925     }
  1926 
  1927     /// \brief Changes the source(ANode) of \c e to \c n
  1928     ///
  1929     /// Changes the source(ANode) of \c e to \c n
  1930     ///
  1931     ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s referencing
  1932     ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are
  1933     ///invalidated.
  1934     void changeSource(UEdge e, Node n) { 
  1935       Parent::changeANode(e,n); 
  1936     }
  1937 
  1938     /// \brief Changes the target(BNode) of \c e to \c n
  1939     ///
  1940     /// Changes the target(BNode) of \c e to \c n
  1941     ///
  1942     /// \note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
  1943     /// referencing the changed edge remain
  1944     /// valid. However <tt>InEdgeIt</tt>s are invalidated.
  1945     void changeTarget(UEdge e, Node n) { 
  1946       Parent::changeBNode(e,n); 
  1947     }
  1948 
  1949     /// \brief Changes the source of \c e to \c n
  1950     ///
  1951     /// Changes the source of \c e to \c n. It changes the proper
  1952     /// node of the represented undirected edge.
  1953     ///
  1954     ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s
  1955     ///referencing the changed edge remain
  1956     ///valid. However <tt>OutEdgeIt</tt>s are invalidated.
  1957     void changeSource(Edge e, Node n) { 
  1958       if (Parent::direction(e)) {
  1959         Parent::changeANode(e,n);
  1960       } else {
  1961         Parent::changeBNode(e,n);
  1962       } 
  1963     }
  1964     /// \brief Changes the target of \c e to \c n
  1965     ///
  1966     /// Changes the target of \c e to \c n. It changes the proper
  1967     /// node of the represented undirected edge.
  1968     ///
  1969     ///\note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
  1970     ///referencing the changed edge remain
  1971     ///valid. However <tt>InEdgeIt</tt>s are invalidated.
  1972     void changeTarget(Edge e, Node n) { 
  1973       if (Parent::direction(e)) {
  1974         Parent::changeBNode(e,n);
  1975       } else {
  1976         Parent::changeANode(e,n);
  1977       } 
  1978     }
  1979     /// \brief Contract two nodes.
  1980     ///
  1981     /// This function contracts two nodes.
  1982     ///
  1983     /// Node \p b will be removed but instead of deleting its
  1984     /// neighboring edges, they will be joined to \p a.  The two nodes
  1985     /// should be from the same nodeset, of course.
  1986     ///
  1987     /// \note The <tt>EdgeIt</tt>s referencing a moved edge remain
  1988     /// valid.
  1989     void contract(const Node& a, const Node& b) {
  1990       LEMON_ASSERT(Parent::aNode(a) == Parent::aNode(b), NodeSetError());
  1991       if (Parent::aNode(a)) {
  1992         for (IncEdgeIt e(*this, b); e!=INVALID;) {
  1993           IncEdgeIt f = e; ++f;
  1994           changeSource(e, a);
  1995           e = f;
  1996         }
  1997       } else {
  1998         for (IncEdgeIt e(*this, b); e!=INVALID;) {
  1999           IncEdgeIt f = e; ++f;
  2000           changeTarget(e, a);
  2001           e = f;
  2002         }
  2003       }
  2004       erase(b);
  2005     }
  2006 
  2007     /// \brief Class to make a snapshot of the graph and restore
  2008     /// to it later.
  2009     ///
  2010     /// Class to make a snapshot of the graph and to restore it
  2011     /// later.
  2012     ///
  2013     /// The newly added nodes and undirected edges can be removed
  2014     /// using the restore() function.
  2015     ///
  2016     /// \warning Edge and node deletions cannot be restored. This
  2017     /// events invalidate the snapshot. 
  2018     class Snapshot {
  2019     protected:
  2020 
  2021       typedef Parent::NodeNotifier NodeNotifier;
  2022 
  2023       class NodeObserverProxy : public NodeNotifier::ObserverBase {
  2024       public:
  2025 
  2026         NodeObserverProxy(Snapshot& _snapshot)
  2027           : snapshot(_snapshot) {}
  2028 
  2029         using NodeNotifier::ObserverBase::attach;
  2030         using NodeNotifier::ObserverBase::detach;
  2031         using NodeNotifier::ObserverBase::attached;
  2032         
  2033       protected:
  2034         
  2035         virtual void add(const Node& node) {
  2036           snapshot.addNode(node);
  2037         }
  2038         virtual void add(const std::vector<Node>& nodes) {
  2039           for (int i = nodes.size() - 1; i >= 0; ++i) {
  2040             snapshot.addNode(nodes[i]);
  2041           }
  2042         }
  2043         virtual void erase(const Node& node) {
  2044           snapshot.eraseNode(node);
  2045         }
  2046         virtual void erase(const std::vector<Node>& nodes) {
  2047           for (int i = 0; i < int(nodes.size()); ++i) {
  2048             snapshot.eraseNode(nodes[i]);
  2049           }
  2050         }
  2051         virtual void build() {
  2052           Node node;
  2053           std::vector<Node> nodes;
  2054           for (notifier()->first(node); node != INVALID; 
  2055                notifier()->next(node)) {
  2056             nodes.push_back(node);
  2057           }
  2058           for (int i = nodes.size() - 1; i >= 0; --i) {
  2059             snapshot.addNode(nodes[i]);
  2060           }
  2061         }
  2062         virtual void clear() {
  2063           Node node;
  2064           for (notifier()->first(node); node != INVALID; 
  2065                notifier()->next(node)) {
  2066             snapshot.eraseNode(node);
  2067           }
  2068         }
  2069 
  2070         Snapshot& snapshot;
  2071       };
  2072 
  2073       class UEdgeObserverProxy : public UEdgeNotifier::ObserverBase {
  2074       public:
  2075 
  2076         UEdgeObserverProxy(Snapshot& _snapshot)
  2077           : snapshot(_snapshot) {}
  2078 
  2079         using UEdgeNotifier::ObserverBase::attach;
  2080         using UEdgeNotifier::ObserverBase::detach;
  2081         using UEdgeNotifier::ObserverBase::attached;
  2082         
  2083       protected:
  2084 
  2085         virtual void add(const UEdge& edge) {
  2086           snapshot.addUEdge(edge);
  2087         }
  2088         virtual void add(const std::vector<UEdge>& edges) {
  2089           for (int i = edges.size() - 1; i >= 0; ++i) {
  2090             snapshot.addUEdge(edges[i]);
  2091           }
  2092         }
  2093         virtual void erase(const UEdge& edge) {
  2094           snapshot.eraseUEdge(edge);
  2095         }
  2096         virtual void erase(const std::vector<UEdge>& edges) {
  2097           for (int i = 0; i < int(edges.size()); ++i) {
  2098             snapshot.eraseUEdge(edges[i]);
  2099           }
  2100         }
  2101         virtual void build() {
  2102           UEdge edge;
  2103           std::vector<UEdge> edges;
  2104           for (notifier()->first(edge); edge != INVALID; 
  2105                notifier()->next(edge)) {
  2106             edges.push_back(edge);
  2107           }
  2108           for (int i = edges.size() - 1; i >= 0; --i) {
  2109             snapshot.addUEdge(edges[i]);
  2110           }
  2111         }
  2112         virtual void clear() {
  2113           UEdge edge;
  2114           for (notifier()->first(edge); edge != INVALID; 
  2115                notifier()->next(edge)) {
  2116             snapshot.eraseUEdge(edge);
  2117           }
  2118         }
  2119 
  2120         Snapshot& snapshot;
  2121       };
  2122       
  2123       ListBpUGraph *graph;
  2124 
  2125       NodeObserverProxy node_observer_proxy;
  2126       UEdgeObserverProxy edge_observer_proxy;
  2127 
  2128       std::list<Node> added_nodes;
  2129       std::list<UEdge> added_edges;
  2130 
  2131 
  2132       void addNode(const Node& node) {
  2133         added_nodes.push_front(node);        
  2134       }
  2135       void eraseNode(const Node& node) {
  2136         std::list<Node>::iterator it = 
  2137           std::find(added_nodes.begin(), added_nodes.end(), node);
  2138         if (it == added_nodes.end()) {
  2139           clear();
  2140           edge_observer_proxy.detach();
  2141           throw NodeNotifier::ImmediateDetach();
  2142         } else {
  2143           added_nodes.erase(it);
  2144         }
  2145       }
  2146 
  2147       void addUEdge(const UEdge& edge) {
  2148         added_edges.push_front(edge);        
  2149       }
  2150       void eraseUEdge(const UEdge& edge) {
  2151         std::list<UEdge>::iterator it = 
  2152           std::find(added_edges.begin(), added_edges.end(), edge);
  2153         if (it == added_edges.end()) {
  2154           clear();
  2155           node_observer_proxy.detach();
  2156           throw UEdgeNotifier::ImmediateDetach();
  2157         } else {
  2158           added_edges.erase(it);
  2159         }        
  2160       }
  2161 
  2162       void attach(ListBpUGraph &_graph) {
  2163 	graph = &_graph;
  2164 	node_observer_proxy.attach(graph->notifier(Node()));
  2165         edge_observer_proxy.attach(graph->notifier(UEdge()));
  2166       }
  2167             
  2168       void detach() {
  2169 	node_observer_proxy.detach();
  2170 	edge_observer_proxy.detach();
  2171       }
  2172 
  2173       bool attached() const {
  2174         return node_observer_proxy.attached();
  2175       }
  2176 
  2177       void clear() {
  2178         added_nodes.clear();
  2179         added_edges.clear();        
  2180       }
  2181 
  2182     public:
  2183 
  2184       /// \brief Default constructor.
  2185       ///
  2186       /// Default constructor.
  2187       /// To actually make a snapshot you must call save().
  2188       Snapshot() 
  2189         : graph(0), node_observer_proxy(*this), 
  2190           edge_observer_proxy(*this) {}
  2191       
  2192       /// \brief Constructor that immediately makes a snapshot.
  2193       ///      
  2194       /// This constructor immediately makes a snapshot of the graph.
  2195       /// \param _graph The graph we make a snapshot of.
  2196       Snapshot(ListBpUGraph &_graph) 
  2197         : node_observer_proxy(*this), 
  2198           edge_observer_proxy(*this) {
  2199 	attach(_graph);
  2200       }
  2201       
  2202       /// \brief Make a snapshot.
  2203       ///
  2204       /// Make a snapshot of the graph.
  2205       ///
  2206       /// This function can be called more than once. In case of a repeated
  2207       /// call, the previous snapshot gets lost.
  2208       /// \param _graph The graph we make the snapshot of.
  2209       void save(ListBpUGraph &_graph) {
  2210         if (attached()) {
  2211           detach();
  2212           clear();
  2213         }
  2214         attach(_graph);
  2215       }
  2216       
  2217       /// \brief Undo the changes until the last snapshot.
  2218       // 
  2219       /// Undo the changes until the last snapshot created by save().
  2220       void restore() {
  2221 	detach();
  2222 	for(std::list<UEdge>::iterator it = added_edges.begin(); 
  2223             it != added_edges.end(); ++it) {
  2224 	  graph->erase(*it);
  2225 	}
  2226 	for(std::list<Node>::iterator it = added_nodes.begin(); 
  2227             it != added_nodes.end(); ++it) {
  2228 	  graph->erase(*it);
  2229 	}
  2230         clear();
  2231       }
  2232 
  2233       /// \brief Gives back true when the snapshot is valid.
  2234       ///
  2235       /// Gives back true when the snapshot is valid.
  2236       bool valid() const {
  2237         return attached();
  2238       }
  2239     };
  2240   };
  2241 
  2242   
  2243   /// @}  
  2244 } //namespace lemon
  2245   
  2246 
  2247 #endif