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