python bijection

[geremy condra]

geremy condra wrote:
...........

I don't want to sound pessimistic, but graph and digraph theory has a lot of
history, especially in computer science.

Of course it does- the rich set of problem-solving tools provided
by theoretical computer science and mathematical graph theory
are what make graphs so useful, which is why I'm advocating
that they be in the standard library.

There are already very many
implementations eg

http://code.google.com/p/igraph
http://www.boost.org/doc/libs/release/libs/graph
http://ernst-schroeder.uni.lu/Digraph/doc/
http://code.google.com/p/python-graph
http://compbio.washington.edu/~zach/py_graph/doc/html/public/py_graph-module.html

and many others......some of the above already seem to be very useful.

I suspect that part of the reason there are so many implementations
is because graphs are a) useful and b) not in the standard library.

Is there reason to suppose that any one representation of graphs or digraphs
is so good we need to add it to python?

I think there are several implementations that would meet the
standards for code quality, and both graphine and python-graph
are full-featured, easy to use, pure python graph libraries. Any
one of them would be a credit to the standard library.

Even for fairly common algorithms eg Dijkstra's shortest path there doesn't
seem to be complete agreement on how to implement them; for the details of
how nodes/edges/paths should be stored and efficiently manipulated there is
huge variety.

Of course there are. Different authors envision different use
cases, and select their data structures and algorithms
appropriately. That doesn't imply that none of them are
appropriate for the common case, which is what we would
be targeting here.

Geremy Condra

 

[Carl Banks]

Is there reason to suppose that any one representation of graphs or digraphs is
so good we need to add it to python?

One of them bothered to write a PEP proposing its inclusion?

Even for fairly common algorithms eg Dijkstra's shortest path there doesn't seem
to be complete agreement on how to implement them; for the details of how
nodes/edges/paths should be stored and efficiently manipulated there is huge
variety.

Wait seems like a good policy.

Geremy's team seems to balance open-mindedness with not being a
pushover quite well; given this, and that they took initiative, I am
satisfied that they will do a good job designing it for the general
case.

Also, "Now is better than never."

