[Haskell-cafe] Folding part of a graph, and FGL's gfold function.

[Ivan Lazar Miljenovic]

On 14 August 2015 at 06:43, Jeffrey Brown <jeffbrown.the at gmail.com> 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#L50
(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 at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
>



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