benchmark/graph-bench.cc
author ladanyi
Sat, 17 Dec 2005 21:51:10 +0000
changeset 1861 5f204c7a1318
parent 1847 7cbc12e42482
child 1956 a055123339d5
permissions -rw-r--r--
Distribute xml.h too.
alpar@921
     1
#include<lemon/list_graph.h>
alpar@711
     2
alpar@711
     3
#include"bench_tools.h"
alpar@699
     4
alpar@921
     5
using namespace lemon;
alpar@699
     6
alpar@699
     7
///Makes a full graph by adding and deleting a lot of edges;
alpar@699
     8
alpar@699
     9
///\param n Number of nodes.
alpar@699
    10
///\param rat The funcion will make \f$rat\timesn^2\f$ edge addition and
alpar@699
    11
///\f$(rat-1)\timesn^2\f$ deletion.
alpar@699
    12
///\param p Tuning parameters.
alpar@699
    13
///\warning \c rat, \c p, and \c n must be pairwise relative primes. 
alpar@699
    14
template <class Graph>
alpar@699
    15
void makeFullGraph(int n, int rat, int p)
alpar@699
    16
{
alpar@1756
    17
  GRAPH_TYPEDEFS(typename Graph);
alpar@699
    18
alpar@699
    19
  Graph G;
alpar@699
    20
  
alpar@708
    21
  //  Node nodes[n];
alpar@708
    22
  std::vector<Node> nodes(n);
alpar@699
    23
  for(int i=0;i<n;i++) nodes[i]=G.addNode();
alpar@699
    24
  
alpar@708
    25
  //Edge equ[rat];
alpar@708
    26
  std::vector<Edge> equ(rat);
alpar@699
    27
  
alpar@718
    28
  long long int count;
alpar@699
    29
  
alpar@699
    30
  for(count=0;count<rat;count++) {
alpar@1855
    31
    equ[int(count%rat)]=G.addEdge(nodes[int((count*p)%n)],
alpar@1855
    32
				  nodes[int((count*p/n)%n)]);
alpar@699
    33
  }
alpar@699
    34
  for(;(count%rat)||((count*p)%n)||((count*p/n)%n);count++) {
alpar@699
    35
    //    if(!(count%1000000)) fprintf(stderr,"%d\r",count);
alpar@699
    36
    if(count%rat) G.erase(equ[count%rat]);
alpar@1855
    37
    equ[int(count%rat)]=G.addEdge(nodes[int((count*p)%n)],
alpar@1855
    38
				  nodes[int((count*p/n)%n)]);
alpar@699
    39
  }
alpar@718
    40
//   std::cout << "Added " << count
alpar@718
    41
// 	    << " ( " << n << "^2 * " << rat << " ) edges\n";
alpar@718
    42
alpar@718
    43
alpar@699
    44
  //  for(int i=0;1;i++) ;
alpar@699
    45
}
alpar@699
    46
alpar@699
    47
int main()
alpar@699
    48
{
alpar@921
    49
  lemon::Timer T;
alpar@699
    50
  makeFullGraph<ListGraph>(nextPrim(1000),nextPrim(300),nextPrim(100));
alpar@718
    51
  
alpar@718
    52
  PrintTime("BIG",T);
alpar@1847
    53
  T.restart();
alpar@699
    54
  makeFullGraph<ListGraph>(nextPrim(100),nextPrim(30000),nextPrim(150));
alpar@718
    55
alpar@718
    56
  PrintTime("SMALL",T);
alpar@699
    57
}