cKit/Graph/c_NonrecursiveDirectedCycle.c

#include <c_NonrecursiveDirectedCycle.h>

/* ------------------------------------------------------------------------------------------------------------------ */
/*  */


typedef struct {
    c_size_t v;           /* Current vertex */
    c_size_t edge_idx;    /* Next neighbor index to examine in the adjacency list */
} c_CycleFrame_t;

/* ------------------------------------------------------------------------------------------------------------------ */
/*  */

/* Private non-recursive DFS engine subroutine */
static void c_NonrecursiveDirectedCycle_Process(c_NonrecursiveDirectedCycle_t* self, const c_Digraph_t* graph, c_size_t root, c_CycleFrame_t* frame_stack) {
    c_size_t stack_size = 0;

    /* Push initial root activation frame entry */
    self->marked[root] = C_TRUE;
    self->on_stack[root] = C_TRUE;
    frame_stack[stack_size++] = (c_CycleFrame_t){ .v = root, .edge_idx = 0 };

    while (stack_size > 0) {
        c_CycleFrame_t* current_frame = &frame_stack[stack_size - 1];
        c_size_t u = current_frame->v;

        c_AdjList_t* adj = &graph->adj_list[u];
        c_size_t neighbor_count = (c_size_t)c_UIntArray_GetSize(adj);

        c_bool_t advanced = C_FALSE;
        while (current_frame->edge_idx < neighbor_count) {
            c_uint_t target_value = 0;
            c_err_t err = c_UIntArray_Get(adj, current_frame->edge_idx, &target_value);
            current_frame->edge_idx++; /* Advance neighbor loop pointer state */

            if (err == C_SUCCESS) {
                c_size_t w = (c_size_t)target_value;

                /* Case A: Found an unvisited branch, push execution block down */
                if (!self->marked[w]) {
                    self->marked[w] = C_TRUE;
                    self->on_stack[w] = C_TRUE;
                    self->edge_to[w] = u;

                    frame_stack[stack_size++] = (c_CycleFrame_t){ .v = w, .edge_idx = 0 };
                    advanced = C_TRUE;
                    break;
                }
                /* Case B: Backedge detected (vertex is still active on stack) -> Cycle Found! */
                else if (self->on_stack[w]) {
                    c_size_t* reverse_stack = (c_size_t*)c_Allocator_Calloc(&self->allocator, graph->V, sizeof(c_size_t));
                    if (!reverse_stack) return;

                    c_size_t trace_size = 0;
                    for (c_size_t x = u; x != w; x = self->edge_to[x]) {
                        reverse_stack[trace_size++] = x;
                    }
                    reverse_stack[trace_size++] = w;
                    reverse_stack[trace_size++] = u;

                    /* Build proper forward loop trail order inside cycle sequence container */
                    while (trace_size > 0) {
                        c_VertexIdList_Append(&self->cycle, (c_uint_t)reverse_stack[--trace_size]);
                    }

                    c_Allocator_Free(&self->allocator, reverse_stack);
                    return; /* Instantly yield loop upon detection */
                }
            }
        }

        /* If short-circuit evaluation trapped a cycle at child nodes, cleanly escape up */
        if (c_NonrecursiveDirectedCycle_HasCycle(self)) return;

        /* If all edges out of vertex u have been fully cleared, pop it from stack tracking */
        if (!advanced) {
            self->on_stack[u] = C_FALSE;
            stack_size--;
        }
    }
}

c_err_t c_NonrecursiveDirectedCycle_Init(c_NonrecursiveDirectedCycle_t* self, const c_Digraph_t* graph, c_Allocator_t* allocator) {
    if (!self || !graph) return C_ERR_PARAM;

    self->allocator = allocator ? *allocator : c_DefaultAllocator;
    self->marked = (c_bool_t*)c_Allocator_Calloc(&self->allocator, graph->V, sizeof(c_bool_t));
    self->edge_to = (c_size_t*)c_Allocator_Calloc(&self->allocator, graph->V, sizeof(c_size_t));
    self->on_stack = (c_bool_t*)c_Allocator_Calloc(&self->allocator, graph->V, sizeof(c_bool_t));

    c_VertexIdList_Init(&self->cycle, 0, allocator);

    if (!self->marked || !self->edge_to || !self->on_stack) {
        c_NonrecursiveDirectedCycle_Destroy(self);
        return C_ERR_NOMEM;
    }

    /* Allocate explicit local runtime runtime loop frame stack structure sized O(V) */
    c_CycleFrame_t* frame_stack = (c_CycleFrame_t*)c_Allocator_Calloc(&self->allocator, graph->V, sizeof(c_CycleFrame_t));
    if (!frame_stack) {
        c_NonrecursiveDirectedCycle_Destroy(self);
        return C_ERR_NOMEM;
    }

    /* Sweep disconnected structural pockets across graph nodes boundary safely */
    for (c_size_t v = 0; v < graph->V; ++v) {
        if (!self->marked[v] && !c_NonrecursiveDirectedCycle_HasCycle(self)) {
            c_NonrecursiveDirectedCycle_Process(self, graph, v, frame_stack);
        }
    }

    c_Allocator_Free(&self->allocator, frame_stack);
    return C_SUCCESS;
}

void c_NonrecursiveDirectedCycle_Destroy(c_NonrecursiveDirectedCycle_t* self) {
    if (!self) return;
    if (self->marked) c_Allocator_Free(&self->allocator, self->marked);
    if (self->edge_to) c_Allocator_Free(&self->allocator, self->edge_to);
    if (self->on_stack) c_Allocator_Free(&self->allocator, self->on_stack);

    c_VertexIdList_Destroy(&self->cycle);

    self->marked = NULL;
    self->edge_to = NULL;
    self->on_stack = NULL;
}

c_err_t c_NonrecursiveDirectedCycle_GetCycle(c_NonrecursiveDirectedCycle_t* self, c_VertexIdList_t* out_cycle) {
    if (!self || !out_cycle) return C_ERR_PARAM;
    if (!c_NonrecursiveDirectedCycle_HasCycle(self)) return C_ERR_FAIL;

    c_size_t size = (c_size_t)c_VertexIdList_GetSize(&self->cycle);
    for (c_size_t i = 0; i < size; ++i) {
        c_uint_t val = 0;
        c_err_t err = c_VertexIdList_Get((c_VertexIdList_t*)&self->cycle, i, &val);
        if (err == C_SUCCESS) {
            c_err_t app_err = c_VertexIdList_Append(out_cycle, val);
            if (app_err != C_SUCCESS) return app_err;
        }
    }
    return C_SUCCESS;
}