Response to Guido's essay on graph representation

[David Eppstein]

I've posted an implementation of Dijkstra's algorithm, which is in some 
sense a response to Guido's essay 
<http://www.python.org/doc/essays/graphs.html> on the proper Pythonic 
representation of graphs, to
<http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/119466>.

In essence, I agree with Guido's point that a full-blown object oriented 
representation is too cumbersome, and that it is better to use Python's 
built-in data structures to form the overall graph structure, and to let 
the graph vertices be anything that can index a dictionary.
However his suggestion of a dictionary mapping vertices to lists of 
neighbors is a little too inflexible: instead I propose a dictionary 
mapping vertices to dictionaries of neighbors.  As a bonus, the 
neighbor-dictionary entries can be used to store additional graph 
information, which I use for the edge lengths needed for Dijkstra.

Comments welcome, here or (preferably) via the comment form on the 
recipe page.

-- 
David Eppstein       UC Irvine Dept. of Information & Computer Science
eppstein at ics.uci.edu http://www.ics.uci.edu/~eppstein/