source: lemon-0.x/benchmark/graph-bench.cc @ 2627:197e2ea11bad

/* -*- C++ -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2003-2008
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * This software is provided "AS IS" with no warranty of any kind,
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */

#include<lemon/list_graph.h>

#include"bench_tools.h"

using namespace lemon;

///Makes a full graph by adding and deleting a lot of edges;

///\param n Number of nodes.
///\param rat The funcion will make \f$rat\timesn^2\f$ edge addition and
///\f$(rat-1)\timesn^2\f$ deletion.
///\param p Tuning parameters.
///\warning \c rat, \c p, and \c n must be pairwise relative primes. 
template <class Graph>
void makeFullGraph(int n, int rat, int p)
{
  GRAPH_TYPEDEFS(typename Graph);

  Graph G;
  
  //  Node nodes[n];
  std::vector<Node> nodes(n);
  for(int i=0;i<n;i++) nodes[i]=G.addNode();
  
  //Edge equ[rat];
  std::vector<Edge> equ(rat);
  
  /// \bug There is no long long int type in C++98.
  long long int count;
  
  for(count=0;count<rat;count++) {
    equ[int(count%rat)]=G.addEdge(nodes[int((count*p)%n)],
                                  nodes[int((count*p/n)%n)]);
  }
  for(;(count%rat)||((count*p)%n)||((count*p/n)%n);count++) {
    //    if(!(count%1000000)) fprintf(stderr,"%d\r",count);
    if(count%rat) G.erase(equ[count%rat]);
    equ[int(count%rat)]=G.addEdge(nodes[int((count*p)%n)],
                                  nodes[int((count*p/n)%n)]);
  }
//   std::cout << "Added " << count
//          << " ( " << n << "^2 * " << rat << " ) edges\n";


  //  for(int i=0;1;i++) ;
}

int main()
{
  lemon::Timer T;
  makeFullGraph<ListGraph>(nextPrim(1000),nextPrim(300),nextPrim(100));
  
  PrintTime("BIG",T);
  T.restart();
  makeFullGraph<ListGraph>(nextPrim(100),nextPrim(30000),nextPrim(150));

  PrintTime("SMALL",T);
}