cKit/Graph/c_AcyclicSP.c

#include <c_AcyclicSP.h>

#define SP_SENTINEL ((c_size_t)-1)

/* Private vertex relaxation handler routine */
static void c_AcyclicSP_Relax(c_AcyclicSP_t* self, c_EdgeWeightedDigraph_t* graph, c_size_t v) {
    c_AdjList_t* adj = &graph->adj_list[v];
    c_size_t size = (c_size_t)c_AdjList_GetSize(adj);

    for (c_size_t i = 0; i < size; ++i) {
        c_uint_t generic_edge_id = 0;
        c_err_t err = c_AdjList_Get(adj, i, &generic_edge_id);

        if (err == C_SUCCESS) {
            c_size_t edge_id = (c_size_t)generic_edge_id;
            c_DirectedEdge_t* edge = &graph->edges_pool[edge_id];
            c_size_t w = edge->to;

            if (self->dist_to[w] > self->dist_to[v] + edge->weight) {
                self->dist_to[w] = self->dist_to[v] + edge->weight;
                self->edge_to[w] = edge_id;
                self->from_vertex[w] = v; /* Record parent step */
            }
        }
    }
}

c_err_t c_AcyclicSP_Init(c_AcyclicSP_t* self, c_EdgeWeightedDigraph_t* graph, c_size_t s, c_Allocator_t* allocator) {
    if (!self || !graph || s >= graph->V) return C_ERR_PARAM;

    self->allocator = allocator ? *allocator : c_DefaultAllocator;
    self->s = s;
    self->V = graph->V;

    /* 1. Allocate primary execution matrices arrays */
    self->edge_to     = (c_size_t*)c_Allocator_Calloc(&self->allocator, self->V, sizeof(c_size_t));
    self->from_vertex = (c_size_t*)c_Allocator_Calloc(&self->allocator, self->V, sizeof(c_size_t));
    self->dist_to     = (double*)c_Allocator_Calloc(&self->allocator, self->V, sizeof(double));

    if (!self->edge_to || !self->from_vertex || !self->dist_to) {
        c_AcyclicSP_Destroy(self);
        return C_ERR_NOMEM;
    }

    for (c_size_t v = 0; v < self->V; ++v) {
        self->dist_to[v]     = DBL_MAX;
        self->edge_to[v]     = SP_SENTINEL;
        self->from_vertex[v] = SP_SENTINEL;
    }
    self->dist_to[s] = 0.0;

    /* 2. Embedded Stack-Safe Kahn's Algorithm to establish Topological Order */
    c_size_t* working_indegree = (c_size_t*)c_Allocator_Calloc(&self->allocator, self->V, sizeof(c_size_t));
    c_size_t* zero_in_degree_queue = (c_size_t*)c_Allocator_Calloc(&self->allocator, self->V, sizeof(c_size_t));
    if (!working_indegree || !zero_in_degree_queue) {
        if (working_indegree) c_Allocator_Free(&self->allocator, working_indegree);
        if (zero_in_degree_queue) c_Allocator_Free(&self->allocator, zero_in_degree_queue);
        c_AcyclicSP_Destroy(self);
        return C_ERR_NOMEM;
    }

    c_size_t head = 0, tail = 0;
    for (c_size_t v = 0; v < self->V; ++v) {
        working_indegree[v] = c_EdgeWeightedDigraph_GetInDegree(graph, v);
        if (working_indegree[v] == 0) {
            zero_in_degree_queue[tail++] = v;
        }
    }

    /* 3. Linear relaxation pass tracing vertices sequentially across topological indices */
    while (head < tail) {
        c_size_t u = zero_in_degree_queue[head++];

        /* If vertex u is reachable from source, relax its outgoing edges */
        if (self->dist_to[u] < DBL_MAX) {
            c_AcyclicSP_Relax(self, graph, u);
        }

        /* Decrement inner dependency states for all downstream neighbors */
        c_UIntArray_t* adj = &graph->adj_list[u];
        c_size_t size = (c_size_t)c_UIntArray_GetSize(adj);
        for (c_size_t i = 0; i < size; ++i) {
            c_uint_t generic_edge_id = 0;
            if (c_UIntArray_Get(adj, i, &generic_edge_id) == C_SUCCESS) {
                c_size_t w = graph->edges_pool[(c_size_t)generic_edge_id].to;
                working_indegree[w]--;
                if (working_indegree[w] == 0) {
                    zero_in_degree_queue[tail++] = w;
                }
            }
        }
    }

    c_Allocator_Free(&self->allocator, working_indegree);
    c_Allocator_Free(&self->allocator, zero_in_degree_queue);

    return C_SUCCESS;
}

void c_AcyclicSP_Destroy(c_AcyclicSP_t* self) {
    if (!self) return;
    if (self->edge_to)     c_Allocator_Free(&self->allocator, self->edge_to);
    if (self->from_vertex) c_Allocator_Free(&self->allocator, self->from_vertex);
    if (self->dist_to)     c_Allocator_Free(&self->allocator, self->dist_to);

    self->edge_to     = NULL;
    self->from_vertex = NULL;
    self->dist_to     = NULL;
    self->V = 0;
    self->s = 0;
}

c_err_t c_AcyclicSP_PathTo(c_AcyclicSP_t* self, c_size_t v, c_VertexIdList_t* out_path) {
    if (!self || !out_path || v >= self->V) return C_ERR_PARAM;
    if (!c_AcyclicSP_HasPathTo(self, v)) return C_ERR_FAIL;

    c_size_t* edge_stack = (c_size_t*)c_Allocator_Calloc(&self->allocator, self->V, sizeof(c_size_t));
    if (!edge_stack) return C_ERR_NOMEM;

    c_size_t stack_size = 0;
    c_size_t curr_v = v;

    while (curr_v != self->s) {
        c_size_t edge_id = self->edge_to[curr_v];
        if (edge_id == SP_SENTINEL) break;

        edge_stack[stack_size++] = edge_id;
        curr_v = self->from_vertex[curr_v];
    }

    c_err_t err = C_SUCCESS;
    while (stack_size > 0) {
        c_size_t target_edge_id = edge_stack[--stack_size];
        err = c_VertexIdList_Append(out_path, (c_uint_t)target_edge_id);
        if (err != C_SUCCESS) break;
    }

    c_Allocator_Free(&self->allocator, edge_stack);
    return err;
}