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