[ccan] [PATCH 3/7] aga: Depth first search

[David Gibson]

On Fri, Jul 10, 2015 at 10:26:34AM +0930, Paul 'Rusty' Russell wrote:
> David Gibson <david at gibson.dropbear.id.au> writes:
> > diff --git a/ccan/aga/aga.h b/ccan/aga/aga.h
> > index 2088c0f..e41ed97 100644
> > --- a/ccan/aga/aga.h
> > +++ b/ccan/aga/aga.h
> > @@ -111,12 +111,17 @@
> >  #include "config.h"
> >  #include <string.h>
> >  
> > +#include <ccan/lstack/lstack.h>
> > +
> >  struct aga_graph;
> >  
> >  struct aga_node {
> >  	int sequence;
> >  	union {
> > -		/* Per-algorithm state here */
> > +		struct {
> > +			struct lstack_link parent;
> > +			const void *edge;
> > +		} dfs;
> >  	} u;
> >  };
> >  
> > @@ -175,4 +180,14 @@ int aga_edge_info(const struct aga_graph *g, const struct aga_node *n,
> >  	     (_e) = aga_next_edge((_g), (_n), (_e)))			\
> >  		if ((_ei).to)
> >  
> > +/*
> > + * Depth first search
> > + */
> > +
> > +int aga_dfs_start(struct aga_graph *g);
> > +struct aga_node *aga_dfs_next(struct aga_graph *g, struct aga_node *n);
> > +
> > +#define aga_dfs_foreach(_n, _g, _start)					\
> > +	for ((_n) = (_start); ((_n) = aga_dfs_next((_g), (_n))) != NULL; )
> > +
> 
> This API is unexpected (at least to me, a casual observer).
> 
> I expected foreach() to call aga_dfs_start() for you, and aga_finish()
> too.
> 
> I know that would make it hard to feed the reentrancy detection back to
> the caller.  But I wonder if you want a global callback on re-entrancy
> detection, which defaults to aborting.  Callers who care will replace
> it.
> 
> Then you could make aga_dfs_start() return aga_dfs_next(), right?  And
> return NULL if that re-entrancy checkfn returns.
> 
> aga_dfs_next() should probably call aga_finish before returning NULL.
> Or maybe not, since you'll need to call it if you break out of the loop?
> 
> The result would be:
> 
> /* If you break out of the loop, be sure to call aga_finish()! */
> #define aga_dfs_foreach(_n, _g, _start)					\
>         for ((_n) = aga_dfs_start(_g); (_n); (_n) = aga_dfs_next((_g), (_n)))

So, yeah, there are some reasons for the interface I'm using, which
probably need explanation somewhere.

First, I couldn't see a sane way to incorporate the aga_finish() into
a for-like macro.  And if I can't include the finish(), it seemed
asymmetric to include the start().

The second reason is the deeper one, and it's related to the reason
that the start node is specified in aga_dfs_foreach() / aga_dfs_next()
instead of in aga_dfs_start().

It's actually one of the simpler examples of an inherent complication
with aga's approach: it can't ever do a "for each node", it can only
find the nodes via the edges.

So, aga_dfs_foreach() doesn't actually traverse every node - just the
ones reachable from the given _start node.  That means for a graph
that isn't all reachable for a single start point you might want to
use aga_dfs_foreach multiple times from different starting locations.
Those all need to be within the same aga_start/aga_finish pair, so
that you don't repeatedly traverse any nodes that are reachable from
multiple starting points.  The "traversal1" case in the tests is an
exmaple of such a graph.

-- 
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/20150710/435360d2/attachment.sig>