57 lines
1.7 KiB
C
57 lines
1.7 KiB
C
|
#include "c_Test.h"
|
||
|
|
#include "c_Digraph.h"
|
||
|
|
#include "c_KosarajuSharirSCC.h"
|
||
|
|
|
||
|
|
TEST_CASE(test_kosaraju_sharir_scc_clustering) {
|
||
|
|
c_Digraph_t g;
|
||
|
|
c_err_t err = c_Digraph_Init(&g, 5, NULL);
|
||
|
|
ASSERT_INT_EQ(C_SUCCESS, err);
|
||
|
|
|
||
|
|
/* Construct a graph topology with 2 separate SCC groups:
|
||
|
|
* Component 1 (Loop group): 0 -> 1 -> 2 -> 0
|
||
|
|
* Bridge link exiting out: 2 -> 3
|
||
|
|
* Component 2 (Loop group): 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 connection */
|
||
|
|
|
||
|
|
c_Digraph_AddEdge(&g, 3, 4);
|
||
|
|
c_Digraph_AddEdge(&g, 4, 3);
|
||
|
|
|
||
|
|
c_KosarajuSharirSCC_t scc;
|
||
|
|
err = c_KosarajuSharirSCC_Init(&scc, &g, 0);
|
||
|
|
ASSERT_INT_EQ(C_SUCCESS, err);
|
||
|
|
|
||
|
|
/* Total strong connected component clusters count must equal exactly 2 */
|
||
|
|
ASSERT_LL_EQ(2, c_KosarajuSharirSCC_GetCount(&scc));
|
||
|
|
|
||
|
|
/* Verify cluster properties (0, 1, 2 must have the exact same group ID) */
|
||
|
|
ASSERT_TRUE(c_KosarajuSharirSCC_StronglyConnected(&scc, 0, 1));
|
||
|
|
ASSERT_TRUE(c_KosarajuSharirSCC_StronglyConnected(&scc, 1, 2));
|
||
|
|
|
||
|
|
/* 3 and 4 must have the exact same group ID */
|
||
|
|
ASSERT_TRUE(c_KosarajuSharirSCC_StronglyConnected(&scc, 3, 4));
|
||
|
|
|
||
|
|
/* Cross verification check (0 and 3 are isolated in different clusters) */
|
||
|
|
ASSERT_FALSE(c_KosarajuSharirSCC_StronglyConnected(&scc, 0, 3));
|
||
|
|
|
||
|
|
c_KosarajuSharirSCC_Destroy(&scc);
|
||
|
|
c_Digraph_Destroy(&g);
|
||
|
|
}
|
||
|
|
|
||
|
|
|
||
|
|
int main(int argc, char** argv){
|
||
|
|
TEST_START(c_NonrecursiveDFS Component Tests);
|
||
|
|
|
||
|
|
// Execution list configurations
|
||
|
|
RUN_TEST(test_kosaraju_sharir_scc_clustering);
|
||
|
|
|
||
|
|
TEST_REPORT();
|
||
|
|
|
||
|
|
RETURN_TEST_STATUS;
|
||
|
|
|
||
|
|
return 0;
|
||
|
|
}
|