Opened 6 years ago

Closed 6 years ago

#20110 closed enhancement (fixed)

Speed up Polyhedron_base.graph()

Reported by: jplitza Owned by:
Priority: trivial Milestone: sage-7.1
Component: geometry Keywords:
Cc: Merged in:
Authors: Jan-Philipp Litza Reviewers: Volker Braun
Report Upstream: N/A Work issues:
Branch: 0a2602f (Commits, GitHub, GitLab) Commit: 0a2602fcba8d18b204dbcd23f8a106f9bc63d55d
Dependencies: Stopgaps:

Status badges


Currently, Polyhedron_base.graph() intersects with the base set of all vertices in every of the n over 2 loop iterations in line 3321, where n is the number of vertices. This is useless as far as I can see, because the sets that are being intersected cannot possibly ever contain something that is not a vertex.

Leaving out this additional intersection speeds up the process of constructing the graph significantly. I tested it on a 4 GHz machine for the polyhedron polytopes.associahedron(['E', 7]), and with my patch it only took close to two minutes instead of 5:15. Other examples like polytopes.associahedron(['E', 8]) also suggest a significant speedup, although I don't have precise measurements from the same machine.

I also tested that the resulting graph is actually the same for some polyhedra.

Change History (6)

comment:1 Changed 6 years ago by vbraun

Looks good to me. I assume tests pass. You should set tickets to "needs review" when you are ready...

comment:2 Changed 6 years ago by jplitza

  • Status changed from new to needs_review

comment:3 Changed 6 years ago by vbraun

  • Reviewers set to Volker Braun

Can you fill in the "Author" field with your real name?

comment:4 Changed 6 years ago by jplitza

  • Authors set to Jan-Philipp Litza

comment:5 Changed 6 years ago by vbraun

  • Status changed from needs_review to positive_review

comment:6 Changed 6 years ago by vbraun

  • Branch changed from u/jplitza/polyhedron_graph to 0a2602fcba8d18b204dbcd23f8a106f9bc63d55d
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.