benchmark/edge_lookup.cc
author deba
Mon, 10 Dec 2007 16:34:31 +0000
changeset 2538 7bdd328de87a
parent 2391 14a343be7a5a
child 2539 c25f62a6452d
permissions -rw-r--r--
Bug fix in doc
alpar@2391
     1
/* -*- C++ -*-
alpar@2391
     2
 *
alpar@2391
     3
 * This file is a part of LEMON, a generic C++ optimization library
alpar@2391
     4
 *
alpar@2391
     5
 * Copyright (C) 2003-2007
alpar@2391
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@2391
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@2391
     8
 *
alpar@2391
     9
 * Permission to use, modify and distribute this software is granted
alpar@2391
    10
 * provided that this copyright notice appears in all copies. For
alpar@2391
    11
 * precise terms see the accompanying LICENSE file.
alpar@2391
    12
 *
alpar@2391
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@2391
    14
 * express or implied, and with no claim as to its suitability for any
alpar@2391
    15
 * purpose.
alpar@2391
    16
 *
alpar@2391
    17
 */
alpar@2391
    18
alpar@2235
    19
#include<lemon/smart_graph.h>
alpar@2235
    20
#include<vector>
alpar@2235
    21
#include<lemon/time_measure.h>
deba@2242
    22
#include<lemon/random.h>
alpar@2271
    23
#include<lemon/graph_utils.h>
alpar@2271
    24
#include<algorithm>
alpar@2235
    25
alpar@2235
    26
using namespace lemon;
alpar@2235
    27
alpar@2271
    28
  template<class G>
alpar@2271
    29
  class EdgeLookUp2
