py3: Simplicial complexes: fix is_isomorphic

[jhpalmieri]

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.

Depends on #26966
Depends on #27027

Component: python3

Keywords: simplicial complexes

Author: John Palmieri

Branch/Commit: af9e661

Reviewer: Darij Grinberg

Issue created by migration from https://trac.sagemath.org/ticket/27067

[jhpalmieri]

Branch: u/jhpalmieri/simplicial-complex-graphs

[jhpalmieri]

New commits:

29ade7e	trac 26966: simplicial complexes: do not publicly sort vertices any more.
b325350	trac 26966: Remove vertex_set. Use dict comprehension.
e79fd39	trac 26966: always sort vertices using key=str
f4a672c	trac 26966: do not sort vertices. Allow the user to specify sort_facets,
41eeaf5	typo
95f6026	trac 26966: minor code cleanup
17cee8c	trac 26067: fix the simplicial complex method is_isomorphic to work

[jhpalmieri]

Commit: 17cee8c

[sagetrac-git]

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

[sagetrac-git]

Changed commit from 17cee8c to af9e661

[fchapoton]

comment:4

two failing doctests, see patchbot

Maybe try to make them more robust ?

[jhpalmieri]

comment:5

That test is fixed by #27027, one of the dependencies. Let's wait until it's merged and then try this again.

[jhpalmieri]

comment:6

(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.)

[jhpalmieri]

comment:7

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

[darijgr]

comment:8

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.

[jhpalmieri]

comment:9

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

[darijgr]

comment:10

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

[darijgr]

comment:11

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.

[jhpalmieri]

comment:12

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}?

[darijgr]

comment:13

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.

[jhpalmieri]

comment:14

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.

[darijgr]

comment:15

OK, then this should be reflected in the doc.

[jhpalmieri]

comment:16

See #27211 for the documentation change.

[darijgr]

Reviewer: Darij Grinberg

[darijgr]

Changed keywords from none to simplicial complexes

[vbraun]

Changed branch from u/jhpalmieri/simplicial-complex-graphs to af9e661