# source:lemon-0.x/src/benchmark/graph-bench.cc@700:236117f60eee

Last change on this file since 700:236117f60eee was 699:59f8d173968e, checked in by Alpar Juttner, 20 years ago

Benchmarks

File size: 2.2 KB
Line
1#include<math.h>
2#include<hugo/list_graph.h>
3#include<hugo/time_measure.h>
4#include<iostream>
5#include<sage_graph.h>
6
7using namespace hugo;
8
9///An experimental typedef factory
10#define GRAPH_TYPEDEF_FACTORY(Graph) \
11   typedef typename Graph::   Node      Node;\
12   typedef typename Graph::   NodeIt    NodeIn;\
13   typedef typename Graph::   Edge      Edge;\
14   typedef typename Graph::   EdgeIt    EdgeIt;\
15   typedef typename Graph:: InEdgeIt  InEdgeIt;\
16   typedef typename Graph::OutEdgeIt OutEdgeIt;
17
18
19///A primitive primtest
20bool isPrim(int n)
21{
22  if(n%2) {
23    for(int k=3;n/k>=k;k+=2)
24      if(!(n%k)) return false;
25    return true;
26  }
27  return false;
28}
29
30///Finds the smallest prime not less then \c n.
31int nextPrim(int n)
32{
33  for(n+=!(n%2);!isPrim(n);n+=2) ;
34  return n;
35}
36
37///Makes a full graph by adding and deleting a lot of edges;
38
39///\param n Number of nodes.
40///\param rat The funcion will make \f\$rat\timesn^2\f\$ edge addition and
41///\f\$(rat-1)\timesn^2\f\$ deletion.
42///\param p Tuning parameters.
43///\warning \c rat, \c p, and \c n must be pairwise relative primes.
44template <class Graph>
45void makeFullGraph(int n, int rat, int p)
46{
47  GRAPH_TYPEDEF_FACTORY(Graph);
48
49  Graph G;
50
51  Node nodes[n];
52  for(int i=0;i<n;i++) nodes[i]=G.addNode();
53
54  Edge equ[rat];
55
56  unsigned long long int count;
57
58  for(count=0;count<rat;count++) {
59    equ[count%rat]=G.addEdge(nodes[(count*p)%n],nodes[(count*p/n)%n]);
60  }
61  for(;(count%rat)||((count*p)%n)||((count*p/n)%n);count++) {
62    //    if(!(count%1000000)) fprintf(stderr,"%d\r",count);
63    if(count%rat) G.erase(equ[count%rat]);
64    equ[count%rat]=G.addEdge(nodes[(count*p)%n],nodes[(count*p/n)%n]);
65  }
66  std::cout << "Added " << count
67            << " ( " << n << "^2 * " << rat << " ) edges\n";
68  //  for(int i=0;1;i++) ;
69}
70
71int main()
72{
73  std::cout << "START: n="  << nextPrim(1000) << " rat="
74            << nextPrim(300) << " p=" << nextPrim(100) << '\n';
75  hugo::Timer T;
76  makeFullGraph<ListGraph>(nextPrim(1000),nextPrim(300),nextPrim(100));
77  std::cout << T  << '\n';
78  std::cout << "START: n="  << nextPrim(1000) << " rat="
79            << nextPrim(300) << " p=" << nextPrim(100) << '\n';
80  T.reset();
81  makeFullGraph<ListGraph>(nextPrim(100),nextPrim(30000),nextPrim(150));
82  std::cout << T  << '\n';
83}
Note: See TracBrowser for help on using the repository browser.