1 #include<lemon/list_graph.h> |
|
2 |
|
3 #include"bench_tools.h" |
|
4 |
|
5 using namespace lemon; |
|
6 |
|
7 ///Makes a full graph by adding and deleting a lot of edges; |
|
8 |
|
9 ///\param n Number of nodes. |
|
10 ///\param rat The funcion will make \f$rat\timesn^2\f$ edge addition and |
|
11 ///\f$(rat-1)\timesn^2\f$ deletion. |
|
12 ///\param p Tuning parameters. |
|
13 ///\warning \c rat, \c p, and \c n must be pairwise relative primes. |
|
14 template <class Graph> |
|
15 void makeFullGraph(int n, int rat, int p) |
|
16 { |
|
17 GRAPH_TYPEDEF_FACTORY(Graph); |
|
18 |
|
19 Graph G; |
|
20 |
|
21 // Node nodes[n]; |
|
22 std::vector<Node> nodes(n); |
|
23 for(int i=0;i<n;i++) nodes[i]=G.addNode(); |
|
24 |
|
25 //Edge equ[rat]; |
|
26 std::vector<Edge> equ(rat); |
|
27 |
|
28 long long int count; |
|
29 |
|
30 for(count=0;count<rat;count++) { |
|
31 equ[count%rat]=G.addEdge(nodes[(count*p)%n],nodes[(count*p/n)%n]); |
|
32 } |
|
33 for(;(count%rat)||((count*p)%n)||((count*p/n)%n);count++) { |
|
34 // if(!(count%1000000)) fprintf(stderr,"%d\r",count); |
|
35 if(count%rat) G.erase(equ[count%rat]); |
|
36 equ[count%rat]=G.addEdge(nodes[(count*p)%n],nodes[(count*p/n)%n]); |
|
37 } |
|
38 // std::cout << "Added " << count |
|
39 // << " ( " << n << "^2 * " << rat << " ) edges\n"; |
|
40 |
|
41 |
|
42 // for(int i=0;1;i++) ; |
|
43 } |
|
44 |
|
45 int main() |
|
46 { |
|
47 lemon::Timer T; |
|
48 makeFullGraph<ListGraph>(nextPrim(1000),nextPrim(300),nextPrim(100)); |
|
49 |
|
50 PrintTime("BIG",T); |
|
51 T.reset(); |
|
52 makeFullGraph<ListGraph>(nextPrim(100),nextPrim(30000),nextPrim(150)); |
|
53 |
|
54 PrintTime("SMALL",T); |
|
55 } |
|