[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.
> 
> 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).

So, I've looked into this.  I do prefer the open-traversal approach
from the caller's point of view, but implementing it for DFS is
surprisingly difficult.

-- 
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/20140714/e17b2e0e/attachment.sig>