git.ozlabs.org Git - ccan/blob - ccan/aga/bfs.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  * Breadth first search
  13  */
  14
  15 typedef LQUEUE(struct aga_node, u.bfs.next) bfs_queue;
  16
  17 static bool bfs_enqueue(struct aga_graph *g, bfs_queue *queue,
  18                         struct aga_node *n)
  19 {
  20         if (!aga_update_node(g, n))
  21                 return false;
  22
  23         lqueue_enqueue(queue, n);
  24         n->u.bfs.edge = aga_first_edge(g, n);
  25         return true;
  26 }
  27
  28 static struct aga_node *bfs_front(bfs_queue *queue)
  29 {
  30         return lqueue_front(queue);
  31 }
  32
  33 static void bfs_dequeue(bfs_queue *queue)
  34 {
  35         (void) lqueue_dequeue(queue);
  36 }
  37
  38 int aga_bfs_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_bfs_explore(struct aga_graph *g, struct aga_node *n)
  50 {
  51         bfs_queue queue = LQUEUE_INIT;
  52
  53         if (!aga_check_state(g))
  54                 return NULL;
  55
  56         if (!n)
  57                 return NULL;
  58
  59         if (bfs_enqueue(g, &queue, n))
  60                 return n;
  61
  62         lqueue_init_from_back(&queue, n);
  63
  64         while ((n = bfs_front(&queue))) {
  65                 const void *e = n->u.bfs.edge;
  66                 int err;
  67                 struct aga_edge_info ei;
  68
  69                 if (!e) {
  70                         /* out of edges, back up */
  71                         bfs_dequeue(&queue);
  72                         continue;
  73                 }
  74
  75                 n->u.bfs.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 (!bfs_enqueue(g, &queue, ei.to)) {
  88                         /* already visited node */
  89                         continue;
  90                 }
  91
  92                 return ei.to;
  93         }
  94
  95         return NULL;
  96 }