[ccan] [PATCH 3/6] aga: Depth first search

David Gibson david at gibson.dropbear.id.au
Wed May 27 21:21:25 AEST 2015


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

Signed-off-by: David Gibson <david at gibson.dropbear.id.au>
---
 ccan/aga/_info          |  2 ++
 ccan/aga/aga.h          | 21 ++++++++++-
 ccan/aga/dfs.c          | 95 +++++++++++++++++++++++++++++++++++++++++++++++++
 ccan/aga/test/api-dfs.c | 85 +++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 202 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 551bec1..5fb94c6 100644
--- a/ccan/aga/_info
+++ b/ccan/aga/_info
@@ -21,12 +21,14 @@ int main(int argc, char *argv[])
 		return 1;
 
 	if (strcmp(argv[1], "depends") == 0) {
+		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 21ca13c..874b7fd 100644
--- a/ccan/aga/aga.h
+++ b/ccan/aga/aga.h
@@ -111,12 +111,17 @@
 #include "config.h"
 #include <string.h>
 
+#include <ccan/lstack/lstack.h>
+
 struct aga_graph;
 
 struct aga_node {
 	int sequence;
 	union {
-		/* Per-algorithm state here */
+		struct {
+			struct lstack_link parent;
+			const void *edge;
+		} dfs;
 	} u;
 };
 
@@ -142,6 +147,10 @@ struct aga_graph {
 	aga_next_edge_fn next_edge;
 
 	union {
+		struct {
+			struct aga_node *first;
+			struct lstack stack;
+		} dfs;
 	} state;
 };
 
@@ -172,4 +181,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 *first);
+struct aga_node *aga_dfs_next(struct aga_graph *g);
+
+#define aga_dfs_foreach(_n, _g) \
+	for ( ; ((_n) = aga_dfs_next((_g))) != NULL; )
+
 #endif /* CCAN_AGA_H */
diff --git a/ccan/aga/dfs.c b/ccan/aga/dfs.c
new file mode 100644
index 0000000..e005255
--- /dev/null
+++ b/ccan/aga/dfs.c
@@ -0,0 +1,95 @@
+/* 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"
+
+/*
+ * Depth first search
+ */
+
+static bool dfs_push(struct aga_graph *g, struct aga_node *n)
+{
+	if (!aga_update_node(g, n))
+		return false;
+
+	lstack_push(&g->state.dfs.stack, n, u.dfs.parent);
+	n->u.dfs.edge = aga_first_edge(g, n);
+	return true;
+}
+
+static void dfs_pop(struct aga_graph *g)
+{
+	lstack_pop(&g->state.dfs.stack, struct aga_node, u.dfs.parent);
+}
+
+static struct aga_node *dfs_top(struct aga_graph *g)
+{
+	return lstack_top(&g->state.dfs.stack, struct aga_node, u.dfs.parent);
+}
+
+int aga_dfs_start(struct aga_graph *g, struct aga_node *first)
+{
+	int rc;
+
+	rc = aga_start(g);
+	if (rc < 0)
+		return rc;
+
+	lstack_init(&g->state.dfs.stack);
+	g->state.dfs.first = first;
+
+	return 0;
+}
+
+struct aga_node *aga_dfs_next(struct aga_graph *g)
+{
+	struct aga_node *n = g->state.dfs.first;
+
+	if (!aga_check_state(g))
+		return NULL;
+
+	if (n) {
+		if (!dfs_push(g, n))
+			assert(0);
+		g->state.dfs.first = NULL;
+		return n;
+	}
+	
+	while ((n = dfs_top(g))) {
+		const void *e = n->u.dfs.edge;
+		int err;
+		struct aga_edge_info ei;
+
+		if (!e) {
+			/* out of edges, back up */
+			dfs_pop(g);
+			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, 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 0000000..565c62f
--- /dev/null
+++ b/ccan/aga/test/api-dfs.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_dfs(sg, first, ...)					\
+	do {								\
+		int cmp[] = { __VA_ARGS__ };				\
+		bool stillok = true;					\
+		struct aga_node *node;					\
+		int i = 0;						\
+		ok1(aga_dfs_start(&(sg)->g, &(sg)->nodes[first]) == 0);	\
+		aga_dfs_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_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, &eg.sg.nodes[3]) == 0,
+	   "started error traversal");
+	node = aga_dfs_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_dfs_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_dfs_next(&eg.sg.g) == NULL);
+	ok1(aga_error(&eg.sg.g) == -1);
+	ok1(aga_dfs_next(&eg.sg.g) == NULL);
+	aga_finish(&eg.sg.g);
+	test_dfs(&eg.sg, 1, 1, 2);
+
+	return exit_status();
+}
-- 
2.1.0



More information about the ccan mailing list