cKit/Graph/c_NonrecursiveDFS.c

#include <c_NonrecursiveDFS.h>
#include <c_ArrayStack.h>

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


c_err_t c_NonrecursiveDFS_Init(c_NonrecursiveDFS_t* self, const c_Graph_t* G, c_VertexId_t s, c_Allocator_t* allocator) {
    if (!self || !G ||  s >= G->V) {
        return C_ERR_PARAM;
    }

    self->allocator = allocator?*allocator:c_DefaultAllocator;
    self->source = s;
    self->count = 0;
    self->marked = NULL;
    self->edge_to = NULL;

    if (G->V == 0) {
        return C_SUCCESS;
    }

    // Allocate structural state tracing map blocks
    self->marked = (c_bool_t*)c_Allocator_Alloc(&self->allocator, G->V * sizeof(*self->marked));
    self->edge_to = (c_size_t*)c_Allocator_Alloc(&self->allocator, G->V * sizeof(*self->edge_to));

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

    memset(self->marked, 0, G->V * sizeof(*self->marked));
    for (c_size_t i = 0; i < G->V; i++) {
        self->edge_to[i] = G->V; // Out-of-bounds boundary sentinel definition
    }

    // Initialize an explicit LIFO dynamic array stack using your core components
    c_ArrayStack_t stack;
    if (c_ArrayStack_Init(&stack, sizeof(c_VertexId_t), 8, &self->allocator) != C_SUCCESS) {
        c_NonrecursiveDFS_Destroy(self);
        return C_ERR_NOMEM;
    }

    // Append starting root index trajectory frame
    if (c_ArrayStack_Push(&stack, &s) != C_ERR_OK) {
        c_ArrayStack_Destroy(&stack);
        c_NonrecursiveDFS_Destroy(self);
        return C_ERR_NOMEM;
    }

    c_err_t err = C_ERR_OK;
    // Main non-recursive traversal processing engine loop
    while (!c_ArrayStack_IsEmpty(&stack)) {
        // Pop operations map straight to reducing active sizing tallies
        c_VertexId_t v = -1;
        if((err = c_ArrayStack_Pop(&stack, &v))!=C_ERR_OK){
            c_ArrayStack_Destroy(&stack);
            c_NonrecursiveDFS_Destroy(self);
            return err;
        }


        if (!self->marked[v]) {
            self->marked[v] = C_TRUE;
            self->count++;

            c_AdjList_t* list = c_Graph_GetAdjList((c_Graph_t*)G, v);
            if (list && !c_AdjList_IsEmpty(list)) {
                // Iterating backward replicates recursive evaluation order identically
                c_size_t i = list->size;
                while (i>0) {
                    i--;
                    const c_VertexId_t w = list->array[i];

                    if (!self->marked[w]) {
                        self->edge_to[w] = v; // Track incoming path route link

                        if (c_ArrayStack_Push(&stack, &w) != C_ERR_OK) {
                            c_ArrayStack_Destroy(&stack);
                            c_NonrecursiveDFS_Destroy(self);
                            return C_ERR_NOMEM;
                        }
                    }
                }
            }
        }
    }

    c_ArrayStack_Destroy(&stack);
    return err;
}

void c_NonrecursiveDFS_Destroy(c_NonrecursiveDFS_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);

    self->marked = NULL;
    self->edge_to = NULL;
    self->count = 0;
    self->source = 0;
}

c_bool_t c_NonrecursiveDFS_HasPathTo(const c_NonrecursiveDFS_t* self, c_VertexId_t v) {
    if (!self || !self->marked) {
        return C_FALSE;
    }
    return self->marked[v];
}

c_err_t c_NonrecursiveDFS_PathTo(const c_NonrecursiveDFS_t* self, c_size_t v, c_VertexIdList_t* path) {
    if (!self || !path ) return C_ERR_PARAM;
    if (!c_NonrecursiveDFS_HasPathTo(self, v)) return C_ERR_FAIL;

    path->size = 0;
    c_size_t current = v;
    while (current != self->source) {
        if (c_VertexIdList_Append(path, (c_uint_t)current) != C_SUCCESS) {
            path->size = 0;
            return C_ERR_NOMEM;
        }
        current = self->edge_to[current];
    }

    if (c_VertexIdList_Append(path, (c_uint_t)self->source) != C_SUCCESS) {
        path->size = 0;
        return C_ERR_NOMEM;
    }

    // Mirror swap to sort sequence output chronologically (source -> v)
    c_size_t left = 0;
    c_size_t right = path->size - 1;
    while (left < right) {
        c_uint_t temp = path->array[left];
        path->array[left] = path->array[right];
        path->array[right] = temp;
        left++;
        right--;
    }

    return C_SUCCESS;
}

c_size_t c_NonrecursiveDFS_Count(const c_NonrecursiveDFS_t* self) {
    if (!self) return 0;
    return self->count;
}