|
1 #include<math.h> |
|
2 #include<hugo/list_graph.h> |
|
3 #include<hugo/time_measure.h> |
|
4 #include<iostream> |
|
5 #include<sage_graph.h> |
|
6 |
|
7 using namespace hugo; |
|
8 |
|
9 ///An experimental typedef factory |
|
10 #define GRAPH_TYPEDEF_FACTORY(Graph) \ |
|
11 typedef typename Graph:: Node Node;\ |
|
12 typedef typename Graph:: NodeIt NodeIn;\ |
|
13 typedef typename Graph:: Edge Edge;\ |
|
14 typedef typename Graph:: EdgeIt EdgeIt;\ |
|
15 typedef typename Graph:: InEdgeIt InEdgeIt;\ |
|
16 typedef typename Graph::OutEdgeIt OutEdgeIt; |
|
17 |
|
18 |
|
19 ///A primitive primtest |
|
20 bool isPrim(int n) |
|
21 { |
|
22 if(n%2) { |
|
23 for(int k=3;n/k>=k;k+=2) |
|
24 if(!(n%k)) return false; |
|
25 return true; |
|
26 } |
|
27 return false; |
|
28 } |
|
29 |
|
30 ///Finds the smallest prime not less then \c n. |
|
31 int nextPrim(int n) |
|
32 { |
|
33 for(n+=!(n%2);!isPrim(n);n+=2) ; |
|
34 return n; |
|
35 } |
|
36 |
|
37 ///Makes a full graph by adding and deleting a lot of edges; |
|
38 |
|
39 ///\param n Number of nodes. |
|
40 ///\param rat The funcion will make \f$rat\timesn^2\f$ edge addition and |
|
41 ///\f$(rat-1)\timesn^2\f$ deletion. |
|
42 ///\param p Tuning parameters. |
|
43 ///\warning \c rat, \c p, and \c n must be pairwise relative primes. |
|
44 template <class Graph> |
|
45 void makeFullGraph(int n, int rat, int p) |
|
46 { |
|
47 GRAPH_TYPEDEF_FACTORY(Graph); |
|
48 |
|
49 Graph G; |
|
50 |
|
51 Node nodes[n]; |
|
52 for(int i=0;i<n;i++) nodes[i]=G.addNode(); |
|
53 |
|
54 Edge equ[rat]; |
|
55 |
|
56 unsigned long long int count; |
|
57 |
|
58 for(count=0;count<rat;count++) { |
|
59 equ[count%rat]=G.addEdge(nodes[(count*p)%n],nodes[(count*p/n)%n]); |
|
60 } |
|
61 for(;(count%rat)||((count*p)%n)||((count*p/n)%n);count++) { |
|
62 // if(!(count%1000000)) fprintf(stderr,"%d\r",count); |
|
63 if(count%rat) G.erase(equ[count%rat]); |
|
64 equ[count%rat]=G.addEdge(nodes[(count*p)%n],nodes[(count*p/n)%n]); |
|
65 } |
|
66 std::cout << "Added " << count |
|
67 << " ( " << n << "^2 * " << rat << " ) edges\n"; |
|
68 // for(int i=0;1;i++) ; |
|
69 } |
|
70 |
|
71 int main() |
|
72 { |
|
73 std::cout << "START: n=" << nextPrim(1000) << " rat=" |
|
74 << nextPrim(300) << " p=" << nextPrim(100) << '\n'; |
|
75 hugo::Timer T; |
|
76 makeFullGraph<ListGraph>(nextPrim(1000),nextPrim(300),nextPrim(100)); |
|
77 std::cout << T << '\n'; |
|
78 std::cout << "START: n=" << nextPrim(1000) << " rat=" |
|
79 << nextPrim(300) << " p=" << nextPrim(100) << '\n'; |
|
80 T.reset(); |
|
81 makeFullGraph<ListGraph>(nextPrim(100),nextPrim(30000),nextPrim(150)); |
|
82 std::cout << T << '\n'; |
|
83 } |