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