Diameter for real directed graphs, implementation doubts

[Madhav Wagle]

Hi, I am Madhav Wagle. I am final year student of computer science and am interested in the

Diameter, radius, eccentricities, and distances problem for gsoc 2020

I read the paper [d1] and implemented it in sage. The function is working correctly and the answer it gives matches the answers produced by the code the authors of [d1] provided on several random sparse graphs.

For example, for the below di-graph

the algorithm outputs

%time D.diameter(algorithm='aik') #'aik' is the name of the new algo (initials of the author's lastnames)
CPU times: user 270 µs, sys: 19 µs, total: 289 µs
Wall time: 302 µs
9

I have some doubts about my implementation though:

1)The above algorithm only works well for directed sparse graphs which aren't strongly connected, Is it fine to modify important and central functions like

simple_BFS()

just to accomodate the needs of this new algorithm?

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.

[d1] Takuya Akiba, Yoichi Iwata, Yuki Kawata: An Exact Algorithm for Diameters of Large Real Directed Graphs. SEA 2015: 56-67 https://doi.org/10.1007/978-3-319-20086-6_5

[David Coudert]

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.

 

[Madhav Wagle]

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

[David Coudert]

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.