alpar@2391: /* -*- C++ -*-
alpar@2391:  *
alpar@2391:  * This file is a part of LEMON, a generic C++ optimization library
alpar@2391:  *
alpar@2391:  * Copyright (C) 2003-2007
alpar@2391:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@2391:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@2391:  *
alpar@2391:  * Permission to use, modify and distribute this software is granted
alpar@2391:  * provided that this copyright notice appears in all copies. For
alpar@2391:  * precise terms see the accompanying LICENSE file.
alpar@2391:  *
alpar@2391:  * This software is provided "AS IS" with no warranty of any kind,
alpar@2391:  * express or implied, and with no claim as to its suitability for any
alpar@2391:  * purpose.
alpar@2391:  *
alpar@2391:  */
alpar@2391: 
alpar@2235: #include<lemon/smart_graph.h>
alpar@2235: #include<vector>
alpar@2235: #include<lemon/time_measure.h>
deba@2242: #include<lemon/random.h>
alpar@2271: #include<lemon/graph_utils.h>
alpar@2271: #include<algorithm>
alpar@2235: 
alpar@2235: using namespace lemon;
alpar@2235: 
alpar@2271:   template<class G>
alpar@2271:   class EdgeLookUp2
alpar@2271:   {
alpar@2271:   public:
alpar@2271:     GRAPH_TYPEDEFS(typename G)
alpar@2271:     typedef G Graph;
alpar@2271: 
alpar@2271:   private:
alpar@2271:     const Graph &_g;
alpar@2271:     typename Graph::template NodeMap<int> _start;
alpar@2271:     typename Graph::template NodeMap<int> _end;
alpar@2271:     std::vector<Edge> _edges;
alpar@2271:     
alpar@2271:     class EdgeLess {
alpar@2271:       const Graph &g;
alpar@2271:     public:
alpar@2271:       EdgeLess(const Graph &_g) : g(_g) {}
alpar@2271:       bool operator()(Edge a,Edge b) const 
alpar@2271:       {
alpar@2271: 	return g.target(a)<g.target(b);
alpar@2271:       }
alpar@2271:     };
alpar@2271:     
alpar@2271:   public:
alpar@2271:     
alpar@2271:     ///Constructor
alpar@2271:     EdgeLookUp2(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
alpar@2271:     
alpar@2271:   public:
alpar@2271:     ///Refresh the data structure at a node.
alpar@2271:     void refresh(Node n) 
alpar@2271:     {
alpar@2271:       const int bi = _start[n] = _edges.size();
alpar@2271:       for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
alpar@2271:       const typename std::vector<Edge>::iterator ei=_edges.end();
alpar@2271:       _end[n]=_edges.size();
alpar@2271:       std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
alpar@2271:     }
alpar@2271:     ///Refresh the full data structure.
alpar@2271:     void refresh() 
alpar@2271:     {
alpar@2271:       _edges.clear();
alpar@2271:       for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
alpar@2271:     }
alpar@2271:     
alpar@2271:     ///Find an edge between two nodes.
alpar@2271:     
alpar@2271:     ///Find an edge between two nodes.
alpar@2271:     ///\param s The source node
alpar@2271:     ///\param t The target node
alpar@2271:     ///\return An edge from \c s to \c t if there exists,
alpar@2271:     ///\ref INVALID otherwise.
alpar@2271: 
alpar@2271:     Edge operator()(Node s, Node t) 
alpar@2271:     {
alpar@2271:       int a=_start[s];
alpar@2271:       int b=_end[s];
alpar@2271:       while(a<b) 
alpar@2271: 	{
alpar@2271: 	  int n=(a+b)/2;
alpar@2271: 	  Node tt = _g.target(_edges[n]);
alpar@2271: 	  if(tt==t) return _edges[n];
alpar@2271: 	  else if(tt<t) a=n+1;
alpar@2271: 	  else b=n;
alpar@2271: 	}
alpar@2271:       return INVALID;
alpar@2271:     }
alpar@2271: 
alpar@2271:     ///Find the next edge
alpar@2271:       
alpar@2271:       ///\warning This function is unimplemented.
alpar@2271:     Edge operator()(Node s, Node t, Edge prev) 
alpar@2271:     {
alpar@2271:       return prev==INVALID?(*this)(s,t):INVALID;
alpar@2271:     }
alpar@2271:       
alpar@2271:   };
alpar@2271: 
alpar@2271:   template<class G>
alpar@2271:   class EdgeLookUp3
alpar@2271:   {
alpar@2271:   public:
alpar@2271:     GRAPH_TYPEDEFS(typename G)
alpar@2271:     typedef G Graph;
alpar@2271: 
alpar@2271:   private:
alpar@2271:     const Graph &_g;
alpar@2271:     typename Graph::template NodeMap<Edge*> _start;
alpar@2271:     typename Graph::template NodeMap<Edge*> _end;
alpar@2271:     std::vector<Edge> _edges;
alpar@2271:     
alpar@2271:     class EdgeLess {
alpar@2271:       const Graph &g;
alpar@2271:     public:
alpar@2271:       EdgeLess(const Graph &_g) : g(_g) {}
alpar@2271:       bool operator()(Edge a,Edge b) const 
alpar@2271:       {
alpar@2271: 	return g.target(a)<g.target(b);
alpar@2271:       }
alpar@2271:     };
alpar@2271:     
alpar@2271:   public:
alpar@2271:     
alpar@2271:     ///Constructor
alpar@2271:     EdgeLookUp3(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
alpar@2271:     
alpar@2271:   public:
alpar@2271:     ///Refresh the data structure at a node.
alpar@2271:     void refresh(Node n) 
alpar@2271:     {
alpar@2271:       const int bi = _start[n] = _edges.size();
alpar@2271:       for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
alpar@2271:       const typename std::vector<Edge>::iterator ei=_edges.end();
alpar@2271:       _end[n]=_edges.size();
alpar@2271:       std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
alpar@2271:     }
alpar@2271:     ///Refresh the full data structure.
alpar@2271:     void refresh() 
alpar@2271:     {
alpar@2271:       _edges.resize(countEdges(_g));
alpar@2271:       int l=0;
alpar@2271:       for(NodeIt n(_g);n!=INVALID;++n)
alpar@2271: 	{
alpar@2271: 	  int ls = l;
alpar@2271: 	  _start[n]=&(_edges[l]);	
alpar@2271: 	  for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;
alpar@2271: 	  _end[n]=&(_edges[l]);
alpar@2271: 	  std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));
alpar@2271: 	}
alpar@2271:       
alpar@2271:     }
alpar@2271:     
alpar@2271:     ///Find an edge between two nodes.
alpar@2271:     
alpar@2271:     ///Find an edge between two nodes.
alpar@2271:     ///\param s The source node
alpar@2271:     ///\param t The target node
alpar@2271:     ///\return An edge from \c s to \c t if there exists,
alpar@2271:     ///\ref INVALID otherwise.
alpar@2271: 
alpar@2271:     Edge operator()(Node s, Node t) 
alpar@2271:     {
alpar@2271:       Edge *a=_start[s];
alpar@2271:       Edge *b=_end[s];
alpar@2271:       while(a!=b) 
alpar@2271: 	{
alpar@2271:  	  Edge *m=a+((b-a)/2);
alpar@2271: 	  Node tt = _g.target(*m);
alpar@2271: 	  if(tt==t) return *m;
alpar@2271: 	  else if(tt<t) a=m+1;
alpar@2271: 	  else b=m;
alpar@2271: 	}
alpar@2271:       return INVALID;
alpar@2271:     }
alpar@2271: 
alpar@2271:     ///Find the next edge
alpar@2271:       
alpar@2271:       ///\warning This function is unimplemented.
alpar@2271:     Edge operator()(Node s, Node t, Edge prev) 
alpar@2271:     {
alpar@2271:       return prev==INVALID?(*this)(s,t):INVALID;
alpar@2271:     }
alpar@2271:       
alpar@2271:   };
alpar@2271: 
alpar@2272: //   template<class G>
alpar@2272: //   class EdgeLookUp4
alpar@2272: //   {
alpar@2272: //   public:
alpar@2272: //     GRAPH_TYPEDEFS(typename G)
alpar@2272: //     typedef G Graph;
alpar@2271:     
alpar@2272: //   private:
alpar@2272: //     const Graph &_g;
alpar@2272: //     typename Graph::template NodeMap<Edge*> _start;
alpar@2272: //     typename Graph::template NodeMap<Edge*> _end;
alpar@2272: //     std::vector<Edge> _edges;
alpar@2271:     
alpar@2272: //     class EdgeLess {
alpar@2272: //       const Graph &g;
alpar@2272: //     public:
alpar@2272: //       EdgeLess(const Graph &_g) : g(_g) {}
alpar@2272: //       bool operator()(Edge a,Edge b) const 
alpar@2272: //       {
alpar@2272: // 	return g.target(a)<g.target(b);
alpar@2272: //       }
alpar@2272: //     };
alpar@2271:     
alpar@2272: //   public:
alpar@2271:     
alpar@2272: //     ///Constructor
alpar@2272: //     EdgeLookUp4(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
alpar@2271:     
alpar@2272: //   public:
alpar@2272: //     ///Refresh the data structure at a node.
alpar@2272: //     void refresh(Node n) 
alpar@2272: //     {
alpar@2272: //       const int bi = _start[n] = _edges.size();
alpar@2272: //       for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
alpar@2272: //       const typename std::vector<Edge>::iterator ei=_edges.end();
alpar@2272: //       _end[n]=_edges.size();
alpar@2272: //       std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
alpar@2272: //     }
alpar@2272: //     ///Refresh the full data structure.
alpar@2272: //     void refresh() 
alpar@2272: //     {
alpar@2272: //       _edges.resize(countEdges(_g));
alpar@2272: //       int l=0;
alpar@2272: //       for(NodeIt n(_g);n!=INVALID;++n)
alpar@2272: // 	{
alpar@2272: // 	  int ls = l;
alpar@2272: // 	  _start[n]=&(_edges[l]);	
alpar@2272: // 	  for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;
alpar@2272: // 	  _end[n]=&(_edges[l]);
alpar@2272: // 	  std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));
alpar@2272: // 	}
alpar@2271:       
alpar@2272: //     }
alpar@2271:     
alpar@2272: //     ///Find an edge between two nodes.
alpar@2271:     
alpar@2272: //     ///Find an edge between two nodes.
alpar@2272: //     ///\param s The source node
alpar@2272: //     ///\param t The target node
alpar@2272: //     ///\return An edge from \c s to \c t if there exists,
alpar@2272: //     ///\ref INVALID otherwise.
alpar@2271: 
alpar@2272: //     Edge operator()(Node s, Node t) 
alpar@2272: //     {
alpar@2272: //       Edge *a=_start[s];
alpar@2272: //       Edge *b=_end[s];
alpar@2272: //       while(a!=b) 
alpar@2272: // 	{
alpar@2272: // // #ifdef X86
alpar@2272: //  	  Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc);
alpar@2272: // // #elif X86_64
alpar@2272: // // 	  Edge *m=(Edge*)(((unsigned long)a+(undigned long)b)/2 & 0xfffffffc);
alpar@2272: // // #else
alpar@2272: // //  	  Edge *m=a+((b-a)/2);
alpar@2272: // // #endif
alpar@2272: // 	  Node tt = _g.target(*m);
alpar@2272: // 	  if(tt==t) return *m;
alpar@2272: // 	  else if(tt<t) a=m+1;
alpar@2272: // 	  else b=m;
alpar@2272: // 	}
alpar@2272: //       return INVALID;
alpar@2272: //     }
alpar@2271: 
alpar@2272: //     ///Find the next edge
alpar@2271:       
alpar@2272: //       ///\warning This function is unimplemented.
alpar@2272: //     Edge operator()(Node s, Node t, Edge prev) 
alpar@2272: //     {
alpar@2272: //       return prev==INVALID?(*this)(s,t):INVALID;
alpar@2272: //     }
alpar@2271:       
alpar@2272: //   };
alpar@2271: 
alpar@2272: //   template<class G>
alpar@2272: //   class EdgeLookUp5
alpar@2272: //   {
alpar@2272: //   public:
alpar@2272: //     GRAPH_TYPEDEFS(typename G)
alpar@2272: //     typedef G Graph;
alpar@2271:     
alpar@2272: //   private:
alpar@2272: //     const Graph &_g;
alpar@2272: //     typename Graph::template NodeMap<Edge*> _start;
alpar@2272: //     typename Graph::template NodeMap<Edge*> _end;
alpar@2272: //     std::vector<Edge> _edges;
alpar@2271:     
alpar@2272: //     class EdgeLess {
alpar@2272: //       const Graph &g;
alpar@2272: //     public:
alpar@2272: //       EdgeLess(const Graph &_g) : g(_g) {}
alpar@2272: //       bool operator()(Edge a,Edge b) const 
alpar@2272: //       {
alpar@2272: // 	return g.target(a)<g.target(b);
alpar@2272: //       }
alpar@2272: //     };
alpar@2271:     
alpar@2272: //   public:
alpar@2271:     
alpar@2272: //     ///Constructor
alpar@2272: //     EdgeLookUp5(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
alpar@2271:     
alpar@2272: //   public:
alpar@2272: //     ///Refresh the data structure at a node.
alpar@2272: //     void refresh(Node n) 
alpar@2272: //     {
alpar@2272: //       const int bi = _start[n] = _edges.size();
alpar@2272: //       for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
alpar@2272: //       const typename std::vector<Edge>::iterator ei=_edges.end();
alpar@2272: //       _end[n]=_edges.size();
alpar@2272: //       std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
alpar@2272: //     }
alpar@2272: //     ///Refresh the full data structure.
alpar@2272: //     void refresh() 
alpar@2272: //     {
alpar@2272: //       _edges.resize(countEdges(_g));
alpar@2272: //       int l=0;
alpar@2272: //       for(NodeIt n(_g);n!=INVALID;++n)
alpar@2272: // 	{
alpar@2272: // 	  int ls = l;
alpar@2272: // 	  _start[n]=&(_edges[l]);	
alpar@2272: // 	  for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;
alpar@2272: // 	  _end[n]=&(_edges[l]);
alpar@2272: // 	  std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));
alpar@2272: // 	}
alpar@2271:       
alpar@2272: //     }
alpar@2271:     
alpar@2272: //     ///Find an edge between two nodes.
alpar@2271:     
alpar@2272: //     ///Find an edge between two nodes.
alpar@2272: //     ///\param s The source node
alpar@2272: //     ///\param t The target node
alpar@2272: //     ///\return An edge from \c s to \c t if there exists,
alpar@2272: //     ///\ref INVALID otherwise.
alpar@2271: 
alpar@2272: //     Edge operator()(Node s, Node t) 
alpar@2272: //     {
alpar@2272: //       Edge *a=_start[s];
alpar@2272: //       Edge *b=_end[s];
alpar@2272: //       while(a!=b) 
alpar@2272: // 	{
alpar@2272: // // #ifdef X86
alpar@2272: //  	  Edge *m=(Edge*)((((unsigned int)a>>1)+((unsigned int)b)>>1)
alpar@2272: // 			  & 0xfffffffc);
alpar@2272: // // #elif X86_64
alpar@2272: // // 	  Edge *m=(Edge*)(((unsigned long)a>>1+(undigned long)b)>>1)&0xfffffffc);
alpar@2272: // // #else
alpar@2272: // //  	  Edge *m=a+((b-a)/2);
alpar@2272: // // #endif
alpar@2272: // 	  Node tt = _g.target(*m);
alpar@2272: // 	  if(tt==t) return *m;
alpar@2272: // 	  else if(tt<t) a=m+1;
alpar@2272: // 	  else b=m;
alpar@2272: // 	}
alpar@2272: //       return INVALID;
alpar@2272: //     }
alpar@2271: 
alpar@2272: //     ///Find the next edge
alpar@2271:       
alpar@2272: //       ///\warning This function is unimplemented.
alpar@2272: //     Edge operator()(Node s, Node t, Edge prev) 
alpar@2272: //     {
alpar@2272: //       return prev==INVALID?(*this)(s,t):INVALID;
alpar@2272: //     }
alpar@2271:       
alpar@2272: //   };
alpar@2271: 
alpar@2235: GRAPH_TYPEDEFS(SmartGraph)
alpar@2235: typedef SmartGraph Graph;
alpar@2235: 
alpar@2235: class FE 
alpar@2235: {
alpar@2235: public:
alpar@2235:   Graph &_g;
alpar@2235:   FE(Graph &g) :_g(g) {}
alpar@2235:   void operator()() 
alpar@2235:   {
alpar@2235:     Edge e;
alpar@2235:     
alpar@2235:     for(NodeIt v(_g);v!=INVALID;++v)
alpar@2235:       for(NodeIt u(_g);u!=INVALID;++u)
alpar@2235: 	e=findEdge(_g,u,v);
alpar@2235:   }
alpar@2235:   
alpar@2235: };
alpar@2235: 
alpar@2235: class EL 
alpar@2235: {
alpar@2235: public:
alpar@2235:   Graph &_g;
alpar@2235:   EdgeLookUp<Graph> _el;
alpar@2235:   EL(Graph &g) :_g(g), _el(g) {}
alpar@2235:   void operator()() 
alpar@2235:   {
alpar@2235:     Edge e;
alpar@2235:     
alpar@2235:     for(NodeIt v(_g);v!=INVALID;++v)
alpar@2235:       for(NodeIt u(_g);u!=INVALID;++u)
alpar@2235: 	e=_el(u,v);
alpar@2235:   }
alpar@2235:   
alpar@2235: };
alpar@2235: class EL2
alpar@2235: {
alpar@2235: public:
alpar@2235:   Graph &_g;
alpar@2235:   EdgeLookUp2<Graph> _el;
alpar@2235:   EL2(Graph &g) :_g(g), _el(g) {}
alpar@2235:   void operator()() 
alpar@2235:   {
alpar@2235:     Edge e;
alpar@2235:     
alpar@2235:     for(NodeIt v(_g);v!=INVALID;++v)
alpar@2235:       for(NodeIt u(_g);u!=INVALID;++u)
alpar@2235: 	e=_el(u,v);
alpar@2235:   }
alpar@2235:   
alpar@2235: };
alpar@2235: 
alpar@2235: class EL3
alpar@2235: {
alpar@2235: public:
alpar@2235:   Graph &_g;
alpar@2235:   EdgeLookUp3<Graph> _el;
alpar@2235:   EL3(Graph &g) :_g(g), _el(g) {}
alpar@2235:   void operator()() 
alpar@2235:   {
alpar@2235:     Edge e;
alpar@2235:     
alpar@2235:     for(NodeIt v(_g);v!=INVALID;++v)
alpar@2235:       for(NodeIt u(_g);u!=INVALID;++u)
alpar@2235: 	e=_el(u,v);
alpar@2235:   }
alpar@2235:   
alpar@2235: };
alpar@2235: 
alpar@2274: // class EL4
alpar@2274: // {
alpar@2274: // public:
alpar@2274: //   Graph &_g;
alpar@2274: //   EdgeLookUp4<Graph> _el;
alpar@2274: //   EL4(Graph &g) :_g(g), _el(g) {}
alpar@2274: //   void operator()() 
alpar@2274: //   {
alpar@2274: //     Edge e;
alpar@2235:     
alpar@2274: //     for(NodeIt v(_g);v!=INVALID;++v)
alpar@2274: //       for(NodeIt u(_g);u!=INVALID;++u)
alpar@2274: // 	e=_el(u,v);
alpar@2274: //   }
alpar@2235:   
alpar@2274: // };
alpar@2235: 
alpar@2274: // class EL5
alpar@2274: // {
alpar@2274: // public:
alpar@2274: //   Graph &_g;
alpar@2274: //   EdgeLookUp5<Graph> _el;
alpar@2274: //   EL5(Graph &g) :_g(g), _el(g) {}
alpar@2274: //   void operator()() 
alpar@2274: //   {
alpar@2274: //     Edge e;
alpar@2271:     
alpar@2274: //     for(NodeIt v(_g);v!=INVALID;++v)
alpar@2274: //       for(NodeIt u(_g);u!=INVALID;++u)
alpar@2274: // 	e=_el(u,v);
alpar@2274: //   }
alpar@2271:   
alpar@2274: // };
alpar@2271: 
alpar@2238: int main(int, char**argv)
alpar@2235: {
alpar@2235:   int N=atoi(argv[1]);
alpar@2235:   int M=int(N*atof(argv[2]));
alpar@2235:   
alpar@2235:   Graph g;
alpar@2235:   
alpar@2235:   std::vector<Node> v;
alpar@2235:   for(int i=0;i<N;i++) v.push_back(g.addNode());
deba@2242:   for(int i=0;i<M;i++) g.addEdge(v[rnd[N]],v[rnd[N]]);
alpar@2235: 
alpar@2235: //   {
alpar@2235: //     Edge e;
alpar@2235:     
alpar@2235: //     TimeReport t("findEdge: ");
alpar@2235: //     for(NodeIt u(g);u!=INVALID;++u)
alpar@2235: //       for(NodeIt v(g);v!=INVALID;++v)
alpar@2235: // 	e=findEdge(g,u,v);
alpar@2235: //   }
alpar@2235: //   {
alpar@2235: //     Edge e;
alpar@2235: //     EdgeLookUp<Graph> el(g);
alpar@2235:     
alpar@2235: //     TimeReport t("EdgeLookUp: ");
alpar@2235: //     for(NodeIt u(g);u!=INVALID;++u)
alpar@2235: //       for(NodeIt v(g);v!=INVALID;++v)
alpar@2235: // 	e=el(u,v);
alpar@2235: //   }
alpar@2235: 
alpar@2235: 
alpar@2235:   TimeStamp t1 = runningTimeTest(FE(g),1);
alpar@2235:   TimeStamp t2 = runningTimeTest(EL(g),1);
alpar@2235:   TimeStamp t3 = runningTimeTest(EL2(g),1);
alpar@2235:   TimeStamp t4 = runningTimeTest(EL3(g),1);
alpar@2272: //   TimeStamp t5 = runningTimeTest(EL4(g),1);
alpar@2272: //   TimeStamp t6 = runningTimeTest(EL5(g),1);
alpar@2235: 
alpar@2235:   std::cout << t1.userTime()/N/N << ' ' 
alpar@2235: 	    << t2.userTime()/N/N << ' '
alpar@2235: 	    << t3.userTime()/N/N << ' '
alpar@2235: 	    << t4.userTime()/N/N << ' '
alpar@2272: // 	    << t5.userTime()/N/N << ' '
alpar@2272: //  	    << t6.userTime()/N/N
alpar@2240: 	    << std::endl;
alpar@2235: }
alpar@2235: