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/1af55d44-ca70-4dd5-a380-a5fe5c5ea7f9%40googlegroups.com.
