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
|
#include "graph.h"
#include "linked_list.h"
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
// Need to declare 'graph_delete' for use in 'graph_new'
void graph_delete(Graph *g);
Graph *graph_new(int n) {
Graph *graph = (Graph *)malloc(sizeof(Graph));
if (!graph)
return NULL;
graph->vertices = (Vertex *)malloc(sizeof(Vertex) * n);
if (!graph->vertices) {
free(graph);
return NULL;
}
graph->num_edges = 0;
graph->num_vertices = n;
for (int i = 0; i < n; i++) {
graph->vertices[i].id = i;
graph->vertices[i].out_neighbours = linked_list_new();
graph->vertices[i].in_neighbours = linked_list_new();
// if allocation for the linked lists failed
if (!graph->vertices[i].out_neighbours
|| !graph->vertices[i].in_neighbours) {
graph_delete(graph);
return NULL;
}
}
return graph;
}
void graph_add_edge(Graph *g, int i, int j) {
linked_list_append(g->vertices[i].out_neighbours, &g->vertices[j]);
linked_list_append(g->vertices[j].in_neighbours, &g->vertices[i]);
g->num_edges++;
}
void graph_remove_edge(Graph *g, int i, int j) {
LinkedListNode *in_node = linked_list_find(
g->vertices[i].out_neighbours,
&g->vertices[j]);
LinkedListNode *out_node = linked_list_find(
g->vertices[j].in_neighbours,
&g->vertices[j]);
linked_list_remove(g->vertices[i].out_neighbours, in_node);
linked_list_remove(g->vertices[j].in_neighbours, out_node);
g->num_edges--;
}
Graph *graph_read(const char *filename) {
FILE *file = fopen(filename, "r");
if (!file)
return NULL;
char line[1024];
fgets(line, 1024, file);
int n = atoi(line);
if (!n)
return NULL;
Graph *g = graph_new(n);
char c = line[0];
int i = 0, j = 0;
while (fgets(line, 1024, file)) {
while (c != '\n') {
if (c == '1') {
graph_add_edge(g, i, j);
j++;
} else if (c == '0') {
j++;
}
c++;
}
i++;
}
return g;
}
void graph_print(Graph *g) {
fprintf(stdout, "Number of vertices: %d\n", g->num_vertices);
fprintf(stdout, "Number of edges: %d\n", g->num_edges);
}
void graph_delete(Graph *g) {
for (int i = 0; i < g->num_vertices; i++) {
linked_list_delete(g->vertices[i].in_neighbours);
linked_list_delete(g->vertices[i].out_neighbours);
}
free(g->vertices);
free(g);
}
|