src/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

#include "graph.h"
#include "linked_list.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->numEdges = n;
    graph->numVertices = 0;
    
    for (int i = 0; i < n; i++) {
        graph->vertices[i].id = i;
        graph->vertices[i].outNeighbours = linked_list_new();
        graph->vertices[i].inNeighbours = linked_list_new();

        // if allocation for the linked lists failed
        if (!graph->vertices[i].outNeighbours
            || !graph->vertices[i].inNeighbours) {
            graph_delete(graph);
            return NULL;
        }
    }

    return graph;
}

void graph_add_edge(Graph *g, int i, int j) {
    linked_list_append(g->vertices[i].outNeighbours, &g->vertices[j]);
    linked_list_append(g->vertices[j].inNeighbours, &g->vertices[i]);
    g->numEdges++;
}

Graph *graph_read(const char *filename) {
    Graph *g = graph_new(69);
    return g;
}

void graph_delete(Graph *g) {
    for (int i = 0; i < g->numVertices; i++) {
        linked_list_delete(g->vertices[i].inNeighbours);
        linked_list_delete(g->vertices[i].outNeighbours);
    }
    free(g->vertices);
    free(g);
}