alpar@2271
    30
  {
alpar@2271
    31
  public:
deba@2510
    32
    GRAPH_TYPEDEFS(typename G);
alpar@2271
    33
    typedef G Graph;
alpar@2271
    34
alpar@2271
    35
  private:
alpar@2271
    36
    const Graph &_g;
alpar@2271
    37
    typename Graph::template NodeMap<int> _start;
alpar@2271
    38
    typename Graph::template NodeMap<int> _end;
alpar@2271
    39
    std::vector<Edge> _edges;
alpar@2271
    40
    
alpar@2271
    41
    class EdgeLess {
alpar@2271
    42
      const Graph &g;
alpar@2271
    43
    public:
alpar@2271
    44
      EdgeLess(const Graph &_g) : g(_g) {}
alpar@2271
    45
      bool operator()(Edge a,Edge b) const 
alpar@2271
    46
      {
alpar@2271
    47
	return g.target(a)<g.target(b);
alpar@2271
    48
      }
alpar@2271
    49
    };
alpar@2271
    50
    
alpar@2271
    51
  public:
alpar@2271
    52
    
alpar@2271
    53
    ///Constructor
alpar@2271
    54
    EdgeLookUp2(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
alpar@2271
    55
    
alpar@2271
    56
  public:
alpar@2271
    57
    ///Refresh the data structure at a node.
alpar@2271
    58
    void refresh(Node n) 
alpar@2271
    59
    {
alpar@2271
    60
      const int bi = _start[n] = _edges.size();
alpar@2271
    61
      for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
alpar@2271
    62
      const typename std::vector<Edge>::iterator ei=_edges.end();
alpar@2271
    63
      _end[n]=_edges.size();
alpar@2271
    64
      std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
alpar@2271
    65
    }
alpar@2271
    66
    ///Refresh the full data structure.
alpar@2271
    67
    void refresh() 
alpar@2271
    68
    {
alpar@2271
    69
      _edges.clear();
alpar@2271
    70
      for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
alpar@2271
    71
    }
alpar@2271
    72
    
alpar@2271
    73
    ///Find an edge between two nodes.
alpar@2271
    74
    
alpar@2271
    75
    ///Find an edge between two nodes.
alpar@2271
    76
    ///\param s The source node
alpar@2271
    77
    ///\param t The target node
alpar@2271
    78
    ///\return An edge from \c s to \c t if there exists,
alpar@2271
    79
    ///\ref INVALID otherwise.
alpar@2271
    80
alpar@2271
    81
    Edge operator()(Node s, Node t) 
alpar@2271
    82
    {
alpar@2271
    83
      int a=_start[s];
alpar@2271
    84
      int b=_end[s];
alpar@2271
    85
      while(a<b) 
alpar@2271
    86
	{
alpar@2271
    87
	  int n=(a+b)/2;
alpar@2271
    88
	  Node tt = _g.target(_edges[n]);
alpar@2271
    89
	  if(tt==t) return _edges[n];
alpar@2271
    90
	  else if(tt<t) a=n+1;
alpar@2271
    91
	  else b=n;
alpar@2271
    92
	}
alpar@2271
    93
      return INVALID;
alpar@2271
    94
    }
alpar@2271
    95
alpar@2271
    96
    ///Find the next edge
alpar@2271
    97
      
alpar@2271
    98
      ///\warning This function is unimplemented.
alpar@2271
    99
    Edge operator()(Node s, Node t, Edge prev) 
alpar@2271
   100
    {
alpar@2271
   101
      return prev==INVALID?(*this)(s,t):INVALID;
alpar@2271
   102
    }
alpar@2271
   103
      
alpar@2271
   104
  };
alpar@2271
   105
alpar@2271
   106
  template<class G>
alpar@2271
   107
  class EdgeLookUp3
alpar@2271
   108
  {
alpar@2271
   109
  public:
deba@2510
   110
    GRAPH_TYPEDEFS(typename G);
alpar@2271
   111
    typedef G Graph;
alpar@2271
   112
alpar@2271
   113
  private:
alpar@2271
   114
    const Graph &_g;
alpar@2271
   115
    typename Graph::template NodeMap<Edge*> _start;
alpar@2271
   116
    typename Graph::template NodeMap<Edge*> _end;
alpar@2271
   117
    std::vector<Edge> _edges;
alpar@2271
   118
    
alpar@2271
   119
    class EdgeLess {
alpar@2271
   120
      const Graph &g;
alpar@2271
   121
    public:
alpar@2271
   122
      EdgeLess(const Graph &_g) : g(_g) {}
alpar@2271
   123
      bool operator()(Edge a,Edge b) const 
alpar@2271
   124
      {
alpar@2271
   125
	return g.target(a)<g.target(b);
alpar@2271
   126
      }
alpar@2271
   127
    };
alpar@2271
   128
    
alpar@2271
   129
  public:
alpar@2271
   130
    
alpar@2271
   131
    ///Constructor
alpar@2271
   132
    EdgeLookUp3(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
alpar@2271
   133
    
alpar@2271
   134
  public:
alpar@2271
   135
    ///Refresh the data structure at a node.
alpar@2271
   136
    void refresh(Node n) 
alpar@2271
   137
    {
alpar@2271
   138
      const int bi = _start[n] = _edges.size();
alpar@2271
   139
      for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
alpar@2271
   140
      const typename std::vector<Edge>::iterator ei=_edges.end();
alpar@2271
   141
      _end[n]=_edges.size();
alpar@2271
   142
      std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
alpar@2271
   143
    }
alpar@2271
   144
    ///Refresh the full data structure.
alpar@2271
   145
    void refresh() 
alpar@2271
   146
    {
alpar@2271
   147
      _edges.resize(countEdges(_g));
alpar@2271
   148
      int l=0;
alpar@2271
   149
      for(NodeIt n(_g);n!=INVALID;++n)
alpar@2271
   150
	{
alpar@2271
   151
	  int ls = l;
alpar@2271
   152
	  _start[n]=&(_edges[l]);	
alpar@2271
   153
	  for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;
alpar@2271
   154
	  _end[n]=&(_edges[l]);
alpar@2271
   155
	  std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));
alpar@2271
   156
	}
alpar@2271
   157
      
alpar@2271
   158
    }
alpar@2271
   159
    
alpar@2271
   160
    ///Find an edge between two nodes.
alpar@2271
   161
    
alpar@2271
   162
    ///Find an edge between two nodes.
alpar@2271
   163
    ///\param s The source node
alpar@2271
   164
    ///\param t The target node
alpar@2271
   165
    ///\return An edge from \c s to \c t if there exists,
alpar@2271
   166
    ///\ref INVALID otherwise.
alpar@2271
   167
alpar@2271
   168
    Edge operator()(Node s, Node t) 
alpar@2271
   169
    {
alpar@2271
   170
      Edge *a=_start[s];
alpar@2271
   171
      Edge *b=_end[s];
alpar@2271
   172
      while(a!=b) 
alpar@2271
   173
	{
alpar@2271
   174
 	  Edge *m=a+((b-a)/2);
alpar@2271
   175
	  Node tt = _g.target(*m);
alpar@2271
   176
	  if(tt==t) return *m;
alpar@2271
   177
	  else if(tt<t) a=m+1;
alpar@2271
   178
	  else b=m;
alpar@2271
   179
	}
alpar@2271
   180
      return INVALID;
alpar@2271
   181
    }
alpar@2271
   182
alpar@2271
   183
    ///Find the next edge
alpar@2271
   184
      
alpar@2271
   185
      ///\warning This function is unimplemented.
alpar@2271
   186
    Edge operator()(Node s, Node t, Edge prev) 
alpar@2271
   187
    {
alpar@2271
   188
      return prev==INVALID?(*this)(s,t):INVALID;
alpar@2271
   189
    }
alpar@2271
   190
      
alpar@2271
   191
  };
