97 lines
3.4 KiB
C
97 lines
3.4 KiB
C
|
#include <c_DepthFirstOrder.h>
|
||
|
|
|
||
|
|
|
||
|
|
/* Private recursive engine helper */
|
||
|
|
static void c_DepthFirstOrder_DFS(c_DepthFirstOrder_t* self, c_Digraph_t* graph, c_size_t v) {
|
||
|
|
self->marked[v] = C_TRUE;
|
||
|
|
|
||
|
|
/* A. Pre-order: append vertex before visiting neighbors */
|
||
|
|
c_VertexIdList_Append(&self->pre_order, (c_uint_t)v);
|
||
|
|
|
||
|
|
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_DepthFirstOrder_DFS(self, graph, w);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
/* B. Post-order: append vertex after visiting all its outgoing branches */
|
||
|
|
c_VertexIdList_Append(&self->post_order, (c_uint_t)v);
|
||
|
|
}
|
||
|
|
|
||
|
|
c_err_t c_DepthFirstOrder_Init(c_DepthFirstOrder_t* self, 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));
|
||
|
|
if (!self->marked) return C_ERR_NOMEM;
|
||
|
|
|
||
|
|
c_VertexIdList_Init(&self->pre_order, 0, allocator);
|
||
|
|
c_VertexIdList_Init(&self->post_order, 0, allocator);
|
||
|
|
c_VertexIdList_Init(&self->reverse_post, 0, allocator);
|
||
|
|
|
||
|
|
/* Run DFS across all vertices to guarantee full coverage of disconnected graph structures */
|
||
|
|
for (c_size_t v = 0; v < graph->V; ++v) {
|
||
|
|
if (!self->marked[v]) {
|
||
|
|
c_DepthFirstOrder_DFS(self, graph, v);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
/* C. Build Reverse Post-Order by reading the post-order sequence backwards */
|
||
|
|
c_size_t post_size = (c_size_t)c_VertexIdList_GetSize(&self->post_order);
|
||
|
|
for (c_size_t i = post_size; i > 0; --i) {
|
||
|
|
c_uint_t val = 0;
|
||
|
|
c_err_t err = c_VertexIdList_Get(&self->post_order, i - 1, &val);
|
||
|
|
if (err == C_SUCCESS) {
|
||
|
|
c_VertexIdList_Append(&self->reverse_post, val);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
return C_SUCCESS;
|
||
|
|
}
|
||
|
|
|
||
|
|
void c_DepthFirstOrder_Destroy(c_DepthFirstOrder_t* self) {
|
||
|
|
if (!self) return;
|
||
|
|
if (self->marked) {
|
||
|
|
c_Allocator_Free(&self->allocator, self->marked);
|
||
|
|
self->marked = NULL;
|
||
|
|
}
|
||
|
|
c_VertexIdList_Destroy(&self->pre_order);
|
||
|
|
c_VertexIdList_Destroy(&self->post_order);
|
||
|
|
c_VertexIdList_Destroy(&self->reverse_post);
|
||
|
|
}
|
||
|
|
|
||
|
|
static c_err_t CopyVertexIdList(c_VertexIdList_t* src, c_VertexIdList_t* dest) {
|
||
|
|
if (!src || !dest) return C_ERR_PARAM;
|
||
|
|
c_size_t size = (c_size_t)c_VertexIdList_GetSize((c_VertexIdList_t*)src);
|
||
|
|
for (c_size_t i = 0; i < size; ++i) {
|
||
|
|
c_uint_t val = 0;
|
||
|
|
c_err_t err = c_VertexIdList_Get((c_VertexIdList_t*)src, i, &val);
|
||
|
|
if (err == C_SUCCESS) {
|
||
|
|
c_err_t app_err = c_VertexIdList_Append(dest, val);
|
||
|
|
if (app_err != C_SUCCESS) return app_err;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
return C_SUCCESS;
|
||
|
|
}
|
||
|
|
|
||
|
|
c_err_t c_DepthFirstOrder_GetPre(c_DepthFirstOrder_t* self, c_VertexIdList_t* out_list) {
|
||
|
|
return CopyVertexIdList(&self->pre_order, out_list);
|
||
|
|
}
|
||
|
|
|
||
|
|
c_err_t c_DepthFirstOrder_GetPost(c_DepthFirstOrder_t* self, c_VertexIdList_t* out_list) {
|
||
|
|
return CopyVertexIdList(&self->post_order, out_list);
|
||
|
|
}
|
||
|
|
|
||
|
|
c_err_t c_DepthFirstOrder_GetReversePost(c_DepthFirstOrder_t* self, c_VertexIdList_t* out_list) {
|
||
|
|
return CopyVertexIdList(&self->reverse_post, out_list);
|
||
|
|
}
|