On 9/17/06, 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.
Well, if your set implementation used weak pointers there would be no need for a cleaning traversal. The garbage collector will take care of that. The only slightly tricky thing is to keep a live pointer to the unique traversal name during the entire of the traversal. But I don't think that should be a big problem. Cheers, Josef