Add finite topological spaces

jcuevas-rozo commented 4 years ago

This ticket provides a class for finite topological spaces and methods dealing with properties in general topology. It is expected to create a second ticket to add algebraic topology properties (see ticket #30447).

Principal reference: Algebraic topology of finite topological spaces and applications by Jonathan Barmak.

Depends on #31925

CC: @jhpalmieri

Component: algebraic topology

Keywords: Finite topological spaces

Work Issues: Rework on top of #31925

Author: Julián Cuevas-Rozo

Branch/Commit: u/gh-jcuevas-rozo/add_finite_topological_spaces @ 3c2e0d4

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

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

Changed commit from 8a123d6 to a06a949

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

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

a06a949 Style suggestions added

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

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

481bef5 two pyflakes errors fixed

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

Changed commit from a06a949 to 481bef5

jcuevas-rozo commented 3 years ago

comment:42

I have seen the pyflakes errors here, but I don't know how to fix them, since the undefined names mentioned there depends on the installation of Kenzo (up to I understand)...

jhpalmieri commented 3 years ago

comment:43

Thank you for checking those pyflakes errors. I agree that they don't need to be fixed.

jhpalmieri commented 3 years ago

comment:44

In the example

    sage: T = FiniteSpace([{0, 3}, {1, 3}, {2, 3}, {3}]) ; T
    Finite T0 topological space of 4 points with minimal basis
     {0: {3, 0}, 1: {3, 1}, 2: {3, 2}, 3: {3}}
    sage: T.elements()
    [3, 0, 1, 2]

I would have expected T.elements() to be [0, 1, 2, 3], so I found the topogeneous matrix confusing. Even more with the following, I expect the elements to be sorted the way I enter them:

    sage: T = FiniteSpace([{0, 3}, {1, 3}, {2, 3}, {3}], elements=[0,1,2,3])                  
    sage: T.elements()                                                                        
    [3, 0, 1, 2]

Should they be sorted in some cases? If the sets of elements are likely to be large, I can understand not wanting to sort by default, but if the user supplies a list of elements, shouldn't we use that?

I have no experience with finite topological spaces, so maybe users won't expect this sorting. From the !Python/Sage point of view, the current situation seems odd, though. Looking at the code, is the point to have an upper triangulate topogeneous matrix? If so, please add a comment about this to the documentation, pointing out an example. However, the example constructed from matrix data does not have an upper triangular topogeneous matrix, so maybe I'm confused. Or is it only upper triangular if the space is T0? The comment in the code could be clarified. Is this right:

diff --git a/src/sage/homology/finite_topological_spaces.py b/src/sage/homology/finite_topological_spaces.py
index 80f0b32fd1..ddab80d6f1 100644
--- a/src/sage/homology/finite_topological_spaces.py
+++ b/src/sage/homology/finite_topological_spaces.py
@@ -129,8 +129,19 @@ def FiniteSpace(data, elements=None, is_T0=False):
          {0: {3, 0}, 1: {3, 1}, 2: {3, 2}, 3: {3}}
         sage: type(T)
         <class 'sage.homology.finite_topological_spaces.FiniteTopologicalSpace_T0'>
+
+    Note that the set of elements is sorted in perhaps an unexpected
+    way. This is to ensure that in the case of a T0 space, the
+    topogenous matrix is upper triangular::
+
         sage: T.elements()
         [3, 0, 1, 2]
+        sage: T.topogenous_matrix()
+        [1 1 1 1]
+        [0 1 0 0]
+        [0 0 1 0]
+        [0 0 0 1]
+
         sage: FiniteSpace(({0, 2}, {0, 2}))
         Traceback (most recent call last):
         ...
@@ -226,7 +237,8 @@ def FiniteSpace(data, elements=None, is_T0=False):
                 basis[j] = Uj
             eltos = range(n)

-    # This fixes a topological sort (it guarantees an upper triangular topogenous matrix)
+    # This fixes a topological sort (it guarantees an upper triangular topogenous matrix
+    # in the T0 case)
     eltos = list(eltos)
     sorted_str_eltos = sorted([str(x) for x in eltos])
     eltos.sort(key = lambda x: (len(basis[x]), sorted_str_eltos.index(str(x))))

jhpalmieri commented 3 years ago

comment:45

After installing kenzo 1.1.9 (via make kenzo), I get doctest failures from the optional kenzo doctests. For example:

File "src/sage/homology/finite_topological_spaces.py", line 300, in sage.homology.finite_topological_spaces.RandomFiniteT0Space
Failed example:
    RandomFiniteT0Space(5, 0)                                # optional - kenzo               
Exception raised:
    Traceback (most recent call last):
      File "/Users/palmieri/Desktop/Sage/sage_builds/TESTING/sage-9.3.beta7/local/lib/python3.9/site-packages/sage/doctest/forker.py", line 714, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/Users/palmieri/Desktop/Sage/sage_builds/TESTING/sage-9.3.beta7/local/lib/python3.9/site-packages/sage/doctest/forker.py", line 1133, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.homology.finite_topological_spaces.RandomFiniteT0Space[1]>", line 1, in <module>
        RandomFiniteT0Space(Integer(5), Integer(0))                                # optional - kenzo
      File "/Users/palmieri/Desktop/Sage/sage_builds/TESTING/sage-9.3.beta7/local/lib/python3.9/site-packages/sage/homology/finite_topological_spaces.py", line 327, in RandomFiniteT0Space
        topogenous = kenzo.k2s_binary_matrix_sparse(kenzo_top)
      File "/Users/palmieri/Desktop/Sage/sage_builds/TESTING/sage-9.3.beta7/local/lib/python3.9/site-packages/sage/interfaces/kenzo.py", line 2130, in k2s_binary_matrix_sparse
        data = __vector_to_list__(__matrice_to_lmtrx__(kmatrix)).python()
      File "sage/libs/ecl.pyx", line 854, in sage.libs.ecl.EclObject.__call__ (build/cythonized/sage/libs/ecl.c:8614)
        return ecl_wrap(ecl_safe_apply(self.obj,(<EclObject>lispargs).obj))
      File "sage/libs/ecl.pyx", line 365, in sage.libs.ecl.ecl_safe_apply (build/cythonized/sage/libs/ecl.c:5896)
        raise RuntimeError("ECL says: {}".format(
    RuntimeError: ECL says: The function VECTOR-TO-LIST is undefined.

jhpalmieri commented 3 years ago

comment:46

I also get failures in src/sage/interfaces/kenzo.py when kenzo is installed. Do I need to do more than ./configure --enable-kenzo=yes && make?

tscrim commented 3 years ago

comment:47

All of the interface tests pass for me without this branch, and I am getting similar failures with the branch. These failures are happening on my Ubuntu machine.

jcuevas-rozo commented 3 years ago

comment:48

I apologize for the delay, but I was looking for the answer to the raised questions. By now, this ticket is working by using the following commands in order to load a testing branch of Kenzo:

git clone https://github.com/miguelmarco/kenzo/

cd kenzo

git checkout testing

sage -ecl < compile.lisp

mv kenzo--all-systems.fasb $HOME/sage/local/lib/ecl/kenzo.fas

The changes made in this branch will be added in a future release of Kenzo.

jcuevas-rozo commented 3 years ago

comment:49

Replying to @jhpalmieri:

In the example
    sage: T = FiniteSpace([{0, 3}, {1, 3}, {2, 3}, {3}]) ; T
    Finite T0 topological space of 4 points with minimal basis
     {0: {3, 0}, 1: {3, 1}, 2: {3, 2}, 3: {3}}
    sage: T.elements()
    [3, 0, 1, 2]
I would have expected T.elements() to be [0, 1, 2, 3], so I found the topogeneous matrix confusing. Even more with the following, I expect the elements to be sorted the way I enter them:
    sage: T = FiniteSpace([{0, 3}, {1, 3}, {2, 3}, {3}], elements=[0,1,2,3])                  
    sage: T.elements()                                                                        
    [3, 0, 1, 2]
Should they be sorted in some cases? If the sets of elements are likely to be large, I can understand not wanting to sort by default, but if the user supplies a list of elements, shouldn't we use that?

I think the attribute T.elements() has no a good name, I think I should change it to T.topogenous_sorting() or something like that. If the user want to obtain the set of elements of the space, the attribute T.underlying_set() could be the best option.

I have no experience with finite topological spaces, so maybe users won't expect this sorting. From the !Python/Sage point of view, the current situation seems odd, though. Looking at the code, is the point to have an upper triangulate topogeneous matrix? If so, please add a comment about this to the documentation, pointing out an example. However, the example constructed from matrix data does not have an upper triangular topogeneous matrix, so maybe I'm confused. Or is it only upper triangular if the space is T0? The comment in the code could be clarified. Is this right:

diff --git a/src/sage/homology/finite_topological_spaces.py b/src/sage/homology/finite_topological_spaces.py
index 80f0b32fd1..ddab80d6f1 100644
--- a/src/sage/homology/finite_topological_spaces.py
+++ b/src/sage/homology/finite_topological_spaces.py
@@ -129,8 +129,19 @@ def FiniteSpace(data, elements=None, is_T0=False):
          {0: {3, 0}, 1: {3, 1}, 2: {3, 2}, 3: {3}}
         sage: type(T)
         <class 'sage.homology.finite_topological_spaces.FiniteTopologicalSpace_T0'>
+
+    Note that the set of elements is sorted in perhaps an unexpected
+    way. This is to ensure that in the case of a T0 space, the
+    topogenous matrix is upper triangular::
+
         sage: T.elements()
         [3, 0, 1, 2]
+        sage: T.topogenous_matrix()
+        [1 1 1 1]
+        [0 1 0 0]
+        [0 0 1 0]
+        [0 0 0 1]
+
         sage: FiniteSpace(({0, 2}, {0, 2}))
         Traceback (most recent call last):
         ...
@@ -226,7 +237,8 @@ def FiniteSpace(data, elements=None, is_T0=False):
                 basis[j] = Uj
             eltos = range(n)

-    # This fixes a topological sort (it guarantees an upper triangular topogenous matrix)
+    # This fixes a topological sort (it guarantees an upper triangular topogenous matrix
+    # in the T0 case)
     eltos = list(eltos)
     sorted_str_eltos = sorted([str(x) for x in eltos])
     eltos.sort(key = lambda x: (len(basis[x]), sorted_str_eltos.index(str(x))))

The comments in the code are absolutely right, thanks for the suggestions!

mkoeppe commented 3 years ago

comment:50

Sage development has entered the release candidate phase for 9.3. Setting a new milestone for this ticket based on a cursory review of ticket status, priority, and last modification date.

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

Changed commit from 481bef5 to 103698c

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

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

103698c .elements() changed by .topogenous_sorting()

dimpase commented 3 years ago

comment:52

This only adds to confusion one gets upon looking at what's in sage/homology/. IMHO this needs a restructuring (not on this ticket), maybe introducing something like sage/topology with parts such as spaces, homology, etc

jhpalmieri commented 3 years ago

comment:53

Replying to @dimpase:

This only adds to confusion one gets upon looking at what's in sage/homology/. IMHO this needs a restructuring (not on this ticket), maybe introducing something like sage/topology with parts such as spaces, homology, etc

I created #31925 for this.

dimpase commented 3 years ago

comment:54

Replying to @jhpalmieri:

Replying to @dimpase:

This only adds to confusion one gets upon looking at what's in sage/homology/. IMHO this needs a restructuring (not on this ticket), maybe introducing something like sage/topology with parts such as spaces, homology, etc

I created #31925 for this.

perhaps this ticket, i.e. #30400, can be a start for sage/topology ?

jhpalmieri commented 3 years ago

comment:55

Replying to @dimpase:

Replying to @jhpalmieri:

Replying to @dimpase:

This only adds to confusion one gets upon looking at what's in sage/homology/. IMHO this needs a restructuring (not on this ticket), maybe introducing something like sage/topology with parts such as spaces, homology, etc

I created #31925 for this.

perhaps this ticket, i.e. #30400, can be a start for sage/topology ?

This and also #31748.

jhpalmieri commented 3 years ago

comment:56

Replying to @jhpalmieri:

Replying to @dimpase:

Replying to @jhpalmieri:

Replying to @dimpase:

This only adds to confusion one gets upon looking at what's in sage/homology/. IMHO this needs a restructuring (not on this ticket), maybe introducing something like sage/topology with parts such as spaces, homology, etc

I created #31925 for this.

perhaps this ticket, i.e. #30400, can be a start for sage/topology ?

This and also #31748.

I'm working on #31925, and if it's in good enough shape, it can be a dependency for this ticket, and the file here would get added to sage/topology. My understanding is that this ticket requires an upgrade to Kenzo anyway, so this one is not immediately ready for merging. Is there a ticket for the new Kenzo?

slel commented 3 years ago

comment:57

Replying to @jhpalmieri:

Is there a ticket for the new Kenzo?

The Trac query for tickets whose summary includes "kenzo" reveals:

29617: Support system installations of ECL and fix the kenzo SPKG build

which upgrades from Kenzo 1.1.9 to Kenzo 1.1.10 and udates the "upstream" info to point to

https://github.com/miguelmarco/kenzo

It got positive review in early April 2021, and was rebased on 9.4.beta0 in late May 2021.

Other Kenzo sources seem more outdated, mentioning only Kenzo 1.1.7:

the homepage and former Kenzo GitHub repo and its releases page and wiki.

Thankfully,

the repology info page for Kenzo points to Miguel Marco's fork, which Sage is using.

jhpalmieri commented 3 years ago

comment:58

Replying to @slel:

Replying to @jhpalmieri:

Is there a ticket for the new Kenzo?

The Trac query for tickets whose summary includes "kenzo" reveals:

29617: Support system installations of ECL and fix the kenzo SPKG build

which upgrades from Kenzo 1.1.9 to Kenzo 1.1.10 and udates the "upstream" info to point to

https://github.com/miguelmarco/kenzo

It got positive review in early April 2021, and was rebased on 9.4.beta0 in late May 2021.

Other Kenzo sources seem more outdated, mentioning only Kenzo 1.1.7:

the homepage and former Kenzo GitHub repo and its releases page and wiki.

Thankfully,

the repology info page for Kenzo points to Miguel Marco's fork, which Sage is using.

See also comment:48 on this ticket for the upgrade that I think we need.

jhpalmieri commented 3 years ago

comment:59

In any case, #31925 is ready for review, and this ticket could go in after it.

mkoeppe commented 3 years ago

Dependencies: #31925

mkoeppe commented 3 years ago

Work Issues: Rework on top of #31925

mkoeppe commented 3 years ago

comment:61

Setting a new milestone for this ticket based on a cursory review.

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

Changed commit from 103698c to d266e72

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

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

`0491dd2`	`Merge branch 't/31925/f641bbb597fbf58103ed8c84867bab207a10ffde' into t/30400/add_finite_topological_spaces`
`d266e72`	`finite spaces moved to topology folder`

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

Changed commit from d266e72 to 3c2e0d4

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

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

3c2e0d4 references updated

jcuevas-rozo commented 3 years ago

comment:64

It has been merged with ticket #31925.

jhpalmieri commented 3 years ago

comment:65

I think there needs to be a ticket with the appropriate upgrade to Kenzo (comment:48), and this ticket should depend on that one. I think that we cannot really test this one without the Kenzo upgrade.

fchapoton commented 3 years ago

comment:66

red branch => needs work

sagemath / sage

Add finite topological spaces #30400

29617: Support system installations of ECL and fix the kenzo SPKG build

29617: Support system installations of ECL and fix the kenzo SPKG build