128 lines
3.8 KiB
C
128 lines
3.8 KiB
C
#include <c_DepthFirstSearch.h>
|
|
|
|
|
|
// Internal deep structural trace walker running down stack frames
|
|
static void c_DFS_Internal(c_DepthFirstSearch_t* self, const c_Graph_t* G, c_size_t v) {
|
|
self->marked[v] = C_TRUE;
|
|
self->count++;
|
|
|
|
const c_AdjList_t* list = c_Graph_GetAdjList((c_Graph_t*)G, v);
|
|
if (!list) return;
|
|
|
|
// High cache-locality contiguous array iteration scan
|
|
for (c_size_t i = 0; i < list->size; i++) {
|
|
c_uint_t w = list->array[i];
|
|
if (!self->marked[w]) {
|
|
self->edge_to[w] = v; // Trace trace track back identity path
|
|
c_DFS_Internal(self, G, w);
|
|
}
|
|
}
|
|
}
|
|
|
|
c_err_t c_DepthFirstSearch_Init(c_DepthFirstSearch_t* self, const c_Graph_t* G, c_size_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 continuous block space arrays
|
|
self->marked = (c_bool_t*)c_Allocator_Alloc(&self->allocator, G->V * sizeof(c_bool_t));
|
|
self->edge_to = (c_size_t*)c_Allocator_Alloc(&self->allocator, G->V * sizeof(c_size_t));
|
|
|
|
if (!self->marked || !self->edge_to) {
|
|
c_DepthFirstSearch_Destroy(self);
|
|
return C_ERR_NOMEM;
|
|
}
|
|
|
|
// Zero out buffers initialization
|
|
memset(self->marked, 0, G->V * sizeof(c_bool_t));
|
|
for (c_size_t i = 0; i < G->V; i++) {
|
|
self->edge_to[i] = G->V; // Use G->V dimension size integer as path sentinel
|
|
}
|
|
|
|
// Run structural execution tracing
|
|
c_DFS_Internal(self, G, s);
|
|
|
|
return C_SUCCESS;
|
|
}
|
|
|
|
void c_DepthFirstSearch_Destroy(c_DepthFirstSearch_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_DepthFirstSearch_HasPathTo(const c_DepthFirstSearch_t* self, c_size_t v) {
|
|
if (!self || !self->marked) {
|
|
return C_FALSE;
|
|
}
|
|
return self->marked[v];
|
|
}
|
|
|
|
c_size_t c_DepthFirstSearch_Count(const c_DepthFirstSearch_t* self) {
|
|
if (!self) return 0;
|
|
return self->count;
|
|
}
|
|
|
|
c_err_t c_DepthFirstSearch_PathTo(const c_DepthFirstSearch_t* self, c_size_t v, c_VertexIdList_t* path) {
|
|
if (!self || !path) {
|
|
return C_ERR_PARAM;
|
|
}
|
|
|
|
// Step 1: Invariant validation check - verify if a real route mapping path exists
|
|
if (!c_DepthFirstSearch_HasPathTo(self, v)) {
|
|
return C_ERR_FAIL;
|
|
}
|
|
|
|
// Ensure the output container list starts completely empty
|
|
path->size = 0;
|
|
|
|
// Step 2: Backtrack from destination 'v' to root 'source' using edge_to routes
|
|
c_size_t current = v;
|
|
while (current != self->source) {
|
|
c_err_t err = c_VertexIdList_Append(path, (c_uint_t)current);
|
|
if (err != C_SUCCESS) {
|
|
path->size = 0; // Reset allocation sequence tracks on failure
|
|
return err;
|
|
}
|
|
current = self->edge_to[current];
|
|
}
|
|
|
|
// Append the starting source root identity node to close the tracking frame
|
|
c_err_t err = c_VertexIdList_Append(path, (c_uint_t)self->source);
|
|
if (err != C_SUCCESS) {
|
|
path->size = 0;
|
|
return err;
|
|
}
|
|
|
|
// Step 3: Mirror inversion optimization step.
|
|
// Because backtracking collects indices in reverse order (v -> source),
|
|
// we reverse the array to restore a chronological (source -> v) pipeline format.
|
|
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;
|
|
}
|