[ccan] [PATCH 2/4] aga: Abstract Graph Algorithms

[Rusty Russell]

David Gibson <david at gibson.dropbear.id.au> writes:
> This module implements some standard graph algoriths.  Rather than
> expecting a specific concrete representation of the graph, it uses
> callbacks, so that the calling code can compute the graph edges on the fly.
> The graph nodes can also be constructed as they're discovered, although
> some information about them does then need to be retained for the life of
> the algorithm.

I had to stare at this for quite a while, and I'm still not sure I get
it.

Querying for an edge makes sense, though the lack of const (and
documentation!) made it confusing:

        typedef void *(*aga_edge_fn)(struct aga_graph *, struct aga_node *,
        			     struct aga_edge *, void *);

I *think* the graph and node are nominally const, and the edge is
returned along with the non-NULL cookie, right?

I idly wonder if there's an opportunity to create open-traversal
variants: they're usually nicer than callbacks in C, eg:

        for (n = aga_dfs_first(graph, start);
             n;
             n = aga_dfs_next(graph, n)) {
                ...

But I think that requires two pointers per node (one "back" pointer, and
one to store cookies).

Thanks,
Rusty.