Graphs: fast implementation to compute antipodal graph

[gh-Ivo-Maffei]

Function to efficiently compute the antipodal graph with low memory usage.

Following the discussion in #30394 a sketch algorithm is

def antipodal_graph(G):
    """
    Return the antipodal graph of ``G``.
    """
    ecc = G.eccentricity(algorithm="DHV", with_labels=True)
    diam = max(ecc.values())
    # Get the list of antipodal vertices, i.e., with eccentricity = diameter
    V = [u for u, ecc_u in ecc.items() if ecc_u == diam]

    E = set()
    for u in V:
        for v, d in G.breadth_first_search(u, report_distance=True):
            if d == diam:
                E.add(frozenset((u, v)))

    name = f"antipodal graph of {G.name()}"
    return Graph([G, E], format='vertices_and_edges', name=name)

[dcoudert]

Roughly, to be efficient, it must be implemented using short_digraph in distances_all_pairs.pyx, and call low level methods.

A first task is to modify diameter/radius/eccentricity methods to take as input a short_digraph, and so avoid extra conversions from one format to the other. That is, the C level methods should use C only.

[git]

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

​28daf4e

modified eccentricity methods to take short_digraph as input

[git]

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

​df8b205	trac #30405: better version
​93c9fcd	trac #30405: fast method for antipodal graph

[dcoudert]

I have improved what you did and add method for constructing the antipodal_graph. So far it is not exposed in Graph. To do so, we should rebuild over #30394 and replace the basic method of #30394 by an import from this new method.

sage: from sage.graphs.distances_all_pairs import antipodal_graph                                                                   
sage: G = graphs.JohnsonGraph(10, 5)                                                                                                
sage: %time A = G.distance_graph(G.diameter())                                                                                      
CPU times: user 279 ms, sys: 4.44 ms, total: 284 ms
Wall time: 284 ms
sage: %time B = antipodal_graph(G)                                                                                                  
CPU times: user 39.7 ms, sys: 1.81 ms, total: 41.5 ms
Wall time: 40.6 ms
sage: A.is_isomorphic(B)                                                                                                            
True
sage: G = graphs.PetersenGraph()                                                                                                    
sage: %time A = G.distance_graph(G.diameter())                                                                                      
CPU times: user 806 µs, sys: 4 µs, total: 810 µs
Wall time: 817 µs
sage: %time B = antipodal_graph(G)                                                                                                  
CPU times: user 404 µs, sys: 1e+03 ns, total: 405 µs
Wall time: 412 µs
sage: A.is_isomorphic(B)                                                                                                            
True
sage: G = graphs.Grid2dGraph(10, 10)                                                                                                
sage: %time A = G.distance_graph(G.diameter())                                                                                      
CPU times: user 9.91 ms, sys: 556 µs, total: 10.5 ms
Wall time: 10.1 ms
sage: %time B = antipodal_graph(G)                                                                                                  
CPU times: user 1.48 ms, sys: 66 µs, total: 1.54 ms
Wall time: 1.61 ms
sage: A.is_isomorphic(B)                                                                                                            
True
sage: G = graphs.Grid2dGraph(20, 50)                                                                                                
sage: %time A = G.distance_graph(G.diameter())                                                                                      
CPU times: user 397 ms, sys: 39.4 ms, total: 436 ms
Wall time: 437 ms
sage: %time B = antipodal_graph(G)                                                                                                  
CPU times: user 9.26 ms, sys: 698 µs, total: 9.96 ms
Wall time: 9.55 ms
sage: A.is_isomorphic(B)                                                                                                            
True
sage: G = graphs.RandomBarabasiAlbert(10000, 2)                                                                                     
sage: %time A = G.distance_graph(G.diameter())                                                                                      
CPU times: user 55 s, sys: 5.3 s, total: 1min
Wall time: 1min
sage: %time B = antipodal_graph(G)                                                                                                  
CPU times: user 427 ms, sys: 5.84 ms, total: 433 ms
Wall time: 434 ms
sage: A.is_isomorphic(B)                                                                                                            
True

These comparisons are not completely fair. Most of the time of distance_graph is wasted in the intermediate dict of dict. A re-implementation is Cython would give better results and could be faster than the new method on small graphs or graphs like the JohnsonGraph. However, the new method is fast enough, so I don't think we should try to optimize further.

[dcoudert]

Green bot. Please review.

[dimpase]

ok.