From be32f4df1263ad0d323d6d401f037a37a19d580f Mon Sep 17 00:00:00 2001 From: David Gibson Date: Sun, 14 Jun 2015 01:34:40 +1000 Subject: [PATCH] aga: Depth first search This implements depth first search for the abstract graph algorithms module. Signed-off-by: David Gibson --- ccan/aga/_info | 2 + ccan/aga/aga.h | 16 ++++++- ccan/aga/dfs.c | 94 ++++++++++++++++++++++++++++++++++++ ccan/aga/test/api-dfs.c | 104 ++++++++++++++++++++++++++++++++++++++++ 4 files changed, 215 insertions(+), 1 deletion(-) create mode 100644 ccan/aga/dfs.c create mode 100644 ccan/aga/test/api-dfs.c diff --git a/ccan/aga/_info b/ccan/aga/_info index 9e44b2cf..a56f1c32 100644 --- a/ccan/aga/_info +++ b/ccan/aga/_info @@ -31,12 +31,14 @@ int main(int argc, char *argv[]) if (strcmp(argv[1], "depends") == 0) { printf("ccan/build_assert\n"); printf("ccan/check_type\n"); + printf("ccan/lstack\n"); return 0; } if (strcmp(argv[1], "testdepends") == 0) { printf("ccan/container_of\n"); printf("ccan/ptrint\n"); + printf("ccan/array_size\n"); return 0; } diff --git a/ccan/aga/aga.h b/ccan/aga/aga.h index d5cc434b..7d6016ff 100644 --- a/ccan/aga/aga.h +++ b/ccan/aga/aga.h @@ -113,6 +113,7 @@ #include #include +#include struct aga_graph; struct aga_node; @@ -140,7 +141,10 @@ typedef int (*aga_edge_info_fn)(const struct aga_graph *g, struct aga_node { int sequence; union { - /* Per-algorithm state here */ + struct { + struct lstack_link parent; + const void *edge; + } dfs; } u; }; @@ -202,4 +206,14 @@ int aga_edge_info(const struct aga_graph *g, const struct aga_node *n, (_e) = aga_next_edge((_g), (_n), (_e))) \ if ((_ei).to) +/* + * Depth first search + */ + +int aga_dfs_start(struct aga_graph *g); +struct aga_node *aga_dfs_explore(struct aga_graph *g, struct aga_node *n); + +#define aga_dfs(_n, _g, _start) \ + for ((_n) = (_start); ((_n) = aga_dfs_explore((_g), (_n))) != NULL; ) + #endif /* CCAN_AGA_H */ diff --git a/ccan/aga/dfs.c b/ccan/aga/dfs.c new file mode 100644 index 00000000..638481c5 --- /dev/null +++ b/ccan/aga/dfs.c @@ -0,0 +1,94 @@ +/* Licensed under LGPLv2+ - see LICENSE file for details */ +#include "config.h" + +#include +#include +#include + +#include +#include "private.h" + +/* + * Depth first search + */ + +static bool dfs_push(struct aga_graph *g, struct lstack *stack, + struct aga_node *n) +{ + if (!aga_update_node(g, n)) + return false; + + lstack_push(stack, n, u.dfs.parent); + n->u.dfs.edge = aga_first_edge(g, n); + return true; +} + +static void dfs_pop(struct lstack *stack) +{ + lstack_pop(stack, struct aga_node, u.dfs.parent); +} + +static struct aga_node *dfs_top(struct lstack *stack) +{ + return lstack_top(stack, struct aga_node, u.dfs.parent); +} + +int aga_dfs_start(struct aga_graph *g) +{ + int rc; + + rc = aga_start(g); + if (rc < 0) + return rc; + + return 0; +} + +struct aga_node *aga_dfs_explore(struct aga_graph *g, struct aga_node *n) +{ + LSTACK(stack); + + if (!aga_check_state(g)) + return NULL; + + if (!n) + return NULL; + + if (dfs_push(g, &stack, n)) + return n; + + lstack_init_from_top(&stack, n, u.dfs.parent); + + while ((n = dfs_top(&stack))) { + const void *e = n->u.dfs.edge; + int err; + struct aga_edge_info ei; + + if (!e) { + /* out of edges, back up */ + dfs_pop(&stack); + continue; + } + + n->u.dfs.edge = aga_next_edge(g, n, e); + + err = aga_edge_info(g, n, e, &ei); + if (err < 0) { + aga_fail(g, err); + return NULL; + } + if (!ei.to) { + /* missing edge */ + continue; + } + + if (!dfs_push(g, &stack, ei.to)) { + /* already visited node */ + continue; + } + + return ei.to; + } + + return NULL; +} diff --git a/ccan/aga/test/api-dfs.c b/ccan/aga/test/api-dfs.c new file mode 100644 index 00000000..8ab15914 --- /dev/null +++ b/ccan/aga/test/api-dfs.c @@ -0,0 +1,104 @@ +#include "config.h" + +#include +#include + +#include +#include + +#include + +#include "simple-graph.h" + +#define test_dfs_partial(sg, first, ...) \ + do { \ + int cmp[] = { __VA_ARGS__ }; \ + bool stillok = true; \ + struct aga_node *node; \ + int i = 0; \ + aga_dfs(node, &(sg)->g, &(sg)->nodes[first]) { \ + int index = node - (sg)->nodes; \ + diag("Visited %d\n", index); \ + if (i >= ARRAY_SIZE(cmp) || (index != cmp[i])) \ + stillok = false; \ + i++; \ + } \ + ok1(stillok); \ + } while (0) + +#define test_dfs(sg, first, ...) \ + do { \ + ok1(aga_dfs_start(&(sg)->g) == 0); \ + test_dfs_partial(sg, first, __VA_ARGS__); \ + aga_finish(&(sg)->g); \ + } while (0) + +int main(void) +{ + struct trivial_graph tg; + struct parallel_graph pg; + struct full_graph fg; + struct chain_graph cg; + struct grid_graph gg1, gg2; + struct error_graph eg; + struct traversal1_graph t1g; + struct aga_node *node; + + plan_tests(2 * 13 + 10 + 10); + + trivial_graph_init(&tg); + test_dfs(&tg.sg, 1, 1); + + parallel_graph_init(&pg, 3); + test_dfs(&pg.sg, 1, 1, 2); + + full_graph_init(&fg, 5); + test_dfs(&fg.sg, 1, 1, 2, 3, 4, 5); + test_dfs(&fg.sg, 3, 3, 1, 2, 4, 5); + + chain_graph_init(&cg, 8); + test_dfs(&cg.fg.sg, 1, 1, 2, 3, 4, 5, 6, 7, 8); + test_dfs(&cg.fg.sg, 8, 8, 7, 6, 5, 4, 3, 2, 1); + test_dfs(&cg.fg.sg, 5, 5, 4, 3, 2, 1, 6, 7, 8); + + grid_graph_init(&gg1, 3, 3, true, true, false, false); + test_dfs(&gg1.sg, 1, 1, 2, 3, 6, 9, 5, 8, 4, 7); + test_dfs(&gg1.sg, 5, 5, 6, 9, 8); + test_dfs(&gg1.sg, 9, 9); + + grid_graph_init(&gg2, 3, 3, true, true, true, true); + test_dfs(&gg2.sg, 1, 1, 2, 3, 6, 9, 8, 7, 4, 5); + test_dfs(&gg2.sg, 5, 5, 6, 9, 8, 7, 4, 1, 2, 3); + test_dfs(&gg2.sg, 9, 9, 8, 7, 4, 5, 6, 3, 2, 1); + + error_graph_init(&eg); + test_dfs(&eg.sg, 1, 1, 2); + ok(aga_dfs_start(&eg.sg.g) == 0, "started error traversal"); + node = aga_dfs_explore(&eg.sg.g, &eg.sg.nodes[3]); + ok(node == &eg.sg.nodes[3], "Expected node #3 (%p), actually #%ld (%p)", + &eg.sg.nodes[3], node - eg.sg.nodes, node); + node = aga_dfs_explore(&eg.sg.g, node); + ok(node == &eg.sg.nodes[4], "Expected node #4 (%p), actually #%ld (%p)", + &eg.sg.nodes[4], node - eg.sg.nodes, node); + ok1(aga_dfs_explore(&eg.sg.g, node) == NULL); + ok1(aga_error(&eg.sg.g) == -1); + ok1(aga_dfs_explore(&eg.sg.g, node) == NULL); + aga_finish(&eg.sg.g); + test_dfs(&eg.sg, 1, 1, 2); + + traversal1_graph_init(&t1g); + test_dfs(&t1g.sg, 1, 1, 2, 4, 5, 3, 6); + test_dfs(&t1g.sg, 9, 9, 8, 6, 5, 7, 4); + + ok1(aga_dfs_start(&t1g.sg.g) == 0); + test_dfs_partial(&t1g.sg, 1, 1, 2, 4, 5, 3, 6); + test_dfs_partial(&t1g.sg, 9, 9, 8, 7); + aga_finish(&t1g.sg.g); + + ok1(aga_dfs_start(&t1g.sg.g) == 0); + test_dfs_partial(&t1g.sg, 9, 9, 8, 6, 5, 7, 4); + test_dfs_partial(&t1g.sg, 1, 1, 2, 3); + aga_finish(&t1g.sg.g); + + return exit_status(); +} -- 2.39.5