125 lines
4.3 KiB
C
125 lines
4.3 KiB
C
#include "c_FloydWarshall.h"
|
|
#include "c_Test.h"
|
|
#include "c_EdgeWeightedDigraph.h"
|
|
#include "c_FloydWarshall.h"
|
|
|
|
TEST_CASE(test_floyd_warshall_all_pairs) {
|
|
c_EdgeWeightedDigraph_t g;
|
|
c_EdgeWeightedDigraph_Init(&g, 3, NULL);
|
|
|
|
/* Construct an evaluation network:
|
|
* 0 -> 1 (Weight: 3.0)
|
|
* 1 -> 2 (Weight: 1.0)
|
|
* 0 -> 2 (Weight: 5.0) -> Shortest path is 0->1->2 (Total = 4.0)
|
|
*/
|
|
c_EdgeWeightedDigraph_AddEdge(&g, 0, 1, 3.0);
|
|
c_EdgeWeightedDigraph_AddEdge(&g, 1, 2, 1.0);
|
|
c_EdgeWeightedDigraph_AddEdge(&g, 0, 2, 5.0);
|
|
|
|
c_FloydWarshall_t fw;
|
|
c_err_t err = c_FloydWarshall_Init(&fw, &g, &g.allocator);
|
|
ASSERT_INT_EQ(C_SUCCESS, err);
|
|
|
|
ASSERT_FALSE(c_FloydWarshall_HasNegativeCycle(&fw));
|
|
|
|
/* Verify all-pairs queries */
|
|
ASSERT_TRUE(c_FloydWarshall_HasPath(&fw, 0, 2));
|
|
ASSERT_DOUBLE_EQ_MSG(4.0, c_FloydWarshall_Dist(&fw, 0, 2), "All-pairs path minimization failed");
|
|
ASSERT_DOUBLE_EQ_MSG(1.0, c_FloydWarshall_Dist(&fw, 1, 2), "Direct neighbor query mismatch");
|
|
|
|
/* Backward parsing check */
|
|
ASSERT_FALSE(c_FloydWarshall_HasPath(&fw, 2, 0));
|
|
|
|
c_FloydWarshall_Destroy(&fw);
|
|
c_EdgeWeightedDigraph_Destroy(&g);
|
|
}
|
|
|
|
TEST_CASE(test_floyd_warshall_negative_cycle) {
|
|
c_EdgeWeightedDigraph_t g;
|
|
c_EdgeWeightedDigraph_Init(&g, 2, NULL);
|
|
|
|
/* Construct a negative loop */
|
|
c_EdgeWeightedDigraph_AddEdge(&g, 0, 1, 1.0);
|
|
c_EdgeWeightedDigraph_AddEdge(&g, 1, 0, -3.0); /* Cycle total is -2.0 */
|
|
|
|
c_FloydWarshall_t fw;
|
|
c_err_t err = c_FloydWarshall_Init(&fw, &g, &g.allocator);
|
|
ASSERT_INT_EQ(C_SUCCESS, err);
|
|
|
|
ASSERT_TRUE(c_FloydWarshall_HasNegativeCycle(&fw));
|
|
|
|
c_FloydWarshall_Destroy(&fw);
|
|
c_EdgeWeightedDigraph_Destroy(&g);
|
|
}
|
|
|
|
TEST_CASE(test_floyd_warshall_exact_path_extraction) {
|
|
c_EdgeWeightedDigraph_t g;
|
|
c_err_t err = c_EdgeWeightedDigraph_Init(&g, 4, NULL);
|
|
ASSERT_INT_EQ(C_SUCCESS, err);
|
|
|
|
/*
|
|
* Construct an evaluation network topology branch:
|
|
* 0 -> 1 (Weight: 3.0) [Edge ID: 0]
|
|
* 1 -> 2 (Weight: 1.0) [Edge ID: 1]
|
|
* 0 -> 2 (Weight: 6.0) [Edge ID: 2] -> Heavy choice, skipped
|
|
* 2 -> 3 (Weight: 2.0) [Edge ID: 3]
|
|
* True Shortest path from 0 to 3 is: 0 -> 1 -> 2 -> 3 (Total Weight = 3.0 + 1.0 + 2.0 = 6.0)
|
|
*/
|
|
c_EdgeWeightedDigraph_AddEdge(&g, 0, 1, 3.0);
|
|
c_EdgeWeightedDigraph_AddEdge(&g, 1, 2, 1.0);
|
|
c_EdgeWeightedDigraph_AddEdge(&g, 0, 2, 6.0);
|
|
c_EdgeWeightedDigraph_AddEdge(&g, 2, 3, 2.0);
|
|
|
|
c_FloydWarshall_t fw;
|
|
err = c_FloydWarshall_Init(&fw, &g, &g.allocator);
|
|
ASSERT_INT_EQ(C_SUCCESS, err);
|
|
|
|
ASSERT_FALSE(c_FloydWarshall_HasNegativeCycle(&fw));
|
|
ASSERT_TRUE(c_FloydWarshall_HasPath(&fw, 0, 3));
|
|
ASSERT_DOUBLE_EQ_MSG(6.0, c_FloydWarshall_Dist(&fw, 0, 3), "Shortest matrix evaluation total math wrong");
|
|
|
|
/* Create target list to capture path edge tokens */
|
|
c_EdgeIdList_t edge_path;
|
|
c_EdgeIdList_Init(&edge_path,0,0);
|
|
|
|
/* Run the matching signature format */
|
|
err = c_FloydWarshall_Path(&fw, 0, 3, &edge_path);
|
|
ASSERT_INT_EQ(C_SUCCESS, err);
|
|
|
|
/* Expected sequence size should be exactly 3 edge steps long */
|
|
c_size_t path_len = (c_size_t)c_EdgeIdList_GetSize(&edge_path);
|
|
ASSERT_LL_EQ(3, path_len);
|
|
|
|
/* Extract and verify raw edge pool tokens matching forward traversal direction */
|
|
c_uint_t e_id = 0;
|
|
c_EdgeIdList_Get(&edge_path, 0, &e_id); ASSERT_LL_EQ(0, e_id); /* Edge 0 (0->1) */
|
|
c_DirectedEdge_t edge;
|
|
c_EdgeWeightedDigraph_GetEdge(&g, e_id, &edge);
|
|
ASSERT_LL_EQ(0, edge.from);
|
|
ASSERT_LL_EQ(1, edge.to);
|
|
|
|
c_EdgeIdList_Get(&edge_path, 1, &e_id); ASSERT_LL_EQ(1, e_id); /* Edge 1 (1->2) */
|
|
|
|
c_EdgeWeightedDigraph_GetEdge(&g, e_id, &edge);
|
|
ASSERT_LL_EQ(1, edge.from);
|
|
ASSERT_LL_EQ(2, edge.to);
|
|
|
|
c_EdgeIdList_Get(&edge_path, 2, &e_id); ASSERT_LL_EQ(3, e_id); /* Edge 3 (2->3) */
|
|
c_EdgeWeightedDigraph_GetEdge(&g, e_id, &edge);
|
|
ASSERT_LL_EQ(2, edge.from);
|
|
ASSERT_LL_EQ(3, edge.to);
|
|
|
|
c_EdgeIdList_Destroy(&edge_path);
|
|
c_FloydWarshall_Destroy(&fw);
|
|
c_EdgeWeightedDigraph_Destroy(&g);
|
|
}
|
|
|
|
int main(void) {
|
|
TEST_START(FloydWarshall_Matrix_Suite);
|
|
RUN_TEST(test_floyd_warshall_all_pairs);
|
|
RUN_TEST(test_floyd_warshall_negative_cycle);
|
|
RUN_TEST(test_floyd_warshall_exact_path_extraction);
|
|
TEST_REPORT();
|
|
RETURN_TEST_STATUS;
|
|
}
|