59 lines
1.7 KiB
C
59 lines
1.7 KiB
C
|
#include "c_BreadthFirstDirectedPaths.h"
|
||
|
|
#include "c_Test.h"
|
||
|
|
#include "c_Digraph.h"
|
||
|
|
|
||
|
|
TEST_CASE(test_breadth_first_directed_paths) {
|
||
|
|
c_Digraph_t g;
|
||
|
|
c_Digraph_Init(&g, 4, NULL);
|
||
|
|
|
||
|
|
/* Construct graph with multiple paths to 3:
|
||
|
|
* Path A (Longer): 0 -> 1 -> 2 -> 3
|
||
|
|
* Path B (Shortest): 0 -> 3
|
||
|
|
*/
|
||
|
|
c_Digraph_AddEdge(&g, 0, 1);
|
||
|
|
c_Digraph_AddEdge(&g, 1, 2);
|
||
|
|
c_Digraph_AddEdge(&g, 2, 3);
|
||
|
|
c_Digraph_AddEdge(&g, 0, 3); /* Short-circuit edge directly to 3 */
|
||
|
|
|
||
|
|
c_BreadthFirstDirectedPaths_t bfs_paths;
|
||
|
|
c_err_t err = c_BreadthFirstDirectedPaths_Init(&bfs_paths, &g, 0, &g.allocator);
|
||
|
|
ASSERT_INT_EQ(C_SUCCESS, err);
|
||
|
|
|
||
|
|
/* Assert reachability and verified shortest path metrics */
|
||
|
|
ASSERT_TRUE(c_BreadthFirstDirectedPaths_HasPathTo(&bfs_paths, 3, g.V));
|
||
|
|
ASSERT_LL_EQ(1, c_BreadthFirstDirectedPaths_DistTo(&bfs_paths, 3, g.V)); /* Distance must be exactly 1 edge */
|
||
|
|
|
||
|
|
c_VertexIdList_t final_path;
|
||
|
|
c_VertexIdList_Init(&final_path, 0, NULL);
|
||
|
|
|
||
|
|
err = c_BreadthFirstDirectedPaths_PathTo(&bfs_paths, 3, g.V, &final_path);
|
||
|
|
ASSERT_INT_EQ(C_SUCCESS, err);
|
||
|
|
|
||
|
|
/* Path size should be 2 for the short circuit route: [0, 3] */
|
||
|
|
ASSERT_INT_EQ(2, c_VertexIdList_GetSize(&final_path));
|
||
|
|
|
||
|
|
c_uint_t val = 0;
|
||
|
|
c_VertexIdList_Get(&final_path, 0, &val);
|
||
|
|
ASSERT_LL_EQ(0, val);
|
||
|
|
|
||
|
|
c_VertexIdList_Get(&final_path, 1, &val);
|
||
|
|
ASSERT_LL_EQ(3, val);
|
||
|
|
|
||
|
|
c_VertexIdList_Destroy(&final_path);
|
||
|
|
c_BreadthFirstDirectedPaths_Destroy(&bfs_paths);
|
||
|
|
c_Digraph_Destroy(&g);
|
||
|
|
}
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
int main(int argc, char** argv){
|
||
|
|
TEST_START(Component Tests);
|
||
|
|
|
||
|
|
// Execution list configurations
|
||
|
|
RUN_TEST(test_breadth_first_directed_paths);
|
||
|
|
|
||
|
|
TEST_REPORT();
|
||
|
|
|
||
|
|
RETURN_TEST_STATUS;
|
||
|
|
}
|