These algorithms are designed to be fast on large sparse graphs (real world large graphs are sparse). So basic algorithms with low overhead might be faster on very dense graphs. I have not seen your code, but it can certainly be optimized further.
Le samedi 7 mars 2020 14:40:27 UTC+1, Madhav Wagle a écrit : > > > Thanks for the response! > It does work for strongly connected graphs. > But the performance of the new algo on denser graphs is worse than the > previous sage implementation(which was basically just finding the max of > eccentricities). > I think the reason is for denser graph, the newer algorithm just seems to > end up performing a BFS on every node. > > With a little experimenting it seems that the performance of the new > algorithm gets worse as the graph gets denser > sage: D = digraphs.RandomDirectedGNP(1000,0.6) > sage: %time D.diameter() > CPU times: user 840 ms, sys: 11.9 ms, total: 852 ms > Wall time: 850 ms > 2 > sage: %time D.diameter(algorithm='aik') > CPU times: user 2.1 s, sys: 3.73 ms, total: 2.11 s > Wall time: 2.1 s > 2 > > I will try to optimize the code further though. > The paper also mention vertex ordering strategies( which I haven't > implemented ) which may give speedups, but they conclude that ordering > strategies dont have a very significant impact on the performance of the > algo. > > Thanks and Regards, > Madhav > > On Saturday, 7 March 2020 15:48:32 UTC+5:30, David Coudert wrote: >> >> Thank you for your interest in this project. >> >> >>> 1)The above algorithm only works well for directed sparse graphs which >>> *aren't* strongly connected, >>> >> >> Why isn't it working for strongly connected graphs ? >> >> >>> Is it fine to modify important and central functions like >>> *simple_BFS()* >>> just to accomodate the needs of this new algorithm? >>> >> >> it depends on the modification as this method is also used elsewhere in >> the graph module. The modification should not affect the behavior. >> >> >>> In my implementation I have implemented all the BFS's as a part of the >>> main algorithm function itself ( instead of funtion calls ), is that ok >>> since it dosen't affect code readability negatively*.* >>> >> >> We added method simple_BFS to avoid code duplication. However, it is >> perfectly acceptable to implement your own BFS if simple_BFS is not >> appropriate (missing instructions, etc.). >> >> Sincerely, >> David. >> >> > -- 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 view this discussion on the web visit https://groups.google.com/d/msgid/sage-gsoc/b6bc3a8e-e869-4406-b906-200679b43cb0%40googlegroups.com.
