Graph implementation file - Toy programs for implementing graph algorithms

graph.c

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include "graph.h"

void graph_init(struct graph* g) {
    for (int i = 0; i < MAX_VERTICES; i++) {
        g->vertices[i] = i;
    }
    for (int i = 0; i < MAX_VERTICES; i++) {
        for (int j = 0; j < MAX_VERTICES; j++) {
            g->edges[i][j] = -1;
        }
    }
}

void graph_print(struct graph* g) {
    for (int i = 0; i < MAX_VERTICES; i++) {
        printf("%2d: ", g->vertices[i]);
        for (int j = 0; j < MAX_VERTICES; j++) {
            if (g->edges[i][j] == -1) { printf("%2s ", "."); }
            else { printf("%2d ", g->edges[i][j]); }
        }
        printf("\n");
    }
}

void graph_add_edge(struct graph* g, int src, int dest, int weight) {
    assert(src < MAX_VERTICES && dest < MAX_VERTICES);
    g->edges[src][dest] = weight;
}

void graph_add_bidi_edge(struct graph* g, int src, int dest, int weight) {
    graph_add_edge(g, src, dest, weight);
    graph_add_edge(g, dest, src, weight);
}

void dfs_recursive_int(struct graph* g, int start, FILE* f) {
    if (g->visited[start]) { return; }
    printf("%2d ", start);
    g->visited[start] = 1;
    for (int j = 0; j < MAX_VERTICES; j++) {
        if (g->edges[start][j] == -1) { continue; }
        if (g->visited[j]) { continue; }
        fprintf(f, "%d -> %d;\n", start, j);
        dfs_recursive_int(g, j, f);
    }
}

void clear_visited(struct graph* g) {
    for (int i = 0; i < MAX_VERTICES; i++) {
        g->visited[i] = 0;
    }
}

void graph_dfs_recursive(struct graph* g, int start) {
    clear_visited(g);
    FILE* f = fopen("dfs.dot", "w+");
    assert(f);
    fprintf(f, "digraph dfs {\n");
    printf("Depth first search from %d [", start);
    dfs_recursive_int(g, start, f);
    printf("]\n");
    fprintf(f, "}\n");
    fclose(f);
    system("dot -Tpng -odfs.png dfs.dot");
}

int queue[MAX_VERTICES];
int queue_size;

void queue_clear() {
    queue_size = 0;
}
int queue_empty() {
}
void queue_append(int vertex) {
    assert(queue_size < MAX_VERTICES - 1);
    queue[queue_size] = vertex;
    queue_size++;
    //printf("QUEUE APPEND: %d\n", vertex);
}
int queue_remove() {
    assert(queue_size > 0);
    int ret = queue[0];
    for (int i = 1; i < queue_size; i++) {
        queue[i - 1] = queue[i];
    }
    queue_size--;
    //printf("QUEUE REMOVE: %d\n", ret);
    return ret;
}

int predecessor[MAX_VERTICES];
int distance[MAX_VERTICES];
void clear_bfs() {
    for (int i = 0; i < MAX_VERTICES; i++) { predecessor[i] = -1; }
    for (int i = 0; i < MAX_VERTICES; i++) { distance[i] = -1; }
}

void graph_bfs(struct graph* g, int start) {
    clear_visited(g);
    clear_bfs();
    FILE* f = fopen("bfs.dot", "w+");
    fprintf(f, "digraph bfs {\n");
    printf("Breadth first search from %d [", start);
    queue_append(start);
    g->visited[start] = 1;
    predecessor[start] = -1;
    distance[start] = 0;
    while (queue_size) {
        int vertex = queue_remove();
        printf("%2d ", vertex);
        for (int j = 0; j < MAX_VERTICES; j++) {
            if (g->edges[vertex][j] != -1 && !g->visited[j]) {
                queue_append(j);
                g->visited[j] = 1;
                predecessor[j] = vertex;
                distance[j] = distance[vertex] + 1;
                fprintf(f, "%d -> %d;\n", vertex, j);
            }
        }
    }
    printf("]\n");
    for (int i = 0; i < MAX_VERTICES; i++) {
        if (distance[i] == -1) { continue; }
        fprintf(f, "%d [label=\"\\N (%d)\"];\n", i, distance[i]);
    }
    fprintf(f, "}\n");
    fclose(f);
    system("dot -Tpng -obfs.png bfs.dot");
}

void graph_bfs_print_path_int(int start, int end, FILE* f) {
    if (start == end) {
        printf("%2d ", start);
    } else if (predecessor[end] == -1) {
        printf("No path from %d to %d\n", start, end);
    } else {
        graph_bfs_print_path_int(start, predecessor[end], f);
        printf("%2d ", end);
        fprintf(f, "  %d -> %d;\n", predecessor[end], end);
    }
}

void graph_bfs_print_path(int start, int end) {
    FILE* f = fopen("bfs-path.dot", "w+");
    assert(f);
    printf("Path from %d to %d [", start, end);
    fprintf(f, "digraph actual {\n");
    graph_bfs_print_path_int(start, end, f);
    printf("]\n");
    fprintf(f, "}\n");
    fclose(f);
    system("dot -Tpng -obfs-path.png bfs-path.dot");
}

void graph_print_bidi_dot(struct graph* g) {
    FILE* f = fopen("graph.dot", "w+");
    assert(f != NULL);
    fprintf(f, "graph actual {\n");
    for (int i = 0; i < MAX_VERTICES; i++) {
        for (int j = 0; j < i; j++) {
            if (g->edges[i][j] != -1) {
                fprintf(f, "  %d -- %d;\n", i, j);
            }
        }
    }
    fprintf(f, "}\n");
    fclose(f);
    system("dot -Tpng -ograph.png graph.dot");
}

void graph_print_dot(struct graph* g) {
    FILE* f = fopen("digraph.dot", "w+");
    assert(f != NULL);
    fprintf(f, "digraph actual {\n");
    for (int i = 0; i < MAX_VERTICES; i++) {
        for (int j = 0; j < MAX_VERTICES; j++) {
            if (g->edges[i][j] != -1) {
                fprintf(f, "  %d -> %d;\n", i, j);
            }
        }
    }
    fprintf(f, "}\n");
    fclose(f);
    system("dot -Tpng -odigraph.png digraph.dot");
}

void toposort_int(struct graph* g) {
}

void toposort(struct graph* g) {
}