/* -*- C++ -*-

  *

  * This file is a part of LEMON, a generic C++ optimization library

  *

  * Copyright (C) 2003-2006

  * 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);

   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);

 }