cKit/Graph/c_TarjanSCC.c

#include <c_TarjanSCC.h>
#include <c_Macros.h>

/* Private recursive DFS engine helper subroutine for single-pass grouping */
static void c_TarjanSCC_DFS(c_TarjanSCC_t* self, c_Digraph_t* graph, c_size_t v) {
    self->marked[v] = C_TRUE;
    self->pre[v] = self->pre_counter++;
    self->low[v] = self->pre[v];

    /* Push vertex onto the component collector stack tracking context */
    self->stack[self->stack_size++] = v;
    self->on_stack[v] = C_TRUE;

    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 target_value = 0;
        c_err_t err = c_AdjList_Get(adj, i, &target_value);

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

            if (!self->marked[w]) {
                c_TarjanSCC_DFS(self, graph, w);
                self->low[v] = C_MIN(self->low[v], self->low[w]);
            }
            else if (self->on_stack[w]) {
                self->low[v] = C_MIN(self->low[v], self->pre[w]);
            }
        }
    }

    /* If v is a root node of an SCC, pop all component nodes off the stack context */
    if (self->low[v] == self->pre[v]) {
        c_size_t w = 0;
        do {
            w = self->stack[--self->stack_size];
            self->id[w] = self->count;
            self->on_stack[w] = C_FALSE;
        } while (w != v);

        self->count++; /* Advance component total tracking identity grouping */
    }
}

c_err_t c_TarjanSCC_Init(c_TarjanSCC_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->stack_size = 0;
    self->V = graph->V; /* Store vertex count locally for safe inline lookup assertions */

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

    /* 1. Allocate essential multi-array structural state mappings */
    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->low      = (c_size_t*)c_Allocator_Calloc(&self->allocator, self->V, sizeof(c_size_t));
    self->stack    = (c_size_t*)c_Allocator_Calloc(&self->allocator, self->V, sizeof(c_size_t));
    self->on_stack = (c_bool_t*)c_Allocator_Calloc(&self->allocator, self->V, sizeof(c_bool_t));

    if (!self->marked || !self->id || !self->pre || !self->low || !self->stack || !self->on_stack) {
        c_TarjanSCC_Destroy(self);
        return C_ERR_NOMEM;
    }

    /* 2. Run Single-Pass algorithm mapping over every unvisited node */
    for (c_size_t v = 0; v < self->V; ++v) {
        if (!self->marked[v]) {
            c_TarjanSCC_DFS(self, graph, v);
        }
    }

    return C_SUCCESS;
}

void c_TarjanSCC_Destroy(c_TarjanSCC_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->low)      c_Allocator_Free(&self->allocator, self->low);
    if (self->stack)    c_Allocator_Free(&self->allocator, self->stack);
    if (self->on_stack) c_Allocator_Free(&self->allocator, self->on_stack);

    self->marked = NULL;
    self->id = NULL;
    self->pre = NULL;
    self->low = NULL;
    self->stack = NULL;
    self->on_stack = NULL;
    self->count = 0;
    self->stack_size = 0;
    self->V = 0;
}