alpar@699: #include<math.h>
alpar@699: #include<hugo/list_graph.h>
alpar@699: #include<hugo/time_measure.h>
alpar@699: #include<iostream>
alpar@699: #include<sage_graph.h>
alpar@708: #include<vector>
alpar@699: 
alpar@699: using namespace hugo;
alpar@699: 
alpar@699: ///An experimental typedef factory
alpar@699: #define GRAPH_TYPEDEF_FACTORY(Graph) \
alpar@699:    typedef typename Graph::   Node      Node;\
alpar@699:    typedef typename Graph::   NodeIt    NodeIn;\
alpar@699:    typedef typename Graph::   Edge      Edge;\
alpar@699:    typedef typename Graph::   EdgeIt    EdgeIt;\
alpar@699:    typedef typename Graph:: InEdgeIt  InEdgeIt;\
alpar@699:    typedef typename Graph::OutEdgeIt OutEdgeIt;
alpar@699:  
alpar@699: 
alpar@699: ///A primitive primtest
alpar@699: bool isPrim(int n)
alpar@699: {
alpar@699:   if(n%2) {
alpar@699:     for(int k=3;n/k>=k;k+=2)
alpar@699:       if(!(n%k)) return false;
alpar@699:     return true;
alpar@699:   }
alpar@699:   return false;
alpar@699: }
alpar@699: 
alpar@699: ///Finds the smallest prime not less then \c n.
alpar@699: int nextPrim(int n)
alpar@699: {
alpar@699:   for(n+=!(n%2);!isPrim(n);n+=2) ;
alpar@699:   return n;
alpar@699: }
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@699:   GRAPH_TYPEDEF_FACTORY(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@699:   unsigned long long int count;
alpar@699:   
alpar@699:   for(count=0;count<rat;count++) {
alpar@699:     equ[count%rat]=G.addEdge(nodes[(count*p)%n],nodes[(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@699:     equ[count%rat]=G.addEdge(nodes[(count*p)%n],nodes[(count*p/n)%n]);
alpar@699:   }
alpar@699:   std::cout << "Added " << count
alpar@699: 	    << " ( " << n << "^2 * " << rat << " ) edges\n";
alpar@699:   //  for(int i=0;1;i++) ;
alpar@699: }
alpar@699: 
alpar@699: int main()
alpar@699: {
alpar@699:   std::cout << "START: n="  << nextPrim(1000) << " rat="
alpar@699: 	    << nextPrim(300) << " p=" << nextPrim(100) << '\n';
alpar@699:   hugo::Timer T;
alpar@699:   makeFullGraph<ListGraph>(nextPrim(1000),nextPrim(300),nextPrim(100));
alpar@699:   std::cout << T  << '\n';
alpar@699:   std::cout << "START: n="  << nextPrim(1000) << " rat="
alpar@699: 	    << nextPrim(300) << " p=" << nextPrim(100) << '\n';
alpar@699:   T.reset();
alpar@699:   makeFullGraph<ListGraph>(nextPrim(100),nextPrim(30000),nextPrim(150));
alpar@699:   std::cout << T  << '\n';
alpar@699: }