cKit/Graph/c_AcyclicLP.c

#include <c_AcyclicLP.h>

#define LP_SENTINEL ((c_size_t)-1)

/* Private vertex relaxation handler routine optimized for maximum distance maximization */
static void c_AcyclicLP_Relax(c_AcyclicLP_t* self, const 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;

            /* Maximization condition check: update if a longer path variation is intercepted */
            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 structural parent lookup */
            }
        }
    }
}

c_err_t c_AcyclicLP_Init(c_AcyclicLP_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 essential tracker state buffers */
    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_AcyclicLP_Destroy(self);
        return C_ERR_NOMEM;
    }

    /* Initialize metrics map to NEGATIVE INFINITY benchmarks */
    for (c_size_t v = 0; v < self->V; ++v) {
        self->dist_to[v]     = -DBL_MAX;
        self->edge_to[v]     = LP_SENTINEL;
        self->from_vertex[v] = LP_SENTINEL;
    }
    self->dist_to[s] = 0.0;

    /* 2. Stack-Safe Kahn's algorithm setup to pull Topological Order profile elements */
    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_AcyclicLP_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. Run non-recursive scheduling pass across topologized nodes sequential blocks */
    while (head < tail) {
        c_size_t u = zero_in_degree_queue[head++];

        /* If vertex u is reachable from our tracking origin boundary source context, compute cuts */
        if (self->dist_to[u] > -DBL_MAX) {
            c_AcyclicLP_Relax(self, graph, u);
        }

        /* Decrement inner dependency states for downstream neighbor vertex arrays */
        c_AdjList_t* adj = &graph->adj_list[u];
        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;
            if (c_AdjList_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_AcyclicLP_Destroy(c_AcyclicLP_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_AcyclicLP_PathTo(c_AcyclicLP_t* self, c_size_t v, c_VertexIdList_t* out_path) {
    if (!self || !out_path || v >= self->V) return C_ERR_PARAM;
    if (!c_AcyclicLP_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 == LP_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;
}