1 | | Extra speedup improvements in `subgraph` with a case forgotten in #30510. We also improve the logic in the selection of the default algorithm. |
| 1 | We add a fast method `subgraph_given_vertices` to `CGraphBackend`. This method allows fast subgraph creation including copying. |
| 2 | Also improvements in `subgraph` with a case forgotten in #30510. |
| 3 | |
| 4 | Before #30665: |
| 5 | |
| 6 | {{{ |
| 7 | sage: G = graphs.Grid2dGraph(100, 100) # dynamic sparse |
| 8 | sage: V = list(G) |
| 9 | sage: %timeit H = G.subgraph(V[:50], algorithm='add') |
| 10 | 280 µs ± 465 ns per loop (mean ± std. dev. of 7 runs, 1000 loops each) |
| 11 | sage: %timeit H = G.copy() |
| 12 | 30.3 ms ± 72.8 µs per loop (mean ± std. dev. of 7 runs, 10 loops each) |
| 13 | |
| 14 | sage: G = G.copy(immutable=True) # static sparse |
| 15 | sage: %timeit H = G.subgraph(V[:50], algorithm='add') |
| 16 | 553 µs ± 373 ns per loop (mean ± std. dev. of 7 runs, 1000 loops each) |
| 17 | sage: %timeit H = G.copy(immutable=False) |
| 18 | 31.6 ms ± 91.6 µs per loop (mean ± std. dev. of 7 runs, 10 loops each) |
| 19 | |
| 20 | sage: G = graphs.CompleteGraph(1000) # dynamic dense |
| 21 | sage: V = list(G) |
| 22 | sage: %timeit H = G.subgraph(V[:50], algorithm='add') |
| 23 | 54.2 ms ± 54.6 µs per loop (mean ± std. dev. of 7 runs, 10 loops each) |
| 24 | sage: %timeit H = G.copy() |
| 25 | 527 ms ± 663 µs per loop (mean ± std. dev. of 7 runs, 1 loop each) |
| 26 | }}} |
| 27 | |
| 28 | With #30665 and #30769: |
| 29 | |
| 30 | {{{ |
| 31 | sage: G = graphs.Grid2dGraph(100, 100) # dynamic sparse |
| 32 | sage: V = list(G) |
| 33 | sage: %timeit H = G.subgraph(V[:50], algorithm='add') |
| 34 | 257 µs ± 356 ns per loop (mean ± std. dev. of 7 runs, 1000 loops each) |
| 35 | sage: %timeit H = G.copy() |
| 36 | 26.4 ms ± 146 µs per loop (mean ± std. dev. of 7 runs, 10 loops each) |
| 37 | |
| 38 | sage: G = G.copy(immutable=True) # static sparse |
| 39 | sage: %timeit H = G.subgraph(V[:50], algorithm='add') |
| 40 | 521 µs ± 308 ns per loop (mean ± std. dev. of 7 runs, 1000 loops each) |
| 41 | sage: %timeit H = G.copy(immutable=False) |
| 42 | 28.3 ms ± 95.2 µs per loop (mean ± std. dev. of 7 runs, 10 loops each) |
| 43 | |
| 44 | sage: G = graphs.CompleteGraph(1000) # dynamic dense |
| 45 | sage: V = list(G) |
| 46 | sage: %timeit H = G.subgraph(V[:50], algorithm='add') |
| 47 | 51.6 ms ± 64.6 µs per loop (mean ± std. dev. of 7 runs, 10 loops each) |
| 48 | sage: %timeit H = G.copy() |
| 49 | 429 ms ± 1.23 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) |
| 50 | }}} |
| 51 | |
| 52 | With this ticket: |
| 53 | |
| 54 | {{{ |
| 55 | sage: G = graphs.Grid2dGraph(100, 100) # dynamic sparse |
| 56 | sage: V = list(G) |
| 57 | sage: %timeit H = G.subgraph(V[:50], algorithm='add') |
| 58 | 80.9 µs ± 19.1 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each) |
| 59 | sage: %timeit H = G.copy() |
| 60 | 15.4 ms ± 10.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) |
| 61 | |
| 62 | sage: G = G.copy(immutable=True) # static sparse |
| 63 | sage: %timeit H = G.subgraph(V[:50], algorithm='add') |
| 64 | 327 µs ± 1.04 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) |
| 65 | sage: %timeit H = G.copy(immutable=False) |
| 66 | 20.3 ms ± 23 µs per loop (mean ± std. dev. of 7 runs, 10 loops each) |
| 67 | |
| 68 | sage: G = graphs.CompleteGraph(1000) # dynamic dense |
| 69 | sage: V = list(G) |
| 70 | sage: %timeit H = G.subgraph(V[:50], algorithm='add') |
| 71 | 1.03 ms ± 10.6 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) |
| 72 | sage: %timeit H = G.copy() |
| 73 | 269 ms ± 3.08 ms per loop (mean ± std. dev. of 7 runs, 10 loops each) |
| 74 | }}} |