Standard graph API?

[David Eppstein]

In article <slrncikldl.e8q.mlh at furu.idi.ntnu.no>,
 mlh at furu.idi.ntnu.no (Magnus Lie Hetland) wrote:

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

If you're doing anything serious with a multigraph you need to have some 
way of distinguishing different edges between the same pair of vertices.  
For instance, an edge object for each edge, that you can use as an index 
to store information about that edge.  A neighbor list that has multiple 
copies of the same neighbor won't let you do that, you can iterate 
through the edges but not distinguish one from another.

Another possibility, which fits into the same general abstract API but 
is more specialized, would be to represent a multigraph by a dict of 
dicts, where the outer dict maps each vertex to its neighbors and the 
inner dict maps each neighbor to the number of edges; then you could 
represent each edge by a tuple (v,w,index) with index in range(G[v][w]).

-- 
David Eppstein
Computer Science Dept., Univ. of California, Irvine
http://www.ics.uci.edu/~eppstein/