1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
|
#include <igraph.h>
#include "bench.h"
int main() {
igraph_t graph;
igraph_vector_t walk, weights;
igraph_integer_t ec, i;
igraph_rng_seed(igraph_rng_default(), 137);
igraph_vector_init(&walk, 0);
igraph_vector_init(&weights, 0);
/* create a small graph, and a compatible weight vector */
igraph_de_bruijn(&graph, 3, 2); /* 9 vertices, 27 edges, average degree: 6 */
ec = igraph_ecount(&graph);
igraph_vector_resize(&weights, ec);
for (i = 0; i < ec; ++i) {
VECTOR(weights)[i] = igraph_rng_get_unif01(igraph_rng_default());
}
BENCH(" 1 Random edge walk, directed, unweighted, small graph ",
igraph_random_edge_walk(&graph, NULL, &walk, 0, IGRAPH_OUT, 50000000, IGRAPH_RANDOM_WALK_STUCK_RETURN)
);
BENCH(" 2 Random edge walk, directed, weighted, small graph ",
igraph_random_edge_walk(&graph, &weights, &walk, 0, IGRAPH_OUT, 50000000, IGRAPH_RANDOM_WALK_STUCK_RETURN)
);
BENCH(" 3 Random vertex walk, directed, unweighted, small graph ",
igraph_random_walk(&graph, &walk, 0, IGRAPH_OUT, 50000000, IGRAPH_RANDOM_WALK_STUCK_RETURN)
);
igraph_to_undirected(&graph, IGRAPH_TO_UNDIRECTED_EACH, NULL);
BENCH(" 4 Random edge walk, undirected, unweighted, small graph ",
igraph_random_edge_walk(&graph, NULL, &walk, 0, IGRAPH_OUT, 50000000, IGRAPH_RANDOM_WALK_STUCK_RETURN)
);
BENCH(" 5 Random edge walk, undirected, weighted, small graph ",
igraph_random_edge_walk(&graph, &weights, &walk, 0, IGRAPH_OUT, 50000000, IGRAPH_RANDOM_WALK_STUCK_RETURN)
);
BENCH(" 6 Random vertex walk, undirected, unweighted, small graph ",
igraph_random_walk(&graph, &walk, 0, IGRAPH_OUT, 50000000, IGRAPH_RANDOM_WALK_STUCK_RETURN)
);
igraph_destroy(&graph);
/* create a big graph, and a compatible weight vector */
igraph_de_bruijn(&graph, 8, 5); /* 32768 vertices, 262144 edges, average degree: 16 */
ec = igraph_ecount(&graph);
igraph_vector_resize(&weights, ec);
for (i = 0; i < ec; ++i) {
VECTOR(weights)[i] = igraph_rng_get_unif01(igraph_rng_default());
}
BENCH(" 7 Random edge walk, directed, unweighted, large graph ",
igraph_random_edge_walk(&graph, NULL, &walk, 0, IGRAPH_OUT, 50000000, IGRAPH_RANDOM_WALK_STUCK_RETURN)
);
BENCH(" 8 Random edge walk, directed, weighted, large graph ",
igraph_random_edge_walk(&graph, &weights, &walk, 0, IGRAPH_OUT, 50000000, IGRAPH_RANDOM_WALK_STUCK_RETURN)
);
BENCH(" 9 Random vertex walk, directed, unweighted, large graph ",
igraph_random_walk(&graph, &walk, 0, IGRAPH_OUT, 50000000, IGRAPH_RANDOM_WALK_STUCK_RETURN)
);
igraph_to_undirected(&graph, IGRAPH_TO_UNDIRECTED_EACH, NULL);
BENCH("10 Random edge walk, undirected, unweighted, large graph ",
igraph_random_edge_walk(&graph, NULL, &walk, 0, IGRAPH_OUT, 50000000, IGRAPH_RANDOM_WALK_STUCK_RETURN)
);
BENCH("11 Random edge walk, undirected, weighted, large graph ",
igraph_random_edge_walk(&graph, &weights, &walk, 0, IGRAPH_OUT, 50000000, IGRAPH_RANDOM_WALK_STUCK_RETURN)
);
BENCH("12 Random vertex walk, undirected, unweighted, large graph ",
igraph_random_walk(&graph, &walk, 0, IGRAPH_OUT, 50000000, IGRAPH_RANDOM_WALK_STUCK_RETURN)
);
igraph_destroy(&graph);
igraph_vector_destroy(&weights);
igraph_vector_destroy(&walk);
return 0;
}
|
