102 lines
3.3 KiB
C
102 lines
3.3 KiB
C
|
#include <c_KosarajuSharirSCC.h>
|
||
|
|
#include "c_DepthFirstOrder.h"
|
||
|
|
|
||
|
|
/* Private recursive DFS engine helper subroutine for the second pass grouping */
|
||
|
|
static void c_KosarajuSharirSCC_DFS(c_KosarajuSharirSCC_t* self, const c_Digraph_t* graph, c_size_t v) {
|
||
|
|
self->marked[v] = C_TRUE;
|
||
|
|
self->id[v] = 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_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_KosarajuSharirSCC_DFS(self, graph, w);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
c_err_t c_KosarajuSharirSCC_Init(c_KosarajuSharirSCC_t* self, c_Digraph_t* graph, c_Allocator_t* allocator) {
|
||
|
|
if (!self || !graph || graph->V==0) return C_ERR_PARAM;
|
||
|
|
|
||
|
|
self->allocator = allocator ? *allocator : c_DefaultAllocator;
|
||
|
|
self->count = 0;
|
||
|
|
self->V = graph->V;
|
||
|
|
|
||
|
|
/* 1. Allocate primary tracking mapping buffers */
|
||
|
|
self->marked = (c_bool_t*)c_Allocator_Calloc(&self->allocator, graph->V, sizeof(c_bool_t));
|
||
|
|
self->id = (c_size_t*)c_Allocator_Calloc(&self->allocator, graph->V, sizeof(c_size_t));
|
||
|
|
if (!self->marked || !self->id) {
|
||
|
|
c_KosarajuSharirSCC_Destroy(self);
|
||
|
|
return C_ERR_NOMEM;
|
||
|
|
}
|
||
|
|
|
||
|
|
/* 2. First Pass: Compute reverse post-order stream on the transposed/reversed graph */
|
||
|
|
c_Digraph_t transposed;
|
||
|
|
c_err_t err = c_Digraph_Reverse(graph, &transposed);
|
||
|
|
if (err != C_SUCCESS) {
|
||
|
|
c_KosarajuSharirSCC_Destroy(self);
|
||
|
|
return err;
|
||
|
|
}
|
||
|
|
|
||
|
|
c_DepthFirstOrder_t dfs_order;
|
||
|
|
err = c_DepthFirstOrder_Init(&dfs_order, &transposed, allocator);
|
||
|
|
if (err != C_SUCCESS) {
|
||
|
|
c_Digraph_Destroy(&transposed);
|
||
|
|
c_KosarajuSharirSCC_Destroy(self);
|
||
|
|
return err;
|
||
|
|
}
|
||
|
|
|
||
|
|
c_VertexIdList_t rev_post_order;
|
||
|
|
c_VertexIdList_Init(&rev_post_order,0, allocator);
|
||
|
|
err = c_DepthFirstOrder_GetReversePost(&dfs_order, &rev_post_order);
|
||
|
|
|
||
|
|
/* Clean up the working transposed graph and its intermediate state variables */
|
||
|
|
c_DepthFirstOrder_Destroy(&dfs_order);
|
||
|
|
c_Digraph_Destroy(&transposed);
|
||
|
|
|
||
|
|
if (err != C_SUCCESS) {
|
||
|
|
c_VertexIdList_Destroy(&rev_post_order);
|
||
|
|
c_KosarajuSharirSCC_Destroy(self);
|
||
|
|
return err;
|
||
|
|
}
|
||
|
|
|
||
|
|
/* 3. Second Pass: Run standard DFS tracking on original graph using the reverse post-order sequence */
|
||
|
|
c_size_t sequence_len = (c_size_t)c_VertexIdList_GetSize(&rev_post_order);
|
||
|
|
for (c_size_t i = 0; i < sequence_len; ++i) {
|
||
|
|
c_uint_t vertex_val = 0;
|
||
|
|
err = c_VertexIdList_Get(&rev_post_order, i, &vertex_val);
|
||
|
|
|
||
|
|
if (err == C_SUCCESS) {
|
||
|
|
c_size_t v = (c_size_t)vertex_val;
|
||
|
|
if (!self->marked[v]) {
|
||
|
|
c_KosarajuSharirSCC_DFS(self, graph, v);
|
||
|
|
self->count++; /* Advance component ID group grouping */
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
c_VertexIdList_Destroy(&rev_post_order);
|
||
|
|
return C_SUCCESS;
|
||
|
|
}
|
||
|
|
|
||
|
|
void c_KosarajuSharirSCC_Destroy(c_KosarajuSharirSCC_t* self) {
|
||
|
|
if (!self) return;
|
||
|
|
if (self->marked) {
|
||
|
|
c_Allocator_Free(&self->allocator, self->marked);
|
||
|
|
self->marked = NULL;
|
||
|
|
}
|
||
|
|
if (self->id) {
|
||
|
|
c_Allocator_Free(&self->allocator, self->id);
|
||
|
|
self->id = NULL;
|
||
|
|
}
|
||
|
|
self->count = 0;
|
||
|
|
self->V = 0;
|
||
|
|
}
|