Opened 6 years ago
Last modified 6 years ago
#17408 closed enhancement
Faster transitive_reduction (=> faster Poset creation) — at Version 1
Reported by: | ncohen | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-6.5 |
Component: | graph theory | Keywords: | poset |
Cc: | chapoton, jmantysalo | Merged in: | |
Authors: | Nathann Cohen | Reviewers: | |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
As reported on #17361, the call to transitive_reduction
represents a non-negligible part of Poset creation.
This branch re-implements it for acyclic graphs.
Before
sage: g = posets.BooleanLattice(5).hasse_diagram().transitive_closure(); g = g.cartesian_product(g) sage: %time Poset(g) CPU times: user 1.3 s, sys: 8 ms, total: 1.3 s Wall time: 1.29 s Finite poset containing 1024 elements
After
sage: g = posets.BooleanLattice(5).hasse_diagram().transitive_closure(); g = g.cartesian_product(g) sage: %time Poset(g) CPU times: user 292 ms, sys: 12 ms, total: 304 ms Wall time: 265 ms Finite poset containing 1024 elements
Note that a LOT of time is lost on calls to __eq__
. If I make no mistake it is because Posets
are UniqueRepresentation
. I would personally be very very glad if we could get rid of that.
Change History (1)
comment:1 Changed 6 years ago by
- Description modified (diff)
- Status changed from new to needs_review
Note: See
TracTickets for help on using
tickets.