#30405 closed enhancement (fixed)

Graphs: fast implementation to compute antipodal graph

Reported by: gh-Ivo-Maffei Owned by:
Priority: major Milestone: sage-9.2
Component: graph theory Keywords:
Cc: dcoudert, gh-vipul79321 Merged in:
Authors: David Coudert, Vipul Gupta Reviewers: Dima Pasechnik
Report Upstream: N/A Work issues:
Branch: 93c9fcd (Commits, GitHub, GitLab) Commit: 93c9fcdd9babfbb7e3340e279cde7ed634712753
Dependencies: Stopgaps:

Status badges

Description

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)

Change History (8)

comment:1 Changed 23 months ago by dcoudert

  • Cc gh-vipul79321 added

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.

comment:2 Changed 22 months ago by gh-vipul79321

  • Authors changed from David Coudert to David Coudert, Vipul Gupta
  • Branch set to public/graphs/antipodal_30405

comment:3 Changed 22 months ago by git

  • Commit set to 28daf4eebe1499e08c727d1b30306152e4507f21

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

28daf4emodified eccentricity methods to take short_digraph as input

comment:4 Changed 22 months ago by git

  • Commit changed from 28daf4eebe1499e08c727d1b30306152e4507f21 to 93c9fcdd9babfbb7e3340e279cde7ed634712753

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

df8b205trac #30405: better version
93c9fcdtrac #30405: fast method for antipodal graph

comment:5 Changed 22 months ago by dcoudert

  • Status changed from new to needs_review

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.

Last edited 22 months ago by dcoudert (previous) (diff)

comment:6 Changed 22 months ago by dcoudert

Green bot. Please review.

comment:7 Changed 22 months ago by dimpase

  • Reviewers set to Dima Pasechnik
  • Status changed from needs_review to positive_review

ok.

comment:8 Changed 22 months ago by vbraun

  • Branch changed from public/graphs/antipodal_30405 to 93c9fcdd9babfbb7e3340e279cde7ed634712753
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.