Opened 3 years ago

Closed 3 years ago

# py3: fundamental group of simplicial complexes

Reported by: Owned by: jhpalmieri major sage-8.7 python3 John Palmieri Travis Scrimshaw, David Coudert N/A 47e4527 47e452753b2d32ced1a962cdc818c6badb476acd

### Description

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

### comment:1 Changed 3 years ago by jhpalmieri

• Branch set to u/jhpalmieri/py3-fundamental-group

### comment:2 Changed 3 years ago by jhpalmieri

• Commit set to 2beaf2049543f06eb3561497828c6dd0d20e030e
• Status changed from new to needs_review

New commits:

 ​2beaf20 `trac 24752: py3 fix for fundamental group of simplicial complexes`

### comment:3 Changed 3 years ago by 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.

### comment:4 Changed 3 years ago by 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]
```

### comment:5 Changed 3 years ago by git

• Commit changed from 2beaf2049543f06eb3561497828c6dd0d20e030e to aa5361b511fd3f9be1425960f480fe63e88b6e6c

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`

### comment:6 Changed 3 years ago by git

• Commit changed from aa5361b511fd3f9be1425960f480fe63e88b6e6c to c1a35e8468a3e671d86e970e6b4f70381c78a745

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`

### comment:7 Changed 3 years ago by git

• Commit changed from c1a35e8468a3e671d86e970e6b4f70381c78a745 to 3fff88c41320b16b07500fd5ce582db5f3044079

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`

### comment:8 Changed 3 years ago by 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.

### comment:9 Changed 3 years ago by 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.

### comment:10 follow-up: ↓ 11 Changed 3 years ago by tscrim

• Reviewers set to Travis Scrimshaw

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.

### comment:11 in reply to: ↑ 10 Changed 3 years ago by jhpalmieri

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.)

### comment:12 Changed 3 years ago by jhpalmieri

• Status changed from needs_review to positive_review

### comment:13 follow-up: ↓ 15 Changed 3 years ago by 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.

### comment:14 Changed 3 years ago by git

• Commit changed from 3fff88c41320b16b07500fd5ce582db5f3044079 to 47e452753b2d32ced1a962cdc818c6badb476acd
• Status changed from positive_review to needs_review

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`

Like this?

### comment:16 Changed 3 years ago by dcoudert

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

### comment:17 Changed 3 years ago by 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.

### comment:18 Changed 3 years ago by dcoudert

• Reviewers changed from Travis Scrimshaw to Travis Scrimshaw, David Coudert
• Status changed from needs_review to positive_review

LGTM

### comment:19 Changed 3 years ago by vbraun

• Branch changed from u/jhpalmieri/py3-fundamental-group to 47e452753b2d32ced1a962cdc818c6badb476acd
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.