Opened 2 years ago

Closed 2 years ago

## #30776 closed enhancement (fixed)

# Implement an improved subgraph test for graph backends

Reported by: | gh-kliem | Owned by: | |
---|---|---|---|

Priority: | major | Milestone: | sage-9.3 |

Component: | graph theory | Keywords: | graph, equality, subgraph |

Cc: | gh-kliem, Dima Pasechnik, David Coudert, Vincent Delecroix | Merged in: | |

Authors: | Jonathan Kliem | Reviewers: | David Coudert |

Report Upstream: | N/A | Work issues: | |

Branch: | 0347b17 (Commits, GitHub, GitLab) | Commit: | 0347b17a8413be9468730f5e85a1d84146f277fa |

Dependencies: | #30753 | Stopgaps: |

### Description

We implement an improved subgraph test that also speeds up equality test.

Before (on #30753):

sage: G = graphs.Grid2dGraph(100, 100) # dynamic sparse sage: H = G.copy() sage: %timeit H == G 14.7 ms ± 34.7 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) sage: V = list(G) sage: H = G.subgraph(V[:50], algorithm='add') sage: %timeit H.is_subgraph(G) 158 µs ± 162 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each) sage: %timeit H.is_subgraph(G, induced=False) 48.8 µs ± 131 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each) sage: G = G.copy(immutable=True) # static sparse sage: H = G.copy() sage: %timeit H == G 10.4 ms ± 5.66 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) sage: V = list(G) sage: H = G.subgraph(V[:50], algorithm='add') sage: %timeit H.is_subgraph(G) 398 µs ± 223 ns per loop (mean ± std. dev. of 7 runs, 1000 loops each) sage: %timeit H.is_subgraph(G, induced=False) 37.2 µs ± 141 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each) sage: G = graphs.CompleteGraph(1000) # dynamic dense sage: H = G.copy() sage: %timeit H == G 349 ms ± 1.9 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) sage: V = list(G) sage: H = G.subgraph(V[:50], algorithm='add') sage: %timeit H.is_subgraph(G) 1.51 ms ± 2.18 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) sage: %timeit H.is_subgraph(G, induced=False) 539 µs ± 705 ns per loop (mean ± std. dev. of 7 runs, 1000 loops each)

After:

sage: G = graphs.Grid2dGraph(100, 100) # dynamic sparse sage: H = G.copy() sage: %timeit H == G 3.8 ms ± 3.04 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) sage: V = list(G) sage: H = G.subgraph(V[:50], algorithm='add') sage: %timeit H.is_subgraph(G) 50.4 µs ± 53.6 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each) sage: %timeit H.is_subgraph(G, induced=False) 34.3 µs ± 22.6 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each) sage: G = G.copy(immutable=True) # static sparse sage: H = G.copy() sage: %timeit H == G 2.42 ms ± 2.44 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) sage: V = list(G) sage: H = G.subgraph(V[:50], algorithm='add') sage: %timeit H.is_subgraph(G) 34.6 µs ± 39.8 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each) sage: %timeit H.is_subgraph(G, induced=False) 24.7 µs ± 31.5 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each) sage: G = graphs.CompleteGraph(1000) # dynamic dense sage: H = G.copy() sage: %timeit H == G 89.5 ms ± 48.5 µs per loop (mean ± std. dev. of 7 runs, 10 loops each) sage: V = list(G) sage: H = G.subgraph(V[:50], algorithm='add') sage: %timeit H.is_subgraph(G) 908 µs ± 810 ns per loop (mean ± std. dev. of 7 runs, 1000 loops each) sage: %timeit H.is_subgraph(G, induced=False) 70.8 µs ± 187 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

This is a step towards #30641.

### Change History (7)

### comment:1 Changed 2 years ago by

Branch: | → public/30776 |
---|---|

Commit: | → 0347b17a8413be9468730f5e85a1d84146f277fa |

Status: | new → needs_review |

### comment:2 Changed 2 years ago by

Milestone: | sage-9.2 → sage-9.3 |
---|

### comment:3 Changed 2 years ago by

Reviewers: | → David Coudert |
---|---|

Status: | needs_review → positive_review |

This looks good to me.

### comment:6 Changed 2 years ago by

Status: | needs_work → positive_review |
---|

### comment:7 Changed 2 years ago by

Branch: | public/30776 → 0347b17a8413be9468730f5e85a1d84146f277fa |
---|---|

Resolution: | → fixed |

Status: | positive_review → closed |

**Note:**See TracTickets for help on using tickets.

Last 10 new commits:

`use cases for subgraph`

`allow deleting of multiedges and loops`

`fix mistakes`

`expose subgraph method to initialization/copying`

`clean up`

`documentation`

`outsource a function that can work more general`

`working version for subgraph check`

`restructering`

`documentation`