Graphs: Faster implementation for HalfCube

[Ivo-Maffei]

Implementation of a faster method to construct the graph HalfCube

Depends on #30329

CC: @dimpase @dcoudert

Component: graph theory

Author: Ivo Maffei

Branch/Commit: 898fbee

Reviewer: David Coudert

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

[Ivo-Maffei]

Dependencies: #30329

[Ivo-Maffei]

Branch: public/graphs/30509

[Ivo-Maffei]

Commit: 3024980

[Ivo-Maffei]

comment:1

To convert the vertices of CubeGraph to integers one can use G.relabel(perm=int) as the vertices are strings and int(str) will convert str to its integer representation.

However, doing so causes an overflow error (not sure why) when we iterate over G.
One can simply iterate over range(2**(n-1)), but I think the construction in this branch is even faster as everything happens in Cython without calling CubeGraph.

---

Last 10 new commits:

97f0450	Merge branch 'develop' into t/30312
2a1861d	Merge branch 't/30312' into t/30329
5344f35	added long time flags and fixed van Lint name
9e69f0d	missing # long time
49cdcc1	Merge branch 't/30312' into t/30329
ea30040	added long time flags
4bcdb3c	typos and TeX fixes
feabf4f	better index section, uniform naming
1fdcad9	fixed typo
3024980	faster implementation of HalfCube

[dcoudert]

comment:2

It's of course faster to not call CubeGraph. The drawback is to lose the placement of vertices done in CubeGraph (which is certainly the most expensive part of the method).

a minor improvement:

-    G = Graph(E, format='list_of_edges')
+    G = Graph([range(2**(n - 1)), E], format='vertices_and_edges')

also, may be it's enough to put the sig_check before the for i... loop ?

[sagetrac-git]

Changed commit from 3024980 to 898fbee

[sagetrac-git]

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

898fbee

added positions to HalfCube

[dcoudert]

Author: Ivo Maffei

[dcoudert]

Reviewer: David Coudert

[dcoudert]

comment:4

LGTM, and the plots are nice.

[vbraun]

Changed branch from public/graphs/30509 to 898fbee