Standard graph API?

David Eppstein eppstein at ics.uci.edu
Mon Aug 23 23:04:26 CEST 2004


In article <slrnciklv0.e8q.mlh at furu.idi.ntnu.no>,
 mlh at furu.idi.ntnu.no (Magnus Lie Hetland) wrote:

> >    Do you have any design thoughts. It would be good to have weighted,
> >directed graphs and depth first traversal.
> 
> I've thought of several alternatives; basically, I just thought about
> defining the "standard" API for the basic abstract data type
> (including weights, direction, labels, colours etc.). Concrete
> implementations and algorithms would be a separate issue.

I would strongly prefer not to have weights or similar attributes as 
part of a graph API.  I would rather have the weights be a separate dict 
or function or whatever passed to the graph algorithm.  The main reason 
is that I might want the same algorithm to be applied to the same graph 
with a different set of weights.

A secondary reason is that we already have in Python a good general 
mechanism (dicts) for associating arbitrary information with objects, I 
don't see a need for reinventing a more specific mechanism for doing so 
when the objects are pieces of graphs and the information is some list 
of weight, label, etc that some graph API designer thinks is sufficient.

I think this may contradict some things I said a year or two ago about 
using a dict-of-dicts representation in which G[v][w] provides the 
weight; I've changed my mind.

-- 
David Eppstein
Computer Science Dept., Univ. of California, Irvine
http://www.ics.uci.edu/~eppstein/



More information about the Python-list mailing list