Concerning Graph Part IV: Single

Based on ADTs developed previously, we address the shortest path problem in this post.

#include "graph.c"
#include "linked_list_stack.c"
#include "linked_list_queue.c"
typedef struct BreadthFirstPathStruct {
    bool *marked;
    int *edgeTo;
    int s;
}*BreadthFirstPath;

void BreadthFirstPathSearch(BreadthFirstPath bfsp, Graph g) {
    LinkedListQueue queue = LinkedListQueueCreate();
    bfsp->marked[bfsp->s] = true;
    LinkedListQueueEnqueue(queue, bfsp->s);
    do {
        int v = LinkedListQueueDequeue(queue);
        int n = 0;
        int *adj = GraphAdjcency(g, v, &n);
        for (int i = 0; i < n; i++) {
            int w = adj[i];
            if (!bfsp->marked[w]) {
                bfsp->marked[w] = true;
                bfsp->edgeTo[w] = v;
                LinkedListQueueEnqueue(queue, w);
            }
        }
        if (adj != NULL) { free(adj); }
    } while(!LinkedListQueueIsEmpty(queue));
    LinkedListQueueRelease(queue);
}

BreadthFirstPath BreadthFirstPathCreate(Graph g, int s) {
    BreadthFirstPath bfsp = (BreadthFirstPath)malloc(sizeof(*bfsp));
    bfsp->marked = (bool*)malloc(g->v * sizeof(bool));
    bfsp->edgeTo = (int*)malloc(g->v * sizeof(int));
    bfsp->s = s;
    BreadthFirstPathSearch(bfsp, g);
    return bfsp;
}

void BreadthFirstPathRelease(BreadthFirstPath bfsp) {
    if (bfsp != NULL) {
        free(bfsp->marked);
        free(bfsp->edgeTo);
        free(bfsp);
    }
}

bool BreadthFirstPathHasPathTo(BreadthFirstPath bfsp, int v) { return bfsp != NULL && bfsp->marked[v]; }

int* BreadthFirstPathPathTo(BreadthFirstPath bfsp, int v, int *n) {
    if (bfsp == NULL) return NULL;
    LinkedListStack stack = LinkedListStackCreate();
    for (int i = v; i != bfsp->s; i = bfsp->edgeTo[i]) { LinkedListStackPush(stack, i); }
    LinkedListStackPush(stack, bfsp->s);
    int *path = LinkedListStackItems(stack, n);
    LinkedListStackRelease(stack);
    return path;
}