Changeset 2235:48801095a410 in lemon-0.x for lemon

Timestamp:

10/12/06 12:53:25 (18 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2978

Message:

EdgeLookUp? and AllEdgeLookUp? added.

File:

• lemon/graph_utils.h (modified) (4 diffs)

lemon/graph_utils.h

@@ -24 +24 @@
 #include <map>
 #include <cmath>
+#include <algorithm>
 
 #include <lemon/bits/invalid.h>
@@ -375 +376 @@
   ///\endcode
   ///
+  ///\sa EdgeLookUp
+  ///\se AllEdgeLookup
   ///\sa ConEdgeIt
   template <typename Graph>
@@ -396 +399 @@
   /// 
   ///\sa findEdge()
+  ///\sa EdgeLookUp
+  ///\se AllEdgeLookup
   ///
   /// \author Balazs Dezso 
@@ -1839 +1844 @@
 
 
+  ///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
+      
+  };
+
   /// @}