X-Git-Url: https://git.ozlabs.org/?a=blobdiff_plain;f=ccan%2Faga%2Fbfs.c;fp=ccan%2Faga%2Fbfs.c;h=01eb851c1a97cc2e1cf748b3c2e39a337e281e3c;hb=f3160af8e033d56f02c8fb188557e42fcdffcf7b;hp=0000000000000000000000000000000000000000;hpb=be32f4df1263ad0d323d6d401f037a37a19d580f;p=ccan

diff --git a/ccan/aga/bfs.c b/ccan/aga/bfs.c
new file mode 100644
index 00000000..01eb851c
--- /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;
+}