aga: Breadth first search

This implements breadth first search for the abstract graph algorithms
module.

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

diff --git a/ccan/aga/_info b/ccan/aga/_info
index a56f1c324ffce2ddcc4392de68da71d339a828f1..3320d37a60044bbc5ebe407c32cc66cc1ec66fbb 100644 (file)
--- a/ccan/aga/_info
+++ b/ccan/aga/_info
@@ -32,6 +32,7 @@ int main(int argc, char *argv[])
                printf("ccan/build_assert\n");
                printf("ccan/check_type\n");
                printf("ccan/lstack\n");
+               printf("ccan/lqueue\n");
                return 0;
        }
 

diff --git a/ccan/aga/aga.h b/ccan/aga/aga.h
index 7d6016ff70606765145fa9f90be5014ba918c757..28fa539947146965068cbc3d19b37cc0a75f2d36 100644 (file)
--- a/ccan/aga/aga.h
+++ b/ccan/aga/aga.h
@@ -107,13 +107,13 @@
  *
  * - Errors are cleared on aga_finish().
  */
-
 #include "config.h"
 #include <string.h>
 
 #include <ccan/build_assert/build_assert.h>
 #include <ccan/check_type/check_type.h>
 #include <ccan/lstack/lstack.h>
+#include <ccan/lqueue/lqueue.h>
 
 struct aga_graph;
 struct aga_node;
@@ -145,6 +145,10 @@ struct aga_node {
                        struct lstack_link parent;
                        const void *edge;
                } dfs;
+               struct {
+                       struct lqueue_link next;
+                       const void *edge;
+               } bfs;
        } u;
 };
 
@@ -216,4 +220,15 @@ 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; )
 
+
+/*
+ * Breadth first search
+ */
+
+int aga_bfs_start(struct aga_graph *g);
+struct aga_node *aga_bfs_explore(struct aga_graph *g, struct aga_node *n);
+
+#define aga_bfs(_n, _g, _start)                                        \
+       for ((_n) = (_start) ; ((_n) = aga_bfs_explore((_g), (_n))) != NULL; )
+
 #endif /* CCAN_AGA_H */

diff --git a/ccan/aga/bfs.c b/ccan/aga/bfs.c
new file mode 100644 (file)
index 0000000..01eb851
--- /dev/null
+++ b/ccan/aga/bfs.c
@@ -0,0 +1,94 @@
+/* Licensed under LGPLv2+ - see LICENSE file for details */
+#include "config.h"
+
+#include <stdbool.h>
+#include <stdlib.h>
+#include <assert.h>
+
+#include <ccan/aga/aga.h>
+#include "private.h"
+
+/*
+ * Breadth first search
+ */
+
+static bool bfs_enqueue(struct aga_graph *g, struct lqueue *queue,
+                       struct aga_node *n)
+{
+       if (!aga_update_node(g, n))
+               return false;
+
+       lqueue_enqueue(queue, n, u.bfs.next);
+       n->u.bfs.edge = aga_first_edge(g, n);
+       return true;
+}
+
+static struct aga_node *bfs_front(struct lqueue *queue)
+{
+       return lqueue_front(queue, struct aga_node, u.bfs.next);
+}
+
+static void bfs_dequeue(struct lqueue *queue)
+{
+       lqueue_dequeue(queue, struct aga_node, u.bfs.next);
+}
+
+int aga_bfs_start(struct aga_graph *g)
+{
+       int rc;
+
+       rc = aga_start(g);
+       if (rc < 0)
+               return rc;
+
+       return 0;
+}
+
+struct aga_node *aga_bfs_explore(struct aga_graph *g, struct aga_node *n)
+{
+       LQUEUE(queue);
+
+       if (!aga_check_state(g))
+               return NULL;
+
+       if (!n)
+               return NULL;
+ 
+       if (bfs_enqueue(g, &queue, n))
+               return n;
+
+       lqueue_init_from_back(&queue, n, u.bfs.next);
+
+       while ((n = bfs_front(&queue))) {
+               const void *e = n->u.bfs.edge;
+               int err;
+               struct aga_edge_info ei;
+
+               if (!e) {
+                       /* out of edges, back up */
+                       bfs_dequeue(&queue);
+                       continue;
+               }
+
+               n->u.bfs.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 (!bfs_enqueue(g, &queue, ei.to)) {
+                       /* already visited node */
+                       continue;
+               }
+
+               return ei.to;
+       }
+       
+       return NULL;
+}

