1 /* Licensed under LGPLv2+ - see LICENSE file for details */
8 #include <ccan/aga/aga.h>
12 * Breadth first search
15 typedef LQUEUE(struct aga_node, u.bfs.next) bfs_queue;
17 static bool bfs_enqueue(struct aga_graph *g, bfs_queue *queue,
20 if (!aga_update_node(g, n))
23 lqueue_enqueue(queue, n);
24 n->u.bfs.edge = aga_first_edge(g, n);
28 static struct aga_node *bfs_front(bfs_queue *queue)
30 return lqueue_front(queue);
33 static void bfs_dequeue(bfs_queue *queue)
35 (void) lqueue_dequeue(queue);
38 int aga_bfs_start(struct aga_graph *g)
49 struct aga_node *aga_bfs_explore(struct aga_graph *g, struct aga_node *n)
51 bfs_queue queue = LQUEUE_INIT;
53 if (!aga_check_state(g))
59 if (bfs_enqueue(g, &queue, n))
62 lqueue_init_from_back(&queue, n);
64 while ((n = bfs_front(&queue))) {
65 const void *e = n->u.bfs.edge;
67 struct aga_edge_info ei;
70 /* out of edges, back up */
75 n->u.bfs.edge = aga_next_edge(g, n, e);
77 err = aga_edge_info(g, n, e, &ei);
87 if (!bfs_enqueue(g, &queue, ei.to)) {
88 /* already visited node */