[Python-ideas] Graph class

[Terry Reedy]

On 12/18/2012 9:24 AM, Yuval Greenfield wrote:
>
> On Tue, Dec 18, 2012 at 2:08 PM, Oscar Benjamin
> <oscar.j.benjamin at gmail.com
> <mailto:oscar.j.benjamin at gmail.com>> wrote:

>     I'd be interested to use (and possibly to contribute to) a graph
>     library of this type on PyPI. I have some suggestions about the
>     appropriate level of abstraction below.
>
>     The graph algorithms that are the most useful can be written in terms
>     of two things:
>     1) An iterator over the nodes

Or iterable if re-iteration is needed.

>     2) A way to map each node into an iterator over its children (or
>     partners)

A callable could be either an iterator class or a generator function.

> Some graphs don't care for the nodes, all their information is in the
> edges. That's why most graph frameworks have iter_edges and iter_nodes
> functions. I'm not sure what's the clean way to represent the
> optional directionality of edges though.
>
> Some example API's from networkx:
>
> http://networkx.lanl.gov/reference/classes.html
> http://networkx.lanl.gov/reference/classes.digraph.html

Thank you both the the 'thought food'. Defining things in terms of 
iterables and iterators instead of (for instance) sets is certainly the 
Python3 way.

Oscar, I don't consider hashability an issue. General class instances 
are hashable by default. One can even consider such instances as 
hashable facades for unhashable dicts. Giving each instance a list 
attribute does the same for lists.

The more important question, it seems to me, is whether to represent 
nodes by counts and let the algorithm do its bookkeeping in private 
structures, or to represent them by externally defined instances that 
the algorithm mutates.

-- 
Terry Jan Reedy