[Haskell-cafe] Traversing a graph in STM

[Josef Svenningsson]

On 9/17/06, Jan-Willem Maessen <jmaessen at alum.mit.edu> wrote:
>
> 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