49 lines
1.5 KiB
C
49 lines
1.5 KiB
C
|
#include "c_Test.h"
|
||
|
|
#include "c_EdgeWeightedGraph.h"
|
||
|
|
#include "c_PrimMST.h"
|
||
|
|
#include "c_VertexIdList.h"
|
||
|
|
|
||
|
|
TEST_CASE(test_realigned_eager_prim_mst) {
|
||
|
|
c_EdgeWeightedGraph_t g;
|
||
|
|
c_err_t err = c_EdgeWeightedGraph_Init(&g, 4, NULL);
|
||
|
|
ASSERT_INT_EQ(C_SUCCESS, err);
|
||
|
|
|
||
|
|
/* Construct a simple graph topology:
|
||
|
|
* 0 - 1 (Weight: 1.0) -> Picked
|
||
|
|
* 1 - 2 (Weight: 2.0) -> Picked
|
||
|
|
* 2 - 3 (Weight: 3.0) -> Picked
|
||
|
|
* 3 - 0 (Weight: 4.0) -> Skipped
|
||
|
|
* 0 - 2 (Weight: 5.0) -> Skipped
|
||
|
|
*/
|
||
|
|
c_EdgeWeightedGraph_AddEdge(&g, 0, 1, 1.0);
|
||
|
|
c_EdgeWeightedGraph_AddEdge(&g, 1, 2, 2.0);
|
||
|
|
c_EdgeWeightedGraph_AddEdge(&g, 2, 3, 3.0);
|
||
|
|
c_EdgeWeightedGraph_AddEdge(&g, 3, 0, 4.0);
|
||
|
|
c_EdgeWeightedGraph_AddEdge(&g, 0, 2, 5.0);
|
||
|
|
|
||
|
|
c_PrimMST_t prim;
|
||
|
|
err = c_PrimMST_Init(&prim, &g, &g.allocator);
|
||
|
|
ASSERT_INT_EQ(C_SUCCESS, err);
|
||
|
|
|
||
|
|
/* Total summation weight must equal 1.0 + 2.0 + 3.0 = 6.0 */
|
||
|
|
ASSERT_DOUBLE_EQ_MSG(6.0, c_PrimMST_Weight(&prim), "Eager Prim failed to compute correct total MST weight");
|
||
|
|
|
||
|
|
c_VertexIdList_t result_list;
|
||
|
|
c_VertexIdList_Init(&result_list, 0, 0);
|
||
|
|
|
||
|
|
err = c_PrimMST_GetEdges(&prim, &result_list);
|
||
|
|
ASSERT_INT_EQ(C_SUCCESS, err);
|
||
|
|
ASSERT_INT_EQ(3, c_VertexIdList_GetSize(&result_list));
|
||
|
|
|
||
|
|
c_VertexIdList_Destroy(&result_list);
|
||
|
|
c_PrimMST_Destroy(&prim);
|
||
|
|
c_EdgeWeightedGraph_Destroy(&g);
|
||
|
|
}
|
||
|
|
|
||
|
|
int main(void) {
|
||
|
|
TEST_START(EagerPrimMST_FormalIndexPQ_Integration_Suite);
|
||
|
|
RUN_TEST(test_realigned_eager_prim_mst);
|
||
|
|
TEST_REPORT();
|
||
|
|
RETURN_TEST_STATUS;
|
||
|
|
}
|