I have a decent semi-recursive Graph class that I think could be a good addition to the Collections module. It probably needs some refactoring, but I'm posting here to see if there's any interest. For those who aren't too abreast of CS theory, a graph is one of the most abstract data structures in computer science, encompassing trees, and lists. I'm a bit surprised that no one's offered one up yet, so I'll present mine. The code is at http://github.com/theProphet/Social-Garden under the pangaia directly called graph.py. It has a default dictionary (defdict.py) dependency that I made before Python came up with it on it's own (another place for refactoring). Cheers, MarkJ
On 7 December 2012 21:45, Mark Adam <dreamingforward@gmail.com> wrote:
For reference, there was a previous idea to make some kind of standard Graph API: http://wiki.python.org/moin/PythonGraphApi When I had to implement a really simple DAG myself, I based it on this Graph ABC library: http://www.linux.it/~della/GraphABC/ Best wishes, Thomas
On Fri, Dec 7, 2012 at 4:22 PM, Thomas Kluyver <thomas@kluyver.me.uk> wrote:
All very interesting. I'm going to suggest a sort of "meta-discussion" about why -- despite the power of graphs as a data structure -- such a feature has not stabilized into a workable solution for inclusion in a high-level language like Python. I identity the following points of "wavery": 1) the naming of methods (add_edge, vs add(1,2)): *aesthetic grounds,* 2) what methods to include (degree + neighbors or the standard dict's __len__ + __getitem__): *API grounds* 3) how much flexibility to be offered (directed, multi-graphs, edge weights with arbitrary labeling, etc.): *functionality grounds* 3) what underlying data structure to use (sparse adjacency dicts, matrices, etc): *representation conflicts*. And upon further thought, it looks like only a killer application could ever settle the issue(s) to make it part of the standard library. mark
On 9 December 2012 01:29, Mark Adam <dreamingforward@gmail.com> wrote:
4) Whether the library requires some sort of "Vertex" type, or works with arbitrary values, similarly whether there is a defined "Edge" class or edges can be labelled, weighted, etc with arbitrary Python values. 5) Granularity - if all I want is a depth-first search algorithm, why pull in a dependency on 100 graph algorithms I'm not interested in? My feeling is that graphs are right on the borderline of a data structure that is simple enough that people invent their own rather than bother conforming to a "standard" model but complex enough that it's worth using library functions rather than getting the details wrong. In C, there are many examples of this type of "borderline" stuff - linked lists, maps, sorting and searching algorithms, etc. In Python, lists, dictionaries, sorting, etc are all "self evidently" basic building blocks, but graphs hit that borderline area. Paul
On 07.12.12 23:45, Mark Adam wrote:
Graph is too abstract conception. There are a lot of implementations of graphs. Every non-trivial program contains some (may be implicit) graphs. See also for some implementations: Magnus Lie Hetland, "Python Algorithms. Mastering Basic Algorithms in the Python Language".
On Fri, 7 Dec 2012 15:45:25 -0600 Mark Adam <dreamingforward@gmail.com> wrote:
Do you know networkx? http://networkx.lanl.gov/ Regards Antoine.
On 7 December 2012 21:45, Mark Adam <dreamingforward@gmail.com> wrote:
For reference, there was a previous idea to make some kind of standard Graph API: http://wiki.python.org/moin/PythonGraphApi When I had to implement a really simple DAG myself, I based it on this Graph ABC library: http://www.linux.it/~della/GraphABC/ Best wishes, Thomas
On Fri, Dec 7, 2012 at 4:22 PM, Thomas Kluyver <thomas@kluyver.me.uk> wrote:
All very interesting. I'm going to suggest a sort of "meta-discussion" about why -- despite the power of graphs as a data structure -- such a feature has not stabilized into a workable solution for inclusion in a high-level language like Python. I identity the following points of "wavery": 1) the naming of methods (add_edge, vs add(1,2)): *aesthetic grounds,* 2) what methods to include (degree + neighbors or the standard dict's __len__ + __getitem__): *API grounds* 3) how much flexibility to be offered (directed, multi-graphs, edge weights with arbitrary labeling, etc.): *functionality grounds* 3) what underlying data structure to use (sparse adjacency dicts, matrices, etc): *representation conflicts*. And upon further thought, it looks like only a killer application could ever settle the issue(s) to make it part of the standard library. mark
On 9 December 2012 01:29, Mark Adam <dreamingforward@gmail.com> wrote:
4) Whether the library requires some sort of "Vertex" type, or works with arbitrary values, similarly whether there is a defined "Edge" class or edges can be labelled, weighted, etc with arbitrary Python values. 5) Granularity - if all I want is a depth-first search algorithm, why pull in a dependency on 100 graph algorithms I'm not interested in? My feeling is that graphs are right on the borderline of a data structure that is simple enough that people invent their own rather than bother conforming to a "standard" model but complex enough that it's worth using library functions rather than getting the details wrong. In C, there are many examples of this type of "borderline" stuff - linked lists, maps, sorting and searching algorithms, etc. In Python, lists, dictionaries, sorting, etc are all "self evidently" basic building blocks, but graphs hit that borderline area. Paul
On 07.12.12 23:45, Mark Adam wrote:
Graph is too abstract conception. There are a lot of implementations of graphs. Every non-trivial program contains some (may be implicit) graphs. See also for some implementations: Magnus Lie Hetland, "Python Algorithms. Mastering Basic Algorithms in the Python Language".
On Fri, 7 Dec 2012 15:45:25 -0600 Mark Adam <dreamingforward@gmail.com> wrote:
Do you know networkx? http://networkx.lanl.gov/ Regards Antoine.
participants (6)
-
Antoine Pitrou -
Mark Adam -
Paul Moore -
Serhiy Storchaka -
Terry Reedy -
Thomas Kluyver