#20751 closed enhancement (fixed)
Check easy invariants first for simplicial complex isomorphism
Reported by:  Travis Scrimshaw  Owned by:  Travis Scrimshaw 

Priority:  major  Milestone:  sage7.3 
Component:  algebraic topology  Keywords:  days74 
Cc:  John Palmieri, Jeremy L Martin  Merged in:  
Authors:  Travis Scrimshaw  Reviewers:  John Palmieri 
Report Upstream:  N/A  Work issues:  
Branch:  fbe4c3d (Commits, GitHub, GitLab)  Commit:  
Dependencies:  #20720  Stopgaps: 
Description (last modified by )
In order to more quickly check if two simplicial complexes are not isomorphic, we should check that their (ordered) facet dimension sequences agree.
We also check that edge labels are respected for the isomorphism, so isomorphisms of the fake degree vertex is not part of the isomorphism.
Change History (13)
comment:1 Changed 6 years ago by
Branch:  → public/simplicial_complex/check_easy_invariants20751 

Commit:  → 00c48e8de85d04e6001b739c6341cf5eb10341fe 
Dependencies:  → #20720 
Status:  new → needs_review 
comment:2 Changed 6 years ago by
Commit:  00c48e8de85d04e6001b739c6341cf5eb10341fe → 0af2d7ff13b3b8aea808f64810f73d1abd1cd2b7 

Branch pushed to git repo; I updated commit sha1. New commits:
0af2d7f  Added check against the facet dimension sequence.

comment:3 Changed 6 years ago by
Commit:  0af2d7ff13b3b8aea808f64810f73d1abd1cd2b7 → 69709a2e19a2cc6cd9633e31850dc0a38d7a5c24 

Branch pushed to git repo; I updated commit sha1. New commits:
69709a2  Make sure edge labels are respected

comment:4 Changed 6 years ago by
Commit:  69709a2e19a2cc6cd9633e31850dc0a38d7a5c24 → fbe4c3df5d54c56812bb09b01f76826b6d7a7226 

Branch pushed to git repo; I updated commit sha1. New commits:
fbe4c3d  Some doc tweaks reflecting then new behavior.

comment:5 Changed 6 years ago by
Description:  modified (diff) 

comment:6 Changed 6 years ago by
I think the initial checks can slow things down. Actually, if two complexes are not isomorphic for "obvious" reasons, it is now much faster (by a factor of 40 on my machine) to check that they are not, but if they are actually isomorphic, it is slower (by a factor of 2) to check that. For these timings, I used the complexes Z1
, Z2
, Z3
from the doctests, and ran
%timeit Z1.is_isomorphic(Z2) # True %timeit Z1.is_isomorphic(Z3) # False
comment:7 Changed 6 years ago by
It is not the initial checks that are slowing it down, it is the additional check(s) of edge labels for the graph isomorphism. The additional checks are very small (< 1%) in comparison to the isomorphism check (both with and without edge label checks), which you can see via
%lprun f X.is_isomorphic X.is_isomorphic(X)
However, Jeremy found it necessary to check the edge labels, at least when we want the certificate. Yet we don't have an example where there is not an isomorphism but the graphs are isomorphic without preserving edge labels. So it might be feasible that we don't need to check the edge labels in that case...
comment:8 Changed 6 years ago by
Reviewers:  → John Palmieri 

Status:  needs_review → positive_review 
comment:9 Changed 6 years ago by
Branch:  public/simplicial_complex/check_easy_invariants20751 → fbe4c3df5d54c56812bb09b01f76826b6d7a7226 

Resolution:  → fixed 
Status:  positive_review → closed 
comment:10 Changed 4 years ago by
Commit:  fbe4c3df5d54c56812bb09b01f76826b6d7a7226 

Exactly what is this doctest supposed to test?
We check that :trac:`20751` is fixed:: sage: C1 = SimplicialComplex([[1,2,3], [1,2,4], [1,3,4]]) sage: C2 = SimplicialComplex([['j','k','l'], ['j','l','m'], ['j','k','m']]) sage: C1.is_isomorphic(C2, certificate=True) (True, {1: 'j', 2: 'k', 3: 'l', 4: 'm'})
I am asking because the output is not unique (one can exchange vertices 2, 3 and 4).
comment:12 Changed 4 years ago by
I believe the fake_vertex
was getting added to the certificate in that test before this ticket.
comment:13 Changed 4 years ago by
Thanks for the info. So it shouldn't be a problem to replace that test with a different one.
New commits:
Having vertices() return a tuple instead of a Simplex.
Fixing a doctest in combinat/cluster_complex.py.
trac 20720: referee changes