1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/benchmark/graph-bench.cc	Tue Jul 13 07:19:34 2004 +0000
     1.3 @@ -0,0 +1,83 @@
     1.4 +#include<math.h>
     1.5 +#include<hugo/list_graph.h>
     1.6 +#include<hugo/time_measure.h>
     1.7 +#include<iostream>
     1.8 +#include<sage_graph.h>
     1.9 +
    1.10 +using namespace hugo;
    1.11 +
    1.12 +///An experimental typedef factory
    1.13 +#define GRAPH_TYPEDEF_FACTORY(Graph) \
    1.14 +   typedef typename Graph::   Node      Node;\
    1.15 +   typedef typename Graph::   NodeIt    NodeIn;\
    1.16 +   typedef typename Graph::   Edge      Edge;\
    1.17 +   typedef typename Graph::   EdgeIt    EdgeIt;\
    1.18 +   typedef typename Graph:: InEdgeIt  InEdgeIt;\
    1.19 +   typedef typename Graph::OutEdgeIt OutEdgeIt;
    1.20 + 
    1.21 +
    1.22 +///A primitive primtest
    1.23 +bool isPrim(int n)
    1.24 +{
    1.25 +  if(n%2) {
    1.26 +    for(int k=3;n/k>=k;k+=2)
    1.27 +      if(!(n%k)) return false;
    1.28 +    return true;
    1.29 +  }
    1.30 +  return false;
    1.31 +}
    1.32 +
    1.33 +///Finds the smallest prime not less then \c n.
    1.34 +int nextPrim(int n)
    1.35 +{
    1.36 +  for(n+=!(n%2);!isPrim(n);n+=2) ;
    1.37 +  return n;
    1.38 +}
    1.39 +
    1.40 +///Makes a full graph by adding and deleting a lot of edges;
    1.41 +
    1.42 +///\param n Number of nodes.
    1.43 +///\param rat The funcion will make \f$rat\timesn^2\f$ edge addition and
    1.44 +///\f$(rat-1)\timesn^2\f$ deletion.
    1.45 +///\param p Tuning parameters.
    1.46 +///\warning \c rat, \c p, and \c n must be pairwise relative primes. 
    1.47 +template <class Graph>
    1.48 +void makeFullGraph(int n, int rat, int p)
    1.49 +{
    1.50 +  GRAPH_TYPEDEF_FACTORY(Graph);
    1.51 +
    1.52 +  Graph G;
    1.53 +  
    1.54 +  Node nodes[n];
    1.55 +  for(int i=0;i<n;i++) nodes[i]=G.addNode();
    1.56 +  
    1.57 +  Edge equ[rat];
    1.58 +  
    1.59 +  unsigned long long int count;
    1.60 +  
    1.61 +  for(count=0;count<rat;count++) {
    1.62 +    equ[count%rat]=G.addEdge(nodes[(count*p)%n],nodes[(count*p/n)%n]);
    1.63 +  }
    1.64 +  for(;(count%rat)||((count*p)%n)||((count*p/n)%n);count++) {
    1.65 +    //    if(!(count%1000000)) fprintf(stderr,"%d\r",count);
    1.66 +    if(count%rat) G.erase(equ[count%rat]);
    1.67 +    equ[count%rat]=G.addEdge(nodes[(count*p)%n],nodes[(count*p/n)%n]);
    1.68 +  }
    1.69 +  std::cout << "Added " << count
    1.70 +	    << " ( " << n << "^2 * " << rat << " ) edges\n";
    1.71 +  //  for(int i=0;1;i++) ;
    1.72 +}
    1.73 +
    1.74 +int main()
    1.75 +{
    1.76 +  std::cout << "START: n="  << nextPrim(1000) << " rat="
    1.77 +	    << nextPrim(300) << " p=" << nextPrim(100) << '\n';
    1.78 +  hugo::Timer T;
    1.79 +  makeFullGraph<ListGraph>(nextPrim(1000),nextPrim(300),nextPrim(100));
    1.80 +  std::cout << T  << '\n';
    1.81 +  std::cout << "START: n="  << nextPrim(1000) << " rat="
    1.82 +	    << nextPrim(300) << " p=" << nextPrim(100) << '\n';
    1.83 +  T.reset();
    1.84 +  makeFullGraph<ListGraph>(nextPrim(100),nextPrim(30000),nextPrim(150));
    1.85 +  std::cout << T  << '\n';
    1.86 +}