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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
|
#include <stdio.h>
#include <stdbool.h>
#include <time.h>
#include <string.h>
#include <stdlib.h>
#include "graph.h"
graph_t g;
graph_t newg;
int step;
void dfs_visit(graph_t *g, vertex_t *u, bool doprint)
{
if ( doprint ) {
printf("dfs_visit( %s )\n", u->ref);
}
step++;
u->dtime = step;
u->color = COLOR_GRAY;
// For every adj
edge_t *e = u->adj;
while ( e ) {
vertex_t *v = e->to;
if ( v->color == COLOR_WHITE ) {
graph_edge(&newg, v->ref, u->ref, 1);
dfs_visit(g, v, doprint);
}
e = e->next;
}
u->color = COLOR_BLACK;
step++;
u->ftime = step;
}
void dfs(graph_t *g, bool doprint)
{
step = 0;
// For every edge
vertex_t *u = vertex_next(g, NULL);
while ( u ) {
if ( u->color == COLOR_WHITE ) {
dfs_visit(g, u, doprint);
}
u = vertex_next(g, u);
}
}
#define BENCH 9999
int main()
{
// benchmark
// Start by generating
for (int i = 0; i < BENCH; i++) {
char from[5];
char to[5];
sprintf(from, "%d", i);
sprintf(to, "%d", rand() % BENCH);
graph_edge(&g, from, to, 1);
}
FILE *f = fopen("hej.dot", "w");
graph_to_dot(f, &g);
{
// Timing start
clock_t t;
t = clock();
dfs(&g, true);
// Timing stop
t = clock() - t;
double time_taken = ((double)t)/CLOCKS_PER_SEC; // in seconds
printf("Dfs took %f seconds\n", time_taken);
}
return 0;
graph_edge(&g, "hej", "med", 1);
graph_edge(&g, "med", "dig", 1);
graph_edge(&g, "dig", "hvordan", 1);
graph_edge(&g, "det", "hvordan", 1);
graph_edge(&g, "hvordan", "det", 1);
graph_to_dot(stdout, &g);
// Timing start
clock_t t;
t = clock();
// Dfs slower when printing.
dfs(&g, true);
// Timing stop
t = clock() - t;
double time_taken = ((double)t)/CLOCKS_PER_SEC; // in seconds
printf("Dfs took %f seconds\n", time_taken);
//graph_to_dot(stdout, &newg);
return 0;
}
|
