Traversing graphs

Vlad Dumitrescu vlad_dumitrescu@REDACTED
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 mailing list