86 lines
3.4 KiB
C
86 lines
3.4 KiB
C
#include "c_Test.h"
|
|
#include "c_EdgeWeightedGraph.h"
|
|
#include "c_LazyPrimMST.h"
|
|
#include "c_VertexIdList.h"
|
|
|
|
TEST_CASE(test_realigned_lazy_prim_mst) {
|
|
c_EdgeWeightedGraph_t g;
|
|
|
|
/* 1. Initialize an undirected edge-weighted graph with 4 vertices */
|
|
c_err_t err = c_EdgeWeightedGraph_Init(&g, 4, NULL);
|
|
ASSERT_INT_EQ(C_SUCCESS, err);
|
|
ASSERT_LL_EQ(4, c_EdgeWeightedGraph_GetV(&g));
|
|
|
|
/*
|
|
* 2. Build a classic cyclical cycle graph topology to verify tree minimization:
|
|
* 0 - 1 (Weight: 1.0) -> Expected in MST
|
|
* 1 - 2 (Weight: 2.0) -> Expected in MST
|
|
* 2 - 3 (Weight: 3.0) -> Expected in MST
|
|
* 3 - 0 (Weight: 4.0) -> Redundant (heavier cycle closer edge)
|
|
* 0 - 2 (Weight: 5.0) -> Heavy redundant cross-diagonal edge
|
|
*/
|
|
err = c_EdgeWeightedGraph_AddEdge(&g, 0, 1, 1.0); ASSERT_INT_EQ(C_SUCCESS, err);
|
|
err = c_EdgeWeightedGraph_AddEdge(&g, 1, 2, 2.0); ASSERT_INT_EQ(C_SUCCESS, err);
|
|
err = c_EdgeWeightedGraph_AddEdge(&g, 2, 3, 3.0); ASSERT_INT_EQ(C_SUCCESS, err);
|
|
err = c_EdgeWeightedGraph_AddEdge(&g, 3, 0, 4.0); ASSERT_INT_EQ(C_SUCCESS, err);
|
|
err = c_EdgeWeightedGraph_AddEdge(&g, 0, 2, 5.0); ASSERT_INT_EQ(C_SUCCESS, err);
|
|
|
|
ASSERT_LL_EQ(5, c_EdgeWeightedGraph_GetE(&g));
|
|
|
|
/* 3. Compute the Minimum Spanning Tree using our normalized Lazy Prim component */
|
|
c_LazyPrimMST_t prim;
|
|
err = c_LazyPrimMST_Init(&prim, &g, 0);
|
|
ASSERT_INT_EQ(C_SUCCESS, err);
|
|
|
|
/* 4. Total minimal spanning tree weight must sum exactly to 1.0 + 2.0 + 3.0 = 6.0 */
|
|
ASSERT_DOUBLE_EQ_MSG(6.0, c_LazyPrimMST_Weight(&prim), "Lazy Prim failed to compute correct total MST weight");
|
|
|
|
/* 5. Extract tree edge selections and parse structural contents */
|
|
c_VertexIdList_t selected_edges;
|
|
c_VertexIdList_Init(&selected_edges, 0, 0);
|
|
|
|
err = c_LazyPrimMST_GetEdges(&prim, &selected_edges);
|
|
ASSERT_INT_EQ(C_SUCCESS, err);
|
|
|
|
/* A graph with V vertices must span exactly V - 1 edges in its minimal spanning layout */
|
|
c_size_t mst_size = (c_size_t)c_VertexIdList_GetSize(&selected_edges);
|
|
ASSERT_LL_EQ(3, mst_size);
|
|
|
|
/* 6. Verify that our heavier redundant edges (4.0 and 5.0) were skipped */
|
|
double computed_weight_check = 0.0;
|
|
for (c_size_t i = 0; i < mst_size; ++i) {
|
|
c_uint_t generic_edge_id = 0;
|
|
err = c_VertexIdList_Get(&selected_edges, i, &generic_edge_id);
|
|
ASSERT_INT_EQ(C_SUCCESS, err);
|
|
|
|
/* Resolve back via the graph's continuous edge pool layout mapping */
|
|
c_Edge_t* edge = &g.edges_pool[(c_size_t)generic_edge_id];
|
|
double w = c_Edge_Weight(edge);
|
|
|
|
computed_weight_check += w;
|
|
|
|
/* Ensure neither of the heavy loop closures was mistakenly collected */
|
|
ASSERT_TRUE(w < 3.9);
|
|
}
|
|
ASSERT_DOUBLE_EQ_MSG(6.0, computed_weight_check, "Sum of extracted edges does not equal total logged weight");
|
|
|
|
/* 7. Reclaim and safely recycle structural resources */
|
|
c_VertexIdList_Destroy(&selected_edges);
|
|
c_LazyPrimMST_Destroy(&prim);
|
|
c_EdgeWeightedGraph_Destroy(&g);
|
|
}
|
|
|
|
int main(void) {
|
|
/* Fire up the core testing wrapper suite */
|
|
TEST_START(LazyPrimMST_GenericPQ_Integration_Suite);
|
|
|
|
/* Run specified structural plumbing edge cases */
|
|
RUN_TEST(test_realigned_lazy_prim_mst);
|
|
|
|
/* Output summary metrics logs to console */
|
|
TEST_REPORT();
|
|
|
|
/* Unwind system back with proper testing suite status signals */
|
|
RETURN_TEST_STATUS;
|
|
}
|