aga,agar: Non-equal edge costs for parallel test graph

At the moment the "parallel" test graph just uses the default cost of 1
for all the links between the two nodes.  This patch changes that so that
the links have cost 2, except (optionally) one with cost 1.  This provides
a useful test for the Dijkstra's algorithm implementation to ensure that
it picks the correct link for the shortest path.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>

diff --git a/ccan/aga/test/api-adjacency.c b/ccan/aga/test/api-adjacency.c
index 5e9bac22db9c9c4ccc0b0eff445f06d643c12967..22126003f13cfa62781806a3ef0be71cfee9e54a 100644 (file)
--- a/ccan/aga/test/api-adjacency.c
+++ b/ccan/aga/test/api-adjacency.c
@@ -67,7 +67,7 @@ int main(void)
        trivial_graph_init(&tg);
        test_adjacency("trivial", &tg.sg, trivial_adjacency);
 
-       parallel_graph_init(&pg, 3);
+       parallel_graph_init(&pg, 3, 0);
        test_adjacency("parallel nlinks 3", &pg.sg,
                       parallel_adjacency_nlinks3);
 

diff --git a/ccan/aga/test/api-bfs.c b/ccan/aga/test/api-bfs.c
index e59c75686fed1495f8817683f420dc32e3e35e62..90fcc62853887595093ce9fff22cc055124d2f23 100644 (file)
--- a/ccan/aga/test/api-bfs.c
+++ b/ccan/aga/test/api-bfs.c
@@ -49,7 +49,7 @@ int main(void)
        trivial_graph_init(&tg);
        test_bfs(&tg.sg, 1, 1);
 
-       parallel_graph_init(&pg, 3);
+       parallel_graph_init(&pg, 3, 0);
        test_bfs(&pg.sg, 1, 1, 2);
 
        full_graph_init(&fg, 5);

diff --git a/ccan/aga/test/api-dfs.c b/ccan/aga/test/api-dfs.c
index 8ab15914e82c034ffc8c669af480df17ceb23cdf..24d1a4f912078551fbb9faa0161e047fc88f2ef5 100644 (file)
--- a/ccan/aga/test/api-dfs.c
+++ b/ccan/aga/test/api-dfs.c
@@ -49,7 +49,7 @@ int main(void)
        trivial_graph_init(&tg);
        test_dfs(&tg.sg, 1, 1);
 
-       parallel_graph_init(&pg, 3);
+       parallel_graph_init(&pg, 3, 0);
        test_dfs(&pg.sg, 1, 1, 2);
 
        full_graph_init(&fg, 5);

diff --git a/ccan/aga/test/api-dijkstra.c b/ccan/aga/test/api-dijkstra.c
index 08b472884728904fb99d53606cc6479d3451b1fa..9be747d976e9f671b3fb5865f77c98c3e6884ff4 100644 (file)
--- a/ccan/aga/test/api-dijkstra.c
+++ b/ccan/aga/test/api-dijkstra.c
@@ -35,8 +35,9 @@ static void test_parallel(void)
        struct parallel_graph pg;
        aga_icost_t cost;
        struct aga_node *node;
+       const void *edge;
 
-       parallel_graph_init(&pg, 3);
+       parallel_graph_init(&pg, 3, 0);
 
        ok1(aga_dijkstra_start(&pg.sg.g, &pg.sg.nodes[1]) == 0);
        ok1(aga_dijkstra_step(&pg.sg.g) == &pg.sg.nodes[1]);
@@ -45,7 +46,7 @@ static void test_parallel(void)
        ok1(aga_dijkstra_path(&pg.sg.g, &pg.sg.nodes[1], &cost, NULL, NULL));
        ok1(cost == 0);
        ok1(aga_dijkstra_path(&pg.sg.g, &pg.sg.nodes[2], &cost, &node, NULL));
-       ok1(cost == 1);
+       ok1(cost == 2);
        ok1(node == &pg.sg.nodes[1]);
        aga_finish(&pg.sg.g);
 
@@ -56,6 +57,15 @@ static void test_parallel(void)
        ok1(cost == 0);
        ok1(!aga_dijkstra_path(&pg.sg.g, &pg.sg.nodes[1], NULL, NULL, NULL));
        aga_finish(&pg.sg.g);
+
+
+       parallel_graph_init(&pg, 3, 2);
+       ok1(aga_dijkstra_start(&pg.sg.g, &pg.sg.nodes[1]) == 0);
+       ok1(aga_dijkstra_path(&pg.sg.g, &pg.sg.nodes[2], &cost, &node, &edge));
+       ok1(cost == 1);
+       ok1(node == &pg.sg.nodes[1]);
+       ok1(ptr2int(edge) == 2);
+       aga_finish(&pg.sg.g);
 }
 
 #define FULL_LEN       4
