# HG changeset patch
# User alpar
# Date 1160650405 0
# Node ID 48801095a41023087389e2fe1411efb3606f3b4c
# Parent  7a1b33d7dc32a996ce707fd78e90ec055793b80d
EdgeLookUp and AllEdgeLookUp added.

diff -r 7a1b33d7dc32 -r 48801095a410 benchmark/Makefile.am
--- a/benchmark/Makefile.am	Thu Oct 12 10:51:51 2006 +0000
+++ b/benchmark/Makefile.am	Thu Oct 12 10:53:25 2006 +0000
@@ -1,5 +1,6 @@
 EXTRA_DIST += \
 	benchmark/Makefile
+	benchmark/edge_lookup_test
 
 noinst_HEADERS += benchmark/bench_tools.h
 
@@ -11,7 +12,8 @@
 	benchmark/swap_bipartite_bench \
 	benchmark/bfs-bench \
 	benchmark/radix_sort-bench \
-	benchmark/swap_bipartite_bench
+	benchmark/swap_bipartite_bench \
+	benchmark/edge_lookup
 
 endif WANT_BENCHMARK
 
@@ -24,3 +26,5 @@
 benchmark_radix_sort_bench_SOURCES = benchmark/radix_sort-bench.cc
 
 benchmark_swap_bipartite_bench_SOURCES = benchmark/swap_bipartite_bench.cc
