X-Git-Url: https://git.ozlabs.org/?a=blobdiff_plain;f=ccan%2Faga%2Ftest%2Fapi-dijkstra.c;fp=ccan%2Faga%2Ftest%2Fapi-dijkstra.c;h=08b472884728904fb99d53606cc6479d3451b1fa;hb=1e742b68d026a258ccf99338f05daf8b694978a3;hp=0000000000000000000000000000000000000000;hpb=f9274cce2171d919d72fe9ec186320f85174b7e5;p=ccan diff --git a/ccan/aga/test/api-dijkstra.c b/ccan/aga/test/api-dijkstra.c new file mode 100644 index 00000000..08b47288 --- /dev/null +++ b/ccan/aga/test/api-dijkstra.c @@ -0,0 +1,222 @@ +#include "config.h" + +#include +#include +#include + +#include +#include + +#include + +#include "simple-graph.h" + +static void test_trivial(void) +{ + struct trivial_graph tg; + aga_icost_t cost; + struct aga_node *node; + const void *edge; + + trivial_graph_init(&tg); + + ok1(aga_dijkstra_start(&tg.sg.g, &tg.sg.nodes[1]) == 0); + ok1(aga_dijkstra_step(&tg.sg.g) == &tg.sg.nodes[1]); + ok1(aga_dijkstra_step(&tg.sg.g) == NULL); + ok1(aga_dijkstra_path(&tg.sg.g, &tg.sg.nodes[1], &cost, &node, &edge)); + ok1(cost == 0); + ok1(node == NULL); + ok1(edge == NULL); + aga_finish(&tg.sg.g); +} + +static void test_parallel(void) +{ + struct parallel_graph pg; + aga_icost_t cost; + struct aga_node *node; + + parallel_graph_init(&pg, 3); + + ok1(aga_dijkstra_start(&pg.sg.g, &pg.sg.nodes[1]) == 0); + ok1(aga_dijkstra_step(&pg.sg.g) == &pg.sg.nodes[1]); + ok1(aga_dijkstra_step(&pg.sg.g) == &pg.sg.nodes[2]); + ok1(aga_dijkstra_step(&pg.sg.g) == NULL); + 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(node == &pg.sg.nodes[1]); + aga_finish(&pg.sg.g); + + ok1(aga_dijkstra_start(&pg.sg.g, &pg.sg.nodes[2]) == 0); + ok1(aga_dijkstra_step(&pg.sg.g) == &pg.sg.nodes[2]); + ok1(aga_dijkstra_step(&pg.sg.g) == NULL); + ok1(aga_dijkstra_path(&pg.sg.g, &pg.sg.nodes[2], &cost, NULL, NULL)); + ok1(cost == 0); + ok1(!aga_dijkstra_path(&pg.sg.g, &pg.sg.nodes[1], NULL, NULL, NULL)); + aga_finish(&pg.sg.g); +} + +#define FULL_LEN 4 + +static void test_full(void) +{ + struct full_graph fg; + int i, j; + + full_graph_init(&fg, FULL_LEN); + + for (i = 1; i <= FULL_LEN; i++) { + ok1(aga_dijkstra_start(&fg.sg.g, &fg.sg.nodes[i]) == 0); + + for (j = 1; j <= FULL_LEN; j++) { + aga_icost_t cost; + struct aga_node *node; + const void *edge; + + ok1(aga_dijkstra_path(&fg.sg.g, &fg.sg.nodes[j], + &cost, &node, &edge)); + if (i == j) { + ok1(cost == 0); + ok1(node == NULL); + ok1(edge == NULL); + } else { + ok1(cost == 1); + ok1(node == &fg.sg.nodes[i]); + ok1(edge == &fg.sg.nodes[j]); + } + } + + aga_finish(&fg.sg.g); + } +} + +#define CHAIN_LEN 8 + +static void test_chain(void) +{ + struct chain_graph cg; + int i, j; + + chain_graph_init(&cg, CHAIN_LEN); + + for (i = 1; i <= CHAIN_LEN; i++) { + ok1(aga_dijkstra_start(&cg.fg.sg.g, &cg.fg.sg.nodes[i]) == 0); + + for (j = 1; j <= CHAIN_LEN; j++) { + aga_icost_t cost; + + ok1(aga_dijkstra_path(&cg.fg.sg.g, &cg.fg.sg.nodes[j], + &cost, NULL, NULL)); + ok1(cost == labs(i - j)); + } + + aga_finish(&cg.fg.sg.g); + } +} + +static void test_error(void) +{ + struct error_graph eg; + aga_icost_t cost; + + error_graph_init(&eg); + + ok1(aga_dijkstra_start(&eg.sg.g, &eg.sg.nodes[1]) == 0); + ok1(aga_dijkstra_path(&eg.sg.g, &eg.sg.nodes[1], &cost, NULL, NULL)); + ok1(cost == 0); + ok1(aga_dijkstra_path(&eg.sg.g, &eg.sg.nodes[2], &cost, NULL, NULL)); + ok1(cost == 1); + ok1(!aga_dijkstra_path(&eg.sg.g, &eg.sg.nodes[3], &cost, NULL, NULL)); + ok1(!aga_dijkstra_path(&eg.sg.g, &eg.sg.nodes[4], &cost, NULL, NULL)); + aga_finish(&eg.sg.g); + + ok1(aga_dijkstra_start(&eg.sg.g, &eg.sg.nodes[3]) == 0); + ok1(aga_dijkstra_path(&eg.sg.g, &eg.sg.nodes[3], &cost, NULL, NULL)); + ok1(cost == 0); + ok1(!aga_dijkstra_path(&eg.sg.g, &eg.sg.nodes[4], &cost, NULL, NULL)); + ok1(aga_error(&eg.sg.g) == -1); + aga_finish(&eg.sg.g); +} + +static void test_traversal1(void) +{ + struct traversal1_graph t1g; + aga_icost_t cost; + + /* This is mostly about testing we correctly handle + * non-reachable nodes */ + traversal1_graph_init(&t1g); + + ok1(aga_dijkstra_start(&t1g.sg.g, &t1g.sg.nodes[1]) == 0); + ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[1], + &cost, NULL, NULL)); + ok1(cost == 0); + ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[2], + &cost, NULL, NULL)); + ok1(cost == 1); + ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[3], + &cost, NULL, NULL)); + ok1(cost == 1); + ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[4], + &cost, NULL, NULL)); + ok1(cost == 2); + ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[5], + &cost, NULL, NULL)); + ok1(cost == 2); + ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[6], + &cost, NULL, NULL)); + ok1(cost == 2); + ok1(!aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[7], + NULL, NULL, NULL)); + ok1(!aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[8], + NULL, NULL, NULL)); + ok1(!aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[9], + NULL, NULL, NULL)); + aga_finish(&t1g.sg.g); + + ok1(aga_dijkstra_start(&t1g.sg.g, &t1g.sg.nodes[9]) == 0); + ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[9], + &cost, NULL, NULL)); + ok1(cost == 0); + ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[8], + &cost, NULL, NULL)); + ok1(cost == 1); + ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[7], + &cost, NULL, NULL)); + ok1(cost == 1); + ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[6], + &cost, NULL, NULL)); + ok1(cost == 2); + ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[5], + &cost, NULL, NULL)); + ok1(cost == 2); + ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[4], + &cost, NULL, NULL)); + ok1(cost == 2); + ok1(!aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[3], + NULL, NULL, NULL)); + ok1(!aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[2], + NULL, NULL, NULL)); + ok1(!aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[1], + NULL, NULL, NULL)); + aga_finish(&t1g.sg.g); +} + +int main(void) +{ + plan_tests(7 + 15 + + FULL_LEN * (1 + FULL_LEN*4) + + CHAIN_LEN * (1 + CHAIN_LEN*2) + + 12 + 32); + + test_trivial(); + test_parallel(); + test_full(); + test_chain(); + test_error(); + test_traversal1(); + + return exit_status(); +}