alpar@2271
   192
alpar@2272
   193
//   template<class G>
alpar@2272
   194
//   class EdgeLookUp4
alpar@2272
   195
//   {
alpar@2272
   196
//   public:
deba@2510
   197
//     GRAPH_TYPEDEFS(typename G);
alpar@2272
   198
//     typedef G Graph;
alpar@2271
   199
    
alpar@2272
   200
//   private:
alpar@2272
   201
//     const Graph &_g;
alpar@2272
   202
//     typename Graph::template NodeMap<Edge*> _start;
alpar@2272
   203
//     typename Graph::template NodeMap<Edge*> _end;
alpar@2272
   204
//     std::vector<Edge> _edges;
alpar@2271
   205
    
alpar@2272
   206
//     class EdgeLess {
alpar@2272
   207
//       const Graph &g;
alpar@2272
   208
//     public:
alpar@2272
   209
//       EdgeLess(const Graph &_g) : g(_g) {}
alpar@2272
   210
//       bool operator()(Edge a,Edge b) const 
alpar@2272
   211
//       {
alpar@2272
   212
// 	return g.target(a)<g.target(b);
alpar@2272
   213
//       }
alpar@2272
   214
//     };
alpar@2271
   215
    
alpar@2272
   216
//   public:
alpar@2271
   217
    
alpar@2272
   218
//     ///Constructor
alpar@2272
   219
//     EdgeLookUp4(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
alpar@2271
   220
    
alpar@2272
   221
//   public:
alpar@2272
   222
//     ///Refresh the data structure at a node.
alpar@2272
   223
//     void refresh(Node n) 
alpar@2272
   224
//     {
alpar@2272
   225
//       const int bi = _start[n] = _edges.size();
alpar@2272
   226
//       for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
alpar@2272
   227
//       const typename std::vector<Edge>::iterator ei=_edges.end();
alpar@2272
   228
//       _end[n]=_edges.size();
alpar@2272
   229
//       std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
alpar@2272
   230
//     }
alpar@2272
   231
//     ///Refresh the full data structure.
alpar@2272
   232
//     void refresh() 
alpar@2272
   233
//     {
alpar@2272
   234
