Imperative graph algorithm, (tail?) recursion, and speed

5 Mar 2015

      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

Jeffrey Brown

Benjamin Edwards

Jeffrey Brown

Ivan Lazar Miljenovic

Jeffrey Brown

Ivan Lazar Miljenovic

Bob Ippolito

tags

participants (4)