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