Opened 23 months ago
Closed 22 months ago
#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: |
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
- Cc gh-vipul79321 added
comment:2 Changed 22 months ago by
- Branch set to public/graphs/antipodal_30405
comment:3 Changed 22 months ago by
- Commit set to 28daf4eebe1499e08c727d1b30306152e4507f21
Branch pushed to git repo; I updated commit sha1. New commits:
28daf4e | modified eccentricity methods to take short_digraph as input
|
comment:4 Changed 22 months ago by
- Commit changed from 28daf4eebe1499e08c727d1b30306152e4507f21 to 93c9fcdd9babfbb7e3340e279cde7ed634712753
comment:5 Changed 22 months ago by
- 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.
comment:6 Changed 22 months ago by
Green bot. Please review.
comment:7 Changed 22 months ago by
- Reviewers set to Dima Pasechnik
- Status changed from needs_review to positive_review
ok.
comment:8 Changed 22 months ago by
- Branch changed from public/graphs/antipodal_30405 to 93c9fcdd9babfbb7e3340e279cde7ed634712753
- Resolution set to fixed
- Status changed from positive_review to closed
Roughly, to be efficient, it must be implemented using
short_digraph
indistances_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.