cKit/Graph/c_FloydWarshall.t.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;
}