Standard graph API?

[Magnus Lie Hetland]

In article <eppstein-4A56C8.14042623082004 at news.service.uci.edu>,
David Eppstein wrote:
[snip]
>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.

I can see that.

[snip stuff about using dicts]

This can be said about all objects, really; no reason to have
attributes as long as we can associate values with the objects using
dicts. This is where things start to look implementation-specific,
even though it is *possible* to keep it abstract using this interface.

One of my motivations is allowing arbitrary structures behind the
scenes, e.g. the graph may be a front-end for something that is
computed on-the-fly using specialized hardware (in fact a very real
possibilit in my case). I could have something like this be
represented by several distinct objects (e.g. one for the topological
structure, one for the weights), of course, but I'd certainly have to
implement the weight mapping myself, and not use built-in dicts.

I do think your API is nice in that it is simple, but I also have the
feeling that using it with other implementations would be sort of
unnatural; one would be trying to emulate the "dict-of-lists with
dicts for properties" implementation, because that implementation
*would* have been simple -- had one used it.

Also, again, this doesn't lend itself very well to manipulating
graphs. If I set one weight to infinity, I might expect (perhaps) the
corresponding edge to disappear (otherwise the graph would have to be
complete in the first place) or similar things; there may also be
other dependencies between properties. Not easily handled with a
separate object for each property. And using functions for everything
that needs calculating doesn't easily lead to polymorphism...

It's not horribly inconvenient, of course (just a matter of defining a
few objects referring to the same underlying mechanism, each with
a different __getitem__ method). I'm just airing my thoughts about why
it *might* be useful to have something else -- possibly in addition.

Perhaps one could have something like two levels? The Level 1 Graph
API would support the "graph as mapping from nodes to neighbors" with
"properties as separate mappings" and the Level 2 Graph API could add
some convenience methods/properties for encapsulation and
manipulation?

[snip]
> 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;

Yeah, I remember you saying that :)

> I've changed my mind.

Fair enough. FWIW, I agree with your new position when it comes to the
simple dict-based implementation; this is basically how it's done in
pseudocode, usually (e.g. having pi[v] represent the predecessor of v
and so forth).

-- 
Magnus Lie Hetland     "Canned Bread: The greatest thing since sliced
http://hetland.org      bread!" [from a can in Spongebob Squarepants]