Hi Nathann , first of all, thanks a lot for your very quick answer! You are right, the sentence about NetworkX graphs referred to an old version of Sage http://www.math.ucla.edu/~jimc/mathnet_d/sage/reference/sage/graphs/graph.html (which unfortunately was one of the first Google results when I searched "sage undirected graphs").
I understand you are not interested in becoming a GSoC mentor: can anybody else be interested in being my mentor? If not, I would still be glad to collaborate on this topic, but I will probably have less time to work on that. Of course, I do not expect to improve functions like add_edge, get_neighbours etc. My goal would be to speed-up the main algorithms: for example, BFS can run on graphs with 1 million nodes and 10 millions edges in fractions of a second, which is the time Sage needs for graphs with 100.000 nodes and 1 million edges. Thank you very much! Michele On Friday, March 13, 2015 at 3:26:24 PM UTC+1, Nathann Cohen wrote: > > Hello Michele, > > > I have checked the graph library in SageMath, and in your documentation, > you > > write "Sage graphs are actually NetworkX graphs, wrapped in a Sage > class.". > > Can you tell me where you found that ? This is actually slighty > incorrect: NetworkX' graphs used to be the default data structure of > Sage's graphs, but that changed quite some time ago. Nowadays you > *can* use NetworkX graph if you want to, but we have our own C > implementation of graphs. > > > Although this implementation is very simple and user-friendly, it is not > > very fast (http://graph-tool.skewed.de/performance). > > Even though those statistics are made for NetworkX and not for Sage, I > would not be surprised to find out that we are not very competitive > for the algorithms they test. > > We could actually be quite competitive for centrality betweenness if > anybody cares: you can compute this easily from the distances between > all pairs of nodes, and we implemented this feature carefully. > > > For this reason, I > > would like to propose a project developing a more efficiency-oriented > > implementation, that might be preferred by some users: not only > researchers > > that analyze very big graphs in the field of Complex Networks (millions > or > > billions of nodes), > > We may not be very good for that indeed. > > > but also people who work in the algorithm design field, > > where efficiency is very important. > > Those guys, however, will probably feel more at home with Sage than > with any other software :-P > > > 1) Are you interested in a project like this, since none of your example > > project deals with Sage graph library? > > Welll.. I would personally be very glad if anybody wanted to work on > this in Sage, and I would be very very glad to contribute to the > effort. I am not very interested to become a GSOC mentor, however. > > > 2) In case, do you have any preference on how to choose the language to > use > > for the implementation? I see that many parts of Sage are written in C > or > > C++, but none in Java: is it possible to embed Java code in Sage? > Otherwise, > > I should only focus on C/C++. > > We do not use java much if at all. As far as I know we sometimes call > JMol for 3D data visualization, but that is all. In particular I am > not aware of any low-level calls to java code. > > > 3) Is there any performance bottleneck I should be aware of, before > starting > > a project like this? For instance, does the notebook interface impact > > performances? > > It depends. Because of our language (because it is not compiled, not > typed, ...) we will forever lose time in functions like add_edge, > get_neighbours etc. This being said, whenever we have some long > computation to run the first thing we do is convert the data structure > into something that is easier to work with, so it does not matter > much. > > If you are interested by this software outside of the GSOC context, I > would be glad to know. > > Have fuuuuuuuuuuun, > > Nathann > -- You received this message because you are subscribed to the Google Groups "sage-gsoc" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at http://groups.google.com/group/sage-gsoc. For more options, visit https://groups.google.com/d/optout.
