Speed up Polyhedron_base.graph()

[jplitza]

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.

Component: geometry

Author: Jan-Philipp Litza

Branch/Commit: 0a2602f

Reviewer: Volker Braun

Issue created by migration from https://trac.sagemath.org/ticket/20110

[vbraun]

comment:1

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

[vbraun]

Reviewer: Volker Braun

[vbraun]

comment:3

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

[jplitza]

Author: Jan-Philipp Litza

[vbraun]

Changed branch from u/jplitza/polyhedron_graph to 0a2602f