[Python-ideas] Fwd: Graph class

[Mark Adam]

Meant this to go to the whole list.  Sorry.

On Sun, Dec 9, 2012 at 5:40 AM, Paul Moore <p.f.moore at gmail.com> wrote:
> On 9 December 2012 01:29, Mark Adam <dreamingforward at gmail.com> wrote:
>> All very interesting.  I'm going to suggest a sort of "meta-discussion"
>> about why -- despite the power of graphs as a data structure -- such a
>> feature has not stabilized into a workable solution for inclusion in a
>> high-level language like Python.
>>
>> I identity the following points of "wavery":
>>
>> 1) the naming of methods (add_edge, vs add(1,2)):  aesthetic grounds,
>> 2) what methods to include (degree + neighbors or the standard dict's
>> __len__ + __getitem__):  API grounds
>> 3) how much flexibility to be offered (directed, multi-graphs, edge weights
>> with arbitrary labeling, etc.):  functionality grounds
>> 4) what underlying data structure to use (sparse adjacency dicts, matrices,
>> etc):  representation conflicts.
>
> 4) Whether the library requires some sort of "Vertex" type, or works
> with arbitrary values, similarly whether there is a defined "Edge"
> class or edges can be labelled, weighted, etc with arbitrary Python
> values.

This I put under #3 (functionality grounds) "edge weights with
arbitrary labeling", Vertex's with abitrary values i think would be
included.

> 5) Granularity - if all I want is a depth-first search algorithm, why
> pull in a dependency on 100 graph algorithms I'm not interested in?

Hmm, I would call this "5) comprehensiveness: whether to include every
graph algorithm known to mankind."

> My feeling is that graphs are right on the borderline of a data
> structure that is simple enough that people invent their own rather
> than bother conforming to a "standard" model but complex enough that
> it's worth using library functions rather than getting the details
> wrong.

But this is also why (on both counts) it would be good to include it
in the standard library.  The *simplicity* of a graph makes everyone
re-implement it, or (worse) work with some cruder work-around (like a
dict of dicts but not at all clear you're dealing with an actual
graph).  But imagine if, for example, Subversion used a python graph
class to track all branches and nodes in it's distributed revision
control system.  Then how easy it would be for third parties to make
tools to view repos or other developers to come in and work with the
dev team:  they're already familiar with the standard graph class
structure.

And for the *complex enough* case, obviously it helps to have a
standard library help you out and just provide the sophistication of a
graph class for you.   There are a lot of obvious uses for a graph,
but if you don't know of it, a beginning programmer won't *think* of
it and make some crude work-around.

Mark