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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe