alpar@2238: #include"edge_lookup_test.h"
alpar@2235: #include<lemon/smart_graph.h>
alpar@2235: #include<vector>
alpar@2235: #include<lemon/time_measure.h>
alpar@2235: 
alpar@2235: using namespace lemon;
alpar@2235: 
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@2235: class EL4
alpar@2235: {
alpar@2235: public:
alpar@2235:   Graph &_g;
alpar@2235:   EdgeLookUp4<Graph> _el;
alpar@2235:   EL4(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@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());
alpar@2235:   for(int i=0;i<M;i++) g.addEdge(v[int(drand48()*N)],v[int(drand48()*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@2235:   TimeStamp t5 = runningTimeTest(EL4(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@2235: 	    << t5.userTime()/N/N << std::endl;
alpar@2235: }
alpar@2235: