lemon-0.x: benchmark/edge_lookup.cc@a2ab63454152

     1 #include<lemon/smart_graph.h>

     2 #include<vector>

     3 #include<lemon/time_measure.h>

     4 #include<lemon/random.h>

     5 #include<lemon/graph_utils.h>

     6 #include<algorithm>

     8 using namespace lemon;

    10   template<class G>

    11   class EdgeLookUp2

    12   {

    13   public:

    14     GRAPH_TYPEDEFS(typename G)

    15     typedef G Graph;

    17   private:

    18     const Graph &_g;

    19     typename Graph::template NodeMap<int> _start;

    20     typename Graph::template NodeMap<int> _end;

    21     std::vector<Edge> _edges;

    23     class EdgeLess {

    24       const Graph &g;

    25     public:

    26       EdgeLess(const Graph &_g) : g(_g) {}

    27       bool operator()(Edge a,Edge b) const

    28       {

    29 	return g.target(a)<g.target(b);

    30       }

    31     };

    33   public:

    35     ///Constructor

    36     EdgeLookUp2(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}

    38   public:

    39     ///Refresh the data structure at a node.

    40     void refresh(Node n)

    41     {

    42       const int bi = _start[n] = _edges.size();

    43       for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);

    44       const typename std::vector<Edge>::iterator ei=_edges.end();

    45       _end[n]=_edges.size();

    46       std::sort(_edges.begin()+bi,ei,EdgeLess(_g));

    47     }

    48     ///Refresh the full data structure.

    49     void refresh()

    50     {

    51       _edges.clear();

    52       for(NodeIt n(_g);n!=INVALID;++n) refresh(n);

    53     }

    55     ///Find an edge between two nodes.

    57     ///Find an edge between two nodes.

    58     ///\param s The source node

    59     ///\param t The target node

    60     ///\return An edge from \c s to \c t if there exists,

    61     ///\ref INVALID otherwise.

    63     Edge operator()(Node s, Node t)

    64     {

    65       int a=_start[s];

    66       int b=_end[s];

    67       while(a<b)

    68 	{

    69 	  int n=(a+b)/2;

    70 	  Node tt = _g.target(_edges[n]);

    71 	  if(tt==t) return _edges[n];

    72 	  else if(tt<t) a=n+1;

    73 	  else b=n;

    74 	}

    75       return INVALID;

    76     }

    78     ///Find the next edge

    80       ///\warning This function is unimplemented.

    81     Edge operator()(Node s, Node t, Edge prev)

    82     {

    83       return prev==INVALID?(*this)(s,t):INVALID;

    84     }

    86   };

    88   template<class G>

    89   class EdgeLookUp3

    90   {

    91   public:

    92     GRAPH_TYPEDEFS(typename G)

    93     typedef G Graph;

    95   private:

    96     const Graph &_g;

    97     typename Graph::template NodeMap<Edge*> _start;

    98     typename Graph::template NodeMap<Edge*> _end;

    99     std::vector<Edge> _edges;

   101     class EdgeLess {

   102       const Graph &g;

   103     public:

   104       EdgeLess(const Graph &_g) : g(_g) {}

   105       bool operator()(Edge a,Edge b) const

   106       {

   107 	return g.target(a)<g.target(b);

   108       }

   109     };

   111   public:

   113     ///Constructor

   114     EdgeLookUp3(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}

   116   public:

   117     ///Refresh the data structure at a node.

   118     void refresh(Node n)

   119     {

   120       const int bi = _start[n] = _edges.size();

   121       for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);

   122       const typename std::vector<Edge>::iterator ei=_edges.end();

   123       _end[n]=_edges.size();

   124       std::sort(_edges.begin()+bi,ei,EdgeLess(_g));

   125     }

   126     ///Refresh the full data structure.

   127     void refresh()

   128     {

   129       _edges.resize(countEdges(_g));

   130       int l=0;

   131       for(NodeIt n(_g);n!=INVALID;++n)

   132 	{

   133 	  int ls = l;

   134 	  _start[n]=&(_edges[l]);

   135 	  for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;

   136 	  _end[n]=&(_edges[l]);

   137 	  std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));

   138 	}

   140     }

   142     ///Find an edge between two nodes.

   144     ///Find an edge between two nodes.

   145     ///\param s The source node

   146     ///\param t The target node

   147     ///\return An edge from \c s to \c t if there exists,

   148     ///\ref INVALID otherwise.

   150     Edge operator()(Node s, Node t)

   151     {

   152       Edge *a=_start[s];

   153       Edge *b=_end[s];

   154       while(a!=b)

   155 	{

   156  	  Edge *m=a+((b-a)/2);

   157 	  Node tt = _g.target(*m);

   158 	  if(tt==t) return *m;

   159 	  else if(tt<t) a=m+1;

   160 	  else b=m;

   161 	}

   162       return INVALID;

   163     }

   165     ///Find the next edge

   167       ///\warning This function is unimplemented.

   168     Edge operator()(Node s, Node t, Edge prev)

   169     {

   170       return prev==INVALID?(*this)(s,t):INVALID;

   171     }

   173   };

   175   template<class G>

   176   class EdgeLookUp4

   177   {

   178   public:

   179     GRAPH_TYPEDEFS(typename G)

   180     typedef G Graph;

   182   private:

   183     const Graph &_g;

   184     typename Graph::template NodeMap<Edge*> _start;

   185     typename Graph::template NodeMap<Edge*> _end;

   186     std::vector<Edge> _edges;

   188     class EdgeLess {

   189       const Graph &g;

   190     public:

   191       EdgeLess(const Graph &_g) : g(_g) {}

   192       bool operator()(Edge a,Edge b) const

   193       {

   194 	return g.target(a)<g.target(b);

   195       }

   196     };

   198   public:

   200     ///Constructor

   201     EdgeLookUp4(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}

   203   public:

   204     ///Refresh the data structure at a node.

   205     void refresh(Node n)

   206     {

   207       const int bi = _start[n] = _edges.size();

   208       for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);

   209       const typename std::vector<Edge>::iterator ei=_edges.end();

   210       _end[n]=_edges.size();

   211       std::sort(_edges.begin()+bi,ei,EdgeLess(_g));

   212     }

   213     ///Refresh the full data structure.

   214     void refresh()

   215     {

   216       _edges.resize(countEdges(_g));

   217       int l=0;

   218       for(NodeIt n(_g);n!=INVALID;++n)

   219 	{

   220 	  int ls = l;

   221 	  _start[n]=&(_edges[l]);

   222 	  for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;

   223 	  _end[n]=&(_edges[l]);

   224 	  std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));

   225 	}

   227     }

   229     ///Find an edge between two nodes.

   231     ///Find an edge between two nodes.

   232     ///\param s The source node

   233     ///\param t The target node

   234     ///\return An edge from \c s to \c t if there exists,

   235     ///\ref INVALID otherwise.

   237     Edge operator()(Node s, Node t)

   238     {

   239       Edge *a=_start[s];

   240       Edge *b=_end[s];

   241       while(a!=b)

   242 	{

   243 // #ifdef X86

   244  	  Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc);

   245 // #elif X86_64

   246 // 	  Edge *m=(Edge*)(((unsigned long)a+(undigned long)b)/2 & 0xfffffffc);

   247 // #else

   248 //  	  Edge *m=a+((b-a)/2);

   249 // #endif

   250 	  Node tt = _g.target(*m);

   251 	  if(tt==t) return *m;

   252 	  else if(tt<t) a=m+1;

   253 	  else b=m;

   254 	}

   255       return INVALID;

   256     }

   258     ///Find the next edge

   260       ///\warning This function is unimplemented.

   261     Edge operator()(Node s, Node t, Edge prev)

   262     {

   263       return prev==INVALID?(*this)(s,t):INVALID;

   264     }

   266   };

   268   template<class G>

   269   class EdgeLookUp5

   270   {

   271   public:

   272     GRAPH_TYPEDEFS(typename G)

   273     typedef G Graph;

   275   private:

   276     const Graph &_g;

   277     typename Graph::template NodeMap<Edge*> _start;

   278     typename Graph::template NodeMap<Edge*> _end;

   279     std::vector<Edge> _edges;

   281     class EdgeLess {

   282       const Graph &g;

   283     public:

   284       EdgeLess(const Graph &_g) : g(_g) {}

   285       bool operator()(Edge a,Edge b) const

   286       {

   287 	return g.target(a)<g.target(b);

   288       }

   289     };

   291   public:

   293     ///Constructor

   294     EdgeLookUp5(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}

   296   public:

   297     ///Refresh the data structure at a node.

   298     void refresh(Node n)

   299     {

   300       const int bi = _start[n] = _edges.size();

   301       for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);

   302       const typename std::vector<Edge>::iterator ei=_edges.end();

   303       _end[n]=_edges.size();

   304       std::sort(_edges.begin()+bi,ei,EdgeLess(_g));

   305     }

   306     ///Refresh the full data structure.

   307     void refresh()

   308     {

   309       _edges.resize(countEdges(_g));

   310       int l=0;

   311       for(NodeIt n(_g);n!=INVALID;++n)

   312 	{

   313 	  int ls = l;

   314 	  _start[n]=&(_edges[l]);

   315 	  for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;

   316 	  _end[n]=&(_edges[l]);

   317 	  std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));

   318 	}

   320     }

   322     ///Find an edge between two nodes.

   324     ///Find an edge between two nodes.

   325     ///\param s The source node

   326     ///\param t The target node

   327     ///\return An edge from \c s to \c t if there exists,

   328     ///\ref INVALID otherwise.

   330     Edge operator()(Node s, Node t)

   331     {

   332       Edge *a=_start[s];

   333       Edge *b=_end[s];

   334       while(a!=b)

   335 	{

   336 // #ifdef X86

   337  	  Edge *m=(Edge*)((((unsigned int)a>>1)+((unsigned int)b)>>1)

   338 			  & 0xfffffffc);

   339 // #elif X86_64

   340 // 	  Edge *m=(Edge*)(((unsigned long)a>>1+(undigned long)b)>>1)&0xfffffffc);

   341 // #else

   342 //  	  Edge *m=a+((b-a)/2);

   343 // #endif

   344 	  Node tt = _g.target(*m);

   345 	  if(tt==t) return *m;

   346 	  else if(tt<t) a=m+1;

   347 	  else b=m;

   348 	}

   349       return INVALID;

   350     }

   352     ///Find the next edge

   354       ///\warning This function is unimplemented.

   355     Edge operator()(Node s, Node t, Edge prev)

   356     {

   357       return prev==INVALID?(*this)(s,t):INVALID;

   358     }

   360   };

   362 GRAPH_TYPEDEFS(SmartGraph)

   363 typedef SmartGraph Graph;

   365 class FE

   366 {

   367 public:

   368   Graph &_g;

   369   FE(Graph &g) :_g(g) {}

   370   void operator()()

   371   {

   372     Edge e;

   374     for(NodeIt v(_g);v!=INVALID;++v)

   375       for(NodeIt u(_g);u!=INVALID;++u)

   376 	e=findEdge(_g,u,v);

   377   }

   379 };

   381 class EL

   382 {

   383 public:

   384   Graph &_g;

   385   EdgeLookUp<Graph> _el;

   386   EL(Graph &g) :_g(g), _el(g) {}

   387   void operator()()

   388   {

   389     Edge e;

   391     for(NodeIt v(_g);v!=INVALID;++v)

   392       for(NodeIt u(_g);u!=INVALID;++u)

   393 	e=_el(u,v);

   394   }

   396 };

   397 class EL2

   398 {

   399 public:

   400   Graph &_g;

   401   EdgeLookUp2<Graph> _el;

   402   EL2(Graph &g) :_g(g), _el(g) {}

   403   void operator()()

   404   {

   405     Edge e;

   407     for(NodeIt v(_g);v!=INVALID;++v)

   408       for(NodeIt u(_g);u!=INVALID;++u)

   409 	e=_el(u,v);

   410   }

   412 };

   414 class EL3

   415 {

   416 public:

   417   Graph &_g;

   418   EdgeLookUp3<Graph> _el;

   419   EL3(Graph &g) :_g(g), _el(g) {}

   420   void operator()()

   421   {

   422     Edge e;

   424     for(NodeIt v(_g);v!=INVALID;++v)

   425       for(NodeIt u(_g);u!=INVALID;++u)

   426 	e=_el(u,v);

   427   }

   429 };

   431 class EL4

   432 {

   433 public:

   434   Graph &_g;

   435   EdgeLookUp4<Graph> _el;

   436   EL4(Graph &g) :_g(g), _el(g) {}

   437   void operator()()

   438   {

   439     Edge e;

   441     for(NodeIt v(_g);v!=INVALID;++v)

   442       for(NodeIt u(_g);u!=INVALID;++u)

   443 	e=_el(u,v);

   444   }

   446 };

   448 class EL5

   449 {

   450 public:

   451   Graph &_g;

   452   EdgeLookUp5<Graph> _el;

   453   EL5(Graph &g) :_g(g), _el(g) {}

   454   void operator()()

   455   {

   456     Edge e;

   458     for(NodeIt v(_g);v!=INVALID;++v)

   459       for(NodeIt u(_g);u!=INVALID;++u)

   460 	e=_el(u,v);

   461   }

   463 };

   465 int main(int, char**argv)

   466 {

   467   int N=atoi(argv[1]);

   468   int M=int(N*atof(argv[2]));

   470   Graph g;

   472   std::vector<Node> v;

   473   for(int i=0;i<N;i++) v.push_back(g.addNode());

   474   for(int i=0;i<M;i++) g.addEdge(v[rnd[N]],v[rnd[N]]);

   476 //   {

   477 //     Edge e;

   479 //     TimeReport t("findEdge: ");

   480 //     for(NodeIt u(g);u!=INVALID;++u)

   481 //       for(NodeIt v(g);v!=INVALID;++v)

   482 // 	e=findEdge(g,u,v);

   483 //   }

   484 //   {

   485 //     Edge e;

   486 //     EdgeLookUp<Graph> el(g);

   488 //     TimeReport t("EdgeLookUp: ");

   489 //     for(NodeIt u(g);u!=INVALID;++u)

   490 //       for(NodeIt v(g);v!=INVALID;++v)

   491 // 	e=el(u,v);

   492 //   }

   495   TimeStamp t1 = runningTimeTest(FE(g),1);

   496   TimeStamp t2 = runningTimeTest(EL(g),1);

   497   TimeStamp t3 = runningTimeTest(EL2(g),1);

   498   TimeStamp t4 = runningTimeTest(EL3(g),1);

   499   TimeStamp t5 = runningTimeTest(EL4(g),1);

   500   TimeStamp t6 = runningTimeTest(EL5(g),1);

   502   std::cout << t1.userTime()/N/N << ' '

   503 	    << t2.userTime()/N/N << ' '

   504 	    << t3.userTime()/N/N << ' '

   505 	    << t4.userTime()/N/N << ' '

   506 	    << t5.userTime()/N/N << ' '

   507  	    << t6.userTime()/N/N

   508 	    << std::endl;

   509 }

author	alpar
	Mon, 30 Oct 2006 15:23:35 +0000
changeset 2271	a2ab63454152
parent 2252	133028e83940
child 2272	f6b352fdc6b1
permissions	-rw-r--r--