Opened 5 years ago
Closed 5 years ago
#22500 closed enhancement (fixed)
Add .is_combinatorially_isomorphic() method to polyhedra
Reported by:  jipilab  Owned by:  

Priority:  major  Milestone:  sage7.6 
Component:  geometry  Keywords:  polytope, geometry, days84 
Cc:  moritz, mkoeppe, vdelecroix, tmonteil, chapoton  Merged in:  
Authors:  Moritz Firsching  Reviewers:  JeanPhilippe Labbé 
Report Upstream:  N/A  Work issues:  
Branch:  42d5205 (Commits, GitHub, GitLab)  Commit:  42d520529e582b4ecdb0a27d3644a1d49f7f7b31 
Dependencies:  Stopgaps: 
Description (last modified by )
Two polyhedra are combinatorially isomorphic if their face lattices are isomorphic as posets.
The test for combinatorial isomorphism should test the isomorphism of the vertexfacet adjacency graph of both polyhedra.
Change History (18)
comment:1 Changed 5 years ago by
 Description modified (diff)
comment:2 Changed 5 years ago by
 Branch set to u/moritz/is_combinatorial_isomorphic
comment:3 Changed 5 years ago by
 Commit set to 508bc6be8582cd08da99074fcf7119ef90c793ae
comment:4 Changed 5 years ago by
 Commit changed from 508bc6be8582cd08da99074fcf7119ef90c793ae to ca97480c2cbb8eb4455336bdbce86455f90445bc
Branch pushed to git repo; I updated commit sha1. New commits:
ca97480  pep8 errors fixed

comment:5 Changed 5 years ago by
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 beintersected 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.)  fvector >
f
vector . (addr
before the docstring)  make the
AssertionError
messages consistent with the input names, to help the user.  separated the
AssertionError
about the compactness ofself
andother
`  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

comment:6 Changed 5 years ago by
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 7cube 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
}}}
comment:7 Changed 5 years ago by
 Commit changed from ca97480c2cbb8eb4455336bdbce86455f90445bc to 03dbd96a6431214c68df02beeec0ca3b0e3d967f
Branch pushed to git repo; I updated commit sha1. New commits:
03dbd96  better assertins, improved docstrings

comment:8 Changed 5 years ago by
Thanks for the remarks, JP! I have implemented all of them..
comment:9 Changed 5 years ago by
 Commit changed from 03dbd96a6431214c68df02beeec0ca3b0e3d967f to 0a29d259a6d815c3a2a9d7ad9faf718598072ea3
comment:11 Changed 5 years ago by
comment:12 Changed 5 years ago by
 Reviewers set to JeanPhilippe Labbé
comment:13 Changed 5 years ago by
 Status changed from needs_review to needs_work
There are still some things to correct:
algo
toalgorithm
: it is better to have a complete keyword. sixgon > hexagon
intersected its...
should beintersected 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.
comment:14 Changed 5 years ago by
 Commit changed from 0a29d259a6d815c3a2a9d7ad9faf718598072ea3 to f0ec516d8d4557c4f507e9c862a8ccbb621b9ea5
Branch pushed to git repo; I updated commit sha1. New commits:
f0ec516  little improvements, change 'algo' to 'algorithm'

comment:15 Changed 5 years ago by
 Status changed from needs_work to needs_review
Merci JP, hopefully I got everything this time.
comment:16 Changed 5 years ago by
 Commit changed from f0ec516d8d4557c4f507e9c862a8ccbb621b9ea5 to 42d520529e582b4ecdb0a27d3644a1d49f7f7b31
Branch pushed to git repo; I updated commit sha1. New commits:
42d5205  deleted a superflous line

comment:17 Changed 5 years ago by
 Status changed from needs_review to positive_review
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.
comment:18 Changed 5 years ago by
 Branch changed from u/moritz/is_combinatorial_isomorphic to 42d520529e582b4ecdb0a27d3644a1d49f7f7b31
 Resolution set to fixed
 Status changed from positive_review to closed
pushed first version, which handles bounded polyhedra
New commits:
initial version