Opened 2 years ago
Closed 2 years ago
#27067 closed defect (fixed)
py3: Simplicial complexes: fix is_isomorphic
Reported by:  jhpalmieri  Owned by:  

Priority:  minor  Milestone:  sage8.7 
Component:  python3  Keywords:  python3, simplicial complexes 
Cc:  Merged in:  
Authors:  John Palmieri  Reviewers:  Darij Grinberg 
Report Upstream:  N/A  Work issues:  
Branch:  af9e661 (Commits, GitHub, GitLab)  Commit:  af9e661f6fb9bad1263701f5bedaafa6d7e9f396 
Dependencies:  #26966, #27027  Stopgaps: 
Description
The method is_isomorphic
for simplicial complexes doesn't work with Python 3 for several reasons. The method constructs graphs associated to self
and other
and then tests whether they are isomorphic, preserving edge labels.
 Some of the edges have labels and some don't, and this is not handled gracefully, so we give all edges labels.
 The vertices and/or facets in the complexes can't be sorted in Python 3, so we translate them all to Python
int
s, sort those, and then translate back if we need to.
Change History (18)
comment:1 Changed 2 years ago by
 Branch set to u/jhpalmieri/simplicialcomplexgraphs
comment:2 Changed 2 years ago by
 Commit set to 17cee8c1ef3b7d5d7ba858591f22d9d26458b51f
 Status changed from new to needs_review
comment:3 Changed 2 years ago by
 Commit changed from 17cee8c1ef3b7d5d7ba858591f22d9d26458b51f to af9e661f6fb9bad1263701f5bedaafa6d7e9f396
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
af9e661  trac 27067: fix the simplicial complex method is_isomorphic to work

comment:4 Changed 2 years ago by
 Status changed from needs_review to needs_work
two failing doctests, see patchbot
Maybe try to make them more robust ?
comment:5 Changed 2 years ago by
 Status changed from needs_work to needs_review
That test is fixed by #27027, one of the dependencies. Let's wait until it's merged and then try this again.
comment:6 Changed 2 years ago by
comment:7 Changed 2 years ago by
Okay, please try this again now (you probably have to rebase onto 8.7.beta2).
comment:8 Changed 2 years ago by
The code LGTM, but please add a doctest showing that the two possible simplicial complexes on a 1element set (one consisting of just the empty set, and another that is the whole powerset) are not isomorphic  this is a bit of an edge case for the implementation.
comment:9 Changed 2 years ago by
I'm not sure I understand. Every vertex in a simplicial set must be in a facet, or to put it another way, the vertices in a simplicial set are formed by taking the union of the facets. (I'm talking about how things are implemented in Sage.) So if you have a vertex, you can't have the empty simplicial set. I can add this:
sage: S = SimplicialComplex() sage: T = SimplicialComplex([0]) sage: S.is_isomorphic(T) False
and/or this:
sage: T.remove_face([0]) sage: S.is_isomorphic(T) True
comment:10 Changed 2 years ago by
Does Sage really forbid ghost vertices? If so, then it's a nonissue, though it's a bad decision if you ask me.
comment:11 Changed 2 years ago by
And then the doc here:
This module implements the basic structure of finite simplicial complexes. Given a set `V` of "vertices", a simplicial complex on `V` is a collection `K` of subsets of `V` satisfying the condition that if `S` is one of the subsets in `K`, then so is every subset of `S`. The subsets `S` are called the 'simplices' of `K`.
is wrong, as it says nothing about ghost vertices being forbidden.
comment:12 Changed 2 years ago by
You're right that the documentation is outdated. I'm curious about "ghost vertices". For example, why should the empty simplicial complex on vertices {1,2} be considered different from the empty simplicial complex on vertices {4,5,6,7}?
comment:13 Changed 2 years ago by
If you don't keep the ghost vertices around, then the link of a vertex of a simplicial complex may lose vertices. Somehow I doubt this is a good thing. Then again I haven't done much with simplicial complexes, so I don't know what is actually good in practice.
comment:14 Changed 2 years ago by
I don't know of any computational reason, in particular any reason within Sage, why it should matter if link(sigma) and the ambient simplicial complex should have the same or different vertex sets.
comment:15 Changed 2 years ago by
OK, then this should be reflected in the doc.
comment:16 Changed 2 years ago by
See #27211 for the documentation change.
comment:17 Changed 2 years ago by
 Keywords python3 simplicial complexes added
 Reviewers set to Darij Grinberg
 Status changed from needs_review to positive_review
comment:18 Changed 2 years ago by
 Branch changed from u/jhpalmieri/simplicialcomplexgraphs to af9e661f6fb9bad1263701f5bedaafa6d7e9f396
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
trac 26966: simplicial complexes: do not publicly sort vertices any more.
trac 26966: Remove vertex_set. Use dict comprehension.
trac 26966: always sort vertices using key=str
trac 26966: do not sort vertices. Allow the user to specify sort_facets,
typo
trac 26966: minor code cleanup
trac 26067: fix the simplicial complex method is_isomorphic to work