#include<math.h>

 #include<hugo/list_graph.h>

 #include<hugo/time_measure.h>

 #include<iostream>

 #include<sage_graph.h>

 using namespace hugo;

 ///An experimental typedef factory

 #define GRAPH_TYPEDEF_FACTORY(Graph) \

    typedef typename Graph::   Node      Node;\

    typedef typename Graph::   NodeIt    NodeIn;\

    typedef typename Graph::   Edge      Edge;\

    typedef typename Graph::   EdgeIt    EdgeIt;\

    typedef typename Graph:: InEdgeIt  InEdgeIt;\

    typedef typename Graph::OutEdgeIt OutEdgeIt;

 ///A primitive primtest

 bool isPrim(int n)

 {

   if(n%2) {

     for(int k=3;n/k>=k;k+=2)

       if(!(n%k)) return false;

     return true;

   }

   return false;

 }

 ///Finds the smallest prime not less then \c n.

 int nextPrim(int n)

 {

   for(n+=!(n%2);!isPrim(n);n+=2) ;

   return n;

 }

 ///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_TYPEDEF_FACTORY(Graph);

   Graph G;

   Node nodes[n];

   for(int i=0;i<n;i++) nodes[i]=G.addNode();

   Edge equ[rat];

   unsigned long long int count;

   for(count=0;count<rat;count++) {

     equ[count%rat]=G.addEdge(nodes[(count*p)%n],nodes[(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[count%rat]=G.addEdge(nodes[(count*p)%n],nodes[(count*p/n)%n]);

   }

   std::cout << "Added " << count

 	    << " ( " << n << "^2 * " << rat << " ) edges\n";

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

 }

 int main()

 {

   std::cout << "START: n="  << nextPrim(1000) << " rat="

 	    << nextPrim(300) << " p=" << nextPrim(100) << '\n';

   hugo::Timer T;

   makeFullGraph<ListGraph>(nextPrim(1000),nextPrim(300),nextPrim(100));

   std::cout << T  << '\n';

   std::cout << "START: n="  << nextPrim(1000) << " rat="

 	    << nextPrim(300) << " p=" << nextPrim(100) << '\n';

   T.reset();

   makeFullGraph<ListGraph>(nextPrim(100),nextPrim(30000),nextPrim(150));

   std::cout << T  << '\n';

 }