Opened 4 years ago
Closed 4 years ago
#27067 closed defect (fixed)
py3: Simplicial complexes: fix is_isomorphic
Reported by:  John Palmieri  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 4 years ago by
Branch:  → u/jhpalmieri/simplicialcomplexgraphs 

comment:2 Changed 4 years ago by
Commit:  → 17cee8c1ef3b7d5d7ba858591f22d9d26458b51f 

Status:  new → needs_review 
comment:3 Changed 4 years ago by
Commit:  17cee8c1ef3b7d5d7ba858591f22d9d26458b51f → 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 4 years ago by
Status:  needs_review → needs_work 

two failing doctests, see patchbot
Maybe try to make them more robust ?
comment:5 Changed 4 years ago by
Status:  needs_work → 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 4 years ago by
comment:7 Changed 4 years ago by
Okay, please try this again now (you probably have to rebase onto 8.7.beta2).
comment:8 Changed 4 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 4 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 4 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 4 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 4 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 4 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 4 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:17 Changed 4 years ago by
Keywords:  python3 simplicial complexes added 

Reviewers:  → Darij Grinberg 
Status:  needs_review → positive_review 
comment:18 Changed 4 years ago by
Branch:  u/jhpalmieri/simplicialcomplexgraphs → af9e661f6fb9bad1263701f5bedaafa6d7e9f396 

Resolution:  → fixed 
Status:  positive_review → 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