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: sage-8.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:

Status badges


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 ints, sort those, and then translate back if we need to.

Change History (18)

comment:1 Changed 4 years ago by John Palmieri

Branch: u/jhpalmieri/simplicial-complex-graphs

comment:2 Changed 4 years ago by John Palmieri

Commit: 17cee8c1ef3b7d5d7ba858591f22d9d26458b51f
Status: newneeds_review

New commits:

29ade7etrac 26966: simplicial complexes: do not publicly sort vertices any more.
b325350trac 26966: Remove vertex_set. Use dict comprehension.
e79fd39trac 26966: always sort vertices using key=str
f4a672ctrac 26966: do not sort vertices. Allow the user to specify sort_facets,
95f6026trac 26966: minor code cleanup
17cee8ctrac 26067: fix the simplicial complex method is_isomorphic to work

comment:3 Changed 4 years ago by git

Commit: 17cee8c1ef3b7d5d7ba858591f22d9d26458b51faf9e661f6fb9bad1263701f5bedaafa6d7e9f396

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

af9e661trac 27067: fix the simplicial complex method is_isomorphic to work

comment:4 Changed 4 years ago by Frédéric Chapoton

Status: needs_reviewneeds_work

two failing doctests, see patchbot

Maybe try to make them more robust ?

comment:5 Changed 4 years ago by John Palmieri

Status: needs_workneeds_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 John Palmieri

(The branch from #26966 is included here because there would be merge conflicts otherwise. I didn't include the one from #27027. I never know the right way to handle dependencies like this.)

comment:7 Changed 4 years ago by John Palmieri

Okay, please try this again now (you probably have to rebase onto 8.7.beta2).

comment:8 Changed 4 years ago by Darij Grinberg

The code LGTM, but please add a doctest showing that the two possible simplicial complexes on a 1-element 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 John Palmieri

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)

and/or this:

sage: T.remove_face([0])
sage: S.is_isomorphic(T)

comment:10 Changed 4 years ago by Darij Grinberg

Does Sage really forbid ghost vertices? If so, then it's a non-issue, though it's a bad decision if you ask me.

comment:11 Changed 4 years ago by Darij Grinberg

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 John Palmieri

You're right that the documentation is out-dated. 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 Darij Grinberg

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 John Palmieri

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 4 years ago by Darij Grinberg

OK, then this should be reflected in the doc.

comment:16 Changed 4 years ago by John Palmieri

See #27211 for the documentation change.

comment:17 Changed 4 years ago by Darij Grinberg

Keywords: python3 simplicial complexes added
Reviewers: Darij Grinberg
Status: needs_reviewpositive_review

comment:18 Changed 4 years ago by Volker Braun

Branch: u/jhpalmieri/simplicial-complex-graphsaf9e661f6fb9bad1263701f5bedaafa6d7e9f396
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.