[Haskell-cafe] Traversing a graph in STM
jmaessen at alum.mit.edu
Sun Sep 17 17:16:42 EDT 2006
On Sep 13, 2006, at 3:37 AM, Einar Karttunen wrote:
> 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
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
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
Would that there were!
> - Einar Karttunen
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
-------------- next part --------------
A non-text attachment was scrubbed...
Size: 2425 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20060917/e8d68062/smime.bin
More information about the Haskell-Cafe