Traversing graphs

[Thomas Lindgren]

--- Vlad Dumitrescu <vlad_dumitrescu@REDACTED>
wrote:
> From: "Vladimir Sekissov" <svg@REDACTED>
> > 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