cKit/Graph/c_NonrecursiveGabowSCC.c

#include <c_NonrecursiveGabowSCC.h>


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

/* Private iterative DFS engine subroutine */
static void c_NonrecursiveGabowSCC_Process(c_NonrecursiveGabowSCC_t* self, c_Digraph_t* graph, c_size_t root, c_GabowFrame_t* frame_stack) {
    c_size_t frame_stack_size = 0;

    /* Push the initial root activation frame entry */
    self->marked[root] = C_TRUE;
    self->pre[root] = self->pre_counter++;
    self->scc_stack[self->scc_stack_sz++] = root;
    self->path_stack[self->path_stack_sz++] = root;

    frame_stack[frame_stack_size++] = (c_GabowFrame_t){ .v = root, .edge_idx = 0 };

    while (frame_stack_size > 0) {
        c_GabowFrame_t* current_frame = &frame_stack[frame_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 edge iterator pointer state */

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

                if (!self->marked[w]) {
                    self->marked[w] = C_TRUE;
                    self->pre[w] = self->pre_counter++;
                    self->scc_stack[self->scc_stack_sz++] = w;
                    self->path_stack[self->path_stack_sz++] = w;

                    /* Push new execution frame onto the state stack (Simulating Recursive Call) */
                    frame_stack[frame_stack_size++] = (c_GabowFrame_t){ .v = w, .edge_idx = 0 };
                    advanced = C_TRUE;
                    break;
                }
                else if (self->id[w] == C_SIZE_MAX) {
                    /* Contract the path tracking stack for active cross-links or backedges */
                    while (self->path_stack_sz > 0 && self->pre[self->path_stack[self->path_stack_sz - 1]] > self->pre[w]) {
                        self->path_stack_sz--;
                    }
                }
            }
        }

        if (advanced) continue; /* Control passes down into child node execution branch */

        /* Post-visit processing block (Unwinding) */
        frame_stack_size--;

        /* If u is detected as the root boundary of an active SCC cluster component */
        if (self->path_stack_sz > 0 && self->path_stack[self->path_stack_sz - 1] == u) {
            self->path_stack_sz--; /* Pop from the active root tracking stack */

            c_size_t component_node = 0;
            do {
                component_node = self->scc_stack[--self->scc_stack_sz];
                self->id[component_node] = self->count;
            } while (component_node != u);

            self->count++; /* Advance final SCC group ID counter label */
        }
    }
}

c_err_t c_NonrecursiveGabowSCC_Init(c_NonrecursiveGabowSCC_t* self, c_Digraph_t* graph, c_Allocator_t* allocator) {
    if (!self || !graph) return C_ERR_PARAM;

    self->allocator = allocator ? *allocator : c_DefaultAllocator;
    self->count = 0;
    self->pre_counter = 0;
    self->scc_stack_sz = 0;
    self->path_stack_sz = 0;
    self->V = graph->V;

    if (self->V == 0) return C_SUCCESS;

    /* 1. Allocate all necessary analytical tracking structures */
    self->marked     = (c_bool_t*)c_Allocator_Calloc(&self->allocator, self->V, sizeof(c_bool_t));
    self->id         = (c_size_t*)c_Allocator_Calloc(&self->allocator, self->V, sizeof(c_size_t));
    self->pre        = (c_size_t*)c_Allocator_Calloc(&self->allocator, self->V, sizeof(c_size_t));
    self->scc_stack  = (c_size_t*)c_Allocator_Calloc(&self->allocator, self->V, sizeof(c_size_t));
    self->path_stack = (c_size_t*)c_Allocator_Calloc(&self->allocator, self->V, sizeof(c_size_t));

    if (!self->marked || !self->id || !self->pre || !self->scc_stack || !self->path_stack) {
        c_NonrecursiveGabowSCC_Destroy(self);
        return C_ERR_NOMEM;
    }

    /* Assign unmapped initialization state labels across all indices */
    for (c_size_t i = 0; i < self->V; ++i) {
        self->id[i] = C_SIZE_MAX;
    }

    /* Allocate continuous explicit compiler-emulated frame scratch buffer stack O(V) */
    c_GabowFrame_t* frame_stack = (c_GabowFrame_t*)c_Allocator_Calloc(&self->allocator, self->V, sizeof(c_GabowFrame_t));
    if (!frame_stack) {
        c_NonrecursiveGabowSCC_Destroy(self);
        return C_ERR_NOMEM;
    }

    /* 2. Process all components securely */
    for (c_size_t v = 0; v < self->V; ++v) {
        if (!self->marked[v]) {
            c_NonrecursiveGabowSCC_Process(self, graph, v, frame_stack);
        }
    }

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

void c_NonrecursiveGabowSCC_Destroy(c_NonrecursiveGabowSCC_t* self) {
    if (!self) return;
    if (self->marked)     c_Allocator_Free(&self->allocator, self->marked);
    if (self->id)         c_Allocator_Free(&self->allocator, self->id);
    if (self->pre)        c_Allocator_Free(&self->allocator, self->pre);
    if (self->scc_stack)  c_Allocator_Free(&self->allocator, self->scc_stack);
    if (self->path_stack) c_Allocator_Free(&self->allocator, self->path_stack);

    self->marked = NULL;
    self->id = NULL;
    self->pre = NULL;
    self->scc_stack = NULL;
    self->path_stack = NULL;
    self->count = 0;
    self->scc_stack_sz = 0;
    self->path_stack_sz = 0;
    self->V = 0;
}