Meta ticket: graphs: improve distances, radius, diameter, eccentricities
The goal of this ticket is to organize and follow the changes and improvements done on methods for computing distances, diameter, radius and eccentricities.
Tickets:
 #29660: Move radius, diameter and eccentricity methods from generic_graph.py to graph.py and digraph.py
 #29715: Implement a fast algorithm by Dragan, Habib and Viennot for computing the radius of undirected graphs.
 #29734: fix an error in
shortest_path_lengths
method in generic_graph.py
. The input graph should not be modified.
 #29744: Implement diameter computation method for undirected graphs given by Dragan, Habib and Viennot.
 #27934: Implement all eccentricity method for undirected graphs given by Dragan, Habib and viennot.
 #29422: DiFUB algorithm for diameter of real (unweighed) directed graphs
 #30039: Weighted version of difub algorithm and 2Dsweep.
 #30081: Cleaning and improving consistency in
distances
methods in graph module
 #30247: memory efficient implementation of Wiener index
 #30269: memory efficient implementation of distances distribution
 #30405: fast (and memory efficient) implementation of
antipodal_graph
To do:
shortest_paths
method in boost_graph.pyx
doesnt properly detect negative cycle using BellmanFord
as algorithm. To solve, we can try to traverse distance dictionary and check if any value is negative. If negative then raise error, since distances can't be negative.
 In #29744 and #29715, we have raised an error, if graph contains negative edge weights. Reason for this was
BellmanFord
is not able to properly detect negative cycle in undirected graphs.
Opened and inactive tickets, to be finalized or ...
 #29346: diameter for large directed real graphs  Algorithm by Takuya Akiba, Yoichi Iwata, Yuki Kawata
 #29309: duplicate of #29346 with a different implementation
 #29336: proposal for making a code of Yuki Kawata to compute the diameter of directed graphs an external package. Same algorithm than #29346 ?
 #27564: methods for computing the diameter of trees. Note that 2 BFS / Dijkstra calls are sufficient for that.
 #27540: approximate algorithm for the diameter of undirected graphs.
 #4854: add parameter
as_edge
to return a path as a list of labeled edges instead of a list of vertices
Change History (24)
Description: 
modified (diff)

Description: 
modified (diff)

Description: 
modified (diff)

Description: 
modified (diff)

Keywords: 
gsoc20 added; gsoc removed

Summary: 
Meta ticket: improvement of distances, radius, diameter and eccentricities →
Meta ticket: graphs: improve distances, radius, diameter, eccentricities

Description: 
modified (diff)

Description: 
modified (diff)

Type: 
task →
defect

Description: 
modified (diff)

Type: 
defect →
task

Description: 
modified (diff)

Description: 
modified (diff)

Description: 
modified (diff)

Keywords: 
gsoc2020 added; gsoc20 removed

Description: 
modified (diff)

Description: 
modified (diff)

Description: 
modified (diff)

Description: 
modified (diff)

Description: 
modified (diff)

Milestone: 
sage9.2 →
sage9.3

Milestone: 
sage9.3 →
sage9.4

Milestone: 
sage9.4 →
sage9.5

Milestone: 
sage9.5 →
sage9.6

Milestone: 
sage9.6 →
sage9.7

Milestone: 
sage9.7 →
sage9.8

I am glad to see this, because there are several open tickets on these topics. Other tickets I noticed that seem to fit the description and I hope will be included in the organization: #29431, #29422, #29346, #29336, #29309, #27934, #27564, #27540, #27506.