@@ -206,7 +216,7 @@ static void test_traversal1(void)
 
 int main(void)
 {
-       plan_tests(7 + 15
+       plan_tests(7 + 20
                   + FULL_LEN * (1 + FULL_LEN*4)
                   + CHAIN_LEN * (1 + CHAIN_LEN*2)
                   + 12 + 32);

diff --git a/ccan/aga/test/parallel.c b/ccan/aga/test/parallel.c
index 997280bc24ec964b57c2fdaf3ed674d13f5a9969..bea951122b221e4a8275312253738ecd0a392fc8 100644 (file)
--- a/ccan/aga/test/parallel.c
+++ b/ccan/aga/test/parallel.c
@@ -50,12 +50,17 @@ static int parallel_edge_info(const struct aga_graph *g, const struct aga_node *
        assert(n == &pg->sg.nodes[1]);
 
        ei->to = &pg->sg.nodes[2];
+       if (ptr2int(edge) == pg->cheaplink)
+               ei->icost = 1;
+       else
+               ei->icost = 2;
        return 0;
 }
 
-void parallel_graph_init(struct parallel_graph *pg, int nlinks)
+void parallel_graph_init(struct parallel_graph *pg, int nlinks, int cheaplink)
 {
        pg->nlinks = nlinks;
+       pg->cheaplink = cheaplink;
 
        simple_graph_init(&pg->sg, parallel_first_edge, parallel_next_edge,
                          parallel_edge_info);

diff --git a/ccan/aga/test/simple-graph.h b/ccan/aga/test/simple-graph.h
index 3f4f9acc767121da1ac4a5c25e969770365b22b8..57f87a881cc38961b28d2eccfb9787aa76752956 100644 (file)
--- a/ccan/aga/test/simple-graph.h
+++ b/ccan/aga/test/simple-graph.h
@@ -52,9 +52,10 @@ static const struct adjacency_list trivial_adjacency[] = {
  */
 struct parallel_graph {
        int nlinks;
+       int cheaplink;
        struct simple_graph sg;
 };
-void parallel_graph_init(struct parallel_graph *pg, int nlinks);
+void parallel_graph_init(struct parallel_graph *pg, int nlinks, int cheaplink);
 static const struct adjacency_list parallel_adjacency_nlinks3[] = {
        {1, {2, 2, 2}},
        {2, {}},

diff --git a/ccan/agar/test/api-adjacency.c b/ccan/agar/test/api-adjacency.c
index c17ead55e3ae7631fcabda93a76b2d8573eb44c9..469cd83e443e29e0d08f940a64781f8ef95ddfee 100644 (file)
--- a/ccan/agar/test/api-adjacency.c
+++ b/ccan/agar/test/api-adjacency.c
@@ -61,7 +61,7 @@ int main(void)
        trivial_graphr_init(&tgr);
        test_adjacency("trivial", &tgr.gr, trivial_adjacencyr);
 
-       parallel_graphr_init(&pgr, 3);
+       parallel_graphr_init(&pgr, 3, 0);
        test_adjacency("parallel nlinks 3", &pgr.gr,
                       parallel_adjacencyr_nlinks3);
 

diff --git a/ccan/agar/test/api-bfs.c b/ccan/agar/test/api-bfs.c
index 8823df8c38b67cdf2141a08f0d133cd9a86c0b25..fae0f8455e6f3cfc8bdb4398c741774b5e2d7223 100644 (file)
--- a/ccan/agar/test/api-bfs.c
+++ b/ccan/agar/test/api-bfs.c
@@ -53,7 +53,7 @@ int main(void)
        trivial_graphr_init(&tgr);
        test_bfs(&tgr.gr, 1, 1);
 
-       parallel_graphr_init(&pgr, 3);
+       parallel_graphr_init(&pgr, 3, 0);
        test_bfs(&pgr.gr, 1, 1, 2);
 
        full_graphr_init(&fgr, 5);

diff --git a/ccan/agar/test/api-dfs.c b/ccan/agar/test/api-dfs.c
index 2a7e4ceaed16cb899117f98fbd9ea6b99c0d810d..ecc05bd744d495d8c9c82be7c13ef5d1cba88011 100644 (file)
--- a/ccan/agar/test/api-dfs.c
+++ b/ccan/agar/test/api-dfs.c
@@ -53,7 +53,7 @@ int main(void)
        trivial_graphr_init(&tgr);
        test_dfs(&tgr.gr, 1, 1);
 
-       parallel_graphr_init(&pgr, 3);
+       parallel_graphr_init(&pgr, 3, 0);
        test_dfs(&pgr.gr, 1, 1, 2);
 
        full_graphr_init(&fgr, 5);

diff --git a/ccan/agar/test/api-dijkstra.c b/ccan/agar/test/api-dijkstra.c
index 4b03bc6b8fcd9c44b7508b98fcfacae1c3a63ba4..5edccd7032bbcfd23ae3ca5da4d34c5f597b4356 100644 (file)
--- a/ccan/agar/test/api-dijkstra.c
+++ b/ccan/agar/test/api-dijkstra.c
@@ -35,9 +35,9 @@ static void test_parallel(void)
        struct parallel_graphr pgr;
        struct agar_state *sr;
        aga_icost_t cost;
-       const void *node;
+       const void *node, *edge;
 
-       parallel_graphr_init(&pgr, 3);
+       parallel_graphr_init(&pgr, 3, 0);
 
        ok1(sr = agar_dijkstra_new(NULL, &pgr.gr, int2ptr(1)));
        ok1(agar_dijkstra_step(sr, &node));
@@ -48,7 +48,7 @@ static void test_parallel(void)
        ok1(agar_dijkstra_path(sr, int2ptr(1), &cost, NULL, NULL));
        ok1(cost == 0);
        ok1(agar_dijkstra_path(sr, int2ptr(2), &cost, &node, NULL));
-       ok1(cost == 1);
+       ok1(cost == 2);
        ok1(node == int2ptr(1));
        tal_free(sr);
 
@@ -60,6 +60,14 @@ static void test_parallel(void)
        ok1(cost == 0);
        ok1(!agar_dijkstra_path(sr, int2ptr(1), NULL, NULL, NULL));
        tal_free(sr);
+
+       parallel_graphr_init(&pgr, 3, 2);
+       ok1(sr = agar_dijkstra_new(NULL, &pgr.gr, int2ptr(1)));
+       ok1(agar_dijkstra_path(sr, int2ptr(2), &cost, &node, &edge));
+       ok1(cost == 1);
+       ok1(ptr2int(node) == 1);
+       ok1(ptr2int(edge) == 2);
+       tal_free(sr);
 }
 
 #define FULL_LEN       4
@@ -213,7 +221,7 @@ static void test_traversal1(void)
 
 int main(void)
 {
-       plan_tests(6 + 18
+       plan_tests(6 + 23
                   + FULL_LEN * (FULL_LEN*4 - 1)
                   + CHAIN_LEN * (1 + CHAIN_LEN*2)
                   + 12 + 32);

diff --git a/ccan/agar/test/parallel.c b/ccan/agar/test/parallel.c
index 741ff3a37033a3775aebc7ecf781afe3d283abc6..6034ad1176494d26537b9a3ae46c19e9508f71d7 100644 (file)
--- a/ccan/agar/test/parallel.c
+++ b/ccan/agar/test/parallel.c
@@ -47,15 +47,23 @@ static int parallel_edge_info_r(const struct agar_graph *gr,
                                const void *nr, const void *edge,
                                struct agar_edge_info *eir)
 {
+       const struct parallel_graphr *pgr
+               = container_of(gr, struct parallel_graphr, gr);
        assert(ptr2int(nr) == 1);
 
        eir->to = int2ptr(2);
+       if (ptr2int(edge) == pgr->cheaplink)
+               eir->icost = 1;
+       else
+               eir->icost = 2;
        return 0;
 }
 
-void parallel_graphr_init(struct parallel_graphr *pgr, int nlinks)
+void parallel_graphr_init(struct parallel_graphr *pgr, int nlinks,
+                         int cheaplink)
 {
        pgr->nlinks = nlinks;
+       pgr->cheaplink = cheaplink;
 
        agar_init_graph(&pgr->gr, parallel_first_edge_r, parallel_next_edge_r,
                        parallel_edge_info_r);

diff --git a/ccan/agar/test/simple-graphr.h b/ccan/agar/test/simple-graphr.h
index de48ff68fe744f037117c01913016d83adabfd28..2abe72dcb6903989fafa71d46b5c5f3715b95ab2 100644 (file)
--- a/ccan/agar/test/simple-graphr.h
+++ b/ccan/agar/test/simple-graphr.h
@@ -37,9 +37,11 @@ static const struct adjacency_listr trivial_adjacencyr[] = {
  */
 struct parallel_graphr {
        int nlinks;
+       int cheaplink;
        struct agar_graph gr;
 };
-void parallel_graphr_init(struct parallel_graphr *pgr, int nlinks);
+void parallel_graphr_init(struct parallel_graphr *pgr, int nlinks,
+                         int cheaplink);
 static const struct adjacency_listr parallel_adjacencyr_nlinks3[] = {
        {1, {2, 2, 2}},
        {2, {}},