Contributor
Vipul Gupta

Efficient methods for Diameter, radius and all eccentricities computations


Mentors
David Coudert
Organization
SageMath

Currently, the algorithms for Radius, Diameter, and all eccentricities calculations in SageMath are too brute and hence too slow. They involve computing eccentricity of each vertex using the shortest path (all pair or single source) method. This project aims at implementing best-known methods for Radius, Diameter, and All eccentricities computation for (weighted) (Directed) graphs. All these algorithms will definitely improve the efficiency in the area of Network Routing problems, Facility location problem, measuring the closeness of groups of individuals in sociology, etc, and will improve the overall functionality of graphs module of SageMath.

Also, refactoring and improving some distance computation methods such as Wiener Index, Distance Distribution, etc. Also, Improving the overall consistency of weight function in the graph module.