1 /* Licensed under LGPLv2+ - see LICENSE file for details */
8 #include <ccan/aga/aga.h>
15 typedef LSTACK(struct aga_node, u.dfs.parent) dfs_stack;
17 static bool dfs_push(struct aga_graph *g, dfs_stack *stack,
20 if (!aga_update_node(g, n))
23 lstack_push(stack, n);
24 n->u.dfs.edge = aga_first_edge(g, n);
28 static void dfs_pop(dfs_stack *stack)
30 (void) lstack_pop(stack);
33 static struct aga_node *dfs_top(dfs_stack *stack)
35 return lstack_top(stack);
38 int aga_dfs_start(struct aga_graph *g)
49 struct aga_node *aga_dfs_explore(struct aga_graph *g, struct aga_node *n)
51 dfs_stack stack = LSTACK_INIT;
53 if (!aga_check_state(g))
59 if (dfs_push(g, &stack, n))
62 lstack_init_from_top(&stack, n);
64 while ((n = dfs_top(&stack))) {
65 const void *e = n->u.dfs.edge;
67 struct aga_edge_info ei;
70 /* out of edges, back up */
75 n->u.dfs.edge = aga_next_edge(g, n, e);
77 err = aga_edge_info(g, n, e, &ei);
87 if (!dfs_push(g, &stack, ei.to)) {
88 /* already visited node */