Internal Design of Estimated Diameter¶
Overview¶
The diameter of a graph is the worst-case distance interm of shortest path between any pairs of vertices. In other word, the graph diameter is the largest distance to traverse from one vertex to another when one always take the shortest path.
Algorithm¶
The implemented algorithm estimates the diameter in a heuristic way. It randomly choose several vertices and compute the distance from each of the chosen vertex to all the other vertices. And find out the maximum distance. The higher the final distance is, the greater the likelihood of getting the actual graph diameter.
Interface¶
The input should be a directed graph in compressed sparse row (CSR) format. The result is a value shows the final estimated diameter. Also, the source and destination of the path is given.
Implementation¶
The algorithm implemention is shown in the figure below:
There are several SSSP algorithm run in parallel as shown in the figure.
The max module will find the maxmum distance found and keep record it.
To find more distance between pairs of vertices, user can re-run this kernel multiple times.