(And before anyone gives the obvious retort, please consider if you
really think it's happening "right now".)


Carl Banks

 

[Gabriel Genellina]

How would this not cause infinite recursion?

That goes under "unless I'm missing something"
You're right, it would cause infinite recursion. Not a good idea...

If both self._flip and self._flip._flip are weak references, no strong
references to the inverse mapping survive leaving the constructor
scope. Unless I'm missing something, only one of these can be a weak
reference, and then you'd have to do something like this in the
property to prevent "TypeError: FlipDict is not callable":

@property
def flip(self):
try:
# we're an inverse, self._flip is a weak reference
return self._flip()
except TypeError:
# we're a forward mapping, self._flip is a strong
reference
return self._flip

Yes - although I'd explicitely test for a weakref object:

def flip(self):
_flip = self._flip
if isinstance(_filp, weakref.ref):
return _flip()
return _flip

and probably all those internal references to self._flip should become
self.flip too; I've not tested the code but I think it *should* work...

 

[geremy condra]

Generally, we've tried to discourage people from instantiating

nodes and edges directly, in favor of having them controlled
through the graph. Maybe something along the lines of:

g = Graph(nodes=['a', 'b', 'c'], edges=[('a', 'b'), ('a', 'c'), ('b', 'c')])

?

That would work as well, but you then miss out on the extra
parameters you can pass to Edge() and Node().

Just pushed a change that will allow that.

In another email you wrote that Edge() and Node() constructors
should not be used directly, since they have to know the Graph
to which they belong.

Wouldn't it be possible to implement this kind of parent-
referencing in a lazy way, ie. by postponing all the init-
processing until the Graph instance is known ?

While possible, I'm wary of this. We tried it in an initial
prototype (all nodes and edges descended naturally from
a Universe graph until otherwise stated) and that way lie
madness. Perhaps at some point someone would like to
give another shot at it, though.

I'd avoid such an ambiguity. It could easily hide programming
errors (testing for edges instead of nodes).

OTOH, you could also regard the graph as a set of nodes
and edges (as you apparently already do). In that case,
you'd define

for x in g: print x

as iteration of both nodes and edges in some arbitrary
order and then use the more specific:

for n in g.nodes: print x
for e in g.edges: print x

for iteration over just the nodes or edges.

Yup, that's exactly what we do.

The idea is that you use the Graph representation of the
data to implement some algorithm e.g. optimizing weights
for example.

The algorithm could be implemented in C to be fast enough
for large data sets.

The above two methods would then be used to quickly push the
original data into the graph and extract it again after
the algorithm has run.

I can see this, but I think the cleaner way is just to iterate
over nodes and edges. Having said that, if somebody wants
to come up with some timing data and it seems to provide a
big advantage, I think robbie for one would make the change.

Hmm. Sounds like a plausible use case to me, although I'm
not sure its one that should be encouraged. The bigger
question in my mind is whether all attribute lookups should
have to pay the extra lookup cost to support a somewhat
narrow need. I'll definitely have to talk with the other devs
about this one, and run a little bit of timing besides.

This would only be an optional second way of accessing
the .data dictionary.

node.data['pass'] = 1
node.data['from'] = 'Las Vegas'
node.data['to'] = 'New York'

would work without such modifications.

Yes, but the change is not reflected on the node. For
example:

g = Graph(nodes={'a':{'spotted':True}})
g['a'].data['spotted'] = False
g['a'].data['spotted']

True

I can see how this would represent a gotcha, though.
Is there a general opinion on whether this is a plus or
a minus?

Geremy Condra

 

[Bearophile]

Robin Becker:

There are already very many implementations eg

http://code.google.com/p/igraphhttp...n.edu/~zach/py_graph/doc/html/public/py_graph...

and many others......some of the above already seem to be very useful.

There's mine too:
http://sourceforge.net/projects/pynetwork/
API:
http://code.activestate.com/recipes/466329/

Bye,
bearophile

 

[geremy condra]

Robin Becker:


There's mine too:
http://sourceforge.net/projects/pynetwork/
API:
http://code.activestate.com/recipes/466329/

Bye,
bearophile

Huh, I don't think I've ever seen that before, and I'm pretty
sure I'd remember if I had. With your permission, I'd like to
go ahead and start integrating some of the features from
that into graphine, especially a topo traversal. Do you
mind?

Geremy Condra

 

[geremy condra]

Huh, I don't think I've ever seen that before, and I'm pretty
sure I'd remember if I had. With your permission, I'd like to
go ahead and start integrating some of the features from
that into graphine, especially a topo traversal. Do you
mind?

Geremy Condra

Since that's released under the python license, I'm going to
go ahead and commit the version that includes the topo
traversal, but if you have any objections you only need to
say the word and I'll take it down.

Geremy Condra

 

[Bearophile]

geremy condra:

Since that's released under the python license, I'm going to
go ahead and commit the version that includes the topo
traversal, but if you have any objections you only need to
say the word and I'll take it down.

No objections

Bye,
bearophile

 

[Tiago de Paula Peixoto]

I don't want to sound pessimistic, but graph and digraph theory has a
lot of history, especially in computer science. There are already very
many implementations eg

http://code.google.com/p/igraph
http://www.boost.org/doc/libs/release/libs/graph
http://ernst-schroeder.uni.lu/Digraph/doc/
http://code.google.com/p/python-graph
http://compbio.washington.edu/~zach/py_graph/doc/html/public/py_graph-module.html

I would like to point out the following two projects as additions to
this list:

http://graph-tool.forked.de (my own project)
http://networkx.lanl.gov

The graph-tool module uses the Boost Graph Library internally to achieve
good numerical performance, while networkx has a more python-only
approach.

Cheers,
Tiago


-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.13 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAksg7hsACgkQBNxGHvNv411zegCeIZeXBmXsQBX2E4tpUlBAI6Wu
lGUAn1VPmUX0VXpIr5Sd8zno9vQm4RN/
=NEPJ
-----END PGP SIGNATURE-----

 

[geremy condra]

geremy condra:


No objections

I appreciate it. I don't seem to be having any luck emailing you
offlist, so please feel free to email me privately if you'd rather
this not be indexed, but is there a particular way you want your
attribution line to read?

Geremy Condra

 

[geremy condra]

I would like to point out the following two projects as additions to
this list:

http://graph-tool.forked.de (my own project)
http://networkx.lanl.gov

The graph-tool module uses the Boost Graph Library internally to achieve
good numerical performance, while networkx has a more python-only
approach.

Cheers,
Tiago

Well, we all seem to have reinvented the wheel differently
Bearophile, Tiago- any interest in trying to combine the
best parts of our libraries, with an eye towards eventual
integration into the standard library?

Geremy Condra

 

[Bearophile]

Geremy Condra:

is there a particular way you want your attribution line to read?

You can just use my nickname (in all lowercase), with the list of
parts you have used. Don't worry.

Well, we all seem to have reinvented the wheel differently

Maybe also because they are designed for different purposes.

Bearophile, Tiago- any interest in trying to combine the
best parts of our libraries, with an eye towards eventual
integration into the standard library?

The first thing to do is to ask Guido and Hettinger if they are
willing to put a "good" graph module into the std lib. If their answer
is positive for some definition of "good", then we can think about
doing something.

Several years ago I have suggested to put a graph module in the std
lib, and the answer was something like: "Put the lib online, and if
people use it a lot, we'll see to put it into the std lib." In the
meantime my lib was used by no one and ten other graph libs are used
(networkx seems among the most used), but I think no one of them has
shown a strong usage. (In the meantime Hettinger has written and added
two or three or four GOOD data structures to the std lib using a "fast
lane", avoiding the step of popular usage test).

Bye,
bearophile

 

[Tiago de Paula Peixoto]

Geremy Condra:

Maybe also because they are designed for different purposes.

This is true. For instance, the data structures and most algorithms in
graph-tool are implemented in C++ to achieve good performance, which is
necessary if you are working with very large graphs. I think this
differs from most python graph libraries, which don't have this as a
high priority.

The first thing to do is to ask Guido and Hettinger if they are
willing to put a "good" graph module into the std lib. If their answer
is positive for some definition of "good", then we can think about
doing something.

A crucial element in this hypothetical module would be the main graph
data structure. The simplest approach would be to implement it in pure
python, with lists, dicts and such, as many libraries do. However, this
would rule out its use by high-performance code, which would need a
simpler C-based data structure for direct interaction. On the other
hand, I'm not sure if there is a need for a high performance graph
module in python's standard library...

Cheers,
Tiago


-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.13 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAksjiqwACgkQBNxGHvNv410M8wCgpXnsdbzCv/+Y+qsD1qtMGt6P
sm8An1QVXn7FxkcMDdTj5ErWYb580wAQ
=irLw
-----END PGP SIGNATURE-----

 

[geremy condra]

Geremy Condra:


You can just use my nickname (in all lowercase), with the list of
parts you have used. Don't worry.



Maybe also because they are designed for different purposes.



The first thing to do is to ask Guido and Hettinger if they are
willing to put a "good" graph module into the std lib. If their answer
is positive for some definition of "good", then we can think about
doing something.

Several years ago I have suggested to put a graph module in the std
lib, and the answer was something like: "Put the lib online, and if
people use it a lot, we'll see to put it into the std lib." In the
meantime my lib was used by no one and ten other graph libs are used
(networkx seems among the most used), but I think no one of them has
shown a strong usage. (In the meantime Hettinger has written and added
two or three or four GOOD data structures to the std lib using a "fast
lane", avoiding the step of popular usage test).

Well, I've just concluded a short conversation with Raymond Hettinger,
and I think its fair to characterize him as being opposed to the idea
at present. In addition to the popularity test, he's also noted that
ideally a core CPython dev should be involved in the project. Putting
the two together is, AFAICS, a death knell for any extant graph lib.

Having said that, I'd still like to see how much common ground we
could find among the existing libraries. IMHO, there's a lot more
in common than there is different.

Geremy Condra

 

[Terry Reedy]

Well, I've just concluded a short conversation with Raymond Hettinger,
and I think its fair to characterize him as being opposed to the idea
at present. In addition to the popularity test, he's also noted that
ideally a core CPython dev should be involved in the project. Putting
the two together is, AFAICS, a death knell for any extant graph lib.

Having said that, I'd still like to see how much common ground we
could find among the existing libraries. IMHO, there's a lot more
in common than there is different.

The large number of current projects practically guarantees that none
will be popular enough, and perhaps than none get the usage needed to
shake out a broadly useful api. So any consolidation wuold be good.

 

[geremy condra]

The large number of current projects practically guarantees that none will
be popular enough, and perhaps than none get the usage needed to shake out a
broadly useful api. So any consolidation wuold be good.

While I agree, I think it's going to be extremely difficult to get any
kind of buy in without a great deal of support from within python.
Any devs willing to throw the time required into this?

Geremy Condra

 

[Tiago de Paula Peixoto]

A crucial element in this hypothetical module would be the main graph
data structure. The simplest approach would be to implement it in pure
python, with lists, dicts and such, as many libraries do. However, this
would rule out its use by high-performance code, which would need a
simpler C-based data structure for direct interaction. On the other
hand, I'm not sure if there is a need for a high performance graph
module in python's standard library...

I disagree...I am not sure of the current need in terms of a precise
survey.....But IMO, as bearophile pointed out.....networkx is the most
popular........and from their claims it is targeted at mathematicians,
physicists, biologists, computer scientists, social scientists.

Given the current trend in the growth of social and professional
networks..... and social scientists (Disclaimer: i aspire to be one).. i
do expect a growing demand for graph data structures and high
performance ones soon enough..

so IMHO if we are going in for it we should go for the high performance
graphs too..

I certainly think it is important to have a high-performance graph
library, that is why I started to write one. I was talking simply about
its inclusion in the standard library. Since something as basic for
scientific computing as, for instance, numpy does not belong in the
standard library, I don't think it makes sense to push for the inclusion
of a scientific graph library. Could we (or rather should we) even make
it _independent_ of numpy?

But if the idea is to consolidate the existing graph libraries into an
uniform package, I'm certainly not against it in principle. But I think
we should first familiarize ourselves with the existing variants, to see
if there is really a common ground. The basic interface to the graph
data structure should not vary much, I believe, but the implementation
may. For instance, I chose in graph-tool to implement most of it in C++
with the Boost Graph Library...

When I get some time, I'll take a careful look at the implementations
listed in this thread, some of which I don't yet know.

Cheers,
Tiago



-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.13 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAksk15wACgkQBNxGHvNv411LHACfXPuT3Pqg8VvYVvIDkmCmhusf
MT4Anio9uFKne4EOfLzxzDSrG//p2TAm
=Nm3y
-----END PGP SIGNATURE-----