//       _edges.resize(countEdges(_g));
alpar@2272
   235
//       int l=0;
alpar@2272
   236
//       for(NodeIt n(_g);n!=INVALID;++n)
alpar@2272
   237
// 	{
alpar@2272
   238
// 	  int ls = l;
alpar@2272
   239
// 	  _start[n]=&(_edges[l]);	
alpar@2272
   240
// 	  for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;
alpar@2272
   241
// 	  _end[n]=&(_edges[l]);
alpar@2272
   242
// 	  std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));
alpar@2272
   243
// 	}
alpar@2271
   244
      
alpar@2272
   245
//     }
alpar@2271
   246
    
alpar@2272
   247
//     ///Find an edge between two nodes.
alpar@2271
   248
    
alpar@2272
   249
//     ///Find an edge between two nodes.
alpar@2272
   250
//     ///\param s The source node
alpar@2272
   251
//     ///\param t The target node
alpar@2272
   252
//     ///\return An edge from \c s to \c t if there exists,
alpar@2272
   253
//     ///\ref INVALID otherwise.
alpar@2271
   254
alpar@2272
   255
//     Edge operator()(Node s, Node t) 
alpar@2272
   256
//     {
alpar@2272
   257
//       Edge *a=_start[s];
alpar@2272
   258
//       Edge *b=_end[s];
alpar@2272
   259
//       while(a!=b) 
alpar@2272
   260
// 	{
alpar@2272
   261
// // #ifdef X86
alpar@2272
   262
//  	  Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc);
alpar@2272
   263
// // #elif X86_64
alpar@2272
   264
// // 	  Edge *m=(Edge*)(((unsigned long)a+(undigned long)b)/2 & 0xfffffffc);
alpar@2272
   265
// // #else
alpar@2272
   266
// //  	  Edge *m=a+((b-a)/2);
alpar@2272
   267
// // #endif
alpar@2272
   268
// 	  Node tt = _g.target(*m);
alpar@2272
   269
// 	  if(tt==t) return *m;
alpar@2272
   270
// 	  else if(tt<t) a=m+1;
alpar@2272
   271
// 	  else b=m;
alpar@2272
   272
// 	}
alpar@2272
   273
//       return INVALID;
alpar@2272
   274
//     }
alpar@2271
   275
alpar@2272
   276
//     ///Find the next edge
alpar@2271
   277
      
alpar@2272
   278
//       ///\warning This function is unimplemented.
alpar@2272
   279
//     Edge operator()(Node s, Node t, Edge prev) 
alpar@2272
   280
//     {
alpar@2272
   281
//       return prev==INVALID?(*this)(s,t):INVALID;
alpar@2272
   282
//     }
alpar@2271
   283
      
alpar@2272
   284
//   };
alpar@2271
   285
alpar@2272
   286
//   template<class G>
alpar@2272
   287
//   class EdgeLookUp5
alpar@2272
   288
//   {
alpar@2272
   289
//   public:
deba@2510
   290
//     GRAPH_TYPEDEFS(typename G);
alpar@2272
   291
//     typedef G Graph;
alpar@2271
   292
    
alpar@2272
   293
//   private:
alpar@2272
   294
//     const Graph &_g;
alpar@2272
   295
//     typename Graph::template NodeMap<Edge*> _start;
alpar@2272
   296
//     typename Graph::template NodeMap<Edge*> _end;
alpar@2272
   297
//     std::vector<Edge> _edges;
alpar@2271
   298
    
alpar@2272
   299
//     class EdgeLess {
alpar@2272
   300
//       const Graph &g;
alpar@2272
   301
//     public:
alpar@2272
   302
//       EdgeLess(const Graph &_g) : g(_g) {}
alpar@2272
   303
//       bool operator()(Edge a,Edge b) const 
alpar@2272
   304
//       {
alpar@2272
   305
// 	return g.target(a)<g.target(b);
alpar@2272
   306
