78 lines
2.8 KiB
C
78 lines
2.8 KiB
C
|
#include "c_Test.h"
|
||
|
|
#include "c_Digraph.h"
|
||
|
|
#include "c_NonrecursiveTarjanSCC.h"
|
||
|
|
|
||
|
|
TEST_CASE(test_tarjan_scc_with_internal_v_bounds) {
|
||
|
|
c_Digraph_t g;
|
||
|
|
|
||
|
|
/* 1. Initialize a directed graph with 5 vertices using default allocator */
|
||
|
|
c_err_t err = c_Digraph_Init(&g, 5, NULL);
|
||
|
|
ASSERT_INT_EQ(C_SUCCESS, err);
|
||
|
|
|
||
|
|
/*
|
||
|
|
* 2. Construct a topology containing 2 separate SCC groups:
|
||
|
|
* Component 1 (Cyclic Loop): 0 -> 1 -> 2 -> 0
|
||
|
|
* Exit Bridge Connection: 2 -> 3
|
||
|
|
* Component 2 (Cyclic Loop): 3 -> 4 -> 3
|
||
|
|
*/
|
||
|
|
c_Digraph_AddEdge(&g, 0, 1);
|
||
|
|
c_Digraph_AddEdge(&g, 1, 2);
|
||
|
|
c_Digraph_AddEdge(&g, 2, 0);
|
||
|
|
|
||
|
|
c_Digraph_AddEdge(&g, 2, 3); /* Bridge edge crossing components */
|
||
|
|
|
||
|
|
c_Digraph_AddEdge(&g, 3, 4);
|
||
|
|
c_Digraph_AddEdge(&g, 4, 3);
|
||
|
|
|
||
|
|
/* 3. Initialize Tarjan's solver (passing graph's inner allocator wrapper) */
|
||
|
|
c_NonrecursiveTarjanSCC_t scc;
|
||
|
|
err = c_NonrecursiveTarjanSCC_Init(&scc, &g, NULL);
|
||
|
|
ASSERT_INT_EQ(C_SUCCESS, err);
|
||
|
|
|
||
|
|
/* 4. Validate that exactly 2 distinct strong component groups are captured */
|
||
|
|
c_size_t scc_count = c_NonrecursiveTarjanSCC_GetCount(&scc);
|
||
|
|
ASSERT_LL_EQ(2, scc_count);
|
||
|
|
|
||
|
|
/* 5. Verify connectivity identities using your sleek inline signatures */
|
||
|
|
/* Vertices 0, 1, and 2 should share identical cluster mapping configurations */
|
||
|
|
ASSERT_TRUE(c_NonrecursiveTarjanSCC_StronglyConnected(&scc, 0, 1));
|
||
|
|
ASSERT_TRUE(c_NonrecursiveTarjanSCC_StronglyConnected(&scc, 1, 2));
|
||
|
|
ASSERT_TRUE(c_NonrecursiveTarjanSCC_StronglyConnected(&scc, 0, 2));
|
||
|
|
|
||
|
|
/* Vertices 3 and 4 should be mapped to the exact same cluster ID */
|
||
|
|
ASSERT_TRUE(c_NonrecursiveTarjanSCC_StronglyConnected(&scc, 3, 4));
|
||
|
|
|
||
|
|
/* Vertices 0 and 3 should be structurally separate */
|
||
|
|
ASSERT_FALSE(c_NonrecursiveTarjanSCC_StronglyConnected(&scc, 0, 3));
|
||
|
|
|
||
|
|
/* 6. Validate safe ID extraction limits via c_NonrecursiveTarjanSCC_GetId */
|
||
|
|
c_size_t id_0 = c_NonrecursiveTarjanSCC_GetId(&scc, 0);
|
||
|
|
c_size_t id_3 = c_NonrecursiveTarjanSCC_GetId(&scc, 3);
|
||
|
|
|
||
|
|
ASSERT_TRUE(id_0 != C_SIZE_MAX);
|
||
|
|
ASSERT_TRUE(id_3 != C_SIZE_MAX);
|
||
|
|
ASSERT_TRUE(id_0 != id_3); /* Component IDs must be uniquely distinct */
|
||
|
|
|
||
|
|
/* Verify that bounds protection prevents out-of-bounds index corruption */
|
||
|
|
c_size_t invalid_id = c_NonrecursiveTarjanSCC_GetId(&scc, 99);
|
||
|
|
ASSERT_LL_EQ(C_SIZE_MAX, invalid_id);
|
||
|
|
|
||
|
|
/* 7. Free and recycle array components tracking states safely */
|
||
|
|
c_NonrecursiveTarjanSCC_Destroy(&scc);
|
||
|
|
c_Digraph_Destroy(&g);
|
||
|
|
}
|
||
|
|
|
||
|
|
int main(void) {
|
||
|
|
/* Bootstrapping test environment wrapper */
|
||
|
|
TEST_START(TarjanSCC_Refactored_Internal_V_Tests);
|
||
|
|
|
||
|
|
/* Run specified edge cases */
|
||
|
|
RUN_TEST(test_tarjan_scc_with_internal_v_bounds);
|
||
|
|
|
||
|
|
/* Generate total logging matrix summaries sheet */
|
||
|
|
TEST_REPORT();
|
||
|
|
|
||
|
|
/* Unwind tracking status frames code signals */
|
||
|
|
RETURN_TEST_STATUS;
|
||
|
|
}
|