jhpalmieri commented 6 years ago

This ticket includes changes for cell complexes and in general files in src/sage/homology for Python 3 compatibility. There are several types of changes:

make sure data are sorted consistently, when they need to be sorted, and in particular for homology calculations. In particular, GenericCellComplex, the class from which the other main ones in this directory inherit, now has a method _n_cells_sorted which does what its name says. This way the sorting is centralized, so we don't have to do it separately in each file and perhaps do it inconsistently between one file and another.
make sure data are sorted in doctests, so that doctests are consistent between Python 2 and Python 3.
bug fixes: the first type of changes led to the discovery of a few bugs. Python 3 doctests kept insisting that certain answers were wrong, and I eventually realized that they were indeed wrong. Some of this was due to sorting inconsistencies, and there was at least one other – the map induced in cohomology by a map of simplicial complexes should be dual to the map induced in homology (as long as we have field coefficients), and this was not the case, because the cohomology situation was just wrong in the code.

Depends on #25932

CC: @fchapoton @tscrim

Component: python3

Author: John Palmieri

Branch/Commit: ff52d03

Reviewer: Travis Scrimshaw

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

jhpalmieri commented 6 years ago

Description changed:

--- 
+++ 
@@ -1 +1,8 @@
-This ticket includes changes for cell complexes and in general files in `src/sage/homology` for Python 3 compatibility.
+This ticket includes changes for cell complexes and in general files in `src/sage/homology` for Python 3 compatibility. There are several types of changes:
+
+- make sure data are sorted consistently, when they need to be sorted, and in particular for homology calculations. In particular, `GenericCellComplex`, the class from which the other main ones in this directory inherit, now has a method `_n_cells_sorted` which does what its name says. This way the sorting is centralized, so we don't have to do it separately in each file and perhaps do it inconsistently between one file and another.
+
+- make sure data are sorted in doctests, so that doctests are consistent between Python 2 and Python 3.
+
+- bug fixes: the first type of changes led to the discovery of a few bugs. Python 3 doctests kept insisting that certain answers were wrong, and I eventually realized that they were indeed wrong. Some of this was due to sorting inconsistencies, and there was at least one other – the map induced in cohomology by a map of simplicial complexes should be dual to the map induced in homology (as long as we have field coefficients), and this was not the case, because the cohomology situation was just wrong in the code.
+

jhpalmieri commented 6 years ago

comment:1

When I run doctests with Python 2, of course everything passes. With Python 3, there are still failures, but they are beyond the scope of this ticket. The remaining failures:

----------------------------------------------------------------------
sage -t --warn-long 55.6 src/sage/homology/simplicial_complex.py  # 27 doctests failed
sage -t --warn-long 55.6 src/sage/homology/examples.py  # 10 doctests failed
----------------------------------------------------------------------

This is contrast to Sage-8.3.rc2 + #25929, built with Python 3:

----------------------------------------------------------------------
sage -t --warn-long 56.0 src/sage/homology/simplicial_complex.py  # 43 doctests failed
sage -t --warn-long 56.0 src/sage/homology/cubical_complex.py  # 4 doctests failed
sage -t --warn-long 56.0 src/sage/homology/simplicial_set_morphism.py  # 33 doctests failed
sage -t --warn-long 56.0 src/sage/homology/simplicial_set_examples.py  # 12 doctests failed
sage -t --warn-long 56.0 src/sage/homology/examples.py  # 13 doctests failed
sage -t --warn-long 56.0 src/sage/homology/simplicial_set_constructions.py  # 96 doctests failed
sage -t --warn-long 56.0 src/sage/homology/homology_morphism.py  # 5 doctests failed
sage -t --warn-long 56.0 src/sage/homology/chain_complex.py  # 7 doctests failed
sage -t --warn-long 56.0 src/sage/homology/simplicial_set.py  # 68 doctests failed
sage -t --warn-long 56.0 src/sage/homology/simplicial_complex_morphism.py  # 10 doctests failed
sage -t --warn-long 56.0 src/sage/homology/chains.py  # 4 doctests failed
sage -t --warn-long 56.0 src/sage/homology/chain_complex_morphism.py  # 3 doctests failed
sage -t --warn-long 56.0 src/sage/homology/koszul_complex.py  # 1 doctest failed
sage -t --warn-long 56.0 src/sage/homology/chain_homotopy.py  # 1 doctest failed
sage -t --warn-long 56.0 src/sage/homology/simplicial_set_catalog.py  # 2 doctests failed
sage -t --warn-long 56.0 src/sage/homology/simplicial_complex_homset.py  # 2 doctests failed
sage -t --warn-long 56.0 src/sage/homology/homology_vector_space_with_basis.py  # 32 doctests failed
----------------------------------------------------------------------

