Index: benchmark/edge_lookup.cc
===================================================================
--- benchmark/edge_lookup.cc	(revision 2510)
+++ benchmark/edge_lookup.cc	(revision 2539)
@@ -413,4 +413,22 @@
   
 };
+
+class DEL 
+{
+public:
+  Graph &_g;
+  DynEdgeLookUp<Graph> _el;
+  DEL(Graph &g) :_g(g), _el(g) {}
+  void operator()() 
+  {
+    Edge e;
+    
+    for(NodeIt v(_g);v!=INVALID;++v)
+      for(NodeIt u(_g);u!=INVALID;++u)
+	e=_el(u,v);
+  }
+  
+};
+
 class EL2
 {
@@ -513,13 +531,23 @@
   TimeStamp t1 = runningTimeTest(FE(g),1);
   TimeStamp t2 = runningTimeTest(EL(g),1);
-  TimeStamp t3 = runningTimeTest(EL2(g),1);
-  TimeStamp t4 = runningTimeTest(EL3(g),1);
+  TimeStamp t3 = runningTimeTest(DEL(g),1);
+  TimeStamp t4 = runningTimeTest(EL2(g),1);
+  TimeStamp t5 = runningTimeTest(EL3(g),1);
 //   TimeStamp t5 = runningTimeTest(EL4(g),1);
 //   TimeStamp t6 = runningTimeTest(EL5(g),1);
 
+  std::cout << t1.userTime() << ' ' 
+	    << t2.userTime() << ' '
+	    << t3.userTime() << ' '
+	    << t4.userTime() << ' '
+	    << t5.userTime() << ' '
+// 	    << t5.userTime() << ' '
+//  	    << t6.userTime()
+	    << std::endl;
   std::cout << t1.userTime()/N/N << ' ' 
 	    << t2.userTime()/N/N << ' '
 	    << t3.userTime()/N/N << ' '
 	    << t4.userTime()/N/N << ' '
+	    << t5.userTime()/N/N << ' '
 // 	    << t5.userTime()/N/N << ' '
 //  	    << t6.userTime()/N/N
Index: lemon/graph_utils.h
===================================================================
--- lemon/graph_utils.h	(revision 2534)
+++ lemon/graph_utils.h	(revision 2539)
@@ -383,4 +383,5 @@
   ///\sa EdgeLookUp
   ///\sa AllEdgeLookUp
+  ///\sa DynEdgeLookUp
   ///\sa ConEdgeIt
   template <typename Graph>
@@ -405,4 +406,5 @@
   ///\sa EdgeLookUp
   ///\sa AllEdgeLookUp
+  ///\sa DynEdgeLookUp
   ///
   /// \author Balazs Dezso 
@@ -2297,4 +2299,13 @@
 	}
       }
+
+      virtual void build() {
+	Parent::build();
+	Key it;
+	typename Parent::Notifier* nf = Parent::notifier();
+	for (nf->first(it); it != INVALID; nf->next(it)) {
+	  Parent::set(it, 0);
+	}
+      }
     };
 
@@ -2409,4 +2420,12 @@
 	}
       }
+      virtual void build() {
+	Parent::build();
+	Key it;
+	typename Parent::Notifier* nf = Parent::notifier();
+	for (nf->first(it); it != INVALID; nf->next(it)) {
+	  Parent::set(it, 0);
+	}
+      }
     };
 
