2 #include<hugo/list_graph.h>
3 #include<hugo/time_measure.h>
10 ///An experimental typedef factory
11 #define GRAPH_TYPEDEF_FACTORY(Graph) \
12 typedef typename Graph:: Node Node;\
13 typedef typename Graph:: NodeIt NodeIn;\
14 typedef typename Graph:: Edge Edge;\
15 typedef typename Graph:: EdgeIt EdgeIt;\
16 typedef typename Graph:: InEdgeIt InEdgeIt;\
17 typedef typename Graph::OutEdgeIt OutEdgeIt;
20 ///A primitive primtest
24 for(int k=3;n/k>=k;k+=2)
25 if(!(n%k)) return false;
31 ///Finds the smallest prime not less then \c n.
34 for(n+=!(n%2);!isPrim(n);n+=2) ;
38 ///Makes a full graph by adding and deleting a lot of edges;
40 ///\param n Number of nodes.
41 ///\param rat The funcion will make \f$rat\timesn^2\f$ edge addition and
42 ///\f$(rat-1)\timesn^2\f$ deletion.
43 ///\param p Tuning parameters.
44 ///\warning \c rat, \c p, and \c n must be pairwise relative primes.
45 template <class Graph>
46 void makeFullGraph(int n, int rat, int p)
48 GRAPH_TYPEDEF_FACTORY(Graph);
53 std::vector<Node> nodes(n);
54 for(int i=0;i<n;i++) nodes[i]=G.addNode();
57 std::vector<Edge> equ(rat);
59 unsigned long long int count;
61 for(count=0;count<rat;count++) {
62 equ[count%rat]=G.addEdge(nodes[(count*p)%n],nodes[(count*p/n)%n]);
64 for(;(count%rat)||((count*p)%n)||((count*p/n)%n);count++) {
65 // if(!(count%1000000)) fprintf(stderr,"%d\r",count);
66 if(count%rat) G.erase(equ[count%rat]);
67 equ[count%rat]=G.addEdge(nodes[(count*p)%n],nodes[(count*p/n)%n]);
69 std::cout << "Added " << count
70 << " ( " << n << "^2 * " << rat << " ) edges\n";
71 // for(int i=0;1;i++) ;
76 std::cout << "START: n=" << nextPrim(1000) << " rat="
77 << nextPrim(300) << " p=" << nextPrim(100) << '\n';
79 makeFullGraph<ListGraph>(nextPrim(1000),nextPrim(300),nextPrim(100));
80 std::cout << T << '\n';
81 std::cout << "START: n=" << nextPrim(1000) << " rat="
82 << nextPrim(300) << " p=" << nextPrim(100) << '\n';
84 makeFullGraph<ListGraph>(nextPrim(100),nextPrim(30000),nextPrim(150));
85 std::cout << T << '\n';