64 lines
2.1 KiB
C
64 lines
2.1 KiB
C
|
#include "c_Test.h"
|
||
|
|
#include "c_EdgeWeightedGraph.h"
|
||
|
|
#include "c_DijkstraUndirectedSP.h"
|
||
|
|
#include "c_VertexIdList.h"
|
||
|
|
|
||
|
|
TEST_CASE(test_dijkstra_undirected_paths) {
|
||
|
|
c_EdgeWeightedGraph_t g;
|
||
|
|
c_err_t err = c_EdgeWeightedGraph_Init(&g, 4, NULL);
|
||
|
|
ASSERT_INT_EQ(C_SUCCESS, err);
|
||
|
|
|
||
|
|
/* Construct an undirected graph:
|
||
|
|
* 0 - 1 (Weight: 5.0) [Edge 0]
|
||
|
|
* 0 - 2 (Weight: 1.0) [Edge 1]
|
||
|
|
* 2 - 1 (Weight: 1.0) [Edge 2] -> Path 0-2-1 total is 2.0
|
||
|
|
* 1 - 3 (Weight: 2.0) [Edge 3] -> Path 0-2-1-3 total is 4.0
|
||
|
|
*/
|
||
|
|
c_EdgeWeightedGraph_AddEdge(&g, 0, 1, 5.0);
|
||
|
|
c_EdgeWeightedGraph_AddEdge(&g, 0, 2, 1.0);
|
||
|
|
c_EdgeWeightedGraph_AddEdge(&g, 2, 1, 1.0);
|
||
|
|
c_EdgeWeightedGraph_AddEdge(&g, 1, 3, 2.0);
|
||
|
|
|
||
|
|
c_DijkstraUndirectedSP_t sp;
|
||
|
|
err = c_DijkstraUndirectedSP_Init(&sp, &g, 0, &g.allocator);
|
||
|
|
ASSERT_INT_EQ(C_SUCCESS, err);
|
||
|
|
|
||
|
|
ASSERT_TRUE(c_DijkstraUndirectedSP_HasPathTo(&sp, 3));
|
||
|
|
ASSERT_DOUBLE_EQ_MSG(4.0, c_DijkstraUndirectedSP_DistTo(&sp, 3), "Shortest undirected distance failed");
|
||
|
|
|
||
|
|
c_VertexIdList_t edge_path;
|
||
|
|
c_VertexIdList_Init(&edge_path, 0, 0);
|
||
|
|
|
||
|
|
err = c_DijkstraUndirectedSP_PathTo(&sp, 3, &edge_path);
|
||
|
|
ASSERT_INT_EQ(C_SUCCESS, err);
|
||
|
|
ASSERT_LL_EQ(3, (c_size_t)c_VertexIdList_GetSize(&edge_path));
|
||
|
|
|
||
|
|
c_uint_t e_id = 0;
|
||
|
|
c_VertexIdList_Get(&edge_path, 0, &e_id); ASSERT_LL_EQ(1, e_id); /* Edge 1 (0-2) */
|
||
|
|
c_Edge_t edge;
|
||
|
|
c_EdgeWeightedGraph_GetEdge(&g, e_id, &edge);
|
||
|
|
ASSERT_LL_EQ(0, edge.v);
|
||
|
|
ASSERT_LL_EQ(2, edge.w);
|
||
|
|
c_VertexIdList_Get(&edge_path, 1, &e_id); ASSERT_LL_EQ(2, e_id); /* Edge 2 (2-1) */
|
||
|
|
c_EdgeWeightedGraph_GetEdge(&g, e_id, &edge);
|
||
|
|
ASSERT_LL_EQ(2, edge.v);
|
||
|
|
ASSERT_LL_EQ(1, edge.w);
|
||
|
|
c_VertexIdList_Get(&edge_path, 2, &e_id); ASSERT_LL_EQ(3, e_id); /* Edge 3 (1-3) */
|
||
|
|
c_EdgeWeightedGraph_GetEdge(&g, e_id, &edge);
|
||
|
|
ASSERT_LL_EQ(1, edge.v);
|
||
|
|
ASSERT_LL_EQ(3, edge.w);
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
c_VertexIdList_Destroy(&edge_path);
|
||
|
|
c_DijkstraUndirectedSP_Destroy(&sp);
|
||
|
|
c_EdgeWeightedGraph_Destroy(&g);
|
||
|
|
}
|
||
|
|
|
||
|
|
int main(void) {
|
||
|
|
TEST_START(DijkstraUndirectedSP_Suite);
|
||
|
|
RUN_TEST(test_dijkstra_undirected_paths);
|
||
|
|
TEST_REPORT();
|
||
|
|
RETURN_TEST_STATUS;
|
||
|
|
}
|