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:

Status badges

Description (last modified by ncohen)

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 ncohen

  • Description modified (diff)
  • Status changed from new to needs_review
Note: See TracTickets for help on using tickets.