//       }
alpar@2272
   307
//     };
alpar@2271
   308
    
alpar@2272
   309
//   public:
alpar@2271
   310
    
alpar@2272
   311
//     ///Constructor
alpar@2272
   312
//     EdgeLookUp5(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
alpar@2271
   313
    
alpar@2272
   314
//   public:
alpar@2272
   315
//     ///Refresh the data structure at a node.
alpar@2272
   316
//     void refresh(Node n) 
alpar@2272
   317
//     {
alpar@2272
   318
//       const int bi = _start[n] = _edges.size();
alpar@2272
   319
//       for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
alpar@2272
   320
//       const typename std::vector<Edge>::iterator ei=_edges.end();
alpar@2272
   321
//       _end[n]=_edges.size();
alpar@2272
   322
//       std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
alpar@2272
   323
//     }
alpar@2272
   324
//     ///Refresh the full data structure.
alpar@2272
   325
//     void refresh() 
alpar@2272
   326
//     {
alpar@2272
   327
//       _edges.resize(countEdges(_g));
alpar@2272
   328
//       int l=0;
alpar@2272
   329
//       for(NodeIt n(_g);n!=INVALID;++n)
alpar@2272
   330
// 	{
alpar@2272
   331
// 	  int ls = l;
alpar@2272
   332
// 	  _start[n]=&(_edges[l]);	
alpar@2272
   333
// 	  for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;
alpar@2272
   334
// 	  _end[n]=&(_edges[l]);
alpar@2272
   335
// 	  std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));
alpar@2272
   336
// 	}
alpar@2271
   337
      
alpar@2272
   338
//     }
alpar@2271
   339
    
alpar@2272
   340
//     ///Find an edge between two nodes.
alpar@2271
   341
    
alpar@2272
   342
//     ///Find an edge between two nodes.
alpar@2272
   343
//     ///\param s The source node
alpar@2272
   344
//     ///\param t The target node
alpar@2272
   345
//     ///\return An edge from \c s to \c t if there exists,
alpar@2272
   346
//     ///\ref INVALID otherwise.
alpar@2271
   347
alpar@2272
   348
//     Edge operator()(Node s, Node t) 
alpar@2272
   349
//     {
alpar@2272
   350
//       Edge *a=_start[s];
alpar@2272
   351
//       Edge *b=_end[s];
alpar@2272
   352
//       while(a!=b) 
alpar@2272
   353
// 	{
alpar@2272
   354
// // #ifdef X86
alpar@2272
   355
//  	  Edge *m=(Edge*)((((unsigned int)a>>1)+((unsigned int)b)>>1)
alpar@2272
   356
// 			  & 0xfffffffc);
alpar@2272
   357
// // #elif X86_64
alpar@2272
   358
// // 	  Edge *m=(Edge*)(((unsigned long)a>>1+(undigned long)b)>>1)&0xfffffffc);
alpar@2272
   359
// // #else
alpar@2272
   360
// //  	  Edge *m=a+((b-a)/2);
alpar@2272
   361
// // #endif
alpar@2272
   362
// 	  Node tt = _g.target(*m);
alpar@2272
   363
// 	  if(tt==t) return *m;
alpar@2272
   364
// 	  else if(tt<t) a=m+1;
alpar@2272
   365
// 	  else b=m;
alpar@2272
   366
// 	}
alpar@2272
   367
//       return INVALID;
alpar@2272
   368
//     }
alpar@2271
   369
alpar@2272
   370
//     ///Find the next edge
alpar@2271
   371
      
alpar@2272
   372
//       ///\warning This function is unimplemented.
alpar@2272
   373
//     Edge operator()(Node s, Node t, Edge prev) 
alpar@2272
   374
//     {
alpar@2272
   375
//       return prev==INVALID?(*this)(s,t):INVALID;
alpar@2272
   376
//     }
alpar@2271
   377
      
alpar@2272
   378
//   };
alpar@2271
   379
