Sage: Ticket #26966: py3: new doctest failures in homology
https://trac.sagemath.org/ticket/26966
<p>
With Python 3, before <a class="closed ticket" href="https://trac.sagemath.org/ticket/26931" title="defect: Predictable sorting in simplicial_complex.py (closed: fixed)">#26931</a>:
</p>
<pre class="wiki">sage -t src/sage/homology/simplicial_complex.py # 22 doctests failed
sage -t src/sage/homology/examples.py # 7 doctests failed
</pre><p>
After <a class="closed ticket" href="https://trac.sagemath.org/ticket/26931" title="defect: Predictable sorting in simplicial_complex.py (closed: fixed)">#26931</a>:
</p>
<pre class="wiki">sage -t src/sage/homology/examples.py # 14 doctests failed
sage -t src/sage/homology/simplicial_complex.py # 35 doctests failed
sage -t src/sage/homology/simplicial_set.py # 6 doctests failed
sage -t src/sage/homology/delta_complex.py # 3 doctests failed
sage -t src/sage/homology/simplicial_complexes_catalog.py # 3 doctests failed
</pre><p>
After this branch:
</p>
<pre class="wiki">sage -t src/sage/homology/simplicial_complex.py # 10 doctests failed
sage -t src/sage/homology/examples.py # 1 doctest failed
</pre>en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/26966
Trac 1.1.6jhpalmieriFri, 28 Dec 2018 22:36:50 GMT
https://trac.sagemath.org/ticket/26966#comment:1
https://trac.sagemath.org/ticket/26966#comment:1
<p>
The failures come from trying to sort vertices. Before <a class="closed ticket" href="https://trac.sagemath.org/ticket/26931" title="defect: Predictable sorting in simplicial_complex.py (closed: fixed)">#26931</a>, there was a fallback to use <code>str</code> as a key, but that was removed.
</p>
<pre class="wiki">File "src/sage/homology/simplicial_complexes_catalog.py", line 57, in sage.homology.simplicial_complexes_catalog
Failed example:
simplicial_complexes.SurfaceOfGenus(3)
Exception raised:
Traceback (most recent call last):
File "/Users/palmieri/Desktop/Sage_stuff/sage_builds/PYTHON3/sage-8.5/local/lib/python3.6/site-packages/sage/doctest/forker.py", line 671, in _run
self.compile_and_execute(example, compiler, test.globs)
File "/Users/palmieri/Desktop/Sage_stuff/sage_builds/PYTHON3/sage-8.5/local/lib/python3.6/site-packages/sage/doctest/forker.py", line 1086, in compile_and_execute
exec(compiled, globs)
File "<doctest sage.homology.simplicial_complexes_catalog[2]>", line 1, in <module>
simplicial_complexes.SurfaceOfGenus(Integer(3))
File "/Users/palmieri/Desktop/Sage_stuff/sage_builds/PYTHON3/sage-8.5/local/lib/python3.6/site-packages/sage/homology/examples.py", line 451, in SurfaceOfGenus
S = S.connected_sum(T)
File "/Users/palmieri/Desktop/Sage_stuff/sage_builds/PYTHON3/sage-8.5/local/lib/python3.6/site-packages/sage/homology/simplicial_complex.py", line 2770, in connected_sum
return SimplicialComplex(facet_set, is_mutable=is_mutable)
File "/Users/palmieri/Desktop/Sage_stuff/sage_builds/PYTHON3/sage-8.5/local/lib/python3.6/site-packages/sage/homology/simplicial_complex.py", line 1040, in __init__
vertex_set = sorted(vertex_set)
TypeError: '<' not supported between instances of 'str' and 'int'
</pre>
TicketjhpalmieriSat, 29 Dec 2018 21:40:53 GMT
https://trac.sagemath.org/ticket/26966#comment:2
https://trac.sagemath.org/ticket/26966#comment:2
<p>
I don't know if this branch is the correct approach, but it helps. If it is the correct approach, it is incomplete: at <a class="closed ticket" href="https://trac.sagemath.org/ticket/26966" title="defect: py3: new doctest failures in homology (closed: fixed)">#26966</a>, I included a list of some of the methods which need attention paid to how vertices are sorted:
</p>
<ul><li>product
</li><li>join
</li><li>disjoint_union
</li><li>wedge
</li><li>connected_sum
</li><li>link
</li><li>star
</li><li>generated_subcomplex
</li><li>alexander_dual
</li><li>stellar_subdivision
</li><li>n_skeleton
</li><li>connected_component
</li><li>fixed_complex
</li><li>intersection
</li><li><code>_contractible_subcomplex</code>
</li><li><code>_enlarge_subcomplex</code>
</li><li><code>__copy__</code>
</li></ul><p>
This list may not be complete, and the branch here only deals with a few of these.
</p>
TicketjhpalmieriSat, 29 Dec 2018 21:42:08 GMTbranch set
https://trac.sagemath.org/ticket/26966#comment:3
https://trac.sagemath.org/ticket/26966#comment:3
<ul>
<li><strong>branch</strong>
set to <em>u/jhpalmieri/sorting-simplicial-complexes</em>
</li>
</ul>
TicketjdemeyerSun, 30 Dec 2018 01:31:57 GMTcommit set
https://trac.sagemath.org/ticket/26966#comment:4
https://trac.sagemath.org/ticket/26966#comment:4
<ul>
<li><strong>commit</strong>
set to <em>b41b33c4bfc020fcfc0e6eda1110d07875f2efde</em>
</li>
</ul>
<p>
I don't agree with
</p>
<div class="wiki-code"><div xmlns="http://www.w3.org/1999/xhtml" class="diff">
<ul class="entries">
<li class="entry">
<h2>
<a>src/sage/homology/simplicial_complex.py</a>
</h2>
<pre>diff --git a/src/sage/homology/simplicial_complex.py b/src/sage/homology/simplicial_complex.py
index 946eda0..fd88c23 100644</pre>
<table class="trac-diff inline" summary="Differences" cellspacing="0">
<colgroup><col class="lineno" /><col class="lineno" /><col class="content" /></colgroup>
<thead>
<tr>
<th title="File a/src/sage/homology/simplicial_complex.py">
a
</th>
<th title="File b/src/sage/homology/simplicial_complex.py">
b
</th>
<td><em> class SimplicialComplex(Parent, GenericCellComplex):</em> </td>
</tr>
</thead>
<tbody class="unmod">
<tr>
<th>1037</th><th>1037</th><td class="l"><span> vertex_set = range(n + 1)</span></td>
</tr><tr>
<th>1038</th><th>1038</th><td class="l"><span></span></td>
</tr><tr>
<th>1039</th><th>1039</th><td class="l"><span> if sort_facets is True:</span></td>
</tr>
</tbody><tbody class="mod">
<tr class="first">
<th>1040</th><th> </th><td class="l"><span> vertex_set = sorted(vertex_set)</span></td>
</tr>
<tr>
<th> </th><th>1040</th><td class="r"><span> try:</span></td>
</tr><tr>
<th> </th><th>1041</th><td class="r"><span> vertex_set = sorted(vertex_set)</span></td>
</tr><tr>
<th> </th><th>1042</th><td class="r"><span> except TypeError:</span></td>
</tr><tr class="last">
<th> </th><th>1043</th><td class="r"><span> vertex_set = sorted(vertex_set, key=str)</span></td>
</tr>
</tbody><tbody class="unmod">
<tr>
<th>1041</th><th>1044</th><td class="l"><span> elif callable(sort_facets):</span></td>
</tr><tr>
<th>1042</th><th>1045</th><td class="l"><span> vertex_set = sorted(vertex_set, key=sort_facets)</span></td>
</tr><tr>
<th>1043</th><th>1046</th><td class="l"><span> elif not sort_facets:</span></td>
</tr>
</tbody>
</table>
</li>
</ul>
</div></div><p>
because it's rather arbitrary and ill-defined.
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=b41b33c4bfc020fcfc0e6eda1110d07875f2efde"><span class="icon"></span>b41b33c</a></td><td><code>trac 26966: clean up sorting for some simplicial complex methods.</code>
</td></tr></table>
TicketjdemeyerSun, 30 Dec 2018 01:40:52 GMT
https://trac.sagemath.org/ticket/26966#comment:5
https://trac.sagemath.org/ticket/26966#comment:5
<p>
Do you know why unsortable lists of vertices are so common in simplicial complexes? Is there a single place where these mixed <code>int</code>/<code>str</code> vertices come from?
</p>
TicketjdemeyerSun, 30 Dec 2018 01:42:47 GMT
https://trac.sagemath.org/ticket/26966#comment:6
https://trac.sagemath.org/ticket/26966#comment:6
<p>
For example, in <code>MooreSpace</code>, the obvious solution to me is to use only strings as vertices, i.e. replace <code>1</code> by <code>"1"</code>.
</p>
TicketjhpalmieriSun, 30 Dec 2018 02:58:30 GMT
https://trac.sagemath.org/ticket/26966#comment:7
https://trac.sagemath.org/ticket/26966#comment:7
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/26966#comment:5" title="Comment 5">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
Do you know why unsortable lists of vertices are so common in simplicial complexes? Is there a single place where these mixed <code>int</code>/<code>str</code> vertices come from?
</p>
</blockquote>
<p>
I don't think we should impose restrictions on what users might choose to do. We can choose good defaults for the specific examples (like <code>MooreSpace</code>), but if someone wants to form a disjoint union from a complex whose vertices are integers with another whose vertices are strings, we should allow that.
</p>
TicketjhpalmieriSun, 30 Dec 2018 02:59:44 GMT
https://trac.sagemath.org/ticket/26966#comment:8
https://trac.sagemath.org/ticket/26966#comment:8
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/26966#comment:4" title="Comment 4">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
I don't agree with
</p>
<div class="wiki-code"><div xmlns="http://www.w3.org/1999/xhtml" class="diff">
<ul class="entries">
<li class="entry">
<h2>
<a>src/sage/homology/simplicial_complex.py</a>
</h2>
<pre>diff --git a/src/sage/homology/simplicial_complex.py b/src/sage/homology/simplicial_complex.py
index 946eda0..fd88c23 100644</pre>
<table class="trac-diff inline" summary="Differences" cellspacing="0">
<colgroup><col class="lineno" /><col class="lineno" /><col class="content" /></colgroup>
<thead>
<tr>
<th title="File a/src/sage/homology/simplicial_complex.py">
a
</th>
<th title="File b/src/sage/homology/simplicial_complex.py">
b
</th>
<td><em> class SimplicialComplex(Parent, GenericCellComplex):</em> </td>
</tr>
</thead>
<tbody class="unmod">
<tr>
<th>1037</th><th>1037</th><td class="l"><span> vertex_set = range(n + 1)</span></td>
</tr><tr>
<th>1038</th><th>1038</th><td class="l"><span></span></td>
</tr><tr>
<th>1039</th><th>1039</th><td class="l"><span> if sort_facets is True:</span></td>
</tr>
</tbody><tbody class="mod">
<tr class="first">
<th>1040</th><th> </th><td class="l"><span> vertex_set = sorted(vertex_set)</span></td>
</tr>
<tr>
<th> </th><th>1040</th><td class="r"><span> try:</span></td>
</tr><tr>
<th> </th><th>1041</th><td class="r"><span> vertex_set = sorted(vertex_set)</span></td>
</tr><tr>
<th> </th><th>1042</th><td class="r"><span> except TypeError:</span></td>
</tr><tr class="last">
<th> </th><th>1043</th><td class="r"><span> vertex_set = sorted(vertex_set, key=str)</span></td>
</tr>
</tbody><tbody class="unmod">
<tr>
<th>1041</th><th>1044</th><td class="l"><span> elif callable(sort_facets):</span></td>
</tr><tr>
<th>1042</th><th>1045</th><td class="l"><span> vertex_set = sorted(vertex_set, key=sort_facets)</span></td>
</tr><tr>
<th>1043</th><th>1046</th><td class="l"><span> elif not sort_facets:</span></td>
</tr>
</tbody>
</table>
</li>
</ul>
</div></div><p>
because it's rather arbitrary and ill-defined.
</p>
</blockquote>
<p>
On the other hand, it's the old behavior, so it's safe. We could throw in a warning if the <code>except</code> clause ever kicks in, to try to discourage it.
</p>
TicketjdemeyerSun, 30 Dec 2018 12:05:45 GMT
https://trac.sagemath.org/ticket/26966#comment:9
https://trac.sagemath.org/ticket/26966#comment:9
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/26966#comment:7" title="Comment 7">jhpalmieri</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/26966#comment:5" title="Comment 5">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
Do you know why unsortable lists of vertices are so common in simplicial complexes? Is there a single place where these mixed <code>int</code>/<code>str</code> vertices come from?
</p>
</blockquote>
<p>
I don't think we should impose restrictions on what users might choose to do.
</p>
</blockquote>
<p>
I didn't say that we should. I'm just saying that, if the user does that, they have to explicitly specify the sorting key. Otherwise, it's too fragile (for example, code will behave <em>differently</em> on Python 2 and Python 3).
</p>
TicketjhpalmieriSun, 30 Dec 2018 18:00:31 GMT
https://trac.sagemath.org/ticket/26966#comment:10
https://trac.sagemath.org/ticket/26966#comment:10
<p>
I feel like the sort key should mainly be internal, and users should not have to worry about it. Sorting the vertices needs to be done consistently for each simplicial complex, but maybe it's not important if, as the simplicial complex changes, the sorting changes. The ticket description at <a class="closed ticket" href="https://trac.sagemath.org/ticket/26931" title="defect: Predictable sorting in simplicial_complex.py (closed: fixed)">#26931</a> sounds compelling, but in retrospect, I'm not convinced. I could easily imagine a user doing this:
</p>
<pre class="wiki">sage: T = SimplicialComplex([range(1,5)])
sage: T.add_face([0,1,'*']) # add a new distinguished vertex
sage: T.homology()
...
TypeError: '<' not supported between instances of 'str' and 'int'
</pre>
TicketjdemeyerSun, 30 Dec 2018 20:14:56 GMT
https://trac.sagemath.org/ticket/26966#comment:11
https://trac.sagemath.org/ticket/26966#comment:11
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/26966#comment:10" title="Comment 10">jhpalmieri</a>:
</p>
<blockquote class="citation">
<p>
I feel like the sort key should mainly be internal, and users should not have to worry about it.
</p>
</blockquote>
<p>
Let me ask an even more basic question: why do we need to sort anything at all? If it's not to hard to drop that, we should go for it. Especially if it's meant to be internal as you say, there shouldn't be a fundamental reason why vertices need to be sorted.
</p>
TicketjhpalmieriSun, 30 Dec 2018 21:00:33 GMT
https://trac.sagemath.org/ticket/26966#comment:12
https://trac.sagemath.org/ticket/26966#comment:12
<p>
In order to compute homology, each simplex needs to be sorted consistently with the other simplices, and the easiest way to achieve that is a total ordering on the vertices. I don't know a minimal example, but if you turn off sorting, then the homology of <code>simplicial_complexes.ComplexProjectivePlane()</code> is wrong. That is:
</p>
<pre class="wiki">S = SimplicialComplex([[1, 2, 4, 5, 6], [2, 3, 5, 6, 4], [3, 1, 6, 4, 5],
[1, 2, 4, 5, 9], [2, 3, 5, 6, 7], [3, 1, 6, 4, 8],
[2, 3, 6, 4, 9], [3, 1, 4, 5, 7], [1, 2, 5, 6, 8],
[3, 1, 5, 6, 9], [1, 2, 6, 4, 7], [2, 3, 4, 5, 8],
[4, 5, 7, 8, 9], [5, 6, 8, 9, 7], [6, 4, 9, 7, 8],
[4, 5, 7, 8, 3], [5, 6, 8, 9, 1], [6, 4, 9, 7, 2],
[5, 6, 9, 7, 3], [6, 4, 7, 8, 1], [4, 5, 8, 9, 2],
[6, 4, 8, 9, 3], [4, 5, 9, 7, 1], [5, 6, 7, 8, 2],
[7, 8, 1, 2, 3], [8, 9, 2, 3, 1], [9, 7, 3, 1, 2],
[7, 8, 1, 2, 6], [8, 9, 2, 3, 4], [9, 7, 3, 1, 5],
[8, 9, 3, 1, 6], [9, 7, 1, 2, 4], [7, 8, 2, 3, 5],
[9, 7, 2, 3, 6], [7, 8, 3, 1, 4], [8, 9, 1, 2, 5]],
sort_facets=False)
S.homology()
</pre><p>
produces the wrong answer: <code>{0: 0, 1: 0, 2: C2, 3: 0, 4: 0}</code> instead of <code>{0: 0, 1: 0, 2: Z, 3: 0, 4: Z}</code>.
</p>
TicketjdemeyerWed, 02 Jan 2019 18:30:22 GMT
https://trac.sagemath.org/ticket/26966#comment:13
https://trac.sagemath.org/ticket/26966#comment:13
<p>
If the only requirement is a predictable ordering, you could have a dict mapping arbitrary vertices to integers and use that to sort.
</p>
TicketjdemeyerWed, 02 Jan 2019 18:36:50 GMT
https://trac.sagemath.org/ticket/26966#comment:14
https://trac.sagemath.org/ticket/26966#comment:14
<p>
For example, the already-existing attribute <code>_vertex_set</code> could be used for that: we could implement a <code>set</code>-like class which internally uses a <code>dict</code> to store a <code>vertex: index</code> mapping.
</p>
TicketgitThu, 03 Jan 2019 19:22:59 GMTcommit changed
https://trac.sagemath.org/ticket/26966#comment:15
https://trac.sagemath.org/ticket/26966#comment:15
<ul>
<li><strong>commit</strong>
changed from <em>b41b33c4bfc020fcfc0e6eda1110d07875f2efde</em> to <em>99eec7ba0857330654daf942d89c9160981bc19b</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=99eec7ba0857330654daf942d89c9160981bc19b"><span class="icon"></span>99eec7b</a></td><td><code>trac 26966: simplicial complexes: do not publicly sort vertices any more.</code>
</td></tr></table>
TicketjhpalmieriThu, 03 Jan 2019 19:28:41 GMTstatus, description changed; author set
https://trac.sagemath.org/ticket/26966#comment:16
https://trac.sagemath.org/ticket/26966#comment:16
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/26966?action=diff&version=16">diff</a>)
</li>
<li><strong>author</strong>
set to <em>John Palmieri</em>
</li>
</ul>
<p>
Okay, here is an attempt at not sorting vertices (publicly) any more. A few Python 3 doctests have random outputs, since if vertices cannot be sorted, they aren't, and the doctests give different outputs depending on the order of the vertices. I've marked one as <code># py3 # random</code> and I've made another Python 2 only.
</p>
TicketjdemeyerThu, 03 Jan 2019 20:12:46 GMTstatus changed
https://trac.sagemath.org/ticket/26966#comment:17
https://trac.sagemath.org/ticket/26966#comment:17
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<ol><li>What's the use case for trying to sort anyway? That way, you make doctests different on Python 2 and Python 3 for no good reason.
</li></ol><ol start="2"><li>Use dict comprehension instead of <code>dict((x,y) ....)</code> for example here:
<pre class="wiki"> vertex_to_index = dict((vertex, i) for i, vertex
in enumerate(vertices))
</pre></li></ol><ol start="3"><li><code>self._vertex_to_index</code> seems redundant with <code>self._vertex_set</code>. It seems that <code>self._vertex_to_index</code> could replace <code>self._vertex_set</code>.
</li></ol>
TicketjhpalmieriThu, 03 Jan 2019 22:16:43 GMT
https://trac.sagemath.org/ticket/26966#comment:18
https://trac.sagemath.org/ticket/26966#comment:18
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/26966#comment:17" title="Comment 17">jdemeyer</a>:
</p>
<blockquote class="citation">
<ol><li>What's the use case for trying to sort anyway? That way, you make doctests different on Python 2 and Python 3 for no good reason.
</li></ol></blockquote>
<p>
I tried without any sorting, but it didn't work well. Various methods rely on sorting: for example, when you take the product of simplicial complexes, if you want to triangulate the product of two edges, there are two choices, and which choice depends on how the vertices are ordered. Another example: when you compute the fundamental group, the presentation of the group depends on how the vertices and edges are sorted. So if nothing is sorted, lots of doctests break and/or the code needs special cases. Why not order if it's easy? Looking to the future when we switch to Python 3, it makes a lot of sense to sort the vertices if the vertices are just integers, and that's what I have in mind in the sorting code.
</p>
<blockquote class="citation">
<ol start="2"><li>Use dict comprehension instead of <code>dict((x,y) ....)</code> for example here:
<pre class="wiki"> vertex_to_index = dict((vertex, i) for i, vertex
in enumerate(vertices))
</pre></li></ol></blockquote>
<p>
I can do that. Is this just a stylistic choice, or is it better to use dict comprehension for other reasons?
</p>
<blockquote class="citation">
<ol start="3"><li><code>self._vertex_to_index</code> seems redundant with <code>self._vertex_set</code>. It seems that <code>self._vertex_to_index</code> could replace <code>self._vertex_set</code>.
</li></ol></blockquote>
<p>
That shouldn't be hard to do.
</p>
TicketgitFri, 04 Jan 2019 01:14:19 GMTcommit changed
https://trac.sagemath.org/ticket/26966#comment:19
https://trac.sagemath.org/ticket/26966#comment:19
<ul>
<li><strong>commit</strong>
changed from <em>99eec7ba0857330654daf942d89c9160981bc19b</em> to <em>6bb3e28d7a95cc11ec1dd7a1040fca1901d50d8d</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=6bb3e28d7a95cc11ec1dd7a1040fca1901d50d8d"><span class="icon"></span>6bb3e28</a></td><td><code>trac 26966: Remove vertex_set. Use dict comprehension.</code>
</td></tr></table>
TicketjhpalmieriFri, 04 Jan 2019 01:14:37 GMTstatus changed
https://trac.sagemath.org/ticket/26966#comment:20
https://trac.sagemath.org/ticket/26966#comment:20
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
TicketjdemeyerFri, 04 Jan 2019 07:33:16 GMT
https://trac.sagemath.org/ticket/26966#comment:21
https://trac.sagemath.org/ticket/26966#comment:21
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/26966#comment:18" title="Comment 18">jhpalmieri</a>:
</p>
<blockquote class="citation">
<p>
Various methods rely on sorting
</p>
</blockquote>
<p>
Well, that's a problem. If things rely on sorting, then allowing the sort to fail is bad.
</p>
<p>
I much prefer either always sorting or never sorting to this "compromise" of trying to sort.
</p>
TicketjhpalmieriFri, 04 Jan 2019 17:58:02 GMT
https://trac.sagemath.org/ticket/26966#comment:22
https://trac.sagemath.org/ticket/26966#comment:22
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/26966#comment:21" title="Comment 21">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/26966#comment:18" title="Comment 18">jhpalmieri</a>:
</p>
<blockquote class="citation">
<p>
Various methods rely on sorting
</p>
</blockquote>
<p>
Well, that's a problem. If things rely on sorting, then allowing the sort to fail is bad.
</p>
</blockquote>
<p>
"Bad" is a bit strong. The answers can vary if the order varies (as will happen if the vertices are unsorted), but the answers will still be mathematically correct.
</p>
<blockquote class="citation">
<p>
I much prefer either always sorting or never sorting to this "compromise" of trying to sort.
</p>
</blockquote>
<p>
How much work should be put into this? You don't like it when I add a fallback to sort using <code>str</code>, so what do you suggest? And note that the compromise works pretty well. In practice, most simplicial complexes will have sortable vertices (either integers or tuples of integers). With the current branch, there are only two doctests with unpredictable results in Python 3: the one in <code>simplicial_set.py</code> now marked "random", and this:
</p>
<pre class="wiki"> sage: G = (S1.wedge(S1)).flip_graph()
sage: G.vertices(); G.edges(labels=False) # py2
[(0, 'L1'), (0, 'L2'), (0, 'R1'), (0, 'R2'), ('L1', 'L2'), ('R1', 'R2')]
[((0, 'L1'), (0, 'L2')),
((0, 'L1'), (0, 'R1')),
((0, 'L1'), (0, 'R2')),
((0, 'L1'), ('L1', 'L2')),
((0, 'L2'), (0, 'R1')),
((0, 'L2'), (0, 'R2')),
((0, 'L2'), ('L1', 'L2')),
((0, 'R1'), (0, 'R2')),
((0, 'R1'), ('R1', 'R2')),
((0, 'R2'), ('R1', 'R2'))]
</pre><p>
With Python 3, the vertices may be ordered randomly, and the same with the edges. Not a big deal, I think.
</p>
TicketjdemeyerFri, 04 Jan 2019 18:14:54 GMT
https://trac.sagemath.org/ticket/26966#comment:23
https://trac.sagemath.org/ticket/26966#comment:23
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/26966#comment:22" title="Comment 22">jhpalmieri</a>:
</p>
<blockquote class="citation">
<p>
the answers will still be mathematically correct.
</p>
</blockquote>
<p>
OK, in that case I misunderstood what you said in <a class="ticket" href="https://trac.sagemath.org/ticket/26966#comment:18" title="Comment 18">18</a>.
</p>
<p>
I would suggest then to not sort and just replace the doctest outputs with the different-but-equally-correct outputs.
</p>
TicketjhpalmieriTue, 08 Jan 2019 22:02:33 GMT
https://trac.sagemath.org/ticket/26966#comment:24
https://trac.sagemath.org/ticket/26966#comment:24
<p>
I was wrong about one thing: when you are dealing with the product of a simplicial complex K with itself, you have to sort the vertices in the product consistently with the sorting of the vertices in K, or else the diagonal map may not be defined properly. So we need some sort of sorting. I can see two easy options:
</p>
<ul><li>always sort using <code>key=str</code>. Consistent, but '10' comes before '9', which is a little annoying to me.
</li><li>test somehow to see if the vertices can be sorted well. Maybe just test to see if they are integers or tuples of integers (the most common cases) and sort those the default way. Sort using <code>key=str</code> in all other cases. I don't know of any way to force Python 2 to behave like Python 3 with regard to sorting. There is no analogue of <code>from __future__ import print_function</code> for sorting, is there?
</li></ul>
TicketjdemeyerWed, 09 Jan 2019 09:12:32 GMT
https://trac.sagemath.org/ticket/26966#comment:25
https://trac.sagemath.org/ticket/26966#comment:25
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/26966#comment:24" title="Comment 24">jhpalmieri</a>:
</p>
<blockquote class="citation">
<ul><li>always sort using <code>key=str</code>. Consistent, but '10' comes before '9', which is a little annoying to me.
</li></ul></blockquote>
<p>
Not guaranteed to be consistent either, since <code>str()</code> does not have to be an injective function:
</p>
<pre class="wiki">sage: L1 = [1.0 + 2^-52, 1.0]; L2 = reversed(L1)
sage: sorted(L1, key=str) == sorted(L2, key=str)
False
</pre>
TicketjhpalmieriWed, 09 Jan 2019 16:25:23 GMT
https://trac.sagemath.org/ticket/26966#comment:26
https://trac.sagemath.org/ticket/26966#comment:26
<p>
Any suggestions, then? I suppose we could delete all of the simplicial complex code.
</p>
TicketjhpalmieriWed, 09 Jan 2019 18:39:55 GMT
https://trac.sagemath.org/ticket/26966#comment:27
https://trac.sagemath.org/ticket/26966#comment:27
<p>
I could do the sort of test you gave: compare <code>sorted(vertices, key=str)</code> with <code>sorted(reversed(vertices), key=str)</code> (or using whatever key is appropriate). If this is <code>False</code>, print a warning when constructing the product of a complex with itself.
</p>
<p>
I don't know of any other case in which the sorting makes a difference. For homology, for example, the facets are sorted once in the <code>__init__</code> method, and that sorting is all that is necessary.
</p>
TicketjhpalmieriWed, 09 Jan 2019 18:54:43 GMT
https://trac.sagemath.org/ticket/26966#comment:28
https://trac.sagemath.org/ticket/26966#comment:28
<p>
And to confirm, if I create a simplicial complex with vertices with nonunique string representations and sort always using <code>key=str</code>, the diagonal map can break. With my own branch which sorts exclusively by str:
</p>
<pre class="wiki">sage: K = SimplicialComplex([[1.0 + 2^-52, 1.0]])
sage: L = K.product(K)
sage: d = Hom(K,L).diagonal_morphism()
sage: d.associated_chain_complex_morphism()
---------------------------------------------------------------------------
ValueError Traceback (most recent call last)
...
ValueError: matrices must define a chain complex morphism
</pre><p>
Edit: this case is actually worse because in the product <code>L</code>, the vertices are named using string representations, so there is only one vertex, not four, as there should be. (Each vertex is named <code>'L1.00000000000000R1.00000000000000'</code>, and since they all have the same name, they are viewed as the same vertex.) You can avoid this as follows:
</p>
<pre class="wiki">sage: K = SimplicialComplex([[1.0 + 2^-52, 1.0]])
sage: L = K.product(K, rename_vertices=False)
sage: d = Hom(K,L).diagonal_morphism(rename_vertices=False)
sage: d.associated_chain_complex_morphism()
---------------------------------------------------------------------------
ValueError Traceback (most recent call last)
...
ValueError: matrices must define a chain complex morphism
</pre><p>
Now the names of the vertices cause bad sorting, and so the purported map <code>d</code> does not induce a chain map as it should. This is the same problem that arises with other complexes if we don't sort at all.
</p>
TicketjdemeyerThu, 10 Jan 2019 08:46:32 GMT
https://trac.sagemath.org/ticket/26966#comment:29
https://trac.sagemath.org/ticket/26966#comment:29
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/26966#comment:26" title="Comment 26">jhpalmieri</a>:
</p>
<blockquote class="citation">
<p>
Any suggestions, then? I suppose we could delete all of the simplicial complex code.
</p>
</blockquote>
<p>
As I suggested several times: just don't sort at all. That's how we have been fixing other sorting-related bugs (for example in incidence structures, graphs, ...).
</p>
TicketdimpaseThu, 10 Jan 2019 12:30:23 GMT
https://trac.sagemath.org/ticket/26966#comment:30
https://trac.sagemath.org/ticket/26966#comment:30
<p>
Jeroen - this might need a novel definition for homology to work smoothly...
</p>
<p>
I'd say: always sort. This "unsortable" insanity of py3 has already taken its toll on the progress of porting to py3.
</p>
TicketjdemeyerThu, 10 Jan 2019 12:41:29 GMT
https://trac.sagemath.org/ticket/26966#comment:31
https://trac.sagemath.org/ticket/26966#comment:31
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/26966#comment:30" title="Comment 30">dimpase</a>:
</p>
<blockquote class="citation">
<p>
Jeroen - this might need a novel definition for homology to work smoothly...
</p>
</blockquote>
<p>
I think you are confusing two kinds of sorting introduced by this ticket.
</p>
<p>
One is the sorting using <code>vertex_to_index</code> which is perfectly fine. It allows consistent ordering of vertices which is indeed required for homology computations.
</p>
<p>
The sorting that I object to is this one:
</p>
<pre class="wiki"> try:
# If vertices can be sorted, sort them.
vertices = tuple(sorted(vertices))
except TypeError:
pass
</pre><p>
This shouldn't be needed for anything. It also adds (rather than solves) problems with porting to Python 3 since this code behaves differently on Python 2 and Python 3.
</p>
TicketjhpalmieriThu, 10 Jan 2019 16:06:22 GMT
https://trac.sagemath.org/ticket/26966#comment:32
https://trac.sagemath.org/ticket/26966#comment:32
<p>
The vertex sorting is needed but just for one thing: for the diagonal map <code>X -> X x X</code> to be defined properly. If you sort the vertices in the product incompatibly with the sorting in the original simplicial complex, you can end up with a square triangulated the wrong way, so the diagonal map is not a map of simplicial complexes. So you really do need to sort the vertices.
</p>
<p>
As Jeroen says in his last comment, the <code>vertex_to_index</code> dictionary is sufficient sorting for homology.
</p>
TicketjhpalmieriThu, 10 Jan 2019 16:09:39 GMT
https://trac.sagemath.org/ticket/26966#comment:33
https://trac.sagemath.org/ticket/26966#comment:33
<p>
Or maybe there is a way to use the <code>vertex_to_index</code> sorting when defining the product, although that take some work to implement. I'll have to think about that.
</p>
TicketgitFri, 11 Jan 2019 23:09:13 GMTcommit changed
https://trac.sagemath.org/ticket/26966#comment:34
https://trac.sagemath.org/ticket/26966#comment:34
<ul>
<li><strong>commit</strong>
changed from <em>6bb3e28d7a95cc11ec1dd7a1040fca1901d50d8d</em> to <em>f4a672c94202bae95cb00c07e7318211f50ca9b0</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=29ade7e2a0b376e2cf203ef7aa6126b094db5666"><span class="icon"></span>29ade7e</a></td><td><code>trac 26966: simplicial complexes: do not publicly sort vertices any more.</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=b32535053b87455000c3f6b6f227b5d436c295ca"><span class="icon"></span>b325350</a></td><td><code>trac 26966: Remove vertex_set. Use dict comprehension.</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=e79fd391f07fb49fd5bee4fbace4d1258065a5db"><span class="icon"></span>e79fd39</a></td><td><code>trac 26966: always sort vertices using key=str</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=f4a672c94202bae95cb00c07e7318211f50ca9b0"><span class="icon"></span>f4a672c</a></td><td><code>trac 26966: do not sort vertices. Allow the user to specify sort_facets,</code>
</td></tr></table>
TicketjhpalmieriFri, 11 Jan 2019 23:12:20 GMT
https://trac.sagemath.org/ticket/26966#comment:35
https://trac.sagemath.org/ticket/26966#comment:35
<p>
The last commit undoes a large part of the previous one, but oh well. This now does not sort vertices at all. It uses <code>sort_facets</code> as an optional argument to allow users to specify the dictionary which converts vertices to integers. This optional argument is only used when taking the product of a simplicial complex with itself. A few doctests had to be changed. In some cases, I knew what they were testing and could provide suitable replacements. In one (for <code>flip_graph</code>), it wasn't clear what the point was, so I replaced with something that I think captures the right spirit.
</p>
TicketgitFri, 11 Jan 2019 23:13:37 GMTcommit changed
https://trac.sagemath.org/ticket/26966#comment:36
https://trac.sagemath.org/ticket/26966#comment:36
<ul>
<li><strong>commit</strong>
changed from <em>f4a672c94202bae95cb00c07e7318211f50ca9b0</em> to <em>41eeaf587878efcdec3499b49353bfe1dfeb7993</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=41eeaf587878efcdec3499b49353bfe1dfeb7993"><span class="icon"></span>41eeaf5</a></td><td><code>typo</code>
</td></tr></table>
TicketjhpalmieriFri, 11 Jan 2019 23:18:56 GMT
https://trac.sagemath.org/ticket/26966#comment:37
https://trac.sagemath.org/ticket/26966#comment:37
<p>
I made a few other changes in here. For example, the change
</p>
<div class="wiki-code"><div class="code"><pre><span class="gu">@@ -1692,10 +1708,7 @@ class SimplicialComplex(Parent, GenericCellComplex):
</span> # construct a graph with one vertex for each facet, one edge
# when two facets intersect in a (d-1)-simplex, and see
# whether that graph is connected.
<span class="gd">- V = [f.set() for f in self.facets()]
- E = (lambda a, b: len(a.intersection(b)) == d)
- g = Graph([V, E])
- return g.is_connected()
</span><span class="gi">+ return self.flip_graph().is_connected()
</span>
def product(self, right, rename_vertices=True, is_mutable=True):
"""
</pre></div></div><p>
is an attempt to make the documentation for <code>flip_graph</code> correct: it says <code>The flip graph is used to detect if ``self`` is a pseudomanifold.</code>
</p>
TicketjhpalmieriFri, 11 Jan 2019 23:30:34 GMT
https://trac.sagemath.org/ticket/26966#comment:38
https://trac.sagemath.org/ticket/26966#comment:38
<p>
By the way, a few doctests were changed from a known output to a random output or to ellipses. In these cases, the answer will depend on, for example, how the vertices are sorted in
</p>
<pre class="wiki">vertex_to_index = {v:i for i,v in enumerate(vertices)}
</pre><p>
which is more or less random. It can certainly depend on whether you are using Python 2 vs. Python 3, and at least with Python 3, it will be random.
</p>
TickettscrimSun, 13 Jan 2019 17:36:15 GMT
https://trac.sagemath.org/ticket/26966#comment:39
https://trac.sagemath.org/ticket/26966#comment:39
<p>
Some minor comments:
</p>
<p>
Instead of <code>lambda x: vertex_to_index[x]</code>, you can use <code>vertex_to_index.__getitem__</code> (which I believe is faster).
</p>
<p>
Also, this <code>try</code> block is if the <code>max</code> is empty, right:
</p>
<div class="wiki-code"><div class="code"><pre> try:
idx = max(vertex_to_index.values()) + 1
except ValueError:
idx = 0
</pre></div></div><p>
so you should be able to do this:
</p>
<div class="wiki-code"><div class="code"><pre> <span class="k">if</span> vertex_to_index<span class="p">:</span>
idx <span class="o">=</span> <span class="nb">max</span><span class="p">(</span>vertex_to_index<span class="o">.</span>values<span class="p">())</span> <span class="o">+</span> <span class="mi">1</span>
<span class="k">else</span><span class="p">:</span>
idx <span class="o">=</span> <span class="mi">0</span>
</pre></div></div><p>
I would pull out the <code>self._translation_to_numeric()</code> call here so it is not called on every <code>key</code> call:
</p>
<pre class="wiki">simplex = Simplex(sorted(face, key=lambda x: self._translation_to_numeric()[x]))
</pre><p>
I think the latter syntax is easier to read (IIRC, it is also a little faster too):
</p>
<div class="wiki-code"><div class="code"><pre><span class="gd">-dict((g, i) for i, g in enumerate(gens))
</span><span class="gi">+{g: i for i, g in enumerate(gens)}
</span></pre></div></div><p>
You might also be able to simply do <code>dict(enumerate(gens))</code> too.
</p>
TicketgitSun, 13 Jan 2019 19:38:10 GMTcommit changed
https://trac.sagemath.org/ticket/26966#comment:40
https://trac.sagemath.org/ticket/26966#comment:40
<ul>
<li><strong>commit</strong>
changed from <em>41eeaf587878efcdec3499b49353bfe1dfeb7993</em> to <em>95f6026404128b5fb82ddc27aa741fd2c20a4978</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=95f6026404128b5fb82ddc27aa741fd2c20a4978"><span class="icon"></span>95f6026</a></td><td><code>trac 26966: minor code cleanup</code>
</td></tr></table>
TicketjhpalmieriSun, 13 Jan 2019 19:38:46 GMT
https://trac.sagemath.org/ticket/26966#comment:41
https://trac.sagemath.org/ticket/26966#comment:41
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/26966#comment:39" title="Comment 39">tscrim</a>:
</p>
<blockquote class="citation">
<p>
Some minor comments:
</p>
</blockquote>
<p>
[snip]
</p>
<blockquote class="citation">
<p>
I think the latter syntax is easier to read (IIRC, it is also a little faster too):
</p>
<div class="wiki-code"><div class="code"><pre><span class="gd">-dict((g, i) for i, g in enumerate(gens))
</span><span class="gi">+{g: i for i, g in enumerate(gens)}
</span></pre></div></div><p>
You might also be able to simply do <code>dict(enumerate(gens))</code> too.
</p>
</blockquote>
<p>
I agree with everything except the very last sentence: <code>dict(enumerate(gens))</code> would be equivalent to <code>{i:g for i,g in enumerate(gens)}</code>, but I want <code>g:i</code>, not <code>i:g</code>.
</p>
TickettscrimSun, 13 Jan 2019 20:29:49 GMT
https://trac.sagemath.org/ticket/26966#comment:42
https://trac.sagemath.org/ticket/26966#comment:42
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/26966#comment:41" title="Comment 41">jhpalmieri</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/26966#comment:39" title="Comment 39">tscrim</a>:
</p>
<blockquote class="citation">
<p>
I think the latter syntax is easier to read (IIRC, it is also a little faster too):
</p>
<div class="wiki-code"><div class="code"><pre><span class="gd">-dict((g, i) for i, g in enumerate(gens))
</span><span class="gi">+{g: i for i, g in enumerate(gens)}
</span></pre></div></div><p>
You might also be able to simply do <code>dict(enumerate(gens))</code> too.
</p>
</blockquote>
<p>
I agree with everything except the very last sentence: <code>dict(enumerate(gens))</code> would be equivalent to <code>{i:g for i,g in enumerate(gens)}</code>, but I want <code>g:i</code>, not <code>i:g</code>.
</p>
</blockquote>
<p>
Ah, right. I will try to finish the review in a day or two.
</p>
TicketembrayTue, 15 Jan 2019 18:15:21 GMTmilestone changed
https://trac.sagemath.org/ticket/26966#comment:43
https://trac.sagemath.org/ticket/26966#comment:43
<ul>
<li><strong>milestone</strong>
changed from <em>sage-8.6</em> to <em>sage-8.7</em>
</li>
</ul>
<p>
Retarging tickets optimistically to the next milestone. If you are responsible for this ticket (either its reporter or owner) and don't believe you are likely to complete this ticket before the next release (8.7) please retarget this ticket's milestone to sage-pending or sage-wishlist.
</p>
TickettscrimTue, 15 Jan 2019 22:41:01 GMT
https://trac.sagemath.org/ticket/26966#comment:44
https://trac.sagemath.org/ticket/26966#comment:44
<p>
Two additional things; everything else LGTM.
</p>
<ul><li><code>return tuple(self._vertex_to_index.keys())</code> is better as <code>return tuple(self._vertex_to_index)</code>
</li><li>In <code>product</code>, is there some way we can avoid creating two simplicial complexes? I imagine it is slower to do it twice. Why not for the first case return the simplicial complex and for the second use the <code>facets</code>?
</li></ul>
TicketjhpalmieriTue, 15 Jan 2019 23:10:48 GMT
https://trac.sagemath.org/ticket/26966#comment:45
https://trac.sagemath.org/ticket/26966#comment:45
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/26966#comment:44" title="Comment 44">tscrim</a>:
</p>
<blockquote class="citation">
<p>
Two additional things; everything else LGTM.
</p>
<ul><li><code>return tuple(self._vertex_to_index.keys())</code> is better as <code>return tuple(self._vertex_to_index)</code>
</li></ul></blockquote>
<p>
Sure, sounds good.
</p>
<blockquote class="citation">
<ul><li>In <code>product</code>, is there some way we can avoid creating two simplicial complexes? I imagine it is slower to do it twice. Why not for the first case return the simplicial complex and for the second use the <code>facets</code>?
</li></ul></blockquote>
<p>
Yes. I think when I first wrote this, I was going to use something produced by the <code>__init__</code> method and so I was constructing the simplicial complex to avoid code duplication. That doesn't seem to be the case any more, so you're right, I can just use <code>facets</code> in the second case.
</p>
TicketgitTue, 15 Jan 2019 23:12:29 GMTcommit changed
https://trac.sagemath.org/ticket/26966#comment:46
https://trac.sagemath.org/ticket/26966#comment:46
<ul>
<li><strong>commit</strong>
changed from <em>95f6026404128b5fb82ddc27aa741fd2c20a4978</em> to <em>3da1d0f108449360fb575d64be78eacf89109cd3</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=3da1d0f108449360fb575d64be78eacf89109cd3"><span class="icon"></span>3da1d0f</a></td><td><code>trac 26966: following reviewer suggestions to simplify a little code.</code>
</td></tr></table>
TickettscrimWed, 16 Jan 2019 00:26:21 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/26966#comment:47
https://trac.sagemath.org/ticket/26966#comment:47
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Jeroen Demeyer, Travis Scrimshaw</em>
</li>
</ul>
<p>
Thanks.
</p>
TicketjhpalmieriWed, 16 Jan 2019 00:42:12 GMT
https://trac.sagemath.org/ticket/26966#comment:48
https://trac.sagemath.org/ticket/26966#comment:48
<p>
Great, thanks for reviewing!
</p>
TicketvbraunWed, 23 Jan 2019 15:39:26 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/26966#comment:49
https://trac.sagemath.org/ticket/26966#comment:49
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>u/jhpalmieri/sorting-simplicial-complexes</em> to <em>3da1d0f108449360fb575d64be78eacf89109cd3</em>
</li>
</ul>
Ticket