diameter for large directed real graphs

[ArchitWagle]

This method implements the [d2] algorithm for computing the diameter of real directed graphs.

[d2] 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

It is designed for directed real sparse graphs.

Component: graph theory

Keywords: gsoc, diameter

Author: Madhav Wagle

Branch/Commit: u/gh-ArchitWagle/real_directed_diameter @ b1bb1ac

Issue created by migration from https://trac.sagemath.org/ticket/29346

[ArchitWagle]

Branch: u/gh-ArchitWagle/real_directed_diameter

[ArchitWagle]

Author: Madhav Wagle

[ArchitWagle]

Commit: aceb725

[ArchitWagle]

Changed keywords from none to gsoc, diameter

[dcoudert]

comment:4

#29309 also implements the same algorithm. Shouldn't you join forces to obtain a stronger implementation ?

[ArchitWagle]

comment:5

Replying to @dcoudert:

#29309 also implements the same algorithm. Shouldn't you join forces to obtain a stronger implementation ?

Hi, The definitions of diameter used by me and
#29309 are different. He has made simplifications to his code based on the standard definition of diameter (like making direct calls to

simple_BFS()

which returns diameter infinity for non strongly connected graphs.

My implementation considers the max finite eccentricty, as specified in https://doi.org/10.1007/978-3-319-20086-6_5
Which returns a finite diameter for both connected and unconnected graphs

His implementation would be a much better choice if we want to keep the definition of diameter the same for all algorithms.

On the other hand, I can also modify my implementation to allow the user to set a parameter to make a choice on which definition of diameter they want to use. I would only need to add 1-2 lines of code to my current implementation to do that.

[ArchitWagle]

comment:6

Few changes to be made

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

b1bb1ac

corrected memset calls

[sagetrac-git]

Changed commit from aceb725 to b1bb1ac

[mkoeppe]

comment:8

Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.

[mkoeppe]

comment:10

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

[mkoeppe]

comment:11

Setting a new milestone for this ticket based on a cursory review.