diff --git a/ccan/aga/test/api-bfs.c b/ccan/aga/test/api-bfs.c
new file mode 100644 (file)
index 0000000..e59c756
--- /dev/null
+++ b/ccan/aga/test/api-bfs.c
@@ -0,0 +1,104 @@
+#include "config.h"
+
+#include <stddef.h>
+#include <assert.h>
+
+#include <ccan/tap/tap.h>
+#include <ccan/array_size/array_size.h>
+
+#include <ccan/aga/aga.h>
+
+#include "simple-graph.h"
+
+#define test_bfs_partial(sg, first, ...)                               \
+       do {                                                            \
+               int cmp[] = { __VA_ARGS__ };                            \
+               bool stillok = true;                                    \
+               struct aga_node *node;                                  \
+               int i = 0;                                              \
+               aga_bfs(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_bfs(sg, first, ...)                                       \
+       do {                                                            \
+               ok1(aga_bfs_start(&(sg)->g) == 0);                      \
+               test_bfs_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_bfs(&tg.sg, 1, 1);
+
+       parallel_graph_init(&pg, 3);
+       test_bfs(&pg.sg, 1, 1, 2);
+
+       full_graph_init(&fg, 5);
+       test_bfs(&fg.sg, 1, 1, 2, 3, 4, 5);
+       test_bfs(&fg.sg, 3, 3, 1, 2, 4, 5);
+
+       chain_graph_init(&cg, 8);
+       test_bfs(&cg.fg.sg, 1, 1, 2, 3, 4, 5, 6, 7, 8);
+       test_bfs(&cg.fg.sg, 8, 8, 7, 6, 5, 4, 3, 2, 1);
+       test_bfs(&cg.fg.sg, 5, 5, 4, 6, 3, 7, 2, 8, 1);
+
+       grid_graph_init(&gg1, 3, 3, true, true, false, false);
+       test_bfs(&gg1.sg, 1, 1, 2, 4, 3, 5, 7, 6, 8, 9);
+       test_bfs(&gg1.sg, 5, 5, 6, 8, 9);
+       test_bfs(&gg1.sg, 9, 9);
+
+       grid_graph_init(&gg2, 3, 3, true, true, true, true);
+       test_bfs(&gg2.sg, 1, 1, 2, 4, 3, 5, 7, 6, 8, 9);
+       test_bfs(&gg2.sg, 5, 5, 6, 8, 4, 2, 9, 3, 7, 1);
+       test_bfs(&gg2.sg, 9, 9, 8, 6, 7, 5, 3, 4, 2, 1);
+
+       error_graph_init(&eg);
+       test_bfs(&eg.sg, 1, 1, 2);
+       ok(aga_bfs_start(&eg.sg.g) == 0, "started error traversal");
+       node = aga_bfs_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_bfs_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_bfs_explore(&eg.sg.g, node) == NULL);
+       ok1(aga_error(&eg.sg.g) == -1);
+       ok1(aga_bfs_explore(&eg.sg.g, node) == NULL);
+       aga_finish(&eg.sg.g);
+       test_bfs(&eg.sg, 1, 1, 2);
+
+       traversal1_graph_init(&t1g);
+       test_bfs(&t1g.sg, 1, 1, 2, 3, 4, 5, 6);
+       test_bfs(&t1g.sg, 9, 9, 8, 7, 6, 5, 4);
+
+       ok1(aga_bfs_start(&t1g.sg.g) == 0);
+       test_bfs_partial(&t1g.sg, 1, 1, 2, 3, 4, 5, 6);
+       test_bfs_partial(&t1g.sg, 9, 9, 8, 7);
+       aga_finish(&t1g.sg.g);
+
+       ok1(aga_bfs_start(&t1g.sg.g) == 0);
+       test_bfs_partial(&t1g.sg, 9, 9, 8, 7, 6, 5, 4);
+       test_bfs_partial(&t1g.sg, 1, 1, 2, 3);
+       aga_finish(&t1g.sg.g);
+
+       return exit_status();
+}