deba@2510
   380
GRAPH_TYPEDEFS(SmartGraph);
alpar@2235
   381
typedef SmartGraph Graph;
alpar@2235
   382
alpar@2235
   383
class FE 
alpar@2235
   384
{
alpar@2235
   385
public:
alpar@2235
   386
  Graph &_g;
alpar@2235
   387
  FE(Graph &g) :_g(g) {}
alpar@2235
   388
  void operator()() 
alpar@2235
   389
  {
alpar@2235
   390
    Edge e;
alpar@2235
   391
    
alpar@2235
   392
    for(NodeIt v(_g);v!=INVALID;++v)
alpar@2235
   393
      for(NodeIt u(_g);u!=INVALID;++u)
alpar@2235
   394
	e=findEdge(_g,u,v);
alpar@2235
   395
  }
alpar@2235
   396
  
alpar@2235
   397
};
alpar@2235
   398
alpar@2235
   399
class EL 
alpar@2235
   400
{
alpar@2235
   401
public:
alpar@2235
   402
  Graph &_g;
alpar@2235
   403
  EdgeLookUp<Graph> _el;
alpar@2235
   404
  EL(Graph &g) :_g(g), _el(g) {}
alpar@2235
   405
  void operator()() 
alpar@2235
   406
  {
alpar@2235
   407
    Edge e;
alpar@2235
   408
    
alpar@2235
   409
    for(NodeIt v(_g);v!=INVALID;++v)
alpar@2235
   410
      for(NodeIt u(_g);u!=INVALID;++u)
alpar@2235
   411
	e=_el(u,v);
alpar@2235
   412
  }
alpar@2235
   413
  
alpar@2235
   414
};
alpar@2235
   415
class EL2
alpar@2235
   416
{
alpar@2235
   417
public:
alpar@2235
   418
  Graph &_g;
alpar@2235
   419
  EdgeLookUp2<Graph> _el;
alpar@2235
   420
  EL2(Graph &g) :_g(g), _el(g) {}
alpar@2235
   421
  void operator()() 
alpar@2235
   422
  {
alpar@2235
   423
    Edge e;
alpar@2235
   424
    
alpar@2235
   425
    for(NodeIt v(_g);v!=INVALID;++v)
alpar@2235
   426
      for(NodeIt u(_g);u!=INVALID;++u)
alpar@2235
   427
	e=_el(u,v);
alpar@2235
   428
  }
alpar@2235
   429
  
alpar@2235
   430
};
alpar@2235
   431
alpar@2235
   432
class EL3
alpar@2235
   433
{
alpar@2235
   434
public:
alpar@2235
   435
  Graph &_g;
alpar@2235
   436
  EdgeLookUp3<Graph> _el;
alpar@2235
   437
  EL3(Graph &g) :_g(g), _el(g) {}
alpar@2235
   438
  void operator()() 
alpar@2235
   439
  {
alpar@2235
   440
    Edge e;
alpar@2235
   441
    
alpar@2235
   442
    for(NodeIt v(_g);v!=INVALID;++v)
alpar@2235
   443
      for(NodeIt u(_g);u!=INVALID;++u)
alpar@2235
   444
	e=_el(u,v);
alpar@2235
   445
  }
alpar@2235
   446
  
alpar@2235
   447
};
alpar@2235
   448
alpar@2274
   449
// class EL4
alpar@2274
   450
// {
alpar@2274
   451
// public:
alpar@2274
   452
//   Graph &_g;
alpar@2274
   453
//   EdgeLookUp4<Graph> _el;
alpar@2274
   454
//   EL4(Graph &g) :_g(g), _el(g) {}
alpar@2274
   455
//   void operator()() 
alpar@2274
   456
//   {
alpar@2274
   457
//     Edge e;
alpar@2235
   458
    
alpar@2274
   459
//     for(NodeIt v(_g);v!=INVALID;++v)
alpar@2274
   460
