#32475 closed enhancement (fixed)

Faster perfect matchings iterator

Reported by: David Coudert Owned by:
Priority: major Milestone: sage-9.5
Component: graph theory Keywords:
Cc: Travis Scrimshaw Merged in:
Authors: David Coudert Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: d6e5089 (Commits, GitHub, GitLab) Commit: d6e5089db13059e1b37b3649818f231981ccb968
Dependencies: Stopgaps:

Status badges

Description

An iterator over all perfect matchings of a graph has been added in #20061. In this ticket, we improve it using ideas from https://trac.sagemath.org/ticket/17132#comment:28

Before

sage: G = graphs.ChvatalGraph()                                                                                                                    
sage: len(list(G.perfect_matchings()))                                                                                                             
52
sage: %timeit len(list(G.perfect_matchings()))                                                                                                     
15.7 ms ± 779 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
sage: G = graphs.CompleteGraph(8)                                                                                                                  
sage: len(list(G.perfect_matchings()))                                                                                                             
105
sage: %timeit len(list(G.perfect_matchings()))                                                                                                     
11.8 ms ± 287 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

With this ticket

sage: G = graphs.ChvatalGraph()                                                                                                                    
sage: len(list(G.perfect_matchings()))                                                                                                             
52
sage: %timeit len(list(G.perfect_matchings()))                                                                                                     
2.49 ms ± 100 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
sage: G = graphs.CompleteGraph(8)                                                                                                                  
sage: len(list(G.perfect_matchings()))                                                                                                             
105
sage: %timeit len(list(G.perfect_matchings()))                                                                                                     
2.58 ms ± 137 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Change History (4)

comment:1 Changed 13 months ago by David Coudert

Branch: public/graphs/32475_perfect_matchings
Commit: d6e5089db13059e1b37b3649818f231981ccb968
Status: newneeds_review

New commits:

d6e5089trac #32475: faster perfect matchings iterator

comment:2 Changed 13 months ago by Travis Scrimshaw

Reviewers: Travis Scrimshaw
Status: needs_reviewpositive_review

That is quite a good speed improvement. LGTM.

comment:3 Changed 13 months ago by David Coudert

Thank you.

comment:4 Changed 12 months ago by Volker Braun

Branch: public/graphs/32475_perfect_matchingsd6e5089db13059e1b37b3649818f231981ccb968
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.