Opened 2 months ago

Closed 6 weeks ago

#27067 closed defect (fixed)

py3: Simplicial complexes: fix is_isomorphic

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

Change History (18)

comment:1 Changed 2 months ago by jhpalmieri

  • Branch set to u/jhpalmieri/simplicial-complex-graphs

comment:2 Changed 2 months ago by jhpalmieri

  • Commit set to 17cee8c1ef3b7d5d7ba858591f22d9d26458b51f
  • Status changed from new to needs_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,
41eeaf5typo
95f6026trac 26966: minor code cleanup
17cee8ctrac 26067: fix the simplicial complex method is_isomorphic to work

comment:3 Changed 2 months ago by git

  • Commit changed from 17cee8c1ef3b7d5d7ba858591f22d9d26458b51f to af9e661f6fb9bad1263701f5bedaafa6d7e9f396

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 2 months ago by chapoton

  • Status changed from needs_review to needs_work

two failing doctests, see patchbot

Maybe try to make them more robust ?

comment:5 Changed 2 months ago by jhpalmieri

  • 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 months ago by jhpalmieri

(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 7 weeks ago by jhpalmieri

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

comment:8 Changed 7 weeks ago by gh-darijgr

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 7 weeks ago by jhpalmieri

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 7 weeks ago by gh-darijgr

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 7 weeks ago by gh-darijgr

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 7 weeks ago by jhpalmieri

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 7 weeks ago by gh-darijgr

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 7 weeks ago by jhpalmieri

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 7 weeks ago by gh-darijgr

OK, then this should be reflected in the doc.

comment:16 Changed 7 weeks ago by jhpalmieri

See #27211 for the documentation change.

comment:17 Changed 6 weeks ago by gh-darijgr

  • Keywords python3 simplicial complexes added
  • Reviewers set to Darij Grinberg
  • Status changed from needs_review to positive_review

comment:18 Changed 6 weeks ago by vbraun

  • Branch changed from u/jhpalmieri/simplicial-complex-graphs to af9e661f6fb9bad1263701f5bedaafa6d7e9f396
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.