On 14 August 2015 at 06:43, Jeffrey Brown wrote:

Given a node N and an edge label L, I want to do things like "find N, and all of N's L-children, and all of their L-children ... and add up their values". Ideally the fold would not traverse the whole graph. (Note that in general, the subgraph induced by N and L-succession is not a tree.)

Writing the fold myself, I can only imagine a very inefficient solution -- I would find each of N's L-children first, collect them, then find each of theirs, etc.

In Data.Graph.Inductive.Basic, FGL provides a function called "gfold". This is its type signature:

-- | Directed graph fold. gfold :: (Graph gr) => (Context a b -> [Node]) -- ^ direction of fold -> (Context a b -> c -> d) -- ^ depth aggregation -> (Maybe d -> c -> c, c) -- ^ breadth\/level aggregation -> [Node] -> gr a b -> c

Is it what I'm looking for? If so, how does it work?

I suspect it _isn't_ what you're looking for, as you don't want to traverse the entire graph. For an example of what you could do, have a look here: https://github.com/haskell/fgl/blob/master/fgl-arbitrary/test/TestSuite.hs#L... (where `vis` is a Set is used to keep track of already visited nodes to avoid getting into endless loops, and `cnd` is a set of candidates for recursion).

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

-- Ivan Lazar Miljenovic Ivan.Miljenovic@gmail.com http://IvanMiljenovic.wordpress.com