93 lines
3.4 KiB
C
93 lines
3.4 KiB
C
|
#include <c_NonrecursiveTopological.h>
|
||
|
|
#include "c_NonrecursiveDirectedCycle.h"
|
||
|
|
|
||
|
|
c_err_t c_NonrecursiveTopological_Init(c_NonrecursiveTopological_t* self, c_Digraph_t* graph, c_Allocator_t* allocator) {
|
||
|
|
if (!self || !graph) return C_ERR_PARAM;
|
||
|
|
|
||
|
|
self->allocator = allocator ? *allocator : c_DefaultAllocator;
|
||
|
|
self->has_order = C_FALSE;
|
||
|
|
c_VertexIdList_Init(&self->order, 0, allocator);
|
||
|
|
|
||
|
|
/* 1. Stack-safe Cycle Check: Ensure the graph is a DAG without relying on recursion stack */
|
||
|
|
c_NonrecursiveDirectedCycle_t cycle_detector;
|
||
|
|
c_err_t err = c_NonrecursiveDirectedCycle_Init(&cycle_detector, graph, allocator);
|
||
|
|
if (err != C_SUCCESS) return err;
|
||
|
|
|
||
|
|
c_bool_t has_cycle = c_NonrecursiveDirectedCycle_HasCycle(&cycle_detector);
|
||
|
|
c_NonrecursiveDirectedCycle_Destroy(&cycle_detector);
|
||
|
|
|
||
|
|
if (has_cycle) {
|
||
|
|
return C_SUCCESS; /* Contains a cycle, return gracefully with has_order = C_FALSE */
|
||
|
|
}
|
||
|
|
|
||
|
|
/* 2. Kahn's Algorithm: Allocate a mutable working array copy of in-degrees */
|
||
|
|
c_size_t* working_indegree = (c_size_t*)c_Allocator_Calloc(&self->allocator, graph->V, sizeof(c_size_t));
|
||
|
|
if (!working_indegree) return C_ERR_NOMEM;
|
||
|
|
|
||
|
|
/* A simple array-based queue bounded tightly by O(V) */
|
||
|
|
c_size_t* zero_in_degree_queue = (c_size_t*)c_Allocator_Calloc(&self->allocator, graph->V, sizeof(c_size_t));
|
||
|
|
if (!zero_in_degree_queue) {
|
||
|
|
c_Allocator_Free(&self->allocator, working_indegree);
|
||
|
|
return C_ERR_NOMEM;
|
||
|
|
}
|
||
|
|
|
||
|
|
c_size_t head = 0;
|
||
|
|
c_size_t tail = 0;
|
||
|
|
|
||
|
|
/* Initialize working in-degrees and seed the queue with source nodes (in-degree == 0) */
|
||
|
|
for (c_size_t v = 0; v < graph->V; ++v) {
|
||
|
|
working_indegree[v] = c_Digraph_GetInDegree(graph, v);
|
||
|
|
if (working_indegree[v] == 0) {
|
||
|
|
zero_in_degree_queue[tail++] = v;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
/* 3. Non-recursive processing loop */
|
||
|
|
while (head < tail) {
|
||
|
|
c_size_t u = zero_in_degree_queue[head++];
|
||
|
|
|
||
|
|
/* Append the processed node to the topological ordering stream */
|
||
|
|
c_VertexIdList_Append(&self->order, (c_uint_t)u);
|
||
|
|
|
||
|
|
c_AdjList_t* adj = &graph->adj_list[u];
|
||
|
|
c_size_t size = (c_size_t)c_AdjList_GetSize(adj);
|
||
|
|
|
||
|
|
/* Decrement in-degree for all downstream neighbors */
|
||
|
|
for (c_size_t i = 0; i < size; ++i) {
|
||
|
|
c_uint_t target_value = 0;
|
||
|
|
err = c_AdjList_Get(adj, i, &target_value);
|
||
|
|
|
||
|
|
if (err == C_SUCCESS) {
|
||
|
|
c_size_t w = (c_size_t)target_value;
|
||
|
|
working_indegree[w]--;
|
||
|
|
|
||
|
|
/* If all parent dependencies are cleared, enqueue the neighbor */
|
||
|
|
if (working_indegree[w] == 0) {
|
||
|
|
zero_in_degree_queue[tail++] = w;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
/* Clean up local working tracking allocations */
|
||
|
|
c_Allocator_Free(&self->allocator, working_indegree);
|
||
|
|
c_Allocator_Free(&self->allocator, zero_in_degree_queue);
|
||
|
|
|
||
|
|
self->has_order = C_TRUE;
|
||
|
|
return C_SUCCESS;
|
||
|
|
}
|
||
|
|
|
||
|
|
void c_NonrecursiveTopological_Destroy(c_NonrecursiveTopological_t* self) {
|
||
|
|
if (!self) return;
|
||
|
|
c_VertexIdList_Destroy(&self->order);
|
||
|
|
self->has_order = C_FALSE;
|
||
|
|
}
|
||
|
|
|
||
|
|
c_err_t c_NonrecursiveTopological_GetOrder(c_NonrecursiveTopological_t* self, c_VertexIdList_t* out_order) {
|
||
|
|
if (!self || !out_order) return C_ERR_PARAM;
|
||
|
|
if (!self->has_order) return C_ERR_FAIL;
|
||
|
|
|
||
|
|
/* High-speed block copy optimization */
|
||
|
|
return c_VertexIdList_Copy(out_order, &self->order);
|
||
|
|
}
|