Re: Standard graph API?

From: David Eppstein (eppstein_at_ics.uci.edu)
Date: 08/23/04 

Date: Mon, 23 Aug 2004 14:04:26 -0700

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

> > Do you have any design thoughts. It would be good to have weighted,
> >directed graphs and depth first traversal.
>
> I've thought of several alternatives; basically, I just thought about
> defining the "standard" API for the basic abstract data type
> (including weights, direction, labels, colours etc.). Concrete
> implementations and algorithms would be a separate issue.

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.

A secondary reason is that we already have in Python a good general
mechanism (dicts) for associating arbitrary information with objects, I
don't see a need for reinventing a more specific mechanism for doing so
when the objects are pieces of graphs and the information is some list
of weight, label, etc that some graph API designer thinks is sufficient.

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; I've changed my mind. 

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

Relevant Pages

  • Re: Problem on an nxn grid
    ... "See Spot Run" in the vocabulary of Graph Theory. ... Gibbons's "Algorithmic Graph Theory" gives a pseudo-code ... parts of the Edmonds algorithm (such as the Hungarian ... All weights are assumed to be ...
    (sci.math)
  • Re: Standard graph API?
    ... I would rather have the weights be a separate dict ... >or function or whatever passed to the graph algorithm. ... [snip stuff about using dicts] ... "properties as separate mappings" and the Level 2 Graph API could add ...
    (comp.lang.python)
  • Re: Graph optimization
    ... represented in the form of a graph. ... I have to add up all the weights to form the ... algorithm is going to be the best for finding the shortest path ...
    (comp.programming)
  • Re: Shortest Path finding with mutating weights
    ... > Dijkstra's algo can be used to find shortest path between 2 nodes in ... > a weighted graph. ... > How to find shortest paths in a graph with mutating weights? ... Connections from one time slice to the another ...
    (comp.theory)
  • Graph problem, is it NP-Complete?
    ... An undirected weighted graph, ... acyclic and all its vertices have 2 neighbours, ... YES if there exists a set of size <= K of connected subgraphs of the ... The sum of all the weights of each edge of each subgraph that "map" to ...
    (comp.theory)