Opened 6 years ago

Last modified 6 years ago

#17408 closed enhancement

Faster transitive_reduction (=> faster Poset creation) — at Version 5

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: u/ncohen/17408 (Commits, GitHub, GitLab) Commit: ce577a909e3ac2835f975cc9515b54459174e8ca
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.

sage: g = posets.BooleanLattice(5).hasse_diagram().transitive_closure(); g = g.cartesian_product(g)
sage: %timeit g.transitive_reduction()
1 loops, best of 3: 1.02 s per loop
sage: %timeit g.transitive_reduction(acyclic=True)
10 loops, best of 3: 28.9 ms per loop

Now the critical part in the creation of a Poset is triggered by UniqueRepresentation. As soon as you create a Poset it is being compared with those that already exists... That is actually pre-computing the equality relationships between all existing posets even if you never asked for it, and I personally see it as wasted time (especially since I cannot disable it).

Nathann

Change History (5)

comment:1 Changed 6 years ago by ncohen

  • Description modified (diff)
  • Status changed from new to needs_review

comment:2 Changed 6 years ago by ncohen

  • Branch set to u/ncohen/17408

comment:3 Changed 6 years ago by git

  • Commit set to ce577a909e3ac2835f975cc9515b54459174e8ca

Branch pushed to git repo; I updated commit sha1. New commits:

ce577a9trac #17408: Faster transitive_reduction (=> faster Poset creation)

comment:4 Changed 6 years ago by chapoton

  • Keywords poset added

comment:5 Changed 6 years ago by ncohen

  • Description modified (diff)
Note: See TracTickets for help on using tickets.