[Haskell-cafe] Traversing a graph in STM

[Jan-Willem Maessen]

On Sep 13, 2006, at 3:37 AM, Einar Karttunen wrote:

> Hello
>
> Is there an elegant way of traversing a directed graph in STM?
>
> type Node  nt et = TVar (NodeT nt et)
> type Edge  et    = TVar et
> data NodeT nt et = NodeT nt [(Node nt et, Edge et)]
>
> type MyGraph = Node String Int
>
> When implementing a simple depth first search we need a way to
> mark nodes (= TVars) as visited. In addition multiple concurrent
> searches should be possible.
>
> Is it possible to avoid passing around an explicit Set of visited
> nodes?

You can associate a unique name with each traversal, and store a set  
of traversals at each node (instead of a mark bit).  But this set  
grows without bound unless you follow each traversal with a "cleaning  
traversal" which removes a traversal tag from the set.  And you'd  
need some way to generate the unique names.

If you're performing no side effects or accesses to TVars (which you  
aren't, as your graph representation requires reading TVars all over  
the place), you can in principle use the following horrid kludge:
   1) keep a TVar indicating "visited" at each node.
   2) within an atomic, perform your traversal in the usual  
sequential way, setting the TVar
      each time a node is visited.
   3) when you're done, package up your desired result in an  
exception and throw it.
      All your marking work will be un-done and your result will emerge.
   4) catch the exception outside the atomic and extract the result  
again.

However, this will still preclude two simultaneous traversals of  
overlapping portions of the graph.  Really, you're just asking the  
STM mechanism to maintain the hash table on your behalf; in practice  
you will be better off doing it yourself.

Really, there's no such thing as a free lunch here, I'm afraid.  If  
you want to concurrently traverse a graph, you need to keep separate  
cycle-avoidance state for each traversal.  Using TVars doesn't change  
that basic algorithmic detail.

> And is there a better way of getting TVar identity than
> StableNames?

Would that there were!

-Jan-Willem Maessen

>
> - Einar Karttunen
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 2425 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20060917/e8d68062/smime.bin