py3: fundamental group of simplicial complexes

[jhpalmieri]

This should fix the last py3 doctest failures in src/homology.

[jhpalmieri]

New commits:

​2beaf20

trac 24752: py3 fix for fundamental group of simplicial complexes

[jhpalmieri]

I first tried something a little more complicated: first computing the minimal spanning tree, and if that raises an error, then do the stuff in this branch. That was not much faster; I tested on simplicial_complexes.PoincareHomologyThreeSphere() which has integers as vertices.

[tscrim]

So I think there is a problem with this that is exposing another problem with graph(). Mainly if the result of graph() is an immutatble graph, then doing G.copy() will give another immutable.

sage: G = graphs.CycleGraph(3)
sage: GI = G.copy(immutable=True)
sage: G.is_immutable()
False
sage: GI.is_immutable()
True
sage: C = GI.copy()
sage: C.is_immutable()   # This is the problem
True
sage: C.relabel({0:'a',1:'b',2:'c'})
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
...
ValueError: To relabel an immutable graph use inplace=False

The result of graph() should be an immutable graph because it is cached, which can be easily achieved when constructing the result by giving immutable=True as an argument. To fix the problem here, you should do G.copy(immutable=False).

I would also think it would be faster to use v_to_int to construct int_to_v than redoing enumerate(G.vertex_iterator()) because of int_to_v being a Python builtin type (a dict).

I would also change the test to be more indicative of the cyclic structure:

-            sage: (x**5).is_one()
-            True
+            sage: [(x**n).is_one() for n in range(1,6)]
+            [False, False, False, False, True]

[git]

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

​aa5361b

trac 24752: py3 fix for fundamental group of simplicial complexes

[git]

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

​c1a35e8

trac 24752: py3 fix for fundamental group of simplicial complexes

[git]

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

​3fff88c

trac 24752: py3 fix for fundamental group of simplicial complexes

[jhpalmieri]

Thanks for the comments. I made those changes, plus a few others along these lines:

             True
         """
         d = self._vertex_to_index
-        return {d[v]:v for v in d}
+        return {idx: v for v, idx in d.items()}
 
     def _chomp_repr_(self):
         r"""

The point is that instead of doing a lot of separate dictionary lookups, it should be faster to dump it once using items and then convert that to a dict.

[jhpalmieri]

It might not be a bad idea to explicitly specify immutable=False when creating the graph associated to a simplicial complex (since it can be changed using add_face or remove_face), or maybe set immutable to whatever the setting is for the simplicial complex. On another ticket, though.

[tscrim]

A bit of the downside of doing foo.items() is that it creates the whole list in Python2. So it is not so memory friendly. Anyways, just food for thought.

Yes, we can fix the graph() issue on another ticket.

If the patchbot comes back green, then this can be set to a positive review.

[jhpalmieri]

Replying to tscrim:

A bit of the downside of doing foo.items() is that it creates the whole list in Python2. So it is not so memory friendly. Anyways, just food for thought.

It's a tradeoff between time and memory. Fortunately, I don't think simplicial complexes are likely to have so many vertices where it is an issue, or if they do, it's not going to be practical to compute the fundamental group.

(For example, simplicial_complexes.NotIConnectedGraphs(7,2) has over a million simplices overall, but just 21 vertices.)

[dcoudert]

You could simplify some parts of this code using frozenset instead of tuples for the spanning tree, the keys of gens_dict, and may be gens (not sure for that one). And also make spanning_tree a set.

[git]

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

​47e4527

trac 27452: some simplifications in fundamental_group

[jhpalmieri]

Like this?

[dcoudert]

Yes. I assume that it's not possible to do it also for gens, right?

[jhpalmieri]

gens doesn't get used much, only in these two lines:

        if len(gens) == 0:
            return gap.TrivialGroup()
        ...
        gens_dict = {frozenset(g): i for i, g in enumerate(gens)}
        FG = FreeGroup(len(gens), 'e')

So I don't think it will make much difference if it is made up of tuples or frozensets.

[dcoudert]

LGTM