On Nov 29, 2009, at 5:22 AM, Minh Nguyen wrote: > Hi Nathann, > > On Sat, Nov 28, 2009 at 1:57 AM, Nathann Cohen <nathann.co...@gmail.com > > wrote: > > <SNIP> > >> If I make no mistake, Robert Miller rewrote the Graph class in C, >> which sounds like we are trying to remove networkX from Sage and use >> our own version of graphs instead. If this is the case, we will >> have a >> C class for graphs, meaning that some Graph functions will be written >> in C instead of Python, thus gaining a lot of speed in Sage. At this >> point, what should we do ? Rewrite the Python implementation of the >> Floyd Marshall algorithm in C ( or whatever was written in NetworkX >> if >> more efficient ), just call NetworkX, something different ?
I think the basic idea was that one could write a faster (sparse and dense) graph "core," and then run all the NetworkX algorithms on top of it as long as it supported the interface (for manipulating and querying vertices and edges). If some code was still too slow then it would be moved down to C (hopefully it would be sufficient to declare the graphs as c-graphs and compile with Cython to remove all the Python function call overhead). I don't know how well this works at the moment. >> I think Sage's graph class needs to be rewritten to be a bit more >> efficient..... Efficiency is a problem I have sometimes in Sage, on >> instances for which this should not be a problem.... So I expect a >> lot >> from the c_graphs that are currently somewhere in Sage ( are they >> used >> ? How, when ? ) They are used for graph isomorphism, for example. >> In the end : What is going on with the C graphs in Sage, can we >> expect >> them to eb available soon ? You can use them right now. They're just not as feature full. >> What are we trying to do with NetworkX (leave it, keep it, nothing >> special ? ) We're certainly keeping it for the time being, but there's a limit to speed if one sticks with pure Python. I don't think there's any goal to replace NetworkX altogether. It could be like a lot of other things were we handle some things ourselves (where we needed absolute speed) and call off to NetworkX for the rest. > I share some of your concerns as expressed above. In the last few > days, I started writing an introductory chapter for a book on > algorithmic graph theory using Sage. In doing so, I found that Sage > lacks some basic features. For example, I have been unable to find a > function/method to compute the degree sequence of a graph. Though much could be added of course, I'm sure something this basic is a lack of documentation rather than functionality. > What is required is a statement from Robert Miller, or people involved > in the development of C graph, about the current state of C graph. The > statement should include the state where C graph is at in terms of > development, other things that need to be implemented, as well as how > to navigate around the graph theory module. That would be helpful, but it's not needed. Robert Miller is busy studying p-descent and other BSD related topics for his thesis right now, not graphs, so I'd imagine that there's not much going on development wise with them unless you want to take up the banner. > I was reading through graph.py only to discover that it's very, very > long. Can that module be split up and organized along topical lines? As a first pass, the Graph and DiGraph class could be split out into their own files. - Robert -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