@@ -2471,4 +2490,449 @@
 
 
+  ///Dynamic edge look up between given endpoints.
+  
+  ///\ingroup gutils
+  ///Using this class, you can find an edge in a graph from a given
+  ///source to a given target in amortized time <em>O(log d)</em>,
+  ///where <em>d</em> is the out-degree of the source node.
+  ///
+  ///It is possible to find \e all parallel edges between two nodes with
+  ///the \c findFirst() and \c findNext() members.
+  ///
+  ///See the \ref EdgeLookUp and \ref AllEdgeLookUp classes if your
+  ///graph do not changed so frequently.
+  ///
+  ///This class uses a self-adjusting binary search tree, Sleator's
+  ///and Tarjan's Splay tree for guarantee the logarithmic amortized
+  ///time bound for edge lookups. This class also guarantees the
+  ///optimal time bound in a constant factor for any distribution of
+  ///queries.
+  ///
+  ///\param G The type of the underlying graph.  
+  ///
+  ///\sa EdgeLookUp  
+  ///\sa AllEdgeLookUp  
+  template<class G>
+  class DynEdgeLookUp 
+    : protected ItemSetTraits<G, typename G::Edge>::ItemNotifier::ObserverBase
+  {
+  public:
+    typedef typename ItemSetTraits<G, typename G::Edge>
+    ::ItemNotifier::ObserverBase Parent;
+
+    GRAPH_TYPEDEFS(typename G);
+    typedef G Graph;
+
+  protected:
+
+    class AutoNodeMap : public DefaultMap<Graph, Node, Edge> {
+    public:
+
+      typedef DefaultMap<Graph, Node, Edge> Parent;
+
+      AutoNodeMap(const Graph& graph) : Parent(graph, INVALID) {}
+      
+      virtual void add(const Node& node) {
+	Parent::add(node);
+	Parent::set(node, INVALID);
+      }
+
+      virtual void add(const std::vector<Node>& nodes) {
+	Parent::add(nodes);
+	for (int i = 0; i < int(nodes.size()); ++i) {
+	  Parent::set(nodes[i], INVALID);
+	}
+      }
+
+      virtual void build() {
+	Parent::build();
+	Node it;
+	typename Parent::Notifier* nf = Parent::notifier();
+	for (nf->first(it); it != INVALID; nf->next(it)) {
+	  Parent::set(it, INVALID);
+	}
+      }
+    };
+
+    const Graph &_g;
+    AutoNodeMap _head;
+    typename Graph::template EdgeMap<Edge> _parent;
+    typename Graph::template EdgeMap<Edge> _left;
+    typename Graph::template EdgeMap<Edge> _right;
+    
+    class EdgeLess {
+      const Graph &g;
+    public:
+      EdgeLess(const Graph &_g) : g(_g) {}
+      bool operator()(Edge a,Edge b) const 
+      {
+	return g.target(a)<g.target(b);
+      }
+    };
+    
+  public:
+    
+    ///Constructor
+
+    ///Constructor.
+    ///
+    ///It builds up the search database.
+    DynEdgeLookUp(const Graph &g) 
+      : _g(g),_head(g),_parent(g),_left(g),_right(g) 
+    { 
+      Parent::attach(_g.notifier(typename Graph::Edge()));
+      refresh(); 
+    }
+    
+  protected:
+
+    virtual void add(const Edge& edge) {
+      insert(edge);
+    }
+
+    virtual void add(const std::vector<Edge>& edges) {
+      for (int i = 0; i < int(edges.size()); ++i) {
+	insert(edges[i]);
+      }
+    }
+
+    virtual void erase(const Edge& edge) {
+      remove(edge);
+    }
+
+    virtual void erase(const std::vector<Edge>& edges) {
+      for (int i = 0; i < int(edges.size()); ++i) {
+	remove(edges[i]);
+      }     
+    }
+
+    virtual void build() {
+      refresh();
+    }
+
+    virtual void clear() {
+      for(NodeIt n(_g);n!=INVALID;++n) {
+	_head.set(n, INVALID);
+      }
+    }
+
+    void insert(Edge edge) {
+      Node s = _g.source(edge);
+      Node t = _g.target(edge);
+      _left.set(edge, INVALID);
+      _right.set(edge, INVALID);
+      
+      Edge e = _head[s];
+      if (e == INVALID) {
+	_head.set(s, edge);
+	_parent.set(edge, INVALID);
+	return;
+      }
+      while (true) {
+	if (t < _g.target(e)) {
+	  if (_left[e] == INVALID) {
+	    _left.set(e, edge);
+	    _parent.set(edge, e);
+	    splay(edge);
+	    return;
+	  } else {
+	    e = _left[e];
+	  }
+	} else {
+	  if (_right[e] == INVALID) {
+	    _right.set(e, edge);
+	    _parent.set(edge, e);
+	    splay(edge);
+	    return;
+	  } else {
+	    e = _right[e];
+	  }
+	}
+      }
+    }
+
+    void remove(Edge edge) {
+      if (_left[edge] == INVALID) {
+	if (_right[edge] != INVALID) {
+	  _parent.set(_right[edge], _parent[edge]);
+	}
+	if (_parent[edge] != INVALID) {
+	  if (_left[_parent[edge]] == edge) {
+	    _left.set(_parent[edge], _right[edge]);
+	  } else {
+	    _right.set(_parent[edge], _right[edge]);
+	  }
+	} else {
+	  _head.set(_g.source(edge), _right[edge]);
+	}
+      } else if (_right[edge] == INVALID) {
+	_parent.set(_left[edge], _parent[edge]);
+	if (_parent[edge] != INVALID) {
+	  if (_left[_parent[edge]] == edge) {
+	    _left.set(_parent[edge], _left[edge]);
+	  } else {
+	    _right.set(_parent[edge], _left[edge]);
+	  }
+	} else {
+	  _head.set(_g.source(edge), _left[edge]);
+	}
+      } else {
+	Edge e = _left[edge];
+	if (_right[e] != INVALID) {
+	  e = _right[e];	  
+	  while (_right[e] != INVALID) {
+	    e = _right[e];
+	  }
+	  Edge s = _parent[e];
+	  _right.set(_parent[e], _left[e]);
+	  if (_left[e] != INVALID) {
+	    _parent.set(_left[e], _parent[e]);
+	  }
+	  
+	  _left.set(e, _left[edge]);
+	  _parent.set(_left[edge], e);
+	  _right.set(e, _right[edge]);
+	  _parent.set(_right[edge], e);
+
+	  _parent.set(e, _parent[edge]);
+	  if (_parent[edge] != INVALID) {
+	    if (_left[_parent[edge]] == edge) {
+	      _left.set(_parent[edge], e);
+	    } else {
+	      _right.set(_parent[edge], e);
+	    }
+	  }
+	  splay(s);
+	} else {
+	  _right.set(e, _right[edge]);
+	  _parent.set(_right[edge], e);
+
+	  if (_parent[edge] != INVALID) {
+	    if (_left[_parent[edge]] == edge) {
+	      _left.set(_parent[edge], e);
+	    } else {
+	      _right.set(_parent[edge], e);
+	    }
+	  } else {
+	    _head.set(_g.source(edge), e);
+	  }
+	}
+      }
+    }
+
+    Edge refreshRec(std::vector<Edge> &v,int a,int b) 
+    {
+      int m=(a+b)/2;
+      Edge me=v[m];
+      if (a < m) {
+	Edge left = refreshRec(v,a,m-1);
+	_left.set(me, left);
+	_parent.set(left, me);
+      } else {
+	_left.set(me, INVALID);
+      }
+      if (m < b) {
+	Edge right = refreshRec(v,m+1,b);
+	_right.set(me, right);
+	_parent.set(right, me);
+      } else {
+	_right.set(me, INVALID);
+      }
+      return me;
+    }
+
+    void refresh() {
+      for(NodeIt n(_g);n!=INVALID;++n) {
+	std::vector<Edge> v;
+	for(OutEdgeIt e(_g,n);e!=INVALID;++e) v.push_back(e);
+	if(v.size()) {
+	  std::sort(v.begin(),v.end(),EdgeLess(_g));
+	  Edge head = refreshRec(v,0,v.size()-1);
+	  _head.set(n, head);
+	  _parent.set(head, INVALID);
+	}
+	else _head.set(n, INVALID);
+      }
+    }
+
+    void zig(Edge v) {        
+      Edge w = _parent[v];
+      _parent.set(v, _parent[w]);
+      _parent.set(w, v);
+      _left.set(w, _right[v]);
+      _right.set(v, w);
+      if (_parent[v] != INVALID) {
+	if (_right[_parent[v]] == w) {
+	  _right.set(_parent[v], v);
+	} else {
+	  _left.set(_parent[v], v);
+	}
+      }
+      if (_left[w] != INVALID){
+	_parent.set(_left[w], w);
+      }
+    }
+
+    void zag(Edge v) {        
+      Edge w = _parent[v];
+      _parent.set(v, _parent[w]);
+      _parent.set(w, v);
+      _right.set(w, _left[v]);
+      _left.set(v, w);
+      if (_parent[v] != INVALID){
+	if (_left[_parent[v]] == w) {
+	  _left.set(_parent[v], v);
+	} else {
+	  _right.set(_parent[v], v);
+	}
+      }
+      if (_right[w] != INVALID){
+	_parent.set(_right[w], w);
+      }
+    }
+
+    void splay(Edge v) {
+      while (_parent[v] != INVALID) {
+	if (v == _left[_parent[v]]) {
+	  if (_parent[_parent[v]] == INVALID) {
+	    zig(v);
+	  } else {
+	    if (_parent[v] == _left[_parent[_parent[v]]]) {
+	      zig(_parent[v]);
+	      zig(v);
+	    } else {
+	      zig(v);
+	      zag(v);
+	    }
+	  }
+	} else {
+	  if (_parent[_parent[v]] == INVALID) {
+	    zag(v);
+	  } else {
+	    if (_parent[v] == _left[_parent[_parent[v]]]) {
+	      zag(v);
+	      zig(v);
+	    } else {
+	      zag(_parent[v]);
+	      zag(v);
+	    }
+	  }
+	}
+      }
+      _head[_g.source(v)] = v;
+    }
+
+
+  public:
+    
+    ///Find an edge between two nodes.
+    
+    ///Find an edge between two nodes in time <em>O(</em>log<em>d)</em>, where
+    /// <em>d</em> is the number of outgoing edges of \c s.
+    ///\param s The source node
+    ///\param t The target node
+    ///\return An edge from \c s to \c t if there exists,
+    ///\ref INVALID otherwise.
+    Edge operator()(Node s, Node t) const
+    {
+      Edge e = _head[s];
+      while (true) {
+	if (_g.target(e) == t) {
+	  const_cast<DynEdgeLookUp&>(*this).splay(e);
+	  return e;
+	} else if (t < _g.target(e)) {
+	  if (_left[e] == INVALID) {
+	    const_cast<DynEdgeLookUp&>(*this).splay(e);
+	    return INVALID;
+	  } else {
+	    e = _left[e];
+	  }
+	} else  {
+	  if (_right[e] == INVALID) {
+	    const_cast<DynEdgeLookUp&>(*this).splay(e);
+	    return INVALID;
+	  } else {
+	    e = _right[e];
+	  }
+	}
+      }
+    }
+
+    ///Find the first edge between two nodes.
+    
+    ///Find the first edge between two nodes in time
+    /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
+    /// outgoing edges of \c s.  
+    ///\param s The source node 
+    ///\param t The target node
+    ///\return An edge from \c s to \c t if there exists, \ref INVALID
+    /// otherwise.
+    Edge findFirst(Node s, Node t) const
+    {
+      Edge e = _head[s];
+      Edge r = INVALID;
+      while (true) {
+	if (_g.target(e) < t) {
+	  if (_right[e] == INVALID) {
+	    const_cast<DynEdgeLookUp&>(*this).splay(e);
+	    return r;
+	  } else {
+	    e = _right[e];
+	  }
+	} else {
+	  if (_g.target(e) == t) {
+	    r = e;
+	  }
+	  if (_left[e] == INVALID) {
+	    const_cast<DynEdgeLookUp&>(*this).splay(e);
+	    return r;
+	  } else {
+	    e = _left[e];
+	  }
+	}
+      }
+    }
+
+    ///Find the next edge between two nodes.
+    
+    ///Find the next edge between two nodes in time
+    /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
+    /// outgoing edges of \c s.  
+    ///\param s The source node 
+    ///\param t The target node
+    ///\return An edge from \c s to \c t if there exists, \ref INVALID
+    /// otherwise.
+
+    ///\note If \c e is not the result of the previous \c findFirst()
+    ///operation then the amorized time bound can not be guaranteed.
+#ifdef DOXYGEN
+    Edge findNext(Node s, Node t, Edge e) const
+#else
+    Edge findNext(Node, Node t, Edge e) const
+#endif
+    {
+      if (_right[e] != INVALID) {
+	e = _right[e];
+	while (_left[e] != INVALID) {
+	  e = _left[e];
+	}
+	const_cast<DynEdgeLookUp&>(*this).splay(e);
+      } else {
+	while (_parent[e] != INVALID && _right[_parent[e]] ==  e) {
+	  e = _parent[e];
+	}
+	if (_parent[e] == INVALID) {
+	  return INVALID;
+	} else {
+	  e = _parent[e];
+	  const_cast<DynEdgeLookUp&>(*this).splay(e);
+	}
+      }
+      if (_g.target(e) == t) return e;
+      else return INVALID;    
+    }
+
+  };
+
   ///Fast edge look up between given endpoints.
   
