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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
|
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include "graph.h"
// Hashtable
static unsigned int hash(char *s)
{
uint32_t hv = 0;
for (int i = 0; s[i] != '\0'; i++) {
// take MSB 6 bits of hv and xors with LSB of s[i]
uint32_t v = (hv >> 26) ^ (s[i] & 0x3f);
// Push those back on hv
hv = (hv << 4) | v;
}
// Return appropriate size
return hv % HASHSIZE;
}
static void table_insert(graph_t *g, vertex_t *v, char *var)
{
unsigned int index = hash(var);
// Save old value
vertex_t *oldSym = g->hashtable[index];
// Make new
g->hashtable[index] = v;
// Link old one
g->hashtable[index]->next = oldSym;
}
static vertex_t *table_lookup(graph_t *g, char *var)
{
unsigned int index = hash(var);
vertex_t *n = g->hashtable[index];
// Look trough list
while (n != NULL && strcmp(n->ref, var) != 0) {
n = n->next;
}
return n;
}
static vertex_t *create_vertex(char *ref)
{
// Get some space TODO check for null
vertex_t *v = malloc(sizeof(vertex_t));
// Set values
v->ref = strdup(ref);
v->color = COLOR_WHITE;
v->p = NULL;
v->dist = -1;
v->adj = NULL;
return v;
}
static edge_t *create_edge(vertex_t *from, vertex_t *to, int weight)
{
edge_t *old = from->adj;
// Create new list node
edge_t *e = malloc(sizeof(edge_t));
e->weight = weight;
e->from = from;
e->to = to;
// Do new link
e->next = old;
if (old) {
e->prev = old->prev;
old->prev = e;
} else {
e->prev = NULL;
}
if (e->prev) {
e->prev->next = e;
}
from->adj = e;
return e;
}
// For iterating edges
edge_t *edge_next(graph_t *g, edge_t *e)
{
if (e == NULL || e->next == NULL) {
// Find next index
vertex_t *v = e ? e->from : NULL;
// Find next vertex
v = vertex_next(g, v);
while (v) {
// Check if found
if (v->adj) {
return v->adj;
}
v = vertex_next(g, v);
}
// No next vertex
return NULL;
}
// Not finished with this adj list
return e->next;
}
vertex_t *vertex_next(graph_t *g, vertex_t *v)
{
if (v == NULL || v->next == NULL) {
// Go to next index in hashtable
int i = v ? hash(v->ref) + 1 : 0;
for (; i < HASHSIZE; i++) {
if (g->hashtable[i]) {
return g->hashtable[i];
}
}
// No next
return NULL;
}
return v->next;
}
void graph_edge(graph_t *g, char *from, char *to, int weight)
{
vertex_t *fromv, *tov;
// Does a exists
if ((fromv = table_lookup(g, from)) == NULL) {
fromv = create_vertex(from);
table_insert(g, fromv, from);
}
// What about b
if ((tov = table_lookup(g, to)) == NULL) {
tov = create_vertex(to);
table_insert(g, tov, to);
}
// Add edge
create_edge(fromv, tov, weight);
}
int graph_print_adj(graph_t *g, char *ref)
{
vertex_t *v = table_lookup(g, ref);
if (v == NULL) {
return 1;
}
edge_t *e = v->adj;
printf("[ ");
while (e && e->from->ref == ref) {
printf("%s[%d] ", e->to->ref, e->weight);
e = e->next;
}
printf("]\n");
return 0;
}
int graph_to_dot(FILE *f, graph_t *g)
{
// print pre stuff
fprintf(f, "digraph coolgraph {\n");
// Label all nodes
vertex_t *v = vertex_next(g, NULL);
while (v) {
fprintf(f, "%s [label=\"%s(%d)\"];\n", v->ref, v->ref, v->dist);
v = vertex_next(g, v);
}
// Print all the edges
edge_t *e = edge_next(g, NULL);
while (e) {
fprintf(f, "%s -> %s [label = %d%s];\n", e->from->ref, e->to->ref,
e->weight, e->to->p == e->from ? " color=blue" : "");
e = edge_next(g, e);
}
// done
fprintf(f, "}\n");
}
// This was created in a hurry sorry
int graph_from_dot(FILE *f, graph_t *g)
{
char from[100], to[100];
int weight;
int count = 0;
// just fscanf it
for (;;) {
// Set first to zero
*from = 0;
*to = 0;
weight = 0;
int c = fscanf(f, "%s -> %s [label=%d];", from, to, &weight);
if (c <= 0) {
break;
}
if (*from == 0 || *to == 0) {
continue;
}
// Sorry i just want it to work
int tolen = strlen(to);
if (to[tolen - 1] == ';') {
to[tolen - 1] = 0;
}
weight = weight ? weight : 1;
//printf("Creating edge from %s to %s with w: %d\n", from, to, weight);
graph_edge(g, from, to, weight);
count++;
}
return count;
}
vertex_t *graph_vertex(graph_t *g, char *ref)
{
return table_lookup(g, ref);
}
|
