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

[David Gibson]

On Tue, Jul 08, 2014 at 08:44:56PM +0930, Paul 'Rusty' Russell wrote:
> 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.

Heh.. yeah.. it needs a bunch more explanation.  A list of rules for
the edge function in particular.

> 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?

Yes, that's 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).

Hrm.. interesting idea.  Visitor functions are usually a bit of a
pain.  The back pointer works fairly naturally; it's essentially an
explicit stack of nodes as a neat contrast to the queue that a breadth
first search uses.  Storing the edge function cookie as well is a bit
uglier.  But it will still be less space in the node than Dijstra's
algorithm will need, so..  I'll give it some thought.

-- 
David Gibson			| I'll have my music baroque, and my code
david AT gibson.dropbear.id.au	| minimalist, thank you.  NOT _the_ _other_
				| _way_ _around_!
http://www.ozlabs.org/~dgibson
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 819 bytes
Desc: not available
URL: <http://lists.ozlabs.org/pipermail/ccan/attachments/20140709/15a8d053/attachment.sig>