Add .is_combinatorially_isomorphic() method to polyhedra

[jplab]

Two polyhedra are combinatorially isomorphic if their face lattices are isomorphic as posets.

The test for combinatorial isomorphism should test the isomorphism of the vertex-facet adjacency graph of both polyhedra.

CC: @mo271 @mkoeppe @videlec @sagetrac-tmonteil @fchapoton

Component: geometry

Keywords: polytope, days84

Author: Moritz Firsching

Branch/Commit: 42d5205

Reviewer: Jean-Philippe Labbé

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

[mo271]

Branch: u/moritz/is_combinatorial_isomorphic

[mo271]

comment:3

pushed first version, which handles bounded polyhedra

---

New commits:

508bc6b

initial version

[mo271]

Commit: 508bc6b

[sagetrac-git]

Changed commit from 508bc6b to ca97480

[sagetrac-git]

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

ca97480

pep8 errors fixed

[jplab]

comment:5

Hi Moritz,

Here are some corrections:

• the input should be something like:

    INPUT:
    - ``other`` - a polyhedron object
    - ``algorithm`` (default=`bipartite_graph`) - specifies the algorithm to use. The other possible value is `face_lattice`.

• The paragraph starting with Checking that a should be unindented (and next block also)
• intersected its... should be intersected with its reflection through the origin.
• isomorpic to -> isomorphic to the
• several other missing words.
• start with a simple example, perhaps move the less informative ones to a section TESTS::
• pep 8 conventions (spacing =, etc.)
• f-vector -> f-vector . (add r before the docstring)
• make the AssertionError messages consistent with the input names, to help the user.
• separated the AssertionError about the compactness of self and `other``
• Add a comment about the prior check on the number of vertices and facets (did you make some tests to see whether this improves the speed on some examples?) It would be nice to have it here.

---

New commits:

ca97480

pep8 errors fixed

---

New commits:

ca97480

pep8 errors fixed

[mo271]

comment:6

Two explanations for speed:

To see, that the check before building the bipartite graph is necessary, we do some timing.
When we don't check the number of vertices facets, we get:

sage: C=polytopes.hypercube(14)
sage: D = polytopes.hypercube(15)
sage: time C.is_combinatorially_isomorphic(D)
CPU times: user 5.4 s, sys: 80 ms, total: 5.48 s
Wall time: 5.43 s
False

otherwise:

sage: C=polytopes.hypercube(14)
Dsage: D=polytopes.hypercube(15)
sage: time C.is_combinatorially_isomorphic(D)
CPU times: user 20 ms, sys: 32 ms, total: 52 ms
Wall time: 38.6 ms
False

The following tests shows, that the bipartite_graph is much faster then face_lattice algorithm. For the 7-cube it is more than 1000 times faster on my machine

sage: time C.is_combinatorially_isomorphic(C, algo='face_lattice')
CPU times: user 28.5 s, sys: 64 ms, total: 28.6 s
Wall time: 28.6 s
True
sage: time C.is_combinatorially_isomorphic(C, algo='bipartite_graph')
CPU times: user 24 ms, sys: 0 ns, total: 24 ms
Wall time: 23.6 ms
True

}}}

[sagetrac-git]

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

03dbd96

better assertins, improved docstrings

[sagetrac-git]

Changed commit from ca97480 to 03dbd96

[mo271]

comment:8

Thanks for the remarks, JP!
I have implemented all of them..

[sagetrac-git]

Changed commit from 03dbd96 to 0a29d25

[sagetrac-git]

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

5a2307d	reference added
0a29d25	whitespace

[mo271]

comment:10

added a reference

[mo271]

Author: Moritz Firsching

[jplab]

Reviewer: Jean-Philippe Labbé

[jplab]

comment:13

There are still some things to correct:

• algo to algorithm: it is better to have a complete keyword.
• sixgon -> hexagon
• intersected its... should be intersected with its reflection through the origin.
• isomorpic to -> isomorphic to the
• but different combinatorial types

The reference did not seem to work, but maybe that may be because my doc is broken. The rest of the doc seems to be okay.

[sagetrac-git]

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

f0ec516

little improvements, change 'algo' to 'algorithm'

[sagetrac-git]

Changed commit from 0a29d25 to f0ec516

[mo271]

comment:15

Merci JP, hopefully I got everything this time.

[sagetrac-git]

Changed commit from f0ec516 to 42d5205

[sagetrac-git]

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

42d5205

deleted a superflous line

[jplab]

comment:17

Hi Moritz,

Thanks for correcting the typos. The last change should not change the result of the last bot check. The ticket now looks good to go.

[vbraun]

Changed branch from u/moritz/is_combinatorial_isomorphic to 42d5205