# HG changeset patch
# User deba
# Date 1197394628 0
# Node ID c25f62a6452d522529362ab9405b2dc385813994
# Parent  7bdd328de87a7063c2d353a9cdd1573b2a8fac91
DynEdgeLookUp implementation based on splay trees
In general case it is slower than the static version, but it should not
refreshed on the change of the graph

diff -r 7bdd328de87a -r c25f62a6452d benchmark/edge_lookup.cc
--- a/benchmark/edge_lookup.cc	Mon Dec 10 16:34:31 2007 +0000
+++ b/benchmark/edge_lookup.cc	Tue Dec 11 17:37:08 2007 +0000
@@ -412,6 +412,24 @@
   }
   
 };
+
+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
 {
 public:
@@ -512,15 +530,25 @@
 
   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
 	    << std::endl;
diff -r 7bdd328de87a -r c25f62a6452d lemon/graph_utils.h
--- a/lemon/graph_utils.h	Mon Dec 10 16:34:31 2007 +0000
+++ b/lemon/graph_utils.h	Tue Dec 11 17:37:08 2007 +0000
@@ -382,6 +382,7 @@
   ///
   ///\sa EdgeLookUp
   ///\sa AllEdgeLookUp
+  ///\sa DynEdgeLookUp
   ///\sa ConEdgeIt
   template <typename Graph>
   inline typename Graph::Edge 
@@ -404,6 +405,7 @@
   ///\sa findEdge()
   ///\sa EdgeLookUp
   ///\sa AllEdgeLookUp
+  ///\sa DynEdgeLookUp
   ///
   /// \author Balazs Dezso 
   template <typename _Graph>
@@ -2296,6 +2298,15 @@
 	  Parent::set(keys[i], 0);
 	}
       }
+
+      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);
+	}
+      }
     };
 
   public:
@@ -2408,6 +2419,14 @@
 	  Parent::set(keys[i], 0);
 	}
       }
+      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);
+	}
+      }
     };
 
   public:
@@ -2470,6 +2489,451 @@
   };
 
 
+  ///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.
   
   ///\ingroup gutils
@@ -2487,6 +2951,7 @@
   ///
   ///\param G The type of the underlying graph.
   ///
+  ///\sa DynEdgeLookUp
   ///\sa AllEdgeLookUp  
   template<class G>
   class EdgeLookUp 
@@ -2522,12 +2987,12 @@
     EdgeLookUp(const Graph &g) :_g(g),_head(g),_left(g),_right(g) {refresh();}
     
   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;
     }
   public:
@@ -2543,7 +3008,7 @@
       for(OutEdgeIt e(_g,n);e!=INVALID;++e) v.push_back(e);
       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;
     }
@@ -2599,6 +3064,7 @@
   ///
   ///\param G The type of the underlying graph.
   ///
+  ///\sa DynEdgeLookUp
   ///\sa EdgeLookUp  
   template<class G>
   class AllEdgeLookUp : public EdgeLookUp<G>