Simplicial complex examples as singletons

[tscrim]

Since each of the examples are unique, there should only be one (immutable) instance of each. In other words, we do not recreate the example each time it is called. For example

sage: S1 = simplicial_complexes.KleinBottle()
sage: S2 = simplicial_complexes.KleinBottle()
sage: S1 == S2
True
sage: S1 is S2
False

where the last should return true. Possibly do this by something like

def KlienBottle(self):
    if not hasattr(self, "_klien_bottle_output"):
        self._klien_bottle_output = SimplicialComplex(facets)
    return self._klien_bottle_output

This is an expansion on the concept in #13244 and the dependency on #12587 is in making simplicial complexes immutable.

[cnassau]

A simpler solution would be to turn the constructors in the SimplicialComplexExamples class into @cached_methods. I'm attaching this as a patch.

[cnassau]

make examples unique using @cached_method

[tscrim]

Please add doctests such as

sage: T1 = simplicial_complexes.Torus()
sage: T2 = simplicial_complexes.Torus()
sage: T1 is T2
True

and make sure this is based on #12587 (the ticket cannot apply with any fuzz). I'd also like to see you put your name in the AUTHORS: block and a general statement of the changes. Also you will need to fill in your real name on the ticket and have a proper commit message in the patch.

Thank you,
Travis

[cnassau]

Hmm, I've tried for about an hour to apply the patches from #12587 on my (essentially clean) 3.5.1, but without success. I think I'll just "withdraw" this patch for now and come back to it after the next release...

[jhpalmieri]

Sorry about that. I think I've recorded the correct dependencies on #12587 now.

[cnassau]

Replying to jhpalmieri:

Sorry about that. I think I've recorded the correct dependencies on #12587 now.

Thanks, that might help. On the other hand, I don't think this issue is urgent so I've pushed it to the back of my queue for now. If someone else wants to implement a fix I wouldn't mind at all ;-)

[jhpalmieri]

Here is a rebased version of Christian's patch. I added a bunch of tests, also.

[jhpalmieri]

By the way, this applies independently of the patches at #13725 for sum complexes. Those can't be cached like this because they can accept a list (which is unhashable) as an argument.

[tscrim]

From what I've heard, custom caches are something we should avoid. So since we can't make sum complexes work with @cached_method, and everything looks good to me, I'm setting this to positive review. Thanks.

[cnassau]

Replying to tscrim:

From what I've heard, custom caches are something we should avoid. So since we can't make sum complexes work with @cached_method, and everything looks good to me, I'm setting this to positive review. Thanks.

The author credits are very generous, many thanks. From my part this was a somewhat reckless case of drive-by patching of which I am rather ashamed now. I hope to do a better job next time... ;-)

Cheers,
Christian

[jdemeyer]

On sage.math, this patch causes

