<p dir="ltr">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'.</p>
<p dir="ltr">Ben</p>
<br><div class="gmail_quote">On Fri, 6 Mar 2015 2:46 am Jeffrey Brown <<a href="mailto:jeffbrown.the@gmail.com">jeffbrown.the@gmail.com</a>> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>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.<br><br>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.<br><br>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.<br><br></div><div>Python code for the algorithm:<br>  def descendedOnlyFrom(gset):<br>    "All Gnodes n for which every ancestry of n includes a Gnode in gset (which can be a set or a list)."<br>    # For efficiency improvement ideas and verbose comments,<br>      # see treeSearch/<a href="http://all.py/node.descendedOnlyFrom" target="_blank">all.py/node.descendedOnlyFrom</a><br>    if 1: # variables<br>      # "pure" = "descended only from the calling Glist"<br>      pe = set(gset) # determined Pure, yet to Explore children of<br>      pf = set() # determined Pure, Finished exploring children of<br>      pb = set(gset) # determined Pure, Both kinds: pe | pf<br>      ud = set() # purity UnDetermined<br>        # descended from root, but might have parents outside of pb<br>      udp = {} # "Parents of the UnDetermined"<br>        # This is a dictionary, from gnodes to sets of gnodes.<br>        # The other four variables are sets.<br>    while pe:<br>      while pe:<br>        k = 1<br>        i = pe.pop();    pf.add(i)<br>        for c in set(i._children()):<br>          if c in pb | ud: continue # If already handled, do not repeat.<br>          if set(c._parents()) <= pb:<br>            pe.add(c);    pb.add(c)<br>          else:<br>            ud.add(c);    udp[c] = set(c._parents()) - pb<br>      for i in ud:<br>        ipf = udp[i] & pb # (i)'s (p)arents newly (f)ound in pb<br>        if ipf:<br>          udp[i] -= ipf<br>          if udp[i]==set():<br>            ud.remove(i);    del( udp[i] )<br>            pe.add(i);       pb.add(i)<br>            break<br>    return pb</div></div>
______________________________<u></u>_________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org" target="_blank">Haskell-Cafe@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" target="_blank">http://mail.haskell.org/cgi-<u></u>bin/mailman/listinfo/haskell-<u></u>cafe</a><br>
</blockquote></div>