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