#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, dimpase, dcoudert, vdelecroix Merged in:
Authors: Jonathan Kliem Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: 0347b17 (Commits, GitHub, GitLab) Commit: 0347b17a8413be9468730f5e85a1d84146f277fa
Dependencies: #30753 Stopgaps:

Status badges

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 14 months ago by gh-kliem

  • Branch set to public/30776
  • Commit set to 0347b17a8413be9468730f5e85a1d84146f277fa
  • Status changed from new to needs_review

Last 10 new commits:

05c3f72use cases for subgraph
7a4326eallow deleting of multiedges and loops
fb96022fix mistakes
776e38fexpose subgraph method to initialization/copying
7c6e1d5clean up
40bacf0documentation
2611e8aoutsource a function that can work more general
54d59eaworking version for subgraph check
bd9c48crestructering
0347b17documentation

comment:2 Changed 14 months ago by gh-kliem

  • Milestone changed from sage-9.2 to sage-9.3

comment:3 Changed 14 months ago by dcoudert

  • Reviewers set to David Coudert
  • Status changed from needs_review to positive_review

This looks good to me.

comment:4 Changed 14 months ago by gh-kliem

Thank you.

comment:5 Changed 13 months ago by vbraun

  • Status changed from positive_review to needs_work

Merge conflict

comment:6 Changed 13 months ago by gh-kliem

  • Status changed from needs_work to positive_review

It appears that Volker Braun tried to merge #30776 and #30777 at the same time, but they had a merge conflict.

We set this back on positive review and hope it works now.

comment:7 Changed 13 months ago by vbraun

  • Branch changed from public/30776 to 0347b17a8413be9468730f5e85a1d84146f277fa
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.