COIN-OR::LEMON - Graph Library

source: lemon-0.x/benchmark/graph-bench.cc @ 2553:bfced05fa852

Last change on this file since 2553:bfced05fa852 was 2553:bfced05fa852, checked in by Alpar Juttner, 12 years ago

Happy New Year to LEMON (+ better update-copyright-header script)

File size: 2.0 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#include<lemon/list_graph.h>
20
21#include"bench_tools.h"
22
23using namespace lemon;
24
25///Makes a full graph by adding and deleting a lot of edges;
26
27///\param n Number of nodes.
28///\param rat The funcion will make \f$rat\timesn^2\f$ edge addition and
29///\f$(rat-1)\timesn^2\f$ deletion.
30///\param p Tuning parameters.
31///\warning \c rat, \c p, and \c n must be pairwise relative primes.
32template <class Graph>
33void makeFullGraph(int n, int rat, int p)
34{
35  GRAPH_TYPEDEFS(typename Graph);
36
37  Graph G;
38 
39  //  Node nodes[n];
40  std::vector<Node> nodes(n);
41  for(int i=0;i<n;i++) nodes[i]=G.addNode();
42 
43  //Edge equ[rat];
44  std::vector<Edge> equ(rat);
45 
46  long long int count;
47 
48  for(count=0;count<rat;count++) {
49    equ[int(count%rat)]=G.addEdge(nodes[int((count*p)%n)],
50                                  nodes[int((count*p/n)%n)]);
51  }
52  for(;(count%rat)||((count*p)%n)||((count*p/n)%n);count++) {
53    //    if(!(count%1000000)) fprintf(stderr,"%d\r",count);
54    if(count%rat) G.erase(equ[count%rat]);
55    equ[int(count%rat)]=G.addEdge(nodes[int((count*p)%n)],
56                                  nodes[int((count*p/n)%n)]);
57  }
58//   std::cout << "Added " << count
59//          << " ( " << n << "^2 * " << rat << " ) edges\n";
60
61
62  //  for(int i=0;1;i++) ;
63}
64
65int main()
66{
67  lemon::Timer T;
68  makeFullGraph<ListGraph>(nextPrim(1000),nextPrim(300),nextPrim(100));
69 
70  PrintTime("BIG",T);
71  T.restart();
72  makeFullGraph<ListGraph>(nextPrim(100),nextPrim(30000),nextPrim(150));
73
74  PrintTime("SMALL",T);
75}
Note: See TracBrowser for help on using the repository browser.