The remaining failures are of three types:

inconsistencies in print representations for some rings, and I think Python 3 is better than Python 2 here. For example

File "src/sage/homology/simplicial_complex.py", line 86, in sage.homology.simplicial_complex
Failed example:
    X.stanley_reisner_ring()
Expected:
    Quotient of Multivariate Polynomial Ring in x0, x1, x2, x3 over Integer Ring by the ideal (x1*x3, x0*x2)
Got:
    Quotient of Multivariate Polynomial Ring in x0, x1, x2, x3 over Integer Ring by the ideal (x0*x2, x1*x3)

and

**********************************************************************
File "src/sage/homology/simplicial_complex.py", line 3258, in sage.homology.simplicial_complex.SimplicialComplex._stanley_reisner_base_ring
Failed example:
    Y._stanley_reisner_base_ring(base_ring=QQ)
Expected:
    Multivariate Polynomial Ring in a, c, b over Rational Field
Got:
    Multivariate Polynomial Ring in a, b, c over Rational Field

problems with file access related to Sage's parallel processing, which is used by the method is_cohen_macaulay:

File "src/sage/homology/simplicial_complex.py", line 2789, in sage.homology.simplicial_complex.SimplicialComplex.is_cohen_macaulay
Failed example:
    S.is_cohen_macaulay(ncpus=3)
Exception raised:
    Traceback (most recent call last):
      File "/Users/jpalmier/Desktop/Sage/sage_builds/PYTHON3/sage-8.3.rc1/local/lib/python3.6/site-packages/sage/doctest/forker.py", line 573, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/Users/jpalmier/Desktop/Sage/sage_builds/PYTHON3/sage-8.3.rc1/local/lib/python3.6/site-packages/sage/doctest/forker.py", line 983, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.homology.simplicial_complex.SimplicialComplex.is_cohen_macaulay[1]>", line 1, in <module>
        S.is_cohen_macaulay(ncpus=Integer(3))
      File "/Users/jpalmier/Desktop/Sage/sage_builds/PYTHON3/sage-8.3.rc1/local/lib/python3.6/site-packages/sage/homology/simplicial_complex.py", line 2833, in is_cohen_macaulay
        return all( answer[1] for answer in all_homologies_in_list_vanish(facs_divided) )
      File "/Users/jpalmier/Desktop/Sage/sage_builds/PYTHON3/sage-8.3.rc1/local/lib/python3.6/site-packages/sage/homology/simplicial_complex.py", line 2833, in <genexpr>
        return all( answer[1] for answer in all_homologies_in_list_vanish(facs_divided) )
      File "/Users/jpalmier/Desktop/Sage/sage_builds/PYTHON3/sage-8.3.rc1/local/lib/python3.6/site-packages/sage/parallel/use_fork.py", line 211, in __call__
        data = file.read()
      File "/Users/jpalmier/Desktop/Sage/sage_builds/PYTHON3/sage-8.3.rc1/local/lib/python3.6/codecs.py", line 321, in decode
        (result, consumed) = self._buffer_decode(data, self.errors, final)
    UnicodeDecodeError: 'utf-8' codec can't decode byte 0x80 in position 0: invalid start byte

Sorting issues in graph theory:

**********************************************************************
File "src/sage/homology/simplicial_complex.py", line 3871, in sage.homology.simplicial_complex.SimplicialComplex.fundamental_group
Failed example:
    S1.wedge(S1).fundamental_group()
Exception raised:
    Traceback (most recent call last):
      File "/Users/jpalmier/Desktop/Sage/sage_builds/PYTHON3/sage-8.3.rc1/local/lib/python3.6/site-packages/sage/doctest/forker.py", line 573, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/Users/jpalmier/Desktop/Sage/sage_builds/PYTHON3/sage-8.3.rc1/local/lib/python3.6/site-packages/sage/doctest/forker.py", line 983, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.homology.simplicial_complex.SimplicialComplex.fundamental_group[13]>", line 1, in <module>
        S1.wedge(S1).fundamental_group()
      File "/Users/jpalmier/Desktop/Sage/sage_builds/PYTHON3/sage-8.3.rc1/local/lib/python3.6/site-packages/sage/homology/simplicial_complex.py", line 3878, in fundamental_group
        if not self.is_connected():
      File "/Users/jpalmier/Desktop/Sage/sage_builds/PYTHON3/sage-8.3.rc1/local/lib/python3.6/site-packages/sage/homology/cell_complex.py", line 1127, in is_connected
        return self.graph().is_connected()
      File "/Users/jpalmier/Desktop/Sage/sage_builds/PYTHON3/sage-8.3.rc1/local/lib/python3.6/site-packages/sage/homology/simplicial_complex.py", line 3475, in graph
        v = min(e)
    TypeError: '<' not supported between instances of 'str' and 'int'

