# HG changeset patch
# User alpar
# Date 1162221815 0
# Node ID a2ab634541525337adddb0ad296f9b7c39b1c445
# Parent  ac729a29120e34f2607f042a7695f05a438151c0
repository cleanup

diff -r ac729a29120e -r a2ab63454152 benchmark/edge_lookup.cc
--- a/benchmark/edge_lookup.cc	Mon Oct 30 12:25:43 2006 +0000
+++ b/benchmark/edge_lookup.cc	Mon Oct 30 15:23:35 2006 +0000
@@ -1,11 +1,364 @@
-#include"edge_lookup_test.h"
 #include<lemon/smart_graph.h>
 #include<vector>
 #include<lemon/time_measure.h>
 #include<lemon/random.h>
+#include<lemon/graph_utils.h>
+#include<algorithm>
 
 using 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) 
+	{
+// #ifdef X86
+ 	  Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc);
+// #elif X86_64
+// 	  Edge *m=(Edge*)(((unsigned long)a+(undigned long)b)/2 & 0xfffffffc);
+// #else
+//  	  Edge *m=a+((b-a)/2);
+// #endif
+	  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 EdgeLookUp5
+  {
+  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
+    EdgeLookUp5(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) 
+	{
+// #ifdef X86
+ 	  Edge *m=(Edge*)((((unsigned int)a>>1)+((unsigned int)b)>>1)
+			  & 0xfffffffc);
+// #elif X86_64
+// 	  Edge *m=(Edge*)(((unsigned long)a>>1+(undigned long)b)>>1)&0xfffffffc);
+// #else
+//  	  Edge *m=a+((b-a)/2);
+// #endif
+	  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;
+    }
+      
+  };
+
 GRAPH_TYPEDEFS(SmartGraph)
 typedef SmartGraph Graph;
 
@@ -92,6 +445,23 @@
   
 };
 
+class EL5
+{
+public:
+  Graph &_g;
+  EdgeLookUp5<Graph> _el;
+  EL5(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, char**argv)
 {
   int N=atoi(argv[1]);
@@ -126,13 +496,15 @@
   TimeStamp t2 = runningTimeTest(EL(g),1);
   TimeStamp t3 = runningTimeTest(EL2(g),1);
   TimeStamp t4 = runningTimeTest(EL3(g),1);
-//   TimeStamp t5 = runningTimeTest(EL4(g),1);
+  TimeStamp t5 = runningTimeTest(EL4(g),1);
+  TimeStamp t6 = runningTimeTest(EL5(g),1);
 
   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 ac729a29120e -r a2ab63454152 benchmark/edge_lookup_test.h
--- a/benchmark/edge_lookup_test.h	Mon Oct 30 12:25:43 2006 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,287 +0,0 @@
-/* -*- 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) 
-	{
-#ifdef X86
- 	  Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc);
-#elif X86_64
-	  Edge *m=(Edge*)(((unsigned long)a+(undigned long)b)/2 & 0xfffffffc);
-#else
- 	  Edge *m=a+((b-a)/2);
-#endif
-	  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