60 lines
1.9 KiB
C
60 lines
1.9 KiB
C
#include <c_DirectedDFS.h>
|
|
|
|
/* Private recursive engine helper */
|
|
static void c_DirectedDFS_Internal(c_DirectedDFS_t* self, const c_Digraph_t* graph, c_size_t v) {
|
|
self->marked[v] = C_TRUE;
|
|
self->count++;
|
|
|
|
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_size_t w;
|
|
if (c_AdjList_Get(adj, i, &w)!=C_ERR_OK) {
|
|
continue;
|
|
}
|
|
if (!self->marked[w]) {
|
|
c_DirectedDFS_Internal(self, graph, w);
|
|
}
|
|
}
|
|
}
|
|
|
|
c_err_t c_DirectedDFS_Init(c_DirectedDFS_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->count = 0;
|
|
self->marked = (c_bool_t*)c_Allocator_Calloc(&self->allocator, graph->V, sizeof(c_bool_t));
|
|
if (!self->marked) return C_ERR_NOMEM;
|
|
|
|
c_DirectedDFS_Internal(self, graph, s);
|
|
return C_SUCCESS;
|
|
}
|
|
|
|
c_err_t c_DirectedDFS_InitMulti(c_DirectedDFS_t* self, const c_Digraph_t* graph, const c_size_t* sources, c_size_t source_count, c_Allocator_t* allocator) {
|
|
if (!self || !graph || !sources || source_count == 0) return C_ERR_PARAM;
|
|
|
|
self->allocator = allocator?*allocator:c_DefaultAllocator;
|
|
self->count = 0;
|
|
self->marked = (c_bool_t*)c_Allocator_Calloc(&self->allocator, graph->V, sizeof(c_bool_t));
|
|
if (!self->marked) return C_ERR_NOMEM;
|
|
|
|
for (c_size_t i = 0; i < source_count; ++i) {
|
|
c_size_t s = sources[i];
|
|
if (s < graph->V && !self->marked[s]) {
|
|
c_DirectedDFS_Internal(self, graph, s);
|
|
}
|
|
}
|
|
return C_SUCCESS;
|
|
}
|
|
|
|
void c_DirectedDFS_Destroy(c_DirectedDFS_t* self) {
|
|
if (!self) return;
|
|
if (self->marked) {
|
|
c_Allocator_Free(&self->allocator, self->marked);
|
|
self->marked = NULL;
|
|
}
|
|
self->count = 0;
|
|
}
|
|
|