Opened 4 years ago

Closed 4 years ago

#22500 closed enhancement (fixed)

Add .is_combinatorially_isomorphic() method to polyhedra

Reported by: jipilab Owned by:
Priority: major Milestone: sage-7.6
Component: geometry Keywords: polytope, geometry, days84
Cc: moritz, mkoeppe, vdelecroix, tmonteil, chapoton Merged in:
Authors: Moritz Firsching Reviewers: Jean-Philippe Labbé
Report Upstream: N/A Work issues:
Branch: 42d5205 (Commits, GitHub, GitLab) Commit: 42d520529e582b4ecdb0a27d3644a1d49f7f7b31
Dependencies: Stopgaps:

Status badges

Description (last modified by jipilab)

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.

Change History (18)

comment:1 Changed 4 years ago by jipilab

  • Description modified (diff)

comment:2 Changed 4 years ago by moritz

  • Branch set to u/moritz/is_combinatorial_isomorphic

comment:3 Changed 4 years ago by moritz

  • Commit set to 508bc6be8582cd08da99074fcf7119ef90c793ae

pushed first version, which handles bounded polyhedra


New commits:

508bc6binitial version

comment:4 Changed 4 years ago by git

  • Commit changed from 508bc6be8582cd08da99074fcf7119ef90c793ae to ca97480c2cbb8eb4455336bdbce86455f90445bc

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

ca97480pep8 errors fixed

comment:5 Changed 4 years ago by jipilab

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:

ca97480pep8 errors fixed

New commits:

ca97480pep8 errors fixed

comment:6 Changed 4 years ago by moritz

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

}}}

comment:7 Changed 4 years ago by git

  • Commit changed from ca97480c2cbb8eb4455336bdbce86455f90445bc to 03dbd96a6431214c68df02beeec0ca3b0e3d967f

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

03dbd96better assertins, improved docstrings

comment:8 Changed 4 years ago by moritz

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

comment:9 Changed 4 years ago by git

  • Commit changed from 03dbd96a6431214c68df02beeec0ca3b0e3d967f to 0a29d259a6d815c3a2a9d7ad9faf718598072ea3

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

5a2307dreference added
0a29d25whitespace

comment:10 Changed 4 years ago by moritz

  • Status changed from new to needs_review

added a reference

comment:11 Changed 4 years ago by moritz

  • Authors set to Moritz Firsching

comment:12 Changed 4 years ago by jipilab

  • Reviewers set to Jean-Philippe Labbé

comment:13 Changed 4 years ago by jipilab

  • Status changed from needs_review to needs_work

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.

comment:14 Changed 4 years ago by git

  • Commit changed from 0a29d259a6d815c3a2a9d7ad9faf718598072ea3 to f0ec516d8d4557c4f507e9c862a8ccbb621b9ea5

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

f0ec516little improvements, change 'algo' to 'algorithm'

comment:15 Changed 4 years ago by moritz

  • Status changed from needs_work to needs_review

Merci JP, hopefully I got everything this time.

comment:16 Changed 4 years ago by git

  • Commit changed from f0ec516d8d4557c4f507e9c862a8ccbb621b9ea5 to 42d520529e582b4ecdb0a27d3644a1d49f7f7b31

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

42d5205deleted a superflous line

comment:17 Changed 4 years ago by jipilab

  • 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 4 years ago by vbraun

  • Branch changed from u/moritz/is_combinatorial_isomorphic to 42d520529e582b4ecdb0a27d3644a1d49f7f7b31
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.