Hello everybody !!! Reviewing patch #7533, Rob Beezer noticed that the Graph function to compute the distances between all the pairs of vertices in a Graph ( shortest_path_all_pairs(), written in Python ) is much slower than computing independently the distances between all the pairs of vertices in the Graph (which uses NetworkX), which is a bit worrying...
I created ticket #7540 to eventually change this, to which Yann replied by mentionning that NetworkX also contained a function to compute all the distances in the graph. Here is one comparision between these functions : sage: g=graphs.RandomGNP(300,.1) sage: time a=[g.distance(i,j) for (i,j) in Subsets(g,2)] CPU times: user 2.67 s, sys: 0.01 s, total: 2.68 s Wall time: 2.68 s sage: time e=g.shortest_path_all_pairs() CPU times: user 37.95 s, sys: 0.13 s, total: 38.08 s Wall time: 38.23 s sage: time e=networkx.all_pairs_shortest_path(g) CPU times: user 1.93 s, sys: 0.02 s, total: 1.94 s Wall time: 1.96 s As you can see, the differences are crystal clear... It then seems we should replace the Floyd-Marshall algorithm in Sage's function shortest_path_all_pairs() by a direct call to NetworkX, and call it a deal. It also seems to be for me the moment to ask a question about the implementation of graphs in Sage : 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 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 ? ) In the end : What is going on with the C graphs in Sage, can we expect them to eb available soon ? What are we trying to do with NetworkX ( leave it, keep it, nothing special ? ) Thank you for your answers ! Nathann Cohen -- 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
