Traversing graphs
Thomas Lindgren
<>
Fri May 27 15:41:03 CEST 2005
--- Vlad Dumitrescu <>
wrote:
> From: "Vladimir Sekissov" <>
> > May be it could be easier with
> continuation-passing style
>
> Yes, that's a good idea. I will look at it.
>
> Maybe my main problem is that I try to wite a
> general mapfold-like function,
> when it would be easier to do it in several steps.
> For example first mark
> some nodes with attributes, then transform the graph
> according to the
> markings.
That is, in my experience, often a good idea. (You can
usually mangle the code later if it turns out to be
costly.)
When working with graphs, the primary problem is
representation IMO. I work with small or medium-sized
graphs (usually 100-1000 nodes or so) and like using
functional representations (no ets tables), so it's
usually dictionaries mapping
(NodeName -> [Successor])
or the equivalent.
When speed is desired, using a tuple with node name =
argument position can be fast enough. (This is
essentially just representing the graph as a vector.
You can split the vector into several ones too, e.g.,
one vector for predecessors, one for successors, one
for content.)
(Note that element/2 on a tuple should be faster than
doing an ets hash lookup too.)
Writing graph programs:
- consider writing higher-order functions on graphs
- if using a functional representation, batch requests
and rebuild the graph afterwards. For sane debugging,
it might be a good idea regardless of representation
:-)
- you will usually need a set of "already-visited"
nodes when doing a traversal; pass this as a
parameter. Here is a depth-first traversal that
transforms a state as it goes along:
traverse(Node, State, Visited, Graph) ->
case visited(Node, Visited) of
true ->
{State, Visited};
false ->
Ns = successors(Node, Graph),
NewVisited = visit(Node, Visited),
NewState = transform_state(Node, Graph, State),
traverse_all(Ns, NewState, NewVisited, Graph)
end.
assuming appropriate implementations of the
operations.
- I have also found the following to be a practical
idiom: have functions to list the graph nodes in
useful orders, then use that list to fold some
operation over the graph.
- encapsulate the graph representation as an ADT, so
that you can at least somewhat easily change
representations. (I haven't found a useful "generic"
ADT for graphs, since some representations need more
managing than others, but you can at least reduce the
pain.)
Best,
Thomas
__________________________________
Yahoo! Mail
Stay connected, organized, and protected. Take the tour:
http://tour.mail.yahoo.com/mailtour.html
More information about the erlang-questions
mailing list