git.ozlabs.org Git - ccan/blob - ccan/aga/dfs.c

   1 /* Licensed under LGPLv2+ - see LICENSE file for details */
   2 #include "config.h"
   3
   4 #include <stdbool.h>
   5 #include <stdlib.h>
   6 #include <assert.h>
   7
   8 #include <ccan/aga/aga.h>
   9 #include "private.h"
  10
  11 /*
  12  * Depth first search
  13  */
  14
  15 typedef LSTACK(struct aga_node, u.dfs.parent) dfs_stack;
  16
  17 static bool dfs_push(struct aga_graph *g, dfs_stack *stack,
  18                      struct aga_node *n)
  19 {
  20         if (!aga_update_node(g, n))
  21                 return false;
  22
  23         lstack_push(stack, n);
  24         n->u.dfs.edge = aga_first_edge(g, n);
  25         return true;
  26 }
  27
  28 static void dfs_pop(dfs_stack *stack)
  29 {
  30         (void) lstack_pop(stack);
  31 }
  32
  33 static struct aga_node *dfs_top(dfs_stack *stack)
  34 {
  35         return lstack_top(stack);
  36 }
  37
  38 int aga_dfs_start(struct aga_graph *g)
  39 {
  40         int rc;
  41
  42         rc = aga_start(g);
  43         if (rc < 0)
  44                 return rc;
  45
  46         return 0;
  47 }
  48
  49 struct aga_node *aga_dfs_explore(struct aga_graph *g, struct aga_node *n)
  50 {
  51         dfs_stack stack = LSTACK_INIT;
  52
  53         if (!aga_check_state(g))
  54                 return NULL;
  55
  56         if (!n)
  57                 return NULL;
  58
  59         if (dfs_push(g, &stack, n))
  60                 return n;
  61
  62         lstack_init_from_top(&stack, n);
  63
  64         while ((n = dfs_top(&stack))) {
  65                 const void *e = n->u.dfs.edge;
  66                 int err;
  67                 struct aga_edge_info ei;
  68
  69                 if (!e) {
  70                         /* out of edges, back up */
  71                         dfs_pop(&stack);
  72                         continue;
  73                 }
  74
  75                 n->u.dfs.edge = aga_next_edge(g, n, e);
  76
  77                 err = aga_edge_info(g, n, e, &ei);
  78                 if (err < 0) {
  79                         aga_fail(g, err);
  80                         return NULL;
  81                 }
  82                 if (!ei.to) {
  83                         /* missing edge */
  84                         continue;
  85                 }
  86
  87                 if (!dfs_push(g, &stack, ei.to)) {
  88                         /* already visited node */
  89                         continue;
  90                 }
  91
  92                 return ei.to;
  93         }
  94
  95         return NULL;
  96 }