69 lines
2.6 KiB
C
69 lines
2.6 KiB
C
|
#ifndef INCLUDED_C_GABOWSCC_H
|
||
|
|
#define INCLUDED_C_GABOWSCC_H
|
||
|
|
|
||
|
|
#ifndef INCLUDED_C_DIGRAPH_H
|
||
|
|
#include <c_Digraph.h>
|
||
|
|
#endif /*INCLUDED_C_DIGRAPH_H*/
|
||
|
|
|
||
|
|
|
||
|
|
/* ------------------------------------------------------------------------------------------------------------------ */
|
||
|
|
/* */
|
||
|
|
|
||
|
|
typedef struct {
|
||
|
|
c_bool_t* marked; /* Visited tracking array (size of graph->V) */
|
||
|
|
c_size_t* id; /* id[v] = component identifier containing v (0 to count-1) */
|
||
|
|
c_size_t* pre; /* pre[v] = preorder index of vertex v */
|
||
|
|
c_size_t* scc_stack; /* Stack to keep track of vertices in the current SCC candidate */
|
||
|
|
c_size_t scc_stack_sz; /* Size of scc_stack */
|
||
|
|
c_size_t* path_stack; /* Stack to determine root of strongly connected components */
|
||
|
|
c_size_t path_stack_sz;/* Size of path_stack */
|
||
|
|
c_size_t pre_counter; /* Preorder index sequencing counter */
|
||
|
|
c_size_t count; /* Total number of strongly connected components discovered */
|
||
|
|
c_size_t V; /* Stored vertex count for safe boundary check lookups */
|
||
|
|
c_Allocator_t allocator; /* Deep copy of the user-provided allocator */
|
||
|
|
} c_GabowSCC_t;
|
||
|
|
|
||
|
|
/* ------------------------------------------------------------------------------------------------------------------ */
|
||
|
|
/* */
|
||
|
|
|
||
|
|
/**
|
||
|
|
* @brief Computes strongly connected components for the specified digraph using Gabow's algorithm.
|
||
|
|
* @param allocator Explicit allocator context used to allocate internal routing arrays
|
||
|
|
*/
|
||
|
|
c_err_t c_GabowSCC_Init(c_GabowSCC_t* self, c_Digraph_t* graph, c_Allocator_t* allocator);
|
||
|
|
|
||
|
|
/**
|
||
|
|
* @brief Releases internal tracking buffers
|
||
|
|
*/
|
||
|
|
void c_GabowSCC_Destroy(c_GabowSCC_t* self);
|
||
|
|
|
||
|
|
/**
|
||
|
|
* @brief Are vertices 'v' and 'w' strongly connected (belong to the same SCC)?
|
||
|
|
*/
|
||
|
|
C_STATIC_FORCE_INLINE
|
||
|
|
c_bool_t c_GabowSCC_StronglyConnected(c_GabowSCC_t* self, c_size_t v, c_size_t w) {
|
||
|
|
if (!self || !self->id || v >= self->V || w >= self->V) return C_FALSE;
|
||
|
|
return self->id[v] == self->id[w];
|
||
|
|
}
|
||
|
|
|
||
|
|
/**
|
||
|
|
* @brief Returns the component id containing vertex 'v'
|
||
|
|
* @return Component integer ID (0 to count-1), or C_SIZE_MAX on boundary check failures
|
||
|
|
*/
|
||
|
|
C_STATIC_FORCE_INLINE
|
||
|
|
c_size_t c_GabowSCC_GetId(const c_GabowSCC_t* self, c_size_t v) {
|
||
|
|
if (!self || !self->id || v >= self->V) return C_SIZE_MAX;
|
||
|
|
return self->id[v];
|
||
|
|
}
|
||
|
|
|
||
|
|
/**
|
||
|
|
* @brief Returns the total number of strongly connected components
|
||
|
|
*/
|
||
|
|
C_STATIC_FORCE_INLINE
|
||
|
|
c_size_t c_GabowSCC_GetCount(const c_GabowSCC_t* self) {
|
||
|
|
return self ? self->count : 0;
|
||
|
|
}
|
||
|
|
|
||
|
|
|
||
|
|
#endif /*INCLUDED_C_GABOWSCC_H*/
|