COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/benchmark/graph-bench.cc @ 717:6874df3f61db

Last change on this file since 717:6874df3f61db was 711:b6c56353832c, checked in by Alpar Juttner, 20 years ago

Some tools of common usage was put to bench_tool.h

File size: 1.6 KB
Line 
1#include<math.h>
2#include<hugo/list_graph.h>
3#include<hugo/time_measure.h>
4#include<iostream>
5
6#include"bench_tools.h"
7
8using namespace hugo;
9
10///Makes a full graph by adding and deleting a lot of edges;
11
12///\param n Number of nodes.
13///\param rat The funcion will make \f$rat\timesn^2\f$ edge addition and
14///\f$(rat-1)\timesn^2\f$ deletion.
15///\param p Tuning parameters.
16///\warning \c rat, \c p, and \c n must be pairwise relative primes.
17template <class Graph>
18void makeFullGraph(int n, int rat, int p)
19{
20  GRAPH_TYPEDEF_FACTORY(Graph);
21
22  Graph G;
23 
24  //  Node nodes[n];
25  std::vector<Node> nodes(n);
26  for(int i=0;i<n;i++) nodes[i]=G.addNode();
27 
28  //Edge equ[rat];
29  std::vector<Edge> equ(rat);
30 
31  unsigned long long int count;
32 
33  for(count=0;count<rat;count++) {
34    equ[count%rat]=G.addEdge(nodes[(count*p)%n],nodes[(count*p/n)%n]);
35  }
36  for(;(count%rat)||((count*p)%n)||((count*p/n)%n);count++) {
37    //    if(!(count%1000000)) fprintf(stderr,"%d\r",count);
38    if(count%rat) G.erase(equ[count%rat]);
39    equ[count%rat]=G.addEdge(nodes[(count*p)%n],nodes[(count*p/n)%n]);
40  }
41  std::cout << "Added " << count
42            << " ( " << n << "^2 * " << rat << " ) edges\n";
43  //  for(int i=0;1;i++) ;
44}
45
46int main()
47{
48  std::cout << "START: n="  << nextPrim(1000) << " rat="
49            << nextPrim(300) << " p=" << nextPrim(100) << '\n';
50  hugo::Timer T;
51  makeFullGraph<ListGraph>(nextPrim(1000),nextPrim(300),nextPrim(100));
52  std::cout << T  << '\n';
53  std::cout << "START: n="  << nextPrim(1000) << " rat="
54            << nextPrim(300) << " p=" << nextPrim(100) << '\n';
55  T.reset();
56  makeFullGraph<ListGraph>(nextPrim(100),nextPrim(30000),nextPrim(150));
57  std::cout << T  << '\n';
58}
Note: See TracBrowser for help on using the repository browser.