alpar@1956: /* -*- C++ -*-
alpar@1956:  *
alpar@1956:  * This file is a part of LEMON, a generic C++ optimization library
alpar@1956:  *
alpar@1956:  * Copyright (C) 2003-2006
alpar@1956:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@1956:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@1956:  *
alpar@1956:  * Permission to use, modify and distribute this software is granted
alpar@1956:  * provided that this copyright notice appears in all copies. For
alpar@1956:  * precise terms see the accompanying LICENSE file.
alpar@1956:  *
alpar@1956:  * This software is provided "AS IS" with no warranty of any kind,
alpar@1956:  * express or implied, and with no claim as to its suitability for any
alpar@1956:  * purpose.
alpar@1956:  *
alpar@1956:  */
alpar@1956: 
alpar@921: #include<lemon/list_graph.h>
alpar@711: 
alpar@711: #include"bench_tools.h"
alpar@699: 
alpar@921: using namespace lemon;
alpar@699: 
alpar@699: ///Makes a full graph by adding and deleting a lot of edges;
alpar@699: 
alpar@699: ///\param n Number of nodes.
alpar@699: ///\param rat The funcion will make \f$rat\timesn^2\f$ edge addition and
alpar@699: ///\f$(rat-1)\timesn^2\f$ deletion.
alpar@699: ///\param p Tuning parameters.
alpar@699: ///\warning \c rat, \c p, and \c n must be pairwise relative primes. 
alpar@699: template <class Graph>
alpar@699: void makeFullGraph(int n, int rat, int p)
alpar@699: {
alpar@1756:   GRAPH_TYPEDEFS(typename Graph);
alpar@699: 
alpar@699:   Graph G;
alpar@699:   
alpar@708:   //  Node nodes[n];
alpar@708:   std::vector<Node> nodes(n);
alpar@699:   for(int i=0;i<n;i++) nodes[i]=G.addNode();
alpar@699:   
alpar@708:   //Edge equ[rat];
alpar@708:   std::vector<Edge> equ(rat);
alpar@699:   
alpar@718:   long long int count;
alpar@699:   
alpar@699:   for(count=0;count<rat;count++) {
alpar@1855:     equ[int(count%rat)]=G.addEdge(nodes[int((count*p)%n)],
alpar@1855: 				  nodes[int((count*p/n)%n)]);
alpar@699:   }
alpar@699:   for(;(count%rat)||((count*p)%n)||((count*p/n)%n);count++) {
alpar@699:     //    if(!(count%1000000)) fprintf(stderr,"%d\r",count);
alpar@699:     if(count%rat) G.erase(equ[count%rat]);
alpar@1855:     equ[int(count%rat)]=G.addEdge(nodes[int((count*p)%n)],
alpar@1855: 				  nodes[int((count*p/n)%n)]);
alpar@699:   }
alpar@718: //   std::cout << "Added " << count
alpar@718: // 	    << " ( " << n << "^2 * " << rat << " ) edges\n";
alpar@718: 
alpar@718: 
alpar@699:   //  for(int i=0;1;i++) ;
alpar@699: }
alpar@699: 
alpar@699: int main()
alpar@699: {
alpar@921:   lemon::Timer T;
alpar@699:   makeFullGraph<ListGraph>(nextPrim(1000),nextPrim(300),nextPrim(100));
alpar@718:   
alpar@718:   PrintTime("BIG",T);
alpar@1847:   T.restart();
alpar@699:   makeFullGraph<ListGraph>(nextPrim(100),nextPrim(30000),nextPrim(150));
alpar@718: 
alpar@718:   PrintTime("SMALL",T);
alpar@699: }