+
+benchmark_edge_lookup_SOURCES = benchmark/edge_lookup.cc
diff -r 7a1b33d7dc32 -r 48801095a410 benchmark/edge_lookup.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/benchmark/edge_lookup.cc	Thu Oct 12 10:53:25 2006 +0000
@@ -0,0 +1,137 @@
+// #include<lemon/edge_lookup.h>
+#include<lemon/edge_lookup_test.h>
+#include<lemon/smart_graph.h>
+#include<vector>
+#include<lemon/time_measure.h>
+
+using namespace lemon;
+
+GRAPH_TYPEDEFS(SmartGraph)
+typedef SmartGraph Graph;
+
+class FE 
+{
+public:
+  Graph &_g;
+  FE(Graph &g) :_g(g) {}
+  void operator()() 
+  {
+    Edge e;
+    
+    for(NodeIt v(_g);v!=INVALID;++v)
+      for(NodeIt u(_g);u!=INVALID;++u)
+	e=findEdge(_g,u,v);
+  }
+  
+};
+
+class EL 
+{
+public:
+  Graph &_g;
+  EdgeLookUp<Graph> _el;
+  EL(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:
+  Graph &_g;
+  EdgeLookUp2<Graph> _el;
+  EL2(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 EL3
+{
+public:
+  Graph &_g;
+  EdgeLookUp3<Graph> _el;
+  EL3(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 EL4
+{
+public:
+  Graph &_g;
+  EdgeLookUp4<Graph> _el;
+  EL4(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);
+  }
+  
+};
+
+int main(int argc, char**argv)
+{
+  int N=atoi(argv[1]);
+  int M=int(N*atof(argv[2]));
+  
+  Graph g;
+  
+  std::vector<Node> v;
+  for(int i=0;i<N;i++) v.push_back(g.addNode());
+  for(int i=0;i<M;i++) g.addEdge(v[int(drand48()*N)],v[int(drand48()*N)]);
+
+//   {
+//     Edge e;
+    
+//     TimeReport t("findEdge: ");
+//     for(NodeIt u(g);u!=INVALID;++u)
+//       for(NodeIt v(g);v!=INVALID;++v)
+// 	e=findEdge(g,u,v);
+//   }
+//   {
+//     Edge e;
+//     EdgeLookUp<Graph> el(g);
+    
+//     TimeReport t("EdgeLookUp: ");
+//     for(NodeIt u(g);u!=INVALID;++u)
+//       for(NodeIt v(g);v!=INVALID;++v)
+// 	e=el(u,v);
+//   }
+
+
+  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 t5 = runningTimeTest(EL4(g),1);
+
+  std::cout << t1.userTime()/N/N << ' ' 
+	    << t2.userTime()/N/N << ' '
+	    << t3.userTime()/N/N << ' '
+	    << t4.userTime()/N/N << ' '
+	    << t5.userTime()/N/N << std::endl;
+}
+
diff -r 7a1b33d7dc32 -r 48801095a410 benchmark/edge_lookup_test
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/benchmark/edge_lookup_test	Thu Oct 12 10:53:25 2006 +0000
@@ -0,0 +1,7 @@
+#!/bin/bash
+
+for((i=1;i<50;i++))
+do
+    echo -n $i ''
+    edge_lookup 100 $i
+done
diff -r 7a1b33d7dc32 -r 48801095a410 benchmark/edge_lookup_test.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/benchmark/edge_lookup_test.h	Thu Oct 12 10:53:25 2006 +0000
@@ -0,0 +1,281 @@
+/* -*- C++ -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2003-2006
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#ifndef LEMON_EDGE_LOOKUP_H
+#define LEMON_EDGE_LOOKUP_H
+
+#include<lemon/graph_utils.h>
+#include<algorithm>
+#include<vector>
+
+namespace lemon {
+  template<class G>
+  class EdgeLookUp2
+  {
+  public:
+    GRAPH_TYPEDEFS(typename G)
+    typedef G Graph;
+
+  private:
+    const Graph &_g;
+    typename Graph::template NodeMap<int> _start;
+    typename Graph::template NodeMap<int> _end;
+    std::vector<Edge> _edges;
+    
+    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
+    EdgeLookUp2(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
+    
+  public:
+    ///Refresh the data structure at a node.
+    void refresh(Node n) 
+    {
+      const int bi = _start[n] = _edges.size();
+      for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
+      const typename std::vector<Edge>::iterator ei=_edges.end();
+      _end[n]=_edges.size();
+      std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
+    }
+    ///Refresh the full data structure.
+    void refresh() 
+    {
+      _edges.clear();
+      for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
+    }
+    
+    ///Find an edge between two nodes.
+    
+    ///Find an edge between two nodes.
+    ///\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) 
+    {
+      int a=_start[s];
+      int b=_end[s];
+      while(a<b) 
+	{
+	  int n=(a+b)/2;
+	  Node tt = _g.target(_edges[n]);
+	  if(tt==t) return _edges[n];
+	  else if(tt<t) a=n+1;
+	  else b=n;
+	}
+      return INVALID;
+    }
+
+    ///Find the next edge
+      
+      ///\warning This function is unimplemented.
+    Edge operator()(Node s, Node t, Edge prev) 
+    {
+      return prev==INVALID?(*this)(s,t):INVALID;
+    }
+      
+  };
+
+  template<class G>
+  class EdgeLookUp3
+  {
+  public:
+    GRAPH_TYPEDEFS(typename G)
+    typedef G Graph;
+
+  private:
+    const Graph &_g;
+    typename Graph::template NodeMap<Edge*> _start;
+    typename Graph::template NodeMap<Edge*> _end;
+    std::vector<Edge> _edges;
+    
+    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
+    EdgeLookUp3(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
+    
+  public:
+    ///Refresh the data structure at a node.
+    void refresh(Node n) 
+    {
+      const int bi = _start[n] = _edges.size();
+      for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
+      const typename std::vector<Edge>::iterator ei=_edges.end();
+      _end[n]=_edges.size();
+      std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
+    }
+    ///Refresh the full data structure.
+    void refresh() 
+    {
+      _edges.resize(countEdges(_g));
+      int l=0;
+      for(NodeIt n(_g);n!=INVALID;++n)
+	{
+	  int ls = l;
+	  _start[n]=&(_edges[l]);	
+	  for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;
+	  _end[n]=&(_edges[l]);
+	  std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));
+	}
+      
+    }
+    
+    ///Find an edge between two nodes.
+    
+    ///Find an edge between two nodes.
+    ///\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) 
+    {
+      Edge *a=_start[s];
+      Edge *b=_end[s];
+      while(a!=b) 
+	{
+ 	  Edge *m=a+((b-a)/2);
+	  Node tt = _g.target(*m);
+	  if(tt==t) return *m;
+	  else if(tt<t) a=m+1;
+	  else b=m;
+	}
+      return INVALID;
+    }
+
+    ///Find the next edge
+      
+      ///\warning This function is unimplemented.
+    Edge operator()(Node s, Node t, Edge prev) 
+    {
+      return prev==INVALID?(*this)(s,t):INVALID;
+    }
+      
+  };
+
+  template<class G>
+  class EdgeLookUp4
+  {
+  public:
+    GRAPH_TYPEDEFS(typename G)
+    typedef G Graph;
+
+  private:
+    const Graph &_g;
+    typename Graph::template NodeMap<Edge*> _start;
+    typename Graph::template NodeMap<Edge*> _end;
+    std::vector<Edge> _edges;
+    
+    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
+    EdgeLookUp4(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
+    
+  public:
+    ///Refresh the data structure at a node.
+    void refresh(Node n) 
+    {
+      const int bi = _start[n] = _edges.size();
+      for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
+      const typename std::vector<Edge>::iterator ei=_edges.end();
+      _end[n]=_edges.size();
+      std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
+    }
+    ///Refresh the full data structure.
+    void refresh() 
+    {
+      _edges.resize(countEdges(_g));
+      int l=0;
+      for(NodeIt n(_g);n!=INVALID;++n)
+	{
+	  int ls = l;
+	  _start[n]=&(_edges[l]);	
+	  for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;
+	  _end[n]=&(_edges[l]);
+	  std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));
+	}
+      
+    }
+    
+    ///Find an edge between two nodes.
+    
+    ///Find an edge between two nodes.
+    ///\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) 
+    {
+      Edge *a=_start[s];
+      Edge *b=_end[s];
+      while(a!=b) 
+	{
+	  Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc);
+	  Node tt = _g.target(*m);
+	  if(tt==t) return *m;
+	  else if(tt<t) a=m+1;
+	  else b=m;
+	}
+      return INVALID;
+    }
+
+    ///Find the next edge
+      
+      ///\warning This function is unimplemented.
+    Edge operator()(Node s, Node t, Edge prev) 
+    {
+      return prev==INVALID?(*this)(s,t):INVALID;
+    }
+      
+  };
+
+}
+
+#endif
diff -r 7a1b33d7dc32 -r 48801095a410 lemon/graph_utils.h
--- a/lemon/graph_utils.h	Thu Oct 12 10:51:51 2006 +0000
+++ b/lemon/graph_utils.h	Thu Oct 12 10:53:25 2006 +0000
@@ -23,6 +23,7 @@
 #include <vector>
 #include <map>
 #include <cmath>
+#include <algorithm>
 
 #include <lemon/bits/invalid.h>
 #include <lemon/bits/utility.h>
@@ -374,6 +375,8 @@
   /// }
   ///\endcode
   ///
+  ///\sa EdgeLookUp
+  ///\se AllEdgeLookup
   ///\sa ConEdgeIt
   template <typename Graph>
   inline typename Graph::Edge findEdge(const Graph &g,
@@ -395,6 +398,8 @@
   ///\endcode
   /// 
   ///\sa findEdge()
+  ///\sa EdgeLookUp
+  ///\se AllEdgeLookup
   ///
   /// \author Balazs Dezso 
   template <typename _Graph>
@@ -1838,6 +1843,242 @@
   };
 
 
+  ///Fast 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 time <em>O(log d)</em>,
+  ///where <em>d</em> is the out-degree of the source node.
+  ///
+  ///It is not possible to find \e all parallel edges between two nodes.
+  ///Use \ref AllEdgeLookUp for this purpose.
+  ///
+  ///\warning This class is static, so you should refresh() (or at least
+  ///refresh(Node)) this data structure
+  ///whenever the graph changes. This is a time consuming (superlinearly
+  ///proportional (<em>O(m</em>log<em>m)</em>) to the number of edges).
+  ///
+  ///\param G The type of the underlying graph.
+  ///
+  ///\sa AllEdgeLookUp  
+  template<class G>
+  class EdgeLookUp 
+  {
+  public:
+    GRAPH_TYPEDEFS(typename G)
+    typedef G Graph;
+
+  protected:
+    const Graph &_g;
+    typename Graph::template NodeMap<Edge> _head;
+    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, which remains valid until the graph
+    ///changes.
+    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) 
+    {
+      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;
+      return me;
+    }
+  public:
+    ///Refresh the data structure at a node.
+
+    ///Build up the search database of node \c n.
+    ///
+    ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
+    ///the number of the outgoing edges of \c n.
+    void refresh(Node 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));
+	_head[n]=refresh_rec(v,0,v.size()-1);
+      }
+      else _head[n]=INVALID;
+    }
+    ///Refresh the full data structure.
+
+    ///Build up the full search database. In fact, it simply calls
+    ///\ref refresh(Node) "refresh(n)" for each node \c n.
+    ///
+    ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
+    ///the number of the edges of \c n and <em>D</em> is the maximum
+    ///out-degree of the graph.
+
+    void refresh() 
+    {
+      for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
+    }
+    
+    ///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.
+    ///
+    ///\warning If you change the graph, refresh() must be called before using
+    ///this operator. If you change the outgoing edges of
+    ///a single node \c n, then
+    ///\ref refresh(Node) "refresh(n)" is enough.
+    ///
+    Edge operator()(Node s, Node t) const
+    {
+      Edge e;
+      for(e=_head[s];
+	  e!=INVALID&&_g.target(e)!=t;
+	  e = t < _g.target(e)?_left[e]:_right[e]) ;
+      return e;
+    }
+
+  };
+
+  ///Fast look up of all edges between given endpoints.
+  
+  ///\ingroup gutils
+  ///This class is the same as \ref EdgeLookUp, with the addition
+  ///that it makes it possible to find all edges between given endpoints.
+  ///
+  ///\warning This class is static, so you should refresh() (or at least
+  ///refresh(Node)) this data structure
+  ///whenever the graph changes. This is a time consuming (superlinearly
+  ///proportional (<em>O(m</em>log<em>m)</em>) to the number of edges).
+  ///
+  ///\param G The type of the underlying graph.
+  ///
+  ///\sa EdgeLookUp  
+  template<class G>
+  class AllEdgeLookUp : public EdgeLookUp<G>
+  {
+    using EdgeLookUp<G>::_g;
+    using EdgeLookUp<G>::_right;
+    using EdgeLookUp<G>::_left;
+    using EdgeLookUp<G>::_head;
+
+    GRAPH_TYPEDEFS(typename G)
+    typedef G Graph;
+    
+    typename Graph::template EdgeMap<Edge> _next;
+    
+    Edge refreshNext(Edge head,Edge next=INVALID)
+    {
+      if(head==INVALID) return next;
+      else {
+	next=refreshNext(_right[head],next);
+// 	_next[head]=next;
+	_next[head]=( next!=INVALID && _g.target(next)==_g.target(head))
+	  ? next : INVALID;
+	return refreshNext(_left[head],head);
+      }
+    }
+    
+    void refreshNext()
+    {
+      for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]);
+    }
+    
+  public:
+    ///Constructor
+
+    ///Constructor.
+    ///
+    ///It builds up the search database, which remains valid until the graph
+    ///changes.
+    AllEdgeLookUp(const Graph &g) : EdgeLookUp<G>(g), _next(g) {refreshNext();}
+
+    ///Refresh the data structure at a node.
+
+    ///Build up the search database of node \c n.
+    ///
+    ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
+    ///the number of the outgoing edges of \c n.
+    
+    void refresh(Node n) 
+    {
+      EdgeLookUp<G>::refresh(n);
+      refreshNext(_head[n]);
+    }
+    
+    ///Refresh the full data structure.
+
+    ///Build up the full search database. In fact, it simply calls
+    ///\ref refresh(Node) "refresh(n)" for each node \c n.
+    ///
+    ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
+    ///the number of the edges of \c n and <em>D</em> is the maximum
+    ///out-degree of the graph.
+
+    void refresh() 
+    {
+      for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]);
+    }
+    
+    ///Find an edge between two nodes.
+    
+    ///Find an edge between two nodes.
+    ///\param s The source node
+    ///\param t The target node
+    ///\param prev The previous edge between \c s and \c t. It it is INVALID or
+    ///not given, the operator finds the first appropriate edge.
+    ///\return An edge from \c s to \c t after \prev or
+    ///\ref INVALID if there is no more.
+    ///
+    ///For example, you can count the number of edges from \c u to \c v in the
+    ///following way.
+    ///\code
+    ///AllEdgeLookUp<ListGraph> ae(g);
+    ///...
+    ///int n=0;
+    ///for(Edge e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++;
+    ///\endcode
+    ///
+    ///Finding the first edge take <em>O(</em>log<em>d)</em> time, where
+    /// <em>d</em> is the number of outgoing edges of \c s. Then, the
+    ///consecutive edges are found in constant time.
+    ///
+    ///\warning If you change the graph, refresh() must be called before using
+    ///this operator. If you change the outgoing edges of
+    ///a single node \c n, then
+    ///\ref refresh(Node) "refresh(n)" is enough.
+    ///
+#ifdef DOXYGEN
+    Edge operator()(Node s, Node t, Edge prev=INVALID) const {}
+#else
+    using EdgeLookUp<G>::operator() ;
+    Edge operator()(Node s, Node t, Edge prev) const
+    {
+      return prev==INVALID?(*this)(s,t):_next[prev];
+    }
+#endif
+      
+  };
+
   /// @}
 
 } //END OF NAMESPACE LEMON