Wed May 25 19:55:49 CEST 2005
From: Thomas Johnsson XA (LN/EAB)
>the first idea that comes to mind is to use a set or an ets table to mark
>already visited nodes.
From: "Mikael Karlsson" <mikael.karlsson@REDACTED>
> are not the digraph and digraph_utils modules in stdlib useful to you?
Unfortunately, no. I have my graph in a different format, and converting
isn't so easy.
To explain in more detail, I am working on a parser. The graph's nodes are
the grammar productions, and by referring to another nonterminal they are
linking to another production.
What I want to do is process the grammar in different ways: for example,
simplifying it or eliminating unreferenced productions. Most of the times,
it's easy to traverse everything, but there are some special cases, where I
have to propagate production attributes "upwards".
Using ets as Thomas suggested is probably easiest, and another easy to
implement solution is to repeatedly traversing all nodes until there are no
more changes. I think I didn't see those before because I was locked on
finding a completely functional solution. It should be possible and now it
has become an intellectual chalenge.
Thanks for the answers!
More information about the erlang-questions