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
|
#include <stdio.h>
#include <stdlib.h>
#include "graph.h"
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 = ref;
v->dist = -1;
v->p = NULL;
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
// Chose starting index 0 if NULL e
unsigned char i = e ? e->from->ref + 1 : 0;
for (; i < 128; i++) {
if (g->vertexes[i] && g->vertexes[i]->adj) {
return g->vertexes[i]->adj;
}
}
// No next vertex
return NULL;
}
// Not finished with this adj list
return e->next;
}
vertex_t *vertex_next(graph_t *g, vertex_t *v)
{
unsigned char ref = v ? v->ref + 1 : 0;
for (; ref < 128; ref++) {
if (g->vertexes[ref]) {
return g->vertexes[ref];
}
}
return NULL;
}
void graph_edge(graph_t *g, char from, char to, int weight)
{
// Does a exists
if (g->vertexes[from] == NULL) {
g->vertexes[from] = create_vertex(from);
}
// What about b
if (g->vertexes[to] == NULL) {
g->vertexes[to] = create_vertex(to);
}
// Add edge
create_edge(g->vertexes[from], g->vertexes[to], weight);
}
int graph_print_adj(graph_t *g, char ref)
{
if (g->vertexes[ref] == NULL) {
return 1;
}
edge_t *e = g->vertexes[ref]->adj;
printf("[ ");
while (e && e->from->ref == ref) {
printf("%c[%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, "%c [label=\"%c(%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, "%c -> %c [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");
}
|
