Concerning Graph Part X MST Algo

We've digressed from graph for a while to give the imls for other algorithms and ADTs(specifically, dynamic connectivity problem and priority queue impl), which is required for the problem we will be addressing in this post: the minimum spanning tree problem.

We present two different algorithms here, for the first of which, Prim's Algorithm, we give two different imls(lazy & eager):

/**
* Prim's algorithm to solve the MST problem, lazy impl.
*/
#include "priority_queue.c"
#include "linked_list_queue.c"
#include "edge_weighted_graph.c"

#ifndef LAZY_PRIM_MST
#define LAZY_PRIM_MST
typedef struct {
    LinkedListQueue mst;
    double weight;
}*LazyPrimMST;

void LazyPrimMSTVisit(EdgeWeightedGraph ewg, int v, bool *marked, PriorityQueue pq) {
    marked[v] = true;
    int n = 0;
    WeightedEdge *edges = EdgeWeightedGraphAdj(ewg, v, &n);
    for (int i = 0; i < n; i++) {
        WeightedEdge we = edges[i];
        if (!marked[WeightedEdgeOther(we, v)]) { PriorityQueueInsert(pq, we); }
    }
    free(edges);
}

LazyPrimMST LazyPrimMSTCreate(EdgeWeightedGraph ewg) {
    LazyPrimMST lpmst = (LazyPrimMST)malloc(sizeof(*lpmst));
    lpmst->mst = LinkedListQueueCreate();
    lpmst->weight = .0f;

    bool *marked = (bool*)malloc(ewg->v * sizeof(bool));
    PriorityQueue pq = PriorityQueueCreate((int(*)(void*, void*))WeightedEdgeDescendingCompare);
    LazyPrimMSTVisit(ewg, 0, marked, pq);
    while(!PriorityQueueIsEmpty(pq)) {
        WeightedEdge we = PriorityQueueDelete(pq);
        int v = WeightedEdgeEither(we), w = WeightedEdgeOther(we, v);
        if (marked[v] && marked[w]) continue;
        LinkedListQueueEnqueue(lpmst->mst, we);
        lpmst->weight += WeightedEdgeWeight(we);
        if (!marked[v]) { LazyPrimMSTVisit(ewg, v, marked, pq); }
        if (!marked[w]) { LazyPrimMSTVisit(ewg, w, marked, pq); }
    }
    free(marked);

    return lpmst;
}

WeightedEdge* LazyPrimMSTEdges(LazyPrimMST lpmst, int *n) { return lpmst == NULL ? NULL : LinkedListQueueItems(lpmst->mst, n); }

double LazyPrimMSTWeight(LazyPrimMST lpmst) { return lpmst == NULL ? DBL_MIN : lpmst->weight; }
#endif

/**
* Prim's algorithm, eager impl
*/

#include "index_priority_queue.c"
#include "linked_list_bag.c"
#include "edge_weighted_graph.c"
#ifndef PRIM_MST
#define PRIM_MST
typedef struct {
    double weight;
    LinkedListBag mst;
}*PrimMST;

void PrimMSTVisit(PrimMST pmst, EdgeWeightedGraph ewg, int v, bool *marked, IndexPriorityQueue ipq) {
    marked[v] = true;
    int n = 0;
    WeightedEdge *adj = EdgeWeightedGraphAdj(ewg, v, &n);
    for (int i = 0; i < n; i++) {
        WeightedEdge we = adj[i];
        int w = WeightedEdgeOther(we, v);
        if (marked[w]) continue;
        if (IndexPriorityQueueContains(ipq, w)) {
            WeightedEdge edge = IndexPriorityQueueKeyAtIndex(ipq, w);
            if (WeightedEdgeWeight(we) < WeightedEdgeWeight(edge)) { IndexPriorityQueueChange(ipq, w, we); }
        } else {
            IndexPriorityQueueInsert(ipq, w, we);
        }
    }
}

PrimMST PrimMSTCreate(EdgeWeightedGraph ewg) {
    PrimMST pmst = (PrimMST)malloc(sizeof(*pmst));
    pmst->weight = .0f;
    pmst->mst = LinkedListBagCreate();
    
    bool *marked = (bool*)malloc(ewg->v * sizeof(*marked));
    IndexPriorityQueue ipq = IndexPriorityQueueCreate((int(*)(void*, void*))WeightedEdgeDescendingCompare);

    PrimMSTVisit(pmst, ewg, 0, marked, ipq);

    while (!IndexPriorityQueueIsEmpty(ipq)) { 
        int v = IndexPriorityQueueHPIndex(ipq);
        WeightedEdge we = IndexPriorityQueueKeyAtIndex(ipq, v);
        LinkedListBagAdd(pmst->mst, we);
        pmst->weight += WeightedEdgeWeight(we);
        PrimMSTVisit(pmst, ewg, IndexPriorityQueueDeleteHP(ipq), marked, ipq); 
    }

    return pmst;
}

double PrimMSTWeight(PrimMST pmst) { return pmst != NULL ? pmst->weight : DBL_MAX; }

WeightedEdge* PrimMSTEdges(PrimMST pmst, int *n) { return pmst != NULL ? LinkedListBagItems(pmst->mst, n) : NULL; }
#endif

/**
* Kruskal's algorithm
*/

#include "linked_list_queue.c"
#include "priority_queue.c"
#include "edge_weighted_graph.c"
#include "weighted_union_find.c"
#ifndef KRUSKAL_MST
#define KRUSKAL_MST
typedef struct {
    double weight;
    LinkedListQueue mst;
}*KruskalMST;

KruskalMST KruskalMSTCreate(EdgeWeightedGraph ewg) {
    KruskalMST kmst = (KruskalMST)malloc(sizeof(*kmst));
    kmst->weight = .0f;
    kmst->mst = LinkedListQueueCreate();

    UnionFind uf = UnionFindCreate(EdgeWeightedGraphNumberOfVertices(ewg));
    WeightedEdge *edges = EdgeWeightedGraphEdges(ewg);
    PriorityQueue pq = PriorityQueueCreateFromKeys((int(*)(void*, void*))WeightedEdgeDescendingCompare, (void**)edges, EdgeWeightedGraphNumberOfEdges(ewg));
    while (!PriorityQueueIsEmpty(pq) && LinkedListQueueCount(kmst->mst) < EdgeWeightedGraphNumberOfVertices(ewg) - 1) {
        WeightedEdge we = PriorityQueueDelete(pq);
        int v = WeightedEdgeEither(we), w = WeightedEdgeOther(we, v);
        if (UnionFindConnected(uf, v, w)) continue;
        UnionFindUnion(uf, v, w);
        LinkedListQueueEnqueue(kmst->mst, we);
        kmst->weight += WeightedEdgeWeight(we);
    }

    if (edges != NULL) { free(edges); }
    PriorityQueueRelease(pq);
    UnionFindRelease(uf);

    return kmst;
}

WeightedEdge* KruskalMSTEdges(KruskalMST kmst, int *n) { return kmst != NULL ? LinkedListQueueItems(kmst->mst, n) : NULL; }

double KruskalMSTWeight(KruskalMST kmst) { return kmst != NULL ? kmst->weight : .0f; }
#endif