@@ -2488,4 +2952,5 @@
   ///\param G The type of the underlying graph.
   ///
+  ///\sa DynEdgeLookUp
   ///\sa AllEdgeLookUp  
   template<class G>
@@ -2523,10 +2988,10 @@
     
   private:
-    Edge refresh_rec(std::vector<Edge> &v,int a,int b) 
+    Edge refreshRec(std::vector<Edge> &v,int a,int b) 
     {
       int m=(a+b)/2;
       Edge me=v[m];
-      _left[me] = a<m?refresh_rec(v,a,m-1):INVALID;
-      _right[me] = m<b?refresh_rec(v,m+1,b):INVALID;
+      _left[me] = a<m?refreshRec(v,a,m-1):INVALID;
+      _right[me] = m<b?refreshRec(v,m+1,b):INVALID;
       return me;
     }
@@ -2544,5 +3009,5 @@
       if(v.size()) {
 	std::sort(v.begin(),v.end(),EdgeLess(_g));
-	_head[n]=refresh_rec(v,0,v.size()-1);
+	_head[n]=refreshRec(v,0,v.size()-1);
       }
       else _head[n]=INVALID;
@@ -2600,4 +3065,5 @@
   ///\param G The type of the underlying graph.
   ///
+  ///\sa DynEdgeLookUp
   ///\sa EdgeLookUp  
   template<class G>
