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"
/*
* Depth first search
*/
static bool dfs_push(struct aga_graph *g, struct lstack *stack,
struct aga_node *n)
{
if (!aga_update_node(g, n))
return false;
lstack_push(stack, n, u.dfs.parent);
n->u.dfs.edge = aga_first_edge(g, n);
return true;
}
static void dfs_pop(struct lstack *stack)
{
lstack_pop(stack, struct aga_node, u.dfs.parent);
}
static struct aga_node *dfs_top(struct lstack *stack)
{
return lstack_top(stack, struct aga_node, u.dfs.parent);
}
int aga_dfs_start(struct aga_graph *g)
{
int rc;
rc = aga_start(g);
if (rc < 0)
return rc;
return 0;
}
struct aga_node *aga_dfs_explore(struct aga_graph *g, struct aga_node *n)
{
LSTACK(stack);
if (!aga_check_state(g))
return NULL;
if (!n)
return NULL;
if (dfs_push(g, &stack, n))
return n;
lstack_init_from_top(&stack, n, u.dfs.parent);
while ((n = dfs_top(&stack))) {
const void *e = n->u.dfs.edge;
int err;
struct aga_edge_info ei;
if (!e) {
/* out of edges, back up */
dfs_pop(&stack);
continue;
}
n->u.dfs.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 (!dfs_push(g, &stack, ei.to)) {
/* already visited node */
continue;
}
return ei.to;
}
return NULL;
}
|
