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 static bool dfs_push(struct aga_graph *g, struct lstack *stack,
  16                      struct aga_node *n)
  17 {
  18         if (!aga_update_node(g, n))
  19                 return false;
  20
  21         lstack_push(stack, n, u.dfs.parent);
  22         n->u.dfs.edge = aga_first_edge(g, n);
  23         return true;
  24 }
  25
  26 static void dfs_pop(struct lstack *stack)
  27 {
  28         lstack_pop(stack, struct aga_node, u.dfs.parent);
  29 }
  30
  31 static struct aga_node *dfs_top(struct lstack *stack)
  32 {
  33         return lstack_top(stack, struct aga_node, u.dfs.parent);
  34 }
  35
  36 int aga_dfs_start(struct aga_graph *g)
  37 {
  38         int rc;
  39
  40         rc = aga_start(g);
  41         if (rc < 0)
  42                 return rc;
  43
  44         return 0;
  45 }
  46
  47 struct aga_node *aga_dfs_explore(struct aga_graph *g, struct aga_node *n)
  48 {
  49         LSTACK(stack);
  50
  51         if (!aga_check_state(g))
  52                 return NULL;
  53
  54         if (!n)
  55                 return NULL;
  56
  57         if (dfs_push(g, &stack, n))
  58                 return n;
  59
  60         lstack_init_from_top(&stack, n, u.dfs.parent);
  61
  62         while ((n = dfs_top(&stack))) {
  63                 const void *e = n->u.dfs.edge;
  64                 int err;
  65                 struct aga_edge_info ei;
  66
  67                 if (!e) {
  68                         /* out of edges, back up */
  69                         dfs_pop(&stack);
  70                         continue;
  71                 }
  72
  73                 n->u.dfs.edge = aga_next_edge(g, n, e);
  74
  75                 err = aga_edge_info(g, n, e, &ei);
  76                 if (err < 0) {
  77                         aga_fail(g, err);
  78                         return NULL;
  79                 }
  80                 if (!ei.to) {
  81                         /* missing edge */
  82                         continue;
  83                 }
  84
  85                 if (!dfs_push(g, &stack, ei.to)) {
  86                         /* already visited node */
  87                         continue;
  88                 }
  89
  90                 return ei.to;
  91         }
  92
  93         return NULL;
  94 }