Standard graph API?

[Andrew Dalke]

Magnus Lie Hetland wrote:
> Hm. How would the algorithms work without a standard API?

There are certain things the different graphs have in
common.  For example,
  1. "test if two nodes/edges are the same"
  2. "test if two nodes/edges are identically colored"
  3. "list of all nodes adjacent to a node"
  4. "list of all edges from a node"  (either directed or
      undirected)
  5. "get the appropriate weight"

Different graphs have different ways to do this.
My molecular graphs do this with

   1. atom1 is atom2
   2. atom_compare(atom1, atom2)
   3. atom.xatoms
   4. atom.bonds
   5. atom.weight  # though that's the atomic weight and
                   # nothing to do with flow :)

An adjacency graph might do this with

   1. node1 is node2
   2. node1 == node2
   3. edge_table[node]
   4.  -- not defined --
   5. weights[node]

The ways to get the properties differ but the things
you do with them do not change.

I can concieve then some way to generate code
based on a template, like this

  dfs =  make_code(dfs_template,
                   args = "node, handler",
                   bond_neighbors = "node.xatoms",
                   on_enter = "handler.enter(node)")

   .. make the graph ...
  class Handler:
     def enter(self, node):
       print "Hi", node

  dfs(graph, Handler())

or for an adjacency graph, something like

  dfs =  make_code(dfs_template,
                   args = "bond_table, node, handler",
                   get_neighbors = "bond_table[node]",
                   on_enter = "handler.enter(node)")
   ...
  dfs(bond_table, start_node, handler)

Obviously it would need some sort of templating language.
Wonder if anyone's ever make one of those before.  ;)

> To clarify, by API I here mean a protocol, i.e. a definition of how a
> graph is supposed to behave -- *not* a standard implementation.

I think we're talking about the same thing -- the sorts
of things you can do with nodes and edges, and not a
statement that a node or edge has a given property or method.

> I've been thinking a bit about the use of object adaptation here; I
> think it would be quite perfect. One possibility would be to use the
> functionality of PyProtocols, but that's hardly standard... But it
> would allow you to do stuff like
> 
>   graph = AdjacencyMap(someStrangeMolecularGraph)
>   # or graph = adapt(someStrange..., AdjacencyMap)
>   graphAlgorithm(graph)

The problem is all the conversion from/to my graph
form to the standard graph form.  Either the adapters
have to be live (so the modification to the standard
form get propogated back to my graph) or there needs
to be conversions between the two.  Both sound slow.
>>David Eppstein wrote:
>>
>>>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.

Me:
>>An alternative, which is both intriguing and sends alarm bells
>>ringing

Magnus
> Sounds like a fun combination ;)

There the idea for me would be

find_flow = make_code(flow_template,
                       args = "source_nodes, sink_nodes, weight_table",
                       edges = "node.out_edges",
                       weight = "weight_table[edge]")

or to use a weight function

find_flow = make_code(flow_template,
                       args = "source_nodes, sink_nodes, weight_func",
                       edges = "node.out_edges",
                       weight = "weight_func(edge)")



> Wouldn't it be *much* better to use the established (but not standard)
> mechanism of object adaptation, as championed in PEP 246 and as
> implemented and extended upon in PyProtocols?

Not really.  Consider the events that could occur in a
DFS.  There's
   - on enter
   - on exit
   - on backtrack
and probably a few more that could be used in a general
purpose DFS.  But I might need only one of them.  With
a PE 246 adapter I can adapt my graph to fit the algorithm,
but if I don't need all of those events there's no way
to adapt the algorithm to fit my needs.

(Yes, even though I'm using Python I'm still worried
about efficiency.)


> (If only adapt() could become a standard library function... <sigh> ;)

Perhaps someday, when people get more experience with it.
I've not yet used it.

>>There would need to be some standards on how the graph is used, like
>>"two nodes are the same iff 'node1 is node2'"
> 
> 
> Yeah. Or one might want to allow equality to determine this, so that
> the implementer could decide how to do it (nodes might be dynamically
> created front-end objects after all).

I found that 'is' testing for my graphs is much better.
At the very least, it's a lot faster (no method call overhead).

> It seems there are at least a few people who are interested in the
> general concept, though. In case there is any merit in the idea, I've
> set up a temporary wiki at
> 
>   http://www.idi.ntnu.no/~mlh/python-graph-wiki.cgi
> 
> I'll post a separate announcement about it.

It said "warning, in use, you might want to wait about 10
minutes before editing."

I think it's been about 10 minutes now.  :)

				Andrew
				dalke at dalkescientific.com