sage -t  -force_lib devel/sage/sage/categories/algebra_modules.py
/release/merger/sage-5.6.beta2/local/lib/libcsage.so(print_backtrace+0x2b)[0x2b1002e4866e]
/release/merger/sage-5.6.beta2/local/lib/libcsage.so(sigdie+0x14)[0x2b1002e4869b]
/release/merger/sage-5.6.beta2/local/lib/libcsage.so(sage_signal_handler+0x20b)[0x2b1002e48189]
/lib/libpthread.so.0[0x2b1000eb27d0]
/release/merger/sage-5.6.beta2/local/lib/libpython2.7.so.1.0(PyObject_GC_Del+0x22)[0x2b1000be54c2]
/release/merger/sage-5.6.beta2/local/lib/libpython2.7.so.1.0[0x2b1000b62e01]
/release/merger/sage-5.6.beta2/local/lib/libpython2.7.so.1.0[0x2b1000b31703]
/release/merger/sage-5.6.beta2/local/lib/libpython2.7.so.1.0[0x2b1000b31978]
/release/merger/sage-5.6.beta2/local/lib/libpython2.7.so.1.0[0x2b1000b31978]
/release/merger/sage-5.6.beta2/local/lib/libpython2.7.so.1.0[0x2b1000bd949b]
/release/merger/sage-5.6.beta2/local/lib/libpython2.7.so.1.0[0x2b1000b44643]
/release/merger/sage-5.6.beta2/local/lib/libpython2.7.so.1.0(PyDict_SetItem+0x73)[0x2b1000b45583]
/release/merger/sage-5.6.beta2/local/lib/libpython2.7.so.1.0(PyDict_SetItemString+0x4b)[0x2b1000b4676b]
/release/merger/sage-5.6.beta2/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x47fd)[0x2b1000bab07d]
/release/merger/sage-5.6.beta2/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x852)[0x2b1000bae352]
/release/merger/sage-5.6.beta2/local/lib/libpython2.7.so.1.0[0x2b1000b329b9]
/release/merger/sage-5.6.beta2/local/lib/libpython2.7.so.1.0(PyObject_Call+0x68)[0x2b1000b05308]
/release/merger/sage-5.6.beta2/local/lib/libpython2.7.so.1.0[0x2b1000b158bf]
/release/merger/sage-5.6.beta2/local/lib/libpython2.7.so.1.0(PyObject_Call+0x68)[0x2b1000b05308]
/release/merger/sage-5.6.beta2/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x1299)[0x2b1000ba7b19]
/release/merger/sage-5.6.beta2/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x852)[0x2b1000bae352]
/release/merger/sage-5.6.beta2/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x5ae4)[0x2b1000bac364]
/release/merger/sage-5.6.beta2/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x852)[0x2b1000bae352]
/release/merger/sage-5.6.beta2/local/lib/libpython2.7.so.1.0[0x2b1000b329b9]
/release/merger/sage-5.6.beta2/local/lib/libpython2.7.so.1.0(PyObject_Call+0x68)[0x2b1000b05308]
/release/merger/sage-5.6.beta2/local/lib/libpython2.7.so.1.0[0x2b1000b158bf]
/release/merger/sage-5.6.beta2/local/lib/libpython2.7.so.1.0(PyObject_Call+0x68)[0x2b1000b05308]
/release/merger/sage-5.6.beta2/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x1299)[0x2b1000ba7b19]
/release/merger/sage-5.6.beta2/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x852)[0x2b1000bae352]
/release/merger/sage-5.6.beta2/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x5ae4)[0x2b1000bac364]
/release/merger/sage-5.6.beta2/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x852)[0x2b1000bae352]
/release/merger/sage-5.6.beta2/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x5ae4)[0x2b1000bac364]
/release/merger/sage-5.6.beta2/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x852)[0x2b1000bae352]
/release/merger/sage-5.6.beta2/local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x5ae4)[0x2b1000bac364]
/release/merger/sage-5.6.beta2/local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x852)[0x2b1000bae352]
/release/merger/sage-5.6.beta2/local/lib/libpython2.7.so.1.0(PyEval_EvalCode+0x32)[0x2b1000bae472]
/release/merger/sage-5.6.beta2/local/lib/libpython2.7.so.1.0(PyRun_FileExFlags+0xc1)[0x2b1000bd21f1]
/release/merger/sage-5.6.beta2/local/lib/libpython2.7.so.1.0(PyRun_SimpleFileExFlags+0x1f9)[0x2b1000bd24c9]
/release/merger/sage-5.6.beta2/local/lib/libpython2.7.so.1.0(Py_Main+0xb15)[0x2b1000be5115]
/lib/libc.so.6(__libc_start_main+0xf4)[0x2b10017671f4]
python[0x400679]

------------------------------------------------------------------------
Unhandled SIGSEGV: A segmentation fault occurred in Sage.
This probably occurred because a *compiled* component of Sage has a bug
in it and is not properly wrapped with sig_on(), sig_off(). You might
want to run Sage under gdb with 'sage -gdb' to debug this.
Sage will now terminate.
------------------------------------------------------------------------
Segmentation fault

[jdemeyer]

Note that this segfault is actually "caused" by #715 + #11521.

[nbruin]

Why is this caching desirable? As far as I can see, this creates a memory leak:

i=1
while true:
   simplicial_complexes.Sphere(i)
   i=i+1

fails much sooner than it should because all the now useless previous examples are still nailed in memory.

You aren't proposing the cache to save computation time, I suppose? It's probably because you find it desirable to guarantee uniqueness when these things exist (are they parents?) In that case, you can get what you want by inheriting from UniqueRepresentation or UniqueFactory. That keeps a weak cache, so that examples that aren't otherwise referenced anymore can be collected.

[cnassau]

Replying to nbruin:

You aren't proposing the cache to save computation time, I suppose? It's probably because you find it desirable to guarantee uniqueness when these things exist (are they parents?) In that case, you can get what you want by inheriting from UniqueRepresentation or UniqueFactory. That keeps a weak cache, so that examples that aren't otherwise referenced anymore can be collected.

I wonder if we could create a new modifier @weakly_chached_method (or maybe @cached_method(weakref=True)) for this purpose. Using a UniqueRepresentation or UniqueFactory probably requires some code re-arrangements (for example, Sphere is a currently a method, not a class whose inheritance we could change).

