benchmark/graph-bench.cc
author hegyi
Wed, 04 Jan 2006 18:05:55 +0000
changeset 1876 5ad84ad1b68f
parent 1847 7cbc12e42482
child 1956 a055123339d5
permissions -rw-r--r--
Communication with algorithm window is developed.
     1 #include<lemon/list_graph.h>
     2 
     3 #include"bench_tools.h"
     4 
     5 using namespace lemon;
     6 
     7 ///Makes a full graph by adding and deleting a lot of edges;
     8 
     9 ///\param n Number of nodes.
    10 ///\param rat The funcion will make \f$rat\timesn^2\f$ edge addition and
    11 ///\f$(rat-1)\timesn^2\f$ deletion.
    12 ///\param p Tuning parameters.
    13 ///\warning \c rat, \c p, and \c n must be pairwise relative primes. 
    14 template <class Graph>
    15 void makeFullGraph(int n, int rat, int p)
    16 {
    17   GRAPH_TYPEDEFS(typename Graph);
    18 
    19   Graph G;
    20   
    21   //  Node nodes[n];
    22   std::vector<Node> nodes(n);
    23   for(int i=0;i<n;i++) nodes[i]=G.addNode();
    24   
    25   //Edge equ[rat];
    26   std::vector<Edge> equ(rat);
    27   
    28   long long int count;
    29   
    30   for(count=0;count<rat;count++) {
    31     equ[int(count%rat)]=G.addEdge(nodes[int((count*p)%n)],
    32 				  nodes[int((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[int(count%rat)]=G.addEdge(nodes[int((count*p)%n)],
    38 				  nodes[int((count*p/n)%n)]);
    39   }
    40 //   std::cout << "Added " << count
    41 // 	    << " ( " << n << "^2 * " << rat << " ) edges\n";
    42 
    43 
    44   //  for(int i=0;1;i++) ;
    45 }
    46 
    47 int main()
    48 {
    49   lemon::Timer T;
    50   makeFullGraph<ListGraph>(nextPrim(1000),nextPrim(300),nextPrim(100));
    51   
    52   PrintTime("BIG",T);
    53   T.restart();
    54   makeFullGraph<ListGraph>(nextPrim(100),nextPrim(30000),nextPrim(150));
    55 
    56   PrintTime("SMALL",T);
    57 }