[Python-ideas] Graph class

[Paul Moore]

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
> 3) 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.
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?

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. In C, there are many examples of this type of "borderline"
stuff - linked lists, maps, sorting and searching algorithms, etc. In
Python, lists, dictionaries, sorting, etc are all "self evidently"
basic building blocks, but graphs hit that borderline area.

Paul