[Bug] Adding a simple failing test case for sssp_bfs()

[crazyboycjr]

[Bug] Adding a simple failing test case for sssp_bfs()

[gsliepen]

Hi! Thanks for finding this issue and posting patches. Yes, please create two PRs, one for the test case and one for the fix. Then the CI tests should be run automatically.

[gsliepen]

Thanks again for the patches, they've been merged!

[crazyboycjr]

I have also created a fix for that. The repo seems not having been actively accepting PR recently, so I just post the patch here. @gsliepen let me know if you would like me to send a PR.

diff --git a/src/graph.c b/src/graph.c
index 5a7a16a7..5bec2c16 100644
--- a/src/graph.c
+++ b/src/graph.c
@@ -141,6 +141,7 @@ void sssp_bfs(void) {
 	myself->prevedge = NULL;
 	myself->via = myself;
 	myself->distance = 0;
+	myself->weighted_distance = 0;
 	list_insert_head(todo_list, myself);

 	/* Loop while todo_list is filled */
@@ -178,14 +179,15 @@ void sssp_bfs(void) {

 			if(e->to->status.visited
 			                && (!e->to->status.indirect || indirect)
-			                && (e->to->distance != n->distance + 1 || e->weight >= e->to->prevedge->weight)) {
+			                && (e->to->distance != n->distance + 1 || e->to->weighted_distance <= n->weighted_distance + e->weight)) {
 				continue;
 			}

 			// Only update nexthop if it doesn't increase the path length

-			if(!e->to->status.visited || (e->to->distance == n->distance + 1 && e->weight < e->to->prevedge->weight)) {
+			if(!e->to->status.visited || (e->to->distance == n->distance + 1 && e->to->weighted_distance > n->weighted_distance + e->weight)) {
 				e->to->nexthop = (n->nexthop == myself) ? e->to : n->nexthop;
+				e->to->weighted_distance = n->weighted_distance + e->weight;
 			}

 			e->to->status.visited = true;
diff --git a/src/node.h b/src/node.h
index 51322c25..7d5a0c8c 100644
--- a/src/node.h
+++ b/src/node.h
@@ -76,6 +76,7 @@ typedef struct node_t {
 	compression_level_t outcompression;     /* Compression level, 0 = no compression */

 	int distance;
+	int weighted_distance;
 	struct node_t *nexthop;                 /* nearest node from us to him */
 	struct edge_t *prevedge;                /* nearest node from him to us */
 	struct node_t *via;                     /* next hop for UDP packets */
diff --git a/test/unit/test_graph.c b/test/unit/test_graph.c
index e09f2fcb..e11c8bc7 100644
--- a/test/unit/test_graph.c
+++ b/test/unit/test_graph.c
@@ -26,6 +26,54 @@ static node_t *make_node(const char *name) {
 	return node;
 }

+static void test_sssp_bfs_2(void **state) {
+	(void)state;
+
+	node_t *mars = make_node("mars");
+	node_t *saturn = make_node("saturn");
+	node_t *neptune = make_node("neptune");
+
+	//          1000            500
+	// myself ---------- mars ------------- neptune
+	//      \                              /
+	//       ------- saturn --------------
+	//          50               501
+
+	// Upper route
+	connect_nodes(myself, mars, 1000);
+	connect_nodes(mars, neptune, 500);
+
+	// Lower route
+	connect_nodes(myself, saturn, 50);
+	connect_nodes(saturn, neptune, 501);
+
+	sssp_bfs();
+
+	assert_true(mars->status.visited);
+	assert_true(saturn->status.visited);
+	assert_true(neptune->status.visited);
+
+	assert_false(mars->status.indirect);
+	assert_false(saturn->status.indirect);
+	assert_false(neptune->status.indirect);
+
+	assert_int_equal(1, mars->distance);
+	assert_int_equal(1, saturn->distance);
+	assert_int_equal(2, neptune->distance);
+
+	assert_ptr_equal(mars, mars->nexthop);
+	assert_ptr_equal(saturn, saturn->nexthop);
+	assert_ptr_equal(saturn, neptune->nexthop);
+
+	assert_ptr_equal(lookup_edge(myself, mars), mars->prevedge);
+	assert_ptr_equal(lookup_edge(myself, saturn), saturn->prevedge);
+	assert_ptr_equal(lookup_edge(saturn, neptune), neptune->prevedge);
+
+	assert_ptr_equal(mars, mars->via);
+	assert_ptr_equal(saturn, saturn->via);
+	assert_ptr_equal(neptune, neptune->via);
+}
+
 static void test_sssp_bfs(void **state) {
 	(void)state;

@@ -91,6 +139,7 @@ static int teardown(void **state) {
 int main(void) {
 	const struct CMUnitTest tests[] = {
 		cmocka_unit_test_setup_teardown(test_sssp_bfs, setup, teardown),
+		cmocka_unit_test_setup_teardown(test_sssp_bfs_2, setup, teardown)
 	};
 	return cmocka_run_group_tests(tests, NULL, NULL);
 }