forked from scottblechman/cs-4379-001-04
-
Notifications
You must be signed in to change notification settings - Fork 0
/
graph.c
100 lines (95 loc) · 2.38 KB
/
graph.c
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
int minimum(int* nums, int n) {
int min = nums[0], i;
for (i = 0; i < n; i++) {
if (nums[i] < min) {
min = nums[i];
}
}
return min;
}
int min(int a, int b) {
return (a<b) ? a : b;
}
void graphsynth(int *edge, int n, time_t seed, int maxweight, int edgeodds) {
srand(seed);
int i, j;
for (i = 0; i < n; i++) {
edge[n*i+i] = 0; // assume no edges contain one node
for (j = 1; j < i; j++) {
int exist = rand() % edgeodds + 1;
int weight = rand() % maxweight + 1;
if ( exist > 1 ) {
edge[n*i+j] = 0;
edge[n*j+i] = 0;
} else if (j != i) {
edge[n*i+j] = weight;
edge[n*j+i] = weight;
}
}
}
// check that all nodes are connected at least once
for (i = 0; i < n; i++) {
int connected = 0;
for (j = 0; (j < i) && (connected == 0); j++) {
if (edge[n*i+j] > connected) {
connected = edge[n*i+j];
}
}
if (connected == 0) {
// edge[i][random not i] = random
j = i;
while (j == i ) {
j = rand()%n;
}
int weight = rand() % maxweight + 1;
edge[n*i+j] = weight;
edge[n*j+i] = weight;
}
}
}
void matrixsynth(int *edge, int n, time_t seed, int maxweight) {
srand(seed);
int i;
for (i = 0; i < n*n; i++) {
int weight = rand() % maxweight + 1;
edge[i] = weight;
}
}
void printgraph(int *edge, int n) {
int i;
#ifdef DEBUG
for (i = 0; i < n; i++) {
fprintf(stderr,"\t%d",i);
}
fprintf(stderr,"\n_");
for (i = 0; i < n; i++) {
fprintf(stderr,"________",i);
}
fprintf(stderr,"\n");
for (i = 0; i < n; i++) {
fprintf(stderr,"%d|\t",i);
int j;
for (j = 0; j < n; j++) {
fprintf(stderr,"%d\t",edge[n*i+j]);
}
fprintf(stderr,"\n");
}
#else
for (i = 0; i < n; i++) {
printf("\t%d",i);
}
printf("\n_");
for (i = 0; i < n; i++) {
fprintf(stderr,"________",i);
}
printf("\n");
for (i = 0; i < n; i++) {
printf("%d|\t",i);
int j;
for (j = 0; j < n; j++) {
printf("%d\t",edge[n*i+j]);
}
printf("\n");
}
#endif
}