Standard graph API?

[Magnus Lie Hetland]

In article <eppstein-08D901.11581523082004 at news.service.uci.edu>,
David Eppstein wrote:
>In article <slrncik8tm.4g.mlh at furu.idi.ntnu.no>,
> mlh at furu.idi.ntnu.no (Magnus Lie Hetland) wrote:
>
>> Yes, we have the standard ways of implementing graphs through (e.g.) 
>> dicts mapping nodes to neighbor-sets, but if one wants a graph that's 
>> implemented in some other way, this may not be the most convenient 
>> (or abstract) interface to emulate.
>
>Actually, my interpretation of this standard way is as a fairly abstract 
>interface, rather than a specific instantiation such as dict-of-sets:
>Most of the time, I merely require that iter(G) produces a sequence of 
>the vertices of graph G, and iter(G[v]) produces a sequence of neighbors 
>of vertex v.  I also sometimes use "v in G" and "w in G[v]" to test 
>existence of vertices or edges.

Yes, I agree, to some extent. I guess the problems start when you want
to manipulate the graph. I think it would be nice to be able to use an
empty graph object to build a given graph without knowing the
implementation. I guess you could do that in this implementation too
(if all the neighbor sets were initialized).

But if this does turn out to be an acceptable API, I'm all for it. I
just think it would be nice to have a Recommended Standard(tm), to
create interoperability.

[snip]
>- It doesn't provide an abstract way of changing the graph (although 
>that's relatively easy if G is e.g. a dict of sets)

Right.

>- It doesn't directly represent multigraphs

Unless you insist on having neighbor-sets, it does, doesn't it?
Neighbor-lists can be used for this...?

[snip]

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