tag:blogger.com,1999:blog-8825992.post7742526250104310276..comments2019-02-13T20:54:50.768-08:00Comments on Electric Duncan: The State of Graphs in PythonUnknownnoreply@blogger.comBlogger17125tag:blogger.com,1999:blog-8825992.post-41477486608185250932013-06-11T02:52:22.061-07:002013-06-11T02:52:22.061-07:00When I started reading this article, I immediately...When I started reading this article, I immediately identify with your intent. In my case, I am constantly on the hunt for good numerical methods. However most responses to questions trigger a gush of library names... and this is less than useless. These names all usually found on the 1st Google search anyway and of course I would try them out.<br /><br />The reason that Guido's article was so powerful is because he provides a very simple graph definition and demonstrated some basic searches with raw Python. Nothing more.<br /><br />It's not a mistake but I think you left out a useful step in your program development.<br /><br />For example, I have been playing with A* search. All implementations I found on line were too complicated and hide the logic of the algorithm. As far as I am concerned, the raw Python is even better than the pseudocode in illustrating the logic.<br /><br />Take a leaf out of Guido's book and start by extending his functions.<br /> <br /><a rel="nofollow">[see here for my feeble attempt...]</a><br /><br />Brucehttps://www.blogger.com/profile/06161967424561002356noreply@blogger.comtag:blogger.com,1999:blog-8825992.post-76952885341918382272009-10-26T15:53:22.320-07:002009-10-26T15:53:22.320-07:00I'm one of the python-graph maintainers. Thank...I'm one of the python-graph maintainers. Thanks for the link. I'd love to know if anybody is using our stuff. <br /><br />We've recently changed focus to Python 3.x - it puts us in a better place. Our focus is to create a truly modular collection of graph tools. The core libraries have no dependancies, however we support optional add-ins which provide support for popular products such as Dot or Numpy.dobsonhttps://www.blogger.com/profile/00634981753587872285noreply@blogger.comtag:blogger.com,1999:blog-8825992.post-62890154198007101882009-04-18T19:46:00.000-07:002009-04-18T19:46:00.000-07:00gcc,
Graphine looks fantastic! Seriously. This is...gcc,<br /><br />Graphine looks fantastic! Seriously. This is just the sort of thing I was looking for: nice and simple, something that anyone with special graph-theoretic needs could base their work on.<br /><br />/me muses on a Python 2.x branch...Duncan McGreggorhttps://www.blogger.com/profile/17155270977759488515noreply@blogger.comtag:blogger.com,1999:blog-8825992.post-44229792153765287522009-04-13T12:30:00.000-07:002009-04-13T12:30:00.000-07:00Yet another one for the heap- we call it Graphine,...Yet another one for the heap- we call it Graphine, and we're aiming at Python 3. You can find us <A HREF="http://gitorious.org/projects/graphine/pages/Home" REL="nofollow"> here </A>geremycondrahttps://www.blogger.com/profile/02824435481099053249noreply@blogger.comtag:blogger.com,1999:blog-8825992.post-64958753145316911602008-12-12T09:16:00.000-08:002008-12-12T09:16:00.000-08:00Here's another for you to look at:http://nodebox.n...Here's another for you to look at:<BR/><BR/>http://nodebox.net/code/index.php/Graphmrjbq7https://www.blogger.com/profile/06842721076008035602noreply@blogger.comtag:blogger.com,1999:blog-8825992.post-4333668675179289912008-12-11T09:45:00.000-08:002008-12-11T09:45:00.000-08:00Kamil,Thanks for your interest! I've created a new...Kamil,<BR/><BR/>Thanks for your interest! I've created a new team on Launchpad for this. If you can email me your lp id, I will invite you.<BR/><BR/>Also, if you branch the project ("bzr branch lp:simplegraph"), just add a sandbox directory for yourself, add your dict classes, and push it up to Launchpad ("bzr push lp~yourusername/simplegraph/yourbranchname") and I'll take a look at the code.<BR/><BR/>All the stuff I've been working on is also in the sandbox... ;-)<BR/><BR/>Thanks!Duncan McGreggorhttps://www.blogger.com/profile/17155270977759488515noreply@blogger.comtag:blogger.com,1999:blog-8825992.post-27013392395424550512008-12-10T17:01:00.000-08:002008-12-10T17:01:00.000-08:00I'd love to help out with this effort. I've been w...I'd love to help out with this effort. I've been wishing for a clean implementation of a bare-bones graph and tree module for a long time, but don't have enough confidence in my own Python-fu to create something general-purpose enough for mass consumption. <BR/><BR/>I've whipped up some basic directed and undirected graph classes based on dictionaries.<BR/><BR/>If you actually want to go ahead with your plan, let me know, I'd be glad to try and help out.Kamil Kisielhttps://www.blogger.com/profile/02593950039815709347noreply@blogger.comtag:blogger.com,1999:blog-8825992.post-33313183126696324642008-12-10T11:46:00.000-08:002008-12-10T11:46:00.000-08:00I went through the same list when porting LAD (lin...I went through the same list when porting LAD (lines and dots) from C++ to Python, ultimately deciding on NetworkX. NetworkX is used by Sage and is pure Python (you can easy_install it!), both of which are pluses for me.<BR/><BR/>Now for some shameless self promotion:<BR/><A HREF="http://www.fprimex.com/programming/lad" REL="nofollow">LAD</A> - Lines and Dots, a graph theory exploration and research program<BR/><BR/>Unfortunately I haven't had the time or motivation to continue working on it. I thought it was a promising idea though and would like to pick up where I left off someday. I even still have the TODO list for it, and support for other graph libraries is in there!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8825992.post-46911038111725690482008-12-09T15:25:00.000-08:002008-12-09T15:25:00.000-08:00This might be useful to you too:http://www.sagemat...This might be useful to you too:<BR/>http://www.sagemath.org:9001/graph_survey<BR/><BR/>http://wiki.sagemath.org/graphDorianhttps://www.blogger.com/profile/00024541691445866909noreply@blogger.comtag:blogger.com,1999:blog-8825992.post-5599518531165478922008-12-09T09:45:00.000-08:002008-12-09T09:45:00.000-08:00usagi:If all goes well, that is exactly what I wou...usagi:<BR/><BR/>If all goes well, that is exactly what I would like to see happen. However, my immediate goal is to have a module that <I>could</I> be easily accepted into the standard library. Whether it goes beyond that (and does eventually get accepted) is yet to be seen. If it does get that far, I'll be looking at PEP 218. But! One step at a time :-)<BR/><BR/>Regardless of how the core developers feel about a graph object in the standard library, one is certainly needed in the community. A basic graph with basic operations could benefit everyone.Duncan McGreggorhttps://www.blogger.com/profile/17155270977759488515noreply@blogger.comtag:blogger.com,1999:blog-8825992.post-22672641439566582192008-12-09T09:25:00.000-08:002008-12-09T09:25:00.000-08:00If your goal is to have a basic graph module in th...If your goal is to have a basic graph module in the standard library, I think it would be a good idea to write (and submitting) a PEP, to check if the core developers think that such a module is a desirable feature.Anonymoushttps://www.blogger.com/profile/02885581033966597420noreply@blogger.comtag:blogger.com,1999:blog-8825992.post-49916808843588790462008-12-09T08:07:00.000-08:002008-12-09T08:07:00.000-08:00It looks like I need to clarify a little more. And...It looks like I need to clarify a little more. And then I'll address the comments that have been posted :-)<BR/><BR/>What would we expect from a graph module in the standard library? What sort of functionality would it contain? What dependencies would it have?<BR/><BR/>In my opinion, such an object would have a bare minimum of methods -- just those needed to actually define a graph and a graph's basic operations. It would have no dependencies other than that which is already in the standard Python library. Anything visual (including labels) is right out. That sort of thing should be supported by projects that need it, not the base object itself.<BR/><BR/>This graph object should -- given its simplicity -- be a perfect basis for all the specialized graphs that various projects need. The intent of this project is not so much a reinvention of the wheel, but rather determining the most basic version of the wheel that could (ideally) be used as the basis for other wheels.<BR/><BR/>Now to respond to the comments...<BR/><BR/>Mike and John:<BR/><BR/>Thanks for the links. As you know,the projects you indicated are not simple graph implementations, but rather something like a "graph suite". NetworkX falls into that same category; the only reason I included it in my original list is because it seems to be the most popular.<BR/> <BR/>illume:<BR/><BR/>The project is called "simple-graph" but the module name (and in fact, the URL) use the name "simplegraph."<BR/><BR/>LBaret:<BR/><BR/>No fun was spoiled :-) Did something I saw give you the impression I only looked at the docs? I'm sorry if that's the case! I have used some of the listed modules for months (and some of them even years). I am intimately familiar with their implementations and am fairly confident of the reasons certain decisions were made. Of them all, Bob's probably comes the closest to meeting my needs.<BR/><BR/>DrKJam:<BR/><BR/>Sadly, NetworkX has built up some cruft over time. The project could probably benefit from a long "tuning" sprint where everyone worked on improving test coverage (mostly edge cases) and refactoring to eliminate redundant code.<BR/><BR/>Thanks for the feedback folks, and I hope this response has cleared up any confusion :-)Duncan McGreggorhttps://www.blogger.com/profile/17155270977759488515noreply@blogger.comtag:blogger.com,1999:blog-8825992.post-89714201611205701292008-12-09T05:44:00.000-08:002008-12-09T05:44:00.000-08:00I've been using NetworkX for over a year now and h...I've been using NetworkX for over a year now and have yet to find a better Python graph library.<BR/><BR/>Personally, all the features I needed are here (configurable graph behaviour, decent graph traversal, persistence, access to graphviz, etc).<BR/><BR/>However, NetworkX does have downsides. You graph is stored entirely in memory which can be very expensive and limits the maximum size of your graphs. I'd love to see a graph implementation that uses Berkeley DB under the covers. Perhaps an idea for simple-graph Duncan ;-)<BR/><BR/>Until the latest (official) release NetworkX didn't have support for graphs that stored data at the vertices (edges only in the past), but this is now solved in version <A HREF="http://pypi.python.org/pypi/networkx" REL="nofollow">0.99 </A> with the inclusion of <B>LabeledGraph</B> and <B>LabeledDiGraph</B>.<BR/><BR/>One serious beef I do have is how long it takes to start up. Try running this several times :-<BR/><BR/>#!/usr/bin/env python<BR/>import networkx<BR/><BR/>You'll notice it can take 2-3 seconds even with all the .pyc files in place.<BR/><BR/>IMHO, this is too costly for anything other than fairly long running processes. This is a real shame and indeed an argument for something a bit simpler with less of the 'kitchen sink' about it.<BR/><BR/>I'll be watching your progress with interest ;-)<BR/><BR/>Dave M.DrKJamhttps://www.blogger.com/profile/17930124567171106000noreply@blogger.comtag:blogger.com,1999:blog-8825992.post-48965109557268485472008-12-09T05:23:00.000-08:002008-12-09T05:23:00.000-08:00Also igraph.Also <A HREF="http://cneurocvs.rmki.kfki.hu/igraph/" REL="nofollow">igraph</A>.Johnhttps://www.blogger.com/profile/08760488516461361152noreply@blogger.comtag:blogger.com,1999:blog-8825992.post-48885530193884644982008-12-09T01:25:00.000-08:002008-12-09T01:25:00.000-08:00Sorry to spoil the fun but...I understand the plea...Sorry to spoil the fun but...<BR/><BR/>I understand the pleasure to reinvent the wheel but the reasonable thing to do would be to test the different frameworks/modules.<BR/><BR/>When I mean test, I mean real code not simply looking at the docs. <BR/><BR/>Even if you do your own thing after this evaluation, you would have a much better understanding of the shortcoming of the others modules.<BR/><BR/>More, you would better understand why the original authors had made the choices they did. <BR/><BR/>More often than not, you need to code with a module to fully grok what trade-off the author have choosen.<BR/><BR/>*That* would add value, as they say.Unknownhttps://www.blogger.com/profile/14963043736528936298noreply@blogger.comtag:blogger.com,1999:blog-8825992.post-27838854873405127982008-12-09T01:05:00.000-08:002008-12-09T01:05:00.000-08:00hello,maybe call it simplegraph so it is a pdp-8 c...hello,<BR/><BR/>maybe call it simplegraph so it is a pdp-8 compatible module name?<BR/><BR/>Another one is kjbuckets. It contained a goodish graph implementation ages ago that used much less memory than using dicts... but I don't know if it's been updated.<BR/><BR/>cu,René Dudfieldhttps://www.blogger.com/profile/17762358075557755436noreply@blogger.comtag:blogger.com,1999:blog-8825992.post-56879874658089238202008-12-08T22:30:00.000-08:002008-12-08T22:30:00.000-08:00Here's another for the list: http://www.osl.iu.edu...Here's another for the list: <BR/><BR/>http://www.osl.iu.edu/~dgregor/bgl-python/Mike Thompsonhttps://www.blogger.com/profile/09017379943922244406noreply@blogger.com