<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
<META content="MSHTML 6.00.2800.1498" name=GENERATOR>
<STYLE></STYLE>
</HEAD>
<BODY bgColor=#ffffff>
<DIV><SPAN class=172190114-25052005><FONT face=Arial color=#0000ff size=2>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? ...),</FONT></SPAN></DIV>
<DIV><SPAN class=172190114-25052005><FONT face=Arial color=#0000ff size=2>but
the first idea that comes to mind is to use a set or an ets table to mark
already visited nodes.</FONT></SPAN></DIV>
<DIV><SPAN class=172190114-25052005><FONT face=Arial color=#0000ff size=2>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.</FONT></SPAN></DIV>
<DIV><SPAN class=172190114-25052005><FONT face=Arial color=#0000ff size=2>--
Thomas</FONT></SPAN></DIV>
<BLOCKQUOTE dir=ltr style="MARGIN-RIGHT: 0px">
<DIV class=OutlookMessageHeader dir=ltr align=left><FONT face=Tahoma
size=2>-----Original Message-----<BR><B>From:</B>
owner-erlang-questions@erlang.org
[mailto:owner-erlang-questions@erlang.org]<B>On Behalf Of </B>Vlad
Dumitrescu<BR><B>Sent:</B> den 25 maj 2005 15:50<BR><B>To:</B>
erlang-questions@erlang.org<BR><B>Subject:</B> Traversing
graphs<BR><BR></FONT></DIV>
<DIV><FONT face=Arial size=2>Hi all,</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2>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.</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2>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.</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2>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?
</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2>I have partial solutions, but I seem to be
missing something, and such a problem can't be something new in computer
science.</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2>Thanks in advance! best regards,</FONT></DIV>
<DIV><FONT face=Arial size=2>Vlad</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV></BLOCKQUOTE></BODY></HTML>