Traversing graphs

[Thomas Johnsson XA (LN/EAB)]

You don't give any details on what you really want to do with the graph, eg what sort of traversal (depth first? breath first? ...),
but the first idea that comes to mind is to use a set or an ets table to mark already visited nodes.
In any case, since Erlang is an imperative language (yeah yeah no flames please, I mean in the sense of allowing side effects :-), standard textbook algorithms should be 'easily' transliterated.
-- Thomas

-----Original Message-----
From: owner-erlang-questions@REDACTED [mailto:owner-erlang-questions@REDACTED]On Behalf Of Vlad Dumitrescu
Sent: den 25 maj 2005 15:50
To: erlang-questions@REDACTED
Subject: Traversing graphs


Hi all,
 
I just hit a problem where I clearly see how simple it would be with lazy evaluation. But since we don't have that, I wonder if anyone could point me to some non-lazy algorithms.
 
I have a graph described by a list of nodes. The nodes refer to other nodes by name. I need to traverse the graph and do stuff on each node, without traversing a node more than once. Of course, the 'stuff' done above is recursive (the value for a node depends on the values of its linked nodes), so visiting a node results in visiting all linked ones.
 
All references I found about doing this in a functional language are Haskell ones, and they use lazyness. Does anyone know about where to look for hints on how to solve this in a strict language? 
 
I have partial solutions, but I seem to be missing something, and such a problem can't be something new in computer science.
 
Thanks in advance! best regards,
Vlad
 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20050525/89e7761a/attachment.htm>