[nbruin]

Well ... you could write a decorator that turns a function into a UniqueFactory?. However, I think you have a more serious problem: The routines you are now defining have no business being a method (note that you don't use the self argument!). Python is not Java. You don't have to stuff everything into a class. Much more appropriate is a module (just a file with functions). In fact, since your functions are just interfaces to SimplicialComplex?, any uniqueness of the output value is already ensured by that thing. And if it isn't, then either SimplicialComplex? should be ensuring uniqueness or there's a good reason why it shouldn't and then your routines shouldn't ensure uniqueness either. In other words: the caching you're proposing should either happen on a deeper level or not at all.

For more information about using modules to gather examples or as convenient namespace groupings, see #13115 and this ​sage-devel thread.

[tscrim]

If I understand #13115/the thread correctly, a way to do this would be:

• have an import homology/examples as simplical_complexes in the all.py
• Make each of these methods into a subclass of SimplicialComplex and UniqueRepresentation and have these be at the module level

since right now SimplicialComplex is mutable until specified otherwise. (I guess with this we can also do some optimization with certain methods, such as homology for Sphere... and that should be a different ticket.)

[nbruin]

Replying to tscrim:

If I understand #13115/the thread correctly, a way to do this would be:

• have an import homology/examples as simplical_complexes in the all.py
• Make each of these methods into a subclass of SimplicialComplex and UniqueRepresentation and have these be at the module level

since right now SimplicialComplex is mutable until specified otherwise. (I guess with this we can also do some optimization with certain methods, such as homology for Sphere... and that should be a different ticket.)

Yes, that sounds looks like a sensible approach. Additionally, if that seems like a heavy-weight solution (it does to me), one should probably see if uniqueness is so important that it warrants a subclass and/or if there are other pressing reasons to make these subclasses. Reasons against uniqueness:

• SimplicialComplex is not a parent so there's no sage-technical reason to enforce uniqueness (that's just a reason not for uniqueness)

• While any two Sphere(3) complexes are isomorphic, they are not canonically so, so mathematically there can be good reasons to have multiple non-identical spheres in memory.