//       for(NodeIt u(_g);u!=INVALID;++u)
alpar@2274
   461
// 	e=_el(u,v);
alpar@2274
   462
//   }
alpar@2235
   463
  
alpar@2274
   464
// };
alpar@2235
   465
alpar@2274
   466
// class EL5
alpar@2274
   467
// {
alpar@2274
   468
// public:
alpar@2274
   469
//   Graph &_g;
alpar@2274
   470
//   EdgeLookUp5<Graph> _el;
alpar@2274
   471
//   EL5(Graph &g) :_g(g), _el(g) {}
alpar@2274
   472
//   void operator()() 
alpar@2274
   473
//   {
alpar@2274
   474
//     Edge e;
alpar@2271
   475
    
alpar@2274
   476
//     for(NodeIt v(_g);v!=INVALID;++v)
alpar@2274
   477
//       for(NodeIt u(_g);u!=INVALID;++u)
alpar@2274
   478
// 	e=_el(u,v);
alpar@2274
   479
//   }
alpar@2271
   480
  
alpar@2274
   481
// };
alpar@2271
   482
alpar@2238
   483
int main(int, char**argv)
alpar@2235
   484
{
alpar@2235
   485
  int N=atoi(argv[1]);
alpar@2235
   486
  int M=int(N*atof(argv[2]));
alpar@2235
   487
  
alpar@2235
   488
  Graph g;
alpar@2235
   489
  
alpar@2235
   490
  std::vector<Node> v;
alpar@2235
   491
  for(int i=0;i<N;i++) v.push_back(g.addNode());
deba@2242
   492
  for(int i=0;i<M;i++) g.addEdge(v[rnd[N]],v[rnd[N]]);
alpar@2235
   493
alpar@2235
   494
//   {
alpar@2235
   495
//     Edge e;
alpar@2235
   496
    
alpar@2235
   497
//     TimeReport t("findEdge: ");
alpar@2235
   498
//     for(NodeIt u(g);u!=INVALID;++u)
alpar@2235
   499
//       for(NodeIt v(g);v!=INVALID;++v)
alpar@2235
   500
// 	e=findEdge(g,u,v);
alpar@2235
   501
//   }
alpar@2235
   502
//   {
alpar@2235
   503
//     Edge e;
alpar@2235
   504
//     EdgeLookUp<Graph> el(g);
alpar@2235
   505
    
alpar@2235
   506
//     TimeReport t("EdgeLookUp: ");
alpar@2235
   507
//     for(NodeIt u(g);u!=INVALID;++u)
alpar@2235
   508
//       for(NodeIt v(g);v!=INVALID;++v)
alpar@2235
   509
// 	e=el(u,v);
alpar@2235
   510
//   }
alpar@2235
   511
alpar@2235
   512
alpar@2235
   513
  TimeStamp t1 = runningTimeTest(FE(g),1);
alpar@2235
   514
  TimeStamp t2 = runningTimeTest(EL(g),1);
alpar@2235
   515
  TimeStamp t3 = runningTimeTest(EL2(g),1);
alpar@2235
   516
  TimeStamp t4 = runningTimeTest(EL3(g),1);
alpar@2272
   517
//   TimeStamp t5 = runningTimeTest(EL4(g),1);
alpar@2272
   518
//   TimeStamp t6 = runningTimeTest(EL5(g),1);
alpar@2235
   519
alpar@2235
   520
  std::cout << t1.userTime()/N/N << ' ' 
alpar@2235
   521
	    << t2.userTime()/N/N << ' '
alpar@2235
   522
	    << t3.userTime()/N/N << ' '
alpar@2235
   523
	    << t4.userTime()/N/N << ' '
alpar@2272
   524
// 	    << t5.userTime()/N/N << ' '
alpar@2272
   525
//  	    << t6.userTime()/N/N
alpar@2240
   526
	    << std::endl;
alpar@2235
   527
}
alpar@2235
   528