COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/benchmark/graph-bench.cc @ 708:429dfcbbf47d

Last change on this file since 708:429dfcbbf47d was 708:429dfcbbf47d, checked in by Alpar Juttner, 16 years ago

A new benchmark (hcube)
and other minor changes

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