109 lines
4.0 KiB
C
109 lines
4.0 KiB
C
#include <c_DirectedCycle.h>
|
|
|
|
|
|
/* Private recursive engine helper */
|
|
static void c_DirectedCycle_DFS(c_DirectedCycle_t* self, const c_Digraph_t* graph, c_size_t v) {
|
|
self->on_stack[v] = C_TRUE;
|
|
self->marked[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;
|
|
/* Safely query edge list element matching custom pointer specifications */
|
|
c_err_t err = c_AdjList_Get(adj, i, &target_value);
|
|
|
|
if (err == C_SUCCESS) {
|
|
c_size_t w = (c_size_t)target_value;
|
|
|
|
/* Short-circuit if a cycle has already been detected */
|
|
if (c_DirectedCycle_HasCycle(self)) return;
|
|
|
|
if (!self->marked[w]) {
|
|
self->edge_to[w] = v;
|
|
c_DirectedCycle_DFS(self, graph, w);
|
|
}
|
|
/* Cycle detected! Trace back path sequence */
|
|
else if (self->on_stack[w]) {
|
|
/* Collect cycle steps onto a temporary reverse stack trace */
|
|
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 stack_size = 0;
|
|
for (c_size_t x = v; x != w; x = self->edge_to[x]) {
|
|
reverse_stack[stack_size++] = x;
|
|
}
|
|
reverse_stack[stack_size++] = w;
|
|
reverse_stack[stack_size++] = v;
|
|
|
|
/* Push structured forward order into the self->cycle storage container using VertexIdList interface */
|
|
while (stack_size > 0) {
|
|
c_VertexIdList_Append(&self->cycle, (c_uint_t)reverse_stack[--stack_size]);
|
|
}
|
|
|
|
c_Allocator_Free(&self->allocator, reverse_stack);
|
|
return;
|
|
}
|
|
}
|
|
}
|
|
|
|
self->on_stack[v] = C_FALSE;
|
|
}
|
|
|
|
c_err_t c_DirectedCycle_Init(c_DirectedCycle_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));
|
|
|
|
/* Using c_VertexIdList_Init mapper directly onto your internal cycle storage */
|
|
c_VertexIdList_Init(&self->cycle,0, allocator);
|
|
|
|
if (!self->marked || !self->edge_to || !self->on_stack) {
|
|
c_DirectedCycle_Destroy(self);
|
|
return C_ERR_NOMEM;
|
|
}
|
|
|
|
/* Iterate through all vertices to handle disconnected graph structures */
|
|
for (c_size_t v = 0; v < graph->V; ++v) {
|
|
if (!self->marked[v] && !c_DirectedCycle_HasCycle(self)) {
|
|
c_DirectedCycle_DFS(self, graph, v);
|
|
}
|
|
}
|
|
|
|
return C_SUCCESS;
|
|
}
|
|
|
|
void c_DirectedCycle_Destroy(c_DirectedCycle_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_DirectedCycle_GetCycle(c_DirectedCycle_t* self, c_VertexIdList_t* out_cycle) {
|
|
if (!self || !out_cycle) return C_ERR_PARAM;
|
|
if (!c_DirectedCycle_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;
|
|
/* Using the safe pointer signature format */
|
|
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;
|
|
}
|