[ccan] [PATCH 4/6] aga: Breadth first search
David Gibson
david at gibson.dropbear.id.au
Wed May 27 21:21:26 AEST 2015
This implements breadth first search for the abstract graph algorithms
module.
Signed-off-by: David Gibson <david at gibson.dropbear.id.au>
---
ccan/aga/_info | 1 +
ccan/aga/aga.h | 21 +++++++++-
ccan/aga/bfs.c | 102 ++++++++++++++++++++++++++++++++++++++++++++++++
ccan/aga/test/api-bfs.c | 85 ++++++++++++++++++++++++++++++++++++++++
4 files changed, 208 insertions(+), 1 deletion(-)
create mode 100644 ccan/aga/bfs.c
create mode 100644 ccan/aga/test/api-bfs.c
diff --git a/ccan/aga/_info b/ccan/aga/_info
index 5fb94c6..f2d22fa 100644
--- a/ccan/aga/_info
+++ b/ccan/aga/_info
@@ -22,6 +22,7 @@ int main(int argc, char *argv[])
if (strcmp(argv[1], "depends") == 0) {
printf("ccan/lstack\n");
+ printf("ccan/lqueue\n");
return 0;
}
diff --git a/ccan/aga/aga.h b/ccan/aga/aga.h
index 874b7fd..e136bac 100644
--- a/ccan/aga/aga.h
+++ b/ccan/aga/aga.h
@@ -107,11 +107,11 @@
*
* - Errors are cleared on aga_finish().
*/
-
#include "config.h"
#include <string.h>
#include <ccan/lstack/lstack.h>
+#include <ccan/lqueue/lqueue.h>
struct aga_graph;
@@ -122,6 +122,9 @@ struct aga_node {
struct lstack_link parent;
const void *edge;
} dfs;
+ struct {
+ struct lqueue_link next;
+ } bfs;
} u;
};
@@ -151,6 +154,11 @@ struct aga_graph {
struct aga_node *first;
struct lstack stack;
} dfs;
+ struct {
+ struct aga_node *first;
+ struct lqueue queue;
+ const void *edge;
+ } bfs;
} state;
};
@@ -191,4 +199,15 @@ struct aga_node *aga_dfs_next(struct aga_graph *g);
#define aga_dfs_foreach(_n, _g) \
for ( ; ((_n) = aga_dfs_next((_g))) != NULL; )
+
+/*
+ * Breadth first search
+ */
+
+int aga_bfs_start(struct aga_graph *g, struct aga_node *first);
+struct aga_node *aga_bfs_next(struct aga_graph *g);
+
+#define aga_bfs_foreach(_node, _bfs) \
+ for ( ; ((_node) = aga_bfs_next((_bfs))) != NULL; )
+
#endif /* CCAN_AGA_H */
diff --git a/ccan/aga/bfs.c b/ccan/aga/bfs.c
new file mode 100644
index 0000000..7abac8f
--- /dev/null
+++ b/ccan/aga/bfs.c
@@ -0,0 +1,102 @@
+/* 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 aga_node *n)
+{
+ if (!aga_update_node(g, n))
+ return false;
+
+ lqueue_enqueue(&g->state.bfs.queue, n, u.bfs.next);
+ return true;
+}
+
+static struct aga_node *bfs_front(struct aga_graph *g)
+{
+ return lqueue_front(&g->state.bfs.queue, struct aga_node, u.bfs.next);
+}
+
+static void bfs_dequeue(struct aga_graph *g)
+{
+ struct aga_node *n;
+
+ lqueue_dequeue(&g->state.bfs.queue, struct aga_node, u.bfs.next);
+ n = lqueue_front(&g->state.bfs.queue, struct aga_node, u.bfs.next);
+ if (n) {
+ g->state.bfs.edge = aga_first_edge(g, n);
+ }
+}
+
+int aga_bfs_start(struct aga_graph *g, struct aga_node *first)
+{
+ int rc;
+
+ rc = aga_start(g);
+ if (rc < 0)
+ return rc;
+
+ lqueue_init(&g->state.bfs.queue);
+
+ g->state.bfs.first = first;
+
+ return 0;
+}
+
+struct aga_node *aga_bfs_next(struct aga_graph *g)
+{
+ struct aga_node *n = g->state.bfs.first;
+
+ if (!aga_check_state(g))
+ return NULL;
+
+ if (n) {
+ if (!bfs_enqueue(g, n))
+ assert(0);
+ g->state.bfs.first = NULL;
+ g->state.bfs.edge = aga_first_edge(g, n);
+ return n;
+ }
+
+ while ((n = bfs_front(g))) {
+ const void *e = g->state.bfs.edge;
+ int err;
+ struct aga_edge_info ei;
+
+ if (!e) {
+ /* out of edges, back up */
+ bfs_dequeue(g);
+ continue;
+ }
+
+ g->state.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, 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
index 0000000..844275d
--- /dev/null
+++ b/ccan/aga/test/api-bfs.c
@@ -0,0 +1,85 @@
+#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(sg, first, ...) \
+ do { \
+ int cmp[] = { __VA_ARGS__ }; \
+ bool stillok = true; \
+ struct aga_node *node; \
+ int i = 0; \
+ ok1(aga_bfs_start(&(sg)->g, &(sg)->nodes[first]) == 0); \
+ aga_bfs_foreach(node, &(sg)->g) { \
+ int index = node - (sg)->nodes; \
+ diag("Visited %d\n", index); \
+ if (i >= ARRAY_SIZE(cmp) || (index != cmp[i])) \
+ stillok = false; \
+ i++; \
+ } \
+ aga_finish(&(sg)->g); \
+ ok1(stillok); \
+ } 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 aga_node *node;
+
+ plan_tests(2 * 13 + 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, &eg.sg.nodes[3]) == 0,
+ "started error traversal");
+ node = aga_bfs_next(&eg.sg.g);
+ 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_next(&eg.sg.g);
+ 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_next(&eg.sg.g) == NULL);
+ ok1(aga_error(&eg.sg.g) == -1);
+ ok1(aga_bfs_next(&eg.sg.g) == NULL);
+ aga_finish(&eg.sg.g);
+ test_bfs(&eg.sg, 1, 1, 2);
+
+ return exit_status();
+}
--
2.1.0
More information about the ccan
mailing list