Changeset 2539:c25f62a6452d in lemon-0.x

Timestamp:

12/11/07 18:37:08 (16 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

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

Message:

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

Files:

• benchmark/edge_lookup.cc (modified) (2 diffs)
• lemon/graph_utils.h (modified) (9 diffs)

benchmark/edge_lookup.cc

@@ -413 +413 @@
   
 };
+
+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 +531 @@
   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

lemon/graph_utils.h

@@ -383 +383 @@
   ///\sa EdgeLookUp
   ///\sa AllEdgeLookUp
+  ///\sa DynEdgeLookUp
   ///\sa ConEdgeIt
   template <typename Graph>
@@ -405 +406 @@
   ///\sa EdgeLookUp
   ///\sa AllEdgeLookUp
+  ///\sa DynEdgeLookUp
   ///
   /// \author Balazs Dezso 
@@ -2297 +2299 @@
         }
       }
+
+      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 +2420 @@
         }
       }
+      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 +2490 @@
 
 
+  ///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 +2952 @@
   ///\param G The type of the underlying graph.
   ///
+  ///\sa DynEdgeLookUp
   ///\sa AllEdgeLookUp  
   template<class G>
@@ -2523 +2988 @@
     
   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 +3009 @@
       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 +3065 @@
   ///\param G The type of the underlying graph.
   ///
+  ///\sa DynEdgeLookUp
   ///\sa EdgeLookUp  
   template<class G>