Opened 3 months ago

Closed 3 months ago

#27452 closed defect (fixed)

py3: fundamental group of simplicial complexes

Reported by: jhpalmieri Owned by:
Priority: major Milestone: sage-8.7
Component: python3 Keywords:
Cc: Merged in:
Authors: John Palmieri Reviewers: Travis Scrimshaw, David Coudert
Report Upstream: N/A Work issues:
Branch: 47e4527 (Commits) Commit: 47e452753b2d32ced1a962cdc818c6badb476acd
Dependencies: Stopgaps:

Description

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

Change History (19)

comment:1 Changed 3 months ago by jhpalmieri

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

comment:2 Changed 3 months ago by jhpalmieri

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

New commits:

2beaf20trac 24752: py3 fix for fundamental group of simplicial complexes

comment:3 Changed 3 months 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 months 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 months 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:

aa5361btrac 24752: py3 fix for fundamental group of simplicial complexes

comment:6 Changed 3 months 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:

c1a35e8trac 24752: py3 fix for fundamental group of simplicial complexes

comment:7 Changed 3 months 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:

3fff88ctrac 24752: py3 fix for fundamental group of simplicial complexes

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

comment:12 Changed 3 months ago by jhpalmieri

  • Status changed from needs_review to positive_review

comment:13 follow-up: Changed 3 months 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 months 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:

47e4527trac 27452: some simplifications in fundamental_group

comment:15 in reply to: ↑ 13 Changed 3 months ago by jhpalmieri

Like this?

comment:16 Changed 3 months ago by dcoudert

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

comment:17 Changed 3 months 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 months 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 months 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.