114 lines
3.8 KiB
C
114 lines
3.8 KiB
C
#include <c_BreadthFirstDirectedPaths.h>
|
|
|
|
|
|
c_err_t c_BreadthFirstDirectedPaths_Init(c_BreadthFirstDirectedPaths_t* self, const c_Digraph_t* graph, c_size_t s, c_Allocator_t* allocator) {
|
|
if (!self || !graph || s >= graph->V) return C_ERR_PARAM;
|
|
|
|
self->allocator = allocator ? *allocator : c_DefaultAllocator;
|
|
self->s = s;
|
|
|
|
/* 1. Allocate tracking arrays */
|
|
self->marked = (c_bool_t*)c_Allocator_Calloc(&self->allocator, graph->V, sizeof(c_bool_t));
|
|
if (!self->marked) return C_ERR_NOMEM;
|
|
|
|
self->edge_to = (c_size_t*)c_Allocator_Calloc(&self->allocator, graph->V, sizeof(c_size_t));
|
|
if (!self->edge_to) {
|
|
c_Allocator_Free(&self->allocator, self->marked);
|
|
self->marked = NULL;
|
|
return C_ERR_NOMEM;
|
|
}
|
|
|
|
self->dist_to = (c_size_t*)c_Allocator_Calloc(&self->allocator, graph->V, sizeof(c_size_t));
|
|
if (!self->dist_to) {
|
|
c_Allocator_Free(&self->allocator, self->marked);
|
|
c_Allocator_Free(&self->allocator, self->edge_to);
|
|
self->marked = NULL;
|
|
self->edge_to = NULL;
|
|
return C_ERR_NOMEM;
|
|
}
|
|
|
|
/* 2. Allocate an explicit circular/linear queue layout matching V bounds */
|
|
c_size_t* queue = (c_size_t*)c_Allocator_Calloc(&self->allocator, graph->V, sizeof(c_size_t));
|
|
if (!queue) {
|
|
c_BreadthFirstDirectedPaths_Destroy(self);
|
|
return C_ERR_NOMEM;
|
|
}
|
|
|
|
c_size_t head = 0;
|
|
c_size_t tail = 0;
|
|
|
|
/* Enqueue source */
|
|
self->marked[s] = C_TRUE;
|
|
self->dist_to[s] = 0;
|
|
queue[tail++] = s;
|
|
|
|
/* 3. BFS Main Loop Processing Engine */
|
|
while (head < tail) {
|
|
c_size_t v = queue[head++];
|
|
|
|
c_AdjList_t* adj = &graph->adj_list[v];
|
|
c_size_t size = (c_size_t)c_UIntArray_GetSize(adj);
|
|
|
|
for (c_size_t i = 0; i < size; ++i) {
|
|
c_uint_t target_value = 0;
|
|
/* Safely query edge list element matching pointer specifications */
|
|
c_err_t err = c_UIntArray_Get(adj, i, &target_value);
|
|
|
|
if (err == C_SUCCESS) {
|
|
c_size_t w = (c_size_t)target_value;
|
|
if (!self->marked[w]) {
|
|
self->edge_to[w] = v;
|
|
self->dist_to[w] = self->dist_to[v] + 1;
|
|
self->marked[w] = C_TRUE;
|
|
queue[tail++] = w; /* Enqueue step */
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
c_Allocator_Free(&self->allocator, queue);
|
|
return C_SUCCESS;
|
|
}
|
|
|
|
void c_BreadthFirstDirectedPaths_Destroy(c_BreadthFirstDirectedPaths_t* self) {
|
|
if (!self) return;
|
|
if (self->marked) {
|
|
c_Allocator_Free(&self->allocator, self->marked);
|
|
self->marked = NULL;
|
|
}
|
|
if (self->edge_to) {
|
|
c_Allocator_Free(&self->allocator, self->edge_to);
|
|
self->edge_to = NULL;
|
|
}
|
|
if (self->dist_to) {
|
|
c_Allocator_Free(&self->allocator, self->dist_to);
|
|
self->dist_to = NULL;
|
|
}
|
|
self->s = 0;
|
|
}
|
|
|
|
c_err_t c_BreadthFirstDirectedPaths_PathTo(c_BreadthFirstDirectedPaths_t* self, c_size_t v, c_size_t total_V, c_AdjList_t* out_path) {
|
|
if (!self || !out_path || v >= total_V) return C_ERR_PARAM;
|
|
if (!c_BreadthFirstDirectedPaths_HasPathTo(self, v, total_V)) return C_ERR_FAIL;
|
|
|
|
/* Temporary track trace stack array */
|
|
c_size_t* reverse_stack = (c_size_t*)c_Allocator_Calloc(&self->allocator, total_V, sizeof(c_size_t));
|
|
if (!reverse_stack) return C_ERR_NOMEM;
|
|
|
|
c_size_t stack_size = 0;
|
|
for (c_size_t x = v; x != self->s; x = self->edge_to[x]) {
|
|
reverse_stack[stack_size++] = x;
|
|
}
|
|
reverse_stack[stack_size++] = self->s;
|
|
|
|
c_err_t err = C_SUCCESS;
|
|
while (stack_size > 0) {
|
|
c_size_t current_vertex = reverse_stack[--stack_size];
|
|
err = c_AdjList_Append(out_path, (c_uint_t)current_vertex);
|
|
if (err != C_SUCCESS) break;
|
|
}
|
|
|
|
c_Allocator_Free(&self->allocator, reverse_stack);
|
|
return err;
|
|
}
|