[Haskell-cafe] Folding part of a graph, and FGL's gfold function.
Ivan Lazar Miljenovic
ivan.miljenovic at gmail.com
Fri Aug 14 02:10:04 UTC 2015
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
More information about the Haskell-Cafe
mailing list