#include "c_Test.h"
#include "c_EdgeWeightedDigraph.h"
#include "c_BellmanFordSP.h"

TEST_CASE(test_bellman_ford_shortest_path_negative_weights) {
    c_EdgeWeightedDigraph_t g;
    c_EdgeWeightedDigraph_Init(&g, 4, NULL);

    /* Construct a graph with negative weights but NO negative cycles:
     * 0 -> 1 (Weight:  5.0)
     * 0 -> 2 (Weight:  2.0)
     * 2 -> 1 (Weight: -4.0) -> Shortest path to 1 is 0->2->1 (Total: -2.0)
     * 1 -> 3 (Weight:  3.0) -> Shortest path to 3 is 0->2->1->3 (Total: 1.0)
     */
    c_EdgeWeightedDigraph_AddEdge(&g, 0, 1,  5.0);
    c_EdgeWeightedDigraph_AddEdge(&g, 0, 2,  2.0);
    c_EdgeWeightedDigraph_AddEdge(&g, 2, 1, -4.0);
    c_EdgeWeightedDigraph_AddEdge(&g, 1, 3,  3.0);

    c_BellmanFordSP_t sp;
    c_err_t err = c_BellmanFordSP_Init(&sp, &g, 0, &g.allocator);
    ASSERT_INT_EQ(C_SUCCESS, err);

    ASSERT_FALSE(c_BellmanFordSP_HasNegativeCycle(&sp));
    ASSERT_TRUE(c_BellmanFordSP_HasPathTo(&sp, 3));
    ASSERT_DOUBLE_EQ_MSG(-2.0, c_BellmanFordSP_DistTo(&sp, 1), "Shortest path to 1 wrong");
    ASSERT_DOUBLE_EQ_MSG(1.0,  c_BellmanFordSP_DistTo(&sp, 3), "Shortest path to 3 wrong");

    c_BellmanFordSP_Destroy(&sp);
    c_EdgeWeightedDigraph_Destroy(&g);
}

TEST_CASE(test_bellman_ford_negative_cycle_detection) {
    c_EdgeWeightedDigraph_t g;
    c_EdgeWeightedDigraph_Init(&g, 3, NULL);

    /* Construct a graph with a negative cycle loop:
     * 0 -> 1 (Weight:  2.0)
     * 1 -> 2 (Weight: -1.0)
     * 2 -> 1 (Weight: -2.0) -> Cycle 1->2->1 has total weight -3.0 (Negative Cycle!)
     */
    c_EdgeWeightedDigraph_AddEdge(&g, 0, 1,  2.0);
    c_EdgeWeightedDigraph_AddEdge(&g, 1, 2, -1.0);
    c_EdgeWeightedDigraph_AddEdge(&g, 2, 1, -2.0);

    c_BellmanFordSP_t sp;
    c_err_t err = c_BellmanFordSP_Init(&sp, &g, 0, &g.allocator);
    ASSERT_INT_EQ(C_SUCCESS, err);

    /* The negative cycle must be caught successfully */
    ASSERT_TRUE(c_BellmanFordSP_HasNegativeCycle(&sp));

    c_VertexIdList_t cycle_loop;
    c_VertexIdList_Init(&cycle_loop, 0, 0);
    err = c_BellmanFordSP_GetNegativeCycle(&sp, &cycle_loop);
    ASSERT_INT_EQ(C_SUCCESS, err);
    ASSERT_TRUE(c_VertexIdList_GetSize(&cycle_loop) > 0);

    c_VertexIdList_Destroy(&cycle_loop);
    c_BellmanFordSP_Destroy(&sp);
    c_EdgeWeightedDigraph_Destroy(&g);
}

int main(void) {
    TEST_START(BellmanFordSP_Engine_Suite);
    RUN_TEST(test_bellman_ford_shortest_path_negative_weights);
    RUN_TEST(test_bellman_ford_negative_cycle_detection);
    TEST_REPORT();
    RETURN_TEST_STATUS;
}