Standard graph API?

[Magnus Lie Hetland]

In article <Sj50d.11652$w%6.5785 at newsread1.news.pas.earthlink.net>,
Andrew Dalke wrote:
>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">

Right. My idea was that we could define a standard API for this
functionality, as in (e.g.) the DB API. Your code generating idea is
an alternative.

>Different graphs have different ways to do this.

Yes.

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

Indeed.

>I can concieve then some way to generate code
>based on a template, like this
[code generating template example snipped]

Hm. What you're basically is proposing is (as you said, basically ;) a
C++-like approach (as used in Boost)?

Or -- this goes beyond the standard C++ approach, of course, as that
would basically be a way of getting "standard Python functionality" in
a static language.

Your idea is interesting -- but quite a way from what I had
envisioned... Would there be a way to combine the ideas? I.e. define
an (abstract) interface to standard graph functionality and in
addition have this sort of template stuff? It might be a bit far
fetched, though, as it seems your template idea obviates the need for
a standard interface.

I need the interface for when I write my own algorithms -- I don't
have as much need for templated stock algorithms; so it seems our
needs may be somewhat complementary, perhaps?

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

Hehe.

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

Well -- I was rather aiming for a definition of a graph protocol
(similar to e.g. the sequence protocol or the mapping protocol), and
that would entail fixing the methods and attributes involved.

[snip]
>The problem is all the conversion from/to my graph
>form to the standard graph form.  Either the adapters
>have to be live

Sure -- that wouldn't be a problem, would it?

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

Maybe. I guess it depends on how you implement things. For example, if
it's only a matter of renaming methods, that wouldn't entail any
performance loss at all (you could just have another attribute bound
to the same method).

[snip]
>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]")

But coding this doesn't seem like much fun.

My hope was that I could write new graph algorithms so they looked
somewhat pretty and readable. Having to write them in some new
template langage doesn't seem very tempting.

(As I said, stock algorithms aren't of that much interest to me.)

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

I don't see how this has anything to do with the issue at hand,
really.

The person who implemented the DFS could deal with this issue (by
parametrizing it) or something. (*Or* using adaptation, for that
matter.) I'm sure there are many other ways of dealing with this...
IMO this is orthogonal. Whether or not you can tell the DFS how you
access the neighbors of a node isn't directly related to what you want
the DFS to do...

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

Well -- you could always make a C library for your graph structures,
with an optional interface (without any performance loss) that
conformed to the Hypothetical Graph API(tm), somewhat reminiscent of
how the DB API works...

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

I agree with you -- one ought to get more experience with it. I have
not used it seriously myself. I think it might have quite a bit of
potential in this sort of situation, though.

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

The problem is that it is impossible to override.

If I were to use some special hardware as the source of my graph
(which is a realistic example for me) I might have to create node
wrappers on the fly. Unless I use the Singleton pattern (the Borg
pattern wouldn't work) I could easily end up with equal but
non-identical nodes, and no way of overriding this.

>At the very least, it's a lot faster (no method call overhead).

Right.

[snip wiki stuff]
>It said "warning, in use, you might want to wait about 10
>minutes before editing."

Right -- I was making some changes ;)

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

Yup. Just go ahead and add stuff.

-- 
Magnus Lie Hetland       The time you enjoy wasting is not wasted time
http://hetland.org                                  -- Bertrand Russel