59 lines
1.8 KiB
C
59 lines
1.8 KiB
C
|
#include "c_Cycle.h"
|
||
|
|
#include "c_Test.h"
|
||
|
|
#include <stdlib.h>
|
||
|
|
#include <stdio.h>
|
||
|
|
|
||
|
|
TEST_CASE(test_c_cycle_detection) {
|
||
|
|
// Test Scenario A: Acyclic Graph (Tree structure: 0-1, 1-2, 1-3)
|
||
|
|
c_Graph_t g_tree;
|
||
|
|
c_Graph_Init(&g_tree, 4, 0);
|
||
|
|
c_Graph_AddEdge(&g_tree, 0, 1);
|
||
|
|
c_Graph_AddEdge(&g_tree, 1, 2);
|
||
|
|
c_Graph_AddEdge(&g_tree, 1, 3);
|
||
|
|
|
||
|
|
c_Cycle_t finder1;
|
||
|
|
c_err_t err = c_Cycle_Init(&finder1, &g_tree, 0);
|
||
|
|
ASSERT_INT_EQ(C_SUCCESS, err);
|
||
|
|
ASSERT_FALSE(c_Cycle_HasCycle(&finder1)); // Tree has no cycle
|
||
|
|
ASSERT_LL_EQ(0, c_Cycle_Path(&finder1)->size);
|
||
|
|
|
||
|
|
// Test Scenario B: Cyclic Graph (Triangle network: 0-1, 1-2, 2-0)
|
||
|
|
c_Graph_t g_cyclic;
|
||
|
|
c_Graph_Init(&g_cyclic, 3, 0);
|
||
|
|
c_Graph_AddEdge(&g_cyclic, 0, 1);
|
||
|
|
c_Graph_AddEdge(&g_cyclic, 1, 2);
|
||
|
|
c_Graph_AddEdge(&g_cyclic, 2, 0);
|
||
|
|
|
||
|
|
c_Cycle_t finder2;
|
||
|
|
err = c_Cycle_Init(&finder2, &g_cyclic, 0);
|
||
|
|
ASSERT_INT_EQ(C_SUCCESS, err);
|
||
|
|
ASSERT_TRUE(c_Cycle_HasCycle(&finder2)); // Must flag true
|
||
|
|
|
||
|
|
// Verify properties of the closed cycle path trail
|
||
|
|
const c_VertexIdList_t* path = c_Cycle_Path(&finder2);
|
||
|
|
ASSERT_PTR_NOT_NULL(path);
|
||
|
|
ASSERT_TRUE(path->size == 4); // Closed triangle sequence holds 4 indices: e.g. 0 -> 1 -> 2 -> 0
|
||
|
|
|
||
|
|
c_uint_t start_node, end_node;
|
||
|
|
c_VertexIdList_Get((c_VertexIdList_t*)path, 0, &start_node);
|
||
|
|
c_VertexIdList_Get((c_VertexIdList_t*)path, path->size - 1, &end_node);
|
||
|
|
ASSERT_LL_EQ(start_node, end_node); // Path must wrap back to start element
|
||
|
|
|
||
|
|
c_Cycle_Destroy(&finder1);
|
||
|
|
c_Cycle_Destroy(&finder2);
|
||
|
|
c_Graph_Destroy(&g_tree);
|
||
|
|
c_Graph_Destroy(&g_cyclic);
|
||
|
|
}
|
||
|
|
|
||
|
|
|
||
|
|
int main(int argc, char** argv){
|
||
|
|
TEST_START(Component Tests);
|
||
|
|
|
||
|
|
// Execution list configurations
|
||
|
|
RUN_TEST(test_c_cycle_detection);
|
||
|
|
|
||
|
|
TEST_REPORT();
|
||
|
|
|
||
|
|
RETURN_TEST_STATUS;
|
||
|
|
}
|