and

File "src/sage/homology/simplicial_complex.py", line 3928, in sage.homology.simplicial_complex.SimplicialComplex.is_isomorphic
Failed example:
    Z1.is_isomorphic(Z2, certificate=True)
Exception raised:
    Traceback (most recent call last):
      File "/Users/jpalmier/Desktop/Sage/sage_builds/PYTHON3/sage-8.3.rc1/local/lib/python3.6/site-packages/sage/doctest/forker.py", line 573, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/Users/jpalmier/Desktop/Sage/sage_builds/PYTHON3/sage-8.3.rc1/local/lib/python3.6/site-packages/sage/doctest/forker.py", line 983, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.homology.simplicial_complex.SimplicialComplex.is_isomorphic[4]>", line 1, in <module>
        Z1.is_isomorphic(Z2, certificate=True)
      File "/Users/jpalmier/Desktop/Sage/sage_builds/PYTHON3/sage-8.3.rc1/local/lib/python3.6/site-packages/sage/misc/decorators.py", line 725, in wrapper
        return func(*args, **kwds)
      File "/Users/jpalmier/Desktop/Sage/sage_builds/PYTHON3/sage-8.3.rc1/local/lib/python3.6/site-packages/sage/homology/simplicial_complex.py", line 3964, in is_isomorphic
        isisom, tr = g1.is_isomorphic(g2, edge_labels=True, certificate=True)
      File "/Users/jpalmier/Desktop/Sage/sage_builds/PYTHON3/sage-8.3.rc1/local/lib/python3.6/site-packages/sage/graphs/generic_graph.py", line 21362, in is_isomorphic
        if edge_labels and sorted(self.edge_labels()) != sorted(other.edge_labels()):
      File "/Users/jpalmier/Desktop/Sage/sage_builds/PYTHON3/sage-8.3.rc1/local/lib/python3.6/site-packages/sage/graphs/generic_graph.py", line 10996, in edge_labels
        return [l for _, _, l in self.edge_iterator()]
      File "/Users/jpalmier/Desktop/Sage/sage_builds/PYTHON3/sage-8.3.rc1/local/lib/python3.6/site-packages/sage/graphs/generic_graph.py", line 10996, in <listcomp>
        return [l for _, _, l in self.edge_iterator()]
      File "sage/graphs/base/sparse_graph.pyx", line 1727, in iterator_edges (build/cythonized/sage/graphs/base/sparse_graph.c:20815)
        yield (v, u, l) if v<=u else (u, v, l)
    TypeError: '<=' not supported between instances of 'int' and 'str'

jhpalmieri commented 6 years ago

Branch: u/jhpalmieri/cell-complex-fixes-py3

jhpalmieri commented 6 years ago

Commit: 91db108

jhpalmieri commented 6 years ago

comment:3

Included in the first type of fixes: when order matters, don't iterate over dictionaries. For example, one change in algebraic_topological_model.py is

diff --git a/src/sage/homology/algebraic_topological_model.py b/src/sage/homology/algebraic_topological_model.py
index eeab74e7c9..97452fabc1 100644
--- a/src/sage/homology/algebraic_topological_model.py
+++ b/src/sage/homology/algebraic_topological_model.py
@@ -251,7 +251,8 @@ def algebraic_topological_model(K, base_ring=None):
             else:
                 # Take any u in gens so that lambda_i = <u, pi(bdry(c_bar))> != 0.
                 # u_idx will be the index of the corresponding cell.
-                for (u_idx, lambda_i) in iteritems(pi_bdry_c_bar):
+                for u_idx in pi_bdry_c_bar.nonzero_positions():
+                    lambda_i = pi_bdry_c_bar[u_idx]
                     # Now find the actual cell.
                     u = old_cells[u_idx]
                     if u in gens[dim-1]:

In this case, pi_bdry_c_bar is a vector, and iteritems returns pairs (index, entry). To make sure the loop is done in consistent order, instead iterate over nonzero_positions. Changing the sorting from the previous version leads to some minor differences in output, like

diff --git a/src/sage/homology/homology_morphism.py b/src/sage/homology/homology_morphism.py
index 8df6ecef5c..149fee910d 100644
--- a/src/sage/homology/homology_morphism.py
+++ b/src/sage/homology/homology_morphism.py
@@ -78,7 +78,7 @@ class InducedHomologyMorphism(Morphism):
         sage: T = simplicial_complexes.Torus()
         sage: y = T.homology_with_basis(QQ).basis()[(1,1)]
         sage: y.to_cycle()
-        (0, 2) - (0, 5) + (2, 5)
+        (0, 5) - (0, 6) + (5, 6)

     Since `(0,2) - (0,5) + (2,5)` is a cycle representing a homology
     class in the torus, we can define a map `S^1 \to T` inducing an

New commits:

`bd76f58`	`trac 25932: fix a few Python 3 issues in simplical_complex.py`
`1f5f05f`	`trac 25932: some clean up`
`16e3aa2`	`trac 25932: one more fix so that sorting works with Python 3`
`dc6b7c9`	`trac 25932: if sort_facets is True, sorting should always succeed,`
`91db108`	`trac 25986: Python 3 fixes for cell complexes: make sure sorting is done`

jhpalmieri commented 6 years ago

comment:4

I overstated things in comment:1. To get the situation down to the few failing doctests listed there, I need to apply #25932, #25929, #25978, #25935, #25940, #25986 (= this ticket), and the change (inspired by #24551)

diff --git a/src/sage/groups/perm_gps/permgroup_named.py b/src/sage/groups/perm_gps/permgroup_named.py
index da1774e96c..54fa034b4a 100644
--- a/src/sage/groups/perm_gps/permgroup_named.py
+++ b/src/sage/groups/perm_gps/permgroup_named.py
@@ -149,6 +149,8 @@ class PermutationGroup_unique(CachedRepresentation, PermutationGroup_generic):
         """
         return super(CachedRepresentation, self).__eq__(other)

+    __hash__ = CachedRepresentation.__hash__
+

 class PermutationGroup_symalt(PermutationGroup_unique):
     """

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

Changed commit from 91db108 to 3974bbb

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

3974bbb trac 25986: a few more Python 3 fixes for simplicial_complex.py

jhpalmieri commented 6 years ago

comment:6

A few more fixes.

jhpalmieri commented 6 years ago

comment:7

25992 fixes the problem with parallel processing, and hence with `is_cohen_macaulay`.

tscrim commented 6 years ago

comment:8

I think it redundant to do

sage: test # random
sage: sorted(test)

Just do the test with sorted output and if you feel it is necessary (I don't), you can explain with a comment why we are sorting things.

I am not sure I agree with deprecating n_faces and not just making it an alias of n_cells. At least, when I think of simplicial complexes, I would call them faces before cells.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

Changed commit from 3974bbb to ff52d03

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

ff52d03 trac 25986: do not deprecate n_faces. Do not include some doctests

jhpalmieri commented 6 years ago

comment:10

Replying to @tscrim:

I think it redundant to do
sage: test # random
sage: sorted(test)
Just do the test with sorted output and if you feel it is necessary (I don't), you can explain with a comment why we are sorting things.

That's fine with me.

I am not sure I agree with deprecating n_faces and not just making it an alias of n_cells. At least, when I think of simplicial complexes, I would call them faces before cells.

I don't feel strongly about it. I thought that a general Python philosophy was to not have multiple ways of doing exactly the same thing. The previous docstring for n_faces could be interpreted as a weak deprecation ("This method is not used elsewhere in Sage."), but I don't mind leaving it as an alias.

tscrim commented 6 years ago

comment:11

I think having n_faces is useful from a user-interface POV.

Thank you. LGTM.

tscrim commented 6 years ago

Reviewer: Travis Scrimshaw

vbraun commented 6 years ago

Changed branch from u/jhpalmieri/cell-complex-fixes-py3 to ff52d03

sagemath / sage

Changes to simplicial complexes, cell complexes for Python 3 compatibility #25986

25992 fixes the problem with parallel processing, and hence with `is_cohen_macaulay`.

sagemath / sage

Changes to simplicial complexes, cell complexes for Python 3 compatibility #25986

25992 fixes the problem with parallel processing, and hence with is_cohen_macaulay.

25992 fixes the problem with parallel processing, and hence with `is_cohen_macaulay`.