• It makes things like Sphere behave different from SimplicialComplex (and more generally not simply be a SimplicialComplex. That makes code harder to maintain because now you have similar-but-subtly-different acting objects. You should only do that if there's a benefit elsewhere.

Should uniqueness of SimplicialComplexes be desirable in general (why? are they meant to become parents?) then it should perhaps be fixed on that level. Mutable obviously can't be forced to be unique, so then you should probably make two: SimplicialComplex and MutableSimplicialComplex (one a subclass of the other if at all possible), where you can make the immutable one unique by also inheriting from UniqueRepresentation?. Going to the immutable one then of course should return an immutable copy, not just change a flag.

Alternatively, (I don't know if that would be too hackish) you could add another flag, canonical_instance=true/false (only to be used with is_mutable=False), or make (a renamed version of) is_mutable tristate, to determines whether a cache is involved. That would have the severe drawback you'd have to break open the caching mechanism used in UniqueRepresentation.

If you find there's no need for Sphere etc. to be anything more than just a SimplicialComplex the implementation becomes really easy: sage.homology.examples.Sphere can simple be a function, returning the relevant SimplicialComplex.

[tscrim]

Replying to nbruin:

Reasons against uniqueness:

• SimplicialComplex is not a parent so there's no sage-technical reason to enforce uniqueness (that's just a reason not for uniqueness)

• While any two Sphere(3) complexes are isomorphic, they are not canonically so, so mathematically there can be good reasons to have multiple non-identical spheres in memory.

That is a good point since I believe not all triangulations of a (high enough dimensional) sphere can be obtained by bistellar flips.

• It makes things like Sphere behave different from SimplicialComplex (and more generally not simply be a SimplicialComplex. That makes code harder to maintain because now you have similar-but-subtly-different acting objects. You should only do that if there's a benefit elsewhere.

Also a good point.

Should uniqueness of SimplicialComplexes be desirable in general (why? are they meant to become parents?) then it should perhaps be fixed on that level. Mutable obviously can't be forced to be unique, so then you should probably make two: SimplicialComplex and MutableSimplicialComplex (one a subclass of the other if at all possible), where you can make the immutable one unique by also inheriting from UniqueRepresentation?. Going to the immutable one then of course should return an immutable copy, not just change a flag.

What I was thinking when I created this ticket was that since these are particular examples of simplicial complexes, they should be unique and immutable. However, perhaps it would be better to have them be mutable copies for computations rather than having the user create a copy (I don't really know offhand if these are used computationally in Sage)...I will leave this decision to someone who uses these more than me.

If you find there's no need for Sphere etc. to be anything more than just a SimplicialComplex the implementation becomes really easy: sage.homology.examples.Sphere can simple be a function, returning the relevant SimplicialComplex.

If it is decided to essentially do nothing, perhaps we should use this ticket to move everything down to a function.

Also it seems like this needs to be rebased to 5.6.beta1.

Thanks,
Travis

PS - I may not be able to respond for 2 weeks

[SimonKing]

Sorry, I did not read the whole discussion, but I see in the patch that cached_method is used. Hence, the constructed simplicial complexes will be kept in memory indefinitely. Wouldn't it be a better idea to turn simplicial_complexes into a UniqueFactory?

Of course, in a UniqueFactory one would usually ask for a Klein bottle by simplicial_complexes("KleinBottle"). But of course one could still define methods KleinBottle and so on, so that simplicial_complexes.KleinBottle() is equivalent to simplicial_complexes("KleinBottle").

The latter could be automatised by a __getattr__ method:

    def __getattr__(self, s):
        return lambda : self(s)

Why would that solve the problem with permanent caching? Well, UniqueFactory will soon be using weak dictionaries for caching (in fact it already uses weak references, but improperly, and that's supposed to be fixed in #12215).

[tscrim]

Sorry for falling behind on this ticket. What we should do strongly depends on the answer the question "Should these examples be immutable to begin with (right now one would need to make a mutable copy to manipulate it)?" My belief is still yes and so I'd support going to a UniqueFactory, however this is at odds with what the graph code does:

sage: g = graphs.StarGraph(5)
sage: g
Star graph: Graph on 6 vertices
sage: g.add_vertex(10)
sage: g
Star graph: Graph on 7 vertices

Since the graph is given a special name, I'd rather that be immutable. (If we do keep them immutable, we probably should give each of our simplicial complex examples special names too...)

Anyways, what are everyone else's thoughts?

Thanks,
Travis

[jhpalmieri]

How do you make an immutable simplicial complex mutable? We seem to have missed adding a set_mutable method in #12587, and so now I don't know how to get a mutable copy of the various examples, short of explicitly setting the _is_mutable attribute.

I think this should be fixed very soon, maybe before the other issues in this ticket.

As far as whether the examples should be immutable, I don't feel strongly either way. I can see a certain elegance in immutability, but other examples in Sage don't seem to work like this. I suppose we could use UniqueFactory to create an immutable unique instance, but the functions (or methods, or whatever) could return a mutable copy each time. For example:

sage: MatrixSpace(QQ, 3, 3).identity_matrix().is_mutable()
False

sage: matrix.identity(QQ, 3).is_mutable()
True

This seems rather odd to me, but I suppose it's an option.

[tscrim]

Replying to jhpalmieri:

How do you make an immutable simplicial complex mutable? We seem to have missed adding a set_mutable method in #12587, and so now I don't know how to get a mutable copy of the various examples, short of explicitly setting the _is_mutable attribute.

For example

sage: S = simplicial_complexes.Sphere(4)
sage: S.is_mutable()
False
sage: T = SimplicialComplex(S, is_mutable=True) # This should work and is a bug I didn't catch
sage: T.is_mutable()
False
sage: T = SimplicialComplex(S) # This one I'm happy with leaving immutable
sage: T.is_mutable()
False

However I do think we should also have a method to make a mutable copy, my suggestions are either copy() and/or make_mutable().

I think this should be fixed very soon, maybe before the other issues in this ticket.

Agreed. This was something I introduced, so I'll be happy to fix it.

As far as whether the examples should be immutable, I don't feel strongly either way. I can see a certain elegance in immutability, but other examples in Sage don't seem to work like this. I suppose we could use UniqueFactory to create an immutable unique instance, but the functions (or methods, or whatever) could return a mutable copy each time. For example:

sage: MatrixSpace(QQ, 3, 3).identity_matrix().is_mutable()
False

sage: matrix.identity(QQ, 3).is_mutable()
True

This seems rather odd to me, but I suppose it's an option.

This is very strange to me as well. Part of the thing is the identity matrix function is cached, so it must return an immutable object.

Best,
Travis

[jhpalmieri]

Replying to tscrim:

However I do think we should also have a method to make a mutable copy, my suggestions are either copy() and/or make_mutable().

Another option is to use __copy__(); then calling copy(X) would return a mutable copy of X. We could make copy() an alias for __copy__(), so it's visible via tab completion.

[tscrim]

I've started #14142 which will allow mutable copies.

[jhpalmieri]

Here is a branch which makes two more examples of simplicial complexes immutable, and then converts all of the examples from methods to functions. They are not cached (and I think that was the consensus).

As Travis said above:

If it is decided to essentially do nothing, perhaps we should use this ticket to move everything down to a function.

I guess that's what I've done.

---

New commits:

​fa33dbe	trac 13566: make two more examples of simplicial complexes immutable
​5bf74b6	trac 13566: remove the class in sage/homology/examples.py:

[git]

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

​1578bdb

trac 13566: add a file simplicial_complexes_catalog.py

[tscrim]

What about having a class which inherits from SimplicialComplex and UniqueRepresentation which takes the cells and a name, and then each of these functions pass the requisite data to that class? That way we get the singleton behavior and naming without really much effort (and wouldn't conflict with anything else we are doing with SimplicialComplex).

[jhpalmieri]

Okay. To do this, I've had to change __cmp__ for SimplicialComplexes to __eq__ and __ne__ so that we could correctly compare a simplicial complex and a UniqueSimplicialComplex. I'm not sure what you meant by naming, but I took a guess. Since the names of these complexes arise frequently in doctests, and since many of those doctests are changed in #6101, I decided to make #6101 a dependency for this, to avoid later rebasing.

[git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

​470ca9b	trac 6102: Merge branch 'AT-model' into t/6101/induced-maps
​6e3e801	trac 6101: Merge branch 'AT-model' into t/6101/induced-maps
​8e761de	Merge branch 't/6102/AT-model' into t/6101/induced-maps
​ec81de2	trac 6101: make morphisms inherit from 'Morphism'
​9d38c71	trac 6101: Merge branch 't/18175/public/categories/topological_metric_spaces-18175' into t/6101/induced-maps
​953e0a6	trac 6101: add _an_element_, etc., to SimplicialComplex
​b6c5657	Add a warning about the abuse of Parent in simplicial complex.
​e9150ca	Merge branch 'develop' into public/algtop/induced_maps-6101
​a4bc8a3	Merge branch 't/6101/induced-maps' into t/13566/simplicial-examples
​9251bde	trac 13566: new class UniqueSimplicialComplex, for use with examples

[git]

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

​f8ed7e4	trac 13566: new class UniqueSimplicialComplex, for use with examples
​090e5f9	trac 13566: fix result of stupid emacs 'fill-paragraph'

[tscrim]

Replying to jhpalmieri:

Okay. To do this, I've had to change __cmp__ for SimplicialComplexes to __eq__ and __ne__ so that we could correctly compare a simplicial complex and a UniqueSimplicialComplex. I'm not sure what you meant by naming, but I took a guess.

Yes, that was what I was looking for. Note to self: Make sure the hash functions match as well.

[tscrim]

It looks like we're going to also have to handle some old pickles... :/

[jhpalmieri]

I think this is easy to fix: just add the line

SimplicialSurface = SimplicialComplex

to examples.py. That line doesn't make any sense, though. Can we get rid of the old pickle?

[tscrim]

Here's my proposal, use register_unpickle_override.

---

New commits:

​ebd4e80

Taking care of an old pickle.

[tscrim]

Nom nom nom

Using --optional=coxeter3,database_gap,dot2tex,gap_packages,lie,mpir,python2,sage
Doctesting 1 file using 8 threads.
sage -t --long ../structure/sage_object.pyx
    [204 tests, 6.00 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 11.2 seconds
    cpu time: 3.3 seconds
    cumulative wall time: 6.0 seconds

If you're happy with this change, then you can set a positive review.

[jhpalmieri]

All tests pass.

[git]

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

​a6ce58c	Implementation of Yokonuma-Hecke algebras.
​efadb13	Adding top-level doctests and checking d=1 case.
​20fd4ce	Merge branch 'u/tscrim/simplicial-examples' of trac.sagemath.org:sage into u/tscrim/simplicial-examples
​14e4184	Fixing some doctest continuations that were there before.

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​9004cdd	Merge commit 'ebd4e8094b4d87baa22d5678820523992ad3312' into u/tscrim/simplicial-examples
​bab305f	Fixing some doctest continuations that were there before.

[tscrim]

Ignore the first commits, I forgot to checkout develop.

Hopefully now this can be merged.

[tscrim]

Volker, will this get merged for the next beta?

[vbraun]

Once you take out the dependencies that don't correspond to merged tickets it'll be merged.

[tscrim]

All of the dependencies had been merged...