[Haskell-cafe] Imperative graph algorithm, (tail?) recursion, and speed

[Benjamin Edwards]

Have you looked at fgl? I would also read the paper that went with the
library. It has some nice notions of graph decomposition, and reading the
source for bfs et al should give you a good idea of how to mix in state
like 'what have I visited'.

Ben

On Fri, 6 Mar 2015 2:46 am Jeffrey Brown <jeffbrown.the at gmail.com> wrote:

> Suppose I have a general (not a tree) directed graph, and I would like to
> find all the "pure descendents" of a node N -- that is, all nodes M for
> which (1) N is an ancestor of M, and (2) every partial or maximal sequence
> of predecessors starting from M either consists entirely of descendents of
> N, or else includes N itself.
>
> I have an imperative algorithm (below) for doing that. I want to know how
> hard it would be to implement in Haskell. It's complex, but basically it
> sets up a few lists like "members of this list have had all their
> descendents processed", "members of this list have been processed but their
> descendents have not been", "members of this list have not been processed
> at all", etc. Then I iterate through the graph, moving nodes from one
> collection to the other until the "to be processed" list is empty.
>
> I would like a function Graph -> Graph that does that and does not need to
> rely on a monad. The only way I can think of involves a few mutually
> recursive functions, each of which passes not only the original graph of
> interest, but all the lists described in the previous paragraph, around to
> the others. I don't understand Haskell's evaluation strategy well enough to
> anticipate the result, but my vague sense is that a lot of copies of the
> same data would be floating around, ruining the speed of it.
>
> Python code for the algorithm:
>   def descendedOnlyFrom(gset):
>     "All Gnodes n for which every ancestry of n includes a Gnode in gset
> (which can be a set or a list)."
>     # For efficiency improvement ideas and verbose comments,
>       # see treeSearch/all.py/node.descendedOnlyFrom
>     if 1: # variables
>       # "pure" = "descended only from the calling Glist"
>       pe = set(gset) # determined Pure, yet to Explore children of
>       pf = set() # determined Pure, Finished exploring children of
>       pb = set(gset) # determined Pure, Both kinds: pe | pf
>       ud = set() # purity UnDetermined
>         # descended from root, but might have parents outside of pb
>       udp = {} # "Parents of the UnDetermined"
>         # This is a dictionary, from gnodes to sets of gnodes.
>         # The other four variables are sets.
>     while pe:
>       while pe:
>         k = 1
>         i = pe.pop();    pf.add(i)
>         for c in set(i._children()):
>           if c in pb | ud: continue # If already handled, do not repeat.
>           if set(c._parents()) <= pb:
>             pe.add(c);    pb.add(c)
>           else:
>             ud.add(c);    udp[c] = set(c._parents()) - pb
>       for i in ud:
>         ipf = udp[i] & pb # (i)'s (p)arents newly (f)ound in pb
>         if ipf:
>           udp[i] -= ipf
>           if udp[i]==set():
>             ud.remove(i);    del( udp[i] )
>             pe.add(i);       pb.add(i)
>             break
>     return pb
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20150306/a7db2113/attachment.html>