COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/benchmark/graph-bench.cc @ 930:e89f3bd26fd4

Last change on this file since 930:e89f3bd26fd4 was 921:818510fa3d99, checked in by Alpar Juttner, 20 years ago

hugo -> lemon

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