[ccan] [PATCH 3/4] aga: Breadth-first search
David Gibson
david at gibson.dropbear.id.au
Mon Jul 7 22:51:02 EST 2014
---
ccan/aga/_info | 1 +
ccan/aga/aga.c | 41 +++++++++++++++++++++++++++++++++++
ccan/aga/aga.h | 8 +++++++
ccan/aga/test/run-chain.c | 21 +++++++++++++++++-
ccan/aga/test/run-grid.c | 55 ++++++++++++++++++++++++++++++++++++++++++++++-
5 files changed, 124 insertions(+), 2 deletions(-)
diff --git a/ccan/aga/_info b/ccan/aga/_info
index d8f3957..87cb565 100644
--- a/ccan/aga/_info
+++ b/ccan/aga/_info
@@ -21,6 +21,7 @@ int main(int argc, char *argv[])
return 1;
if (strcmp(argv[1], "depends") == 0) {
+ printf("ccan/queue\n");
return 0;
}
diff --git a/ccan/aga/aga.c b/ccan/aga/aga.c
index d510616..f028059 100644
--- a/ccan/aga/aga.c
+++ b/ccan/aga/aga.c
@@ -3,6 +3,8 @@
#include <stdbool.h>
+#include <ccan/queue/queue.h>
+
#include <ccan/aga/aga.h>
void aga_init(struct aga_graph *g, aga_edge_fn edge_fn)
@@ -62,3 +64,42 @@ int aga_depth_first_search(struct aga_graph *g, struct aga_node *start,
return 0;
}
+
+static void bfs_queue_node(struct aga_graph *g, struct aga_node *node,
+ struct queue *q)
+{
+ if (!update_node(g, node))
+ return;
+
+ queue_enqueue(q, &node->u.bfs);
+}
+
+int aga_breadth_first_search(struct aga_graph *g, struct aga_node *start,
+ aga_visit_fn fn, void *opaque)
+{
+ QUEUE(q);
+
+ if (aga_start(g))
+ return -1;
+
+ bfs_queue_node(g, start, &q);
+
+ while (!queue_empty(&q)) {
+ struct aga_node *node = queue_entry(queue_dequeue(&q),
+ struct aga_node, u.bfs);
+ struct aga_edge edge;
+ void *p;
+
+ fn(g, node, opaque);
+
+ p = g->edge_fn(g, node, &edge, NULL);
+ while (p) {
+ bfs_queue_node(g, edge.to, &q);
+ p = g->edge_fn(g, node, &edge, p);
+ }
+ }
+
+ aga_finish(g);
+
+ return 0;
+}
diff --git a/ccan/aga/aga.h b/ccan/aga/aga.h
index cfa9791..e9fa583 100644
--- a/ccan/aga/aga.h
+++ b/ccan/aga/aga.h
@@ -4,12 +4,17 @@
#include "config.h"
#include <string.h>
+#include <ccan/queue/queue.h>
+
/*
*
*/
struct aga_node {
int sequence;
+ union {
+ struct queue_entry bfs;
+ } u;
};
struct aga_edge {
@@ -38,4 +43,7 @@ typedef int(*aga_visit_fn)(struct aga_graph *, struct aga_node *, void *);
int aga_depth_first_search(struct aga_graph *g, struct aga_node *start,
aga_visit_fn fn, void *opaque);
+int aga_breadth_first_search(struct aga_graph *g, struct aga_node *start,
+ aga_visit_fn fn, void *opaque);
+
#endif /* CCAN_AGA_H */
diff --git a/ccan/aga/test/run-chain.c b/ccan/aga/test/run-chain.c
index 55e6e16..2da3486 100644
--- a/ccan/aga/test/run-chain.c
+++ b/ccan/aga/test/run-chain.c
@@ -74,7 +74,7 @@ int main(void)
setup();
/* This is how many tests you plan to run */
- plan_tests(3);
+ plan_tests(6);
/* Depth-first traverse forwards */
memset(&tb, 0, sizeof(tb));
@@ -93,6 +93,25 @@ int main(void)
visit_fn, &tb);
check_trace(&tb, 4, 3, 2, 1, 0, 5, 6, 7);
+
+ /* Breadth-first traversee forwards */
+ memset(&tb, 0, sizeof(tb));
+ aga_breadth_first_search(&chain_graph, &chain[0], visit_fn, &tb);
+ check_trace(&tb, 0, 1, 2, 3, 4, 5, 6, 7);
+
+ /* Breadth-first traversee backwards */
+ memset(&tb, 0, sizeof(tb));
+ aga_breadth_first_search(&chain_graph, &chain[CHAIN_LENGTH - 1],
+ visit_fn, &tb);
+ check_trace(&tb, 7, 6, 5, 4, 3, 2, 1, 0);
+
+ /* Breadth-first traversee outwards */
+ memset(&tb, 0, sizeof(tb));
+ aga_breadth_first_search(&chain_graph, &chain[CHAIN_LENGTH/2],
+ visit_fn, &tb);
+ check_trace(&tb, 4, 3, 5, 2, 6, 1, 7, 0);
+
+
/* This exits depending on whether all tests passed */
return exit_status();
}
diff --git a/ccan/aga/test/run-grid.c b/ccan/aga/test/run-grid.c
index 482b8dd..9c6cf05 100644
--- a/ccan/aga/test/run-grid.c
+++ b/ccan/aga/test/run-grid.c
@@ -164,7 +164,7 @@ int main(void)
setup();
/* This is how many tests you plan to run */
- plan_tests(10);
+ plan_tests(20);
/* (A) Depth-first traverse from top-left */
memset(&tb, 0, sizeof(tb));
@@ -192,6 +192,32 @@ int main(void)
check_trace(&tb, 4, 5, 8, 7);
+ /* (A) Breadth-first traverse from top-left */
+ memset(&tb, 0, sizeof(tb));
+ aga_breadth_first_search(&grid_graph_a, &grid[0].a, visit_fn_a, &tb);
+ check_trace(&tb, 0, 1, 3, 2, 4, 6, 5, 7, 8);
+
+ /* (A) Breadth-first traverse from top-right */
+ memset(&tb, 0, sizeof(tb));
+ aga_breadth_first_search(&grid_graph_a, &grid[2].a, visit_fn_a, &tb);
+ check_trace(&tb, 2, 5, 8);
+
+ /* (A) Breadth-first traverse from bottom-left */
+ memset(&tb, 0, sizeof(tb));
+ aga_breadth_first_search(&grid_graph_a, &grid[6].a, visit_fn_a, &tb);
+ check_trace(&tb, 6, 7, 8);
+
+ /* (A) Breadth-first traverse from bottom-right */
+ memset(&tb, 0, sizeof(tb));
+ aga_breadth_first_search(&grid_graph_a, &grid[8].a, visit_fn_a, &tb);
+ check_trace(&tb, 8);
+
+ /* (A) Breadth-first traverse from centre */
+ memset(&tb, 0, sizeof(tb));
+ aga_breadth_first_search(&grid_graph_a, &grid[4].a, visit_fn_a, &tb);
+ check_trace(&tb, 4, 5, 7, 8);
+
+
/* (B) Depth-first traverse from top-left */
memset(&tb, 0, sizeof(tb));
aga_depth_first_search(&grid_graph_b, &grid[0].b, visit_fn_b, &tb);
@@ -217,6 +243,33 @@ int main(void)
aga_depth_first_search(&grid_graph_b, &grid[4].b, visit_fn_b, &tb);
check_trace(&tb, 4, 5, 8, 7, 6, 3, 0, 1, 2);
+
+ /* (B) Breadth-first traverse from top-left */
+ memset(&tb, 0, sizeof(tb));
+ aga_breadth_first_search(&grid_graph_b, &grid[0].b, visit_fn_b, &tb);
+ check_trace(&tb, 0, 1, 3, 2, 4, 6, 5, 7, 8);
+
+ /* (B) Breadth-first traverse from top-right */
+ memset(&tb, 0, sizeof(tb));
+ aga_breadth_first_search(&grid_graph_b, &grid[2].b, visit_fn_b, &tb);
+ check_trace(&tb, 2, 5, 1, 8, 4, 0, 7, 3, 6);
+
+ /* (B) Breadth-first traverse from bottom-left */
+ memset(&tb, 0, sizeof(tb));
+ aga_breadth_first_search(&grid_graph_b, &grid[6].b, visit_fn_b, &tb);
+ check_trace(&tb, 6, 7, 3, 8, 4, 0, 5, 1, 2);
+
+ /* (B) Breadth-first traverse from bottom-right */
+ memset(&tb, 0, sizeof(tb));
+ aga_breadth_first_search(&grid_graph_b, &grid[8].b, visit_fn_b, &tb);
+ check_trace(&tb, 8, 7, 5, 6, 4, 2, 3, 1, 0);
+
+ /* (B) Breadth-first traverse from centre */
+ memset(&tb, 0, sizeof(tb));
+ aga_breadth_first_search(&grid_graph_b, &grid[4].b, visit_fn_b, &tb);
+ check_trace(&tb, 4, 5, 7, 3, 1, 8, 2, 6, 0);
+
+
/* This exits depending on whether all tests passed */
return exit_status();
}
--
1.9.3
More information about the ccan
mailing list