X-Git-Url: https://git.ozlabs.org/?a=blobdiff_plain;f=ccan%2Faga%2Faga.h;h=28fa539947146965068cbc3d19b37cc0a75f2d36;hb=0ddea4131eca28437638cdaf9394324fafab33da;hp=d5cc434b50ccb33ee0d5c3f7204d67ffeeb76cfa;hpb=3b7409ea08a7d1643bc7de31ece63e20b89f319b;p=ccan

diff --git a/ccan/aga/aga.h b/ccan/aga/aga.h
index d5cc434b..28fa5399 100644
--- a/ccan/aga/aga.h
+++ b/ccan/aga/aga.h
@@ -107,12 +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;
@@ -140,7 +141,14 @@ 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;
+		struct {
+			struct lqueue_link next;
+			const void *edge;
+		} bfs;
 	} u;
 };
 
@@ -202,4 +210,25 @@ 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; )
+
+
+/*
+ * 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 */