Opened 6 weeks ago
Closed 5 weeks ago
#27452 closed defect (fixed)
py3: fundamental group of simplicial complexes
Reported by:  jhpalmieri  Owned by:  

Priority:  major  Milestone:  sage8.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 6 weeks ago by
 Branch set to u/jhpalmieri/py3fundamentalgroup
comment:2 Changed 6 weeks ago by
 Commit set to 2beaf2049543f06eb3561497828c6dd0d20e030e
 Status changed from new to needs_review
comment:3 Changed 6 weeks ago by
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 6 weeks ago by
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 6 weeks ago by
 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 6 weeks ago by
 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 6 weeks ago by
 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 6 weeks ago by
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 6 weeks ago by
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 followup: ↓ 11 Changed 6 weeks ago by
 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 6 weeks ago by
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 6 weeks ago by
 Status changed from needs_review to positive_review
comment:13 followup: ↓ 15 Changed 6 weeks ago by
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 6 weeks ago by
 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

comment:15 in reply to: ↑ 13 Changed 6 weeks ago by
Like this?
comment:16 Changed 6 weeks ago by
Yes. I assume that it's not possible to do it also for gens
, right?
comment:17 Changed 6 weeks ago by
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 6 weeks ago by
 Reviewers changed from Travis Scrimshaw to Travis Scrimshaw, David Coudert
 Status changed from needs_review to positive_review
LGTM
comment:19 Changed 5 weeks ago by
 Branch changed from u/jhpalmieri/py3fundamentalgroup to 47e452753b2d32ced1a962cdc818c6badb476acd
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
trac 24752: py3 fix for fundamental group of simplicial complexes