Sage: Ticket #17225: Degrees of looped *immutable* graphs are wrong
https://trac.sagemath.org/ticket/17225
<p>
See <a class="ext-link" href="http://stackoverflow.com/questions/26566823/sage-python-bug-in-looped-graph-degree-computation"><span class="icon"></span>this SO question</a>.
</p>
<pre class="wiki">q=graphs.CompleteGraph(2)
q.allow_loops(True)
q.allow_multiple_edges(True)
q.add_edge([1,1])
a=q.copy(immutable=True)
b=q.copy(immutable=False)
sage: a==b
True
sage: a.degree()
[1, 2]
sage: b.degree()
[1, 3]
</pre><p>
Basically, the problem is that the usual backend has a case for this
</p>
<pre class="wiki"> if self._loops and self.has_edge(v, v, None):
if self._multiple_edges:
d += len(self.get_edge_label(v, v))
else:
d += 1
</pre><p>
but the "static" one doesn't.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/17225
Trac 1.1.6ncohenSun, 26 Oct 2014 11:43:25 GMT
https://trac.sagemath.org/ticket/17225#comment:1
https://trac.sagemath.org/ticket/17225#comment:1
<p>
HMmmmmm... Well, the thing is that it depends on what you want the degree to be. If you want the degree of a vertex to be equal to the number of edges incident to it, then it is correct.
</p>
<p>
If you want the number of edges to be twice the sum of degrees, then it is wrong.
</p>
<p>
Nathann
</p>
TicketncohenSun, 26 Oct 2014 14:11:32 GMTstatus changed; branch, author set
https://trac.sagemath.org/ticket/17225#comment:2
https://trac.sagemath.org/ticket/17225#comment:2
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>branch</strong>
set to <em>u/ncohen/17225</em>
</li>
<li><strong>author</strong>
set to <em>Nathann Cohen</em>
</li>
</ul>
<p>
Not sure that I ever mentionned it, but I hate loops, I hate labels and I hate multiple edges.
</p>
<p>
Nathann
</p>
TicketgitSun, 26 Oct 2014 14:13:38 GMTcommit set
https://trac.sagemath.org/ticket/17225#comment:3
https://trac.sagemath.org/ticket/17225#comment:3
<ul>
<li><strong>commit</strong>
set to <em>2810414d7f8c74ef2a71e4ac1b4a3809f18938db</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="http://git.sagemath.org/sage.git/commit/?id=2810414d7f8c74ef2a71e4ac1b4a3809f18938db"><span class="icon"></span>2810414</a></td><td><code>trac #17225: Degrees of looped *immutable* graphs are wrong</code>
</td></tr></table>
TicketgitSun, 26 Oct 2014 14:16:32 GMTcommit changed
https://trac.sagemath.org/ticket/17225#comment:4
https://trac.sagemath.org/ticket/17225#comment:4
<ul>
<li><strong>commit</strong>
changed from <em>2810414d7f8c74ef2a71e4ac1b4a3809f18938db</em> to <em>58cf24722664d1b299ab4de934455579125e3326</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="http://git.sagemath.org/sage.git/commit/?id=58cf24722664d1b299ab4de934455579125e3326"><span class="icon"></span>58cf247</a></td><td><code>trac #17225: Degrees of looped *immutable* graphs are wrong</code>
</td></tr></table>
TicketkcrismanSun, 26 Oct 2014 20:30:06 GMT
https://trac.sagemath.org/ticket/17225#comment:5
https://trac.sagemath.org/ticket/17225#comment:5
<blockquote class="citation">
<p>
HMmmmmm... Well, the thing is that it depends on what you want the degree to be. If you want the degree of a vertex to be equal to the number of edges incident to it, then it is correct.
</p>
<p>
If you want the number of edges to be twice the sum of degrees, then it is wrong.
</p>
</blockquote>
<p>
I mostly want immutable and mutable graphs to have the same behavior.
</p>
TicketncohenSun, 26 Oct 2014 21:42:17 GMT
https://trac.sagemath.org/ticket/17225#comment:6
https://trac.sagemath.org/ticket/17225#comment:6
<blockquote class="citation">
<p>
I mostly want immutable and mutable graphs to have the same behavior.
</p>
</blockquote>
<p>
Yesyes I understand. Well, I was rather happy to find a way to fix that without changing the internal data structure. I really did not want to add an "if" there, in a function that was just a substraction <code>:-)</code>
</p>
<p>
The only difference will be at Python level, so it does not matter much.
</p>
<p>
Nathann
</p>
TicketkcrismanMon, 27 Oct 2014 12:52:59 GMT
https://trac.sagemath.org/ticket/17225#comment:7
https://trac.sagemath.org/ticket/17225#comment:7
<blockquote class="citation">
<p>
Yesyes I understand. Well, I was rather happy to find a way to fix that without changing the internal data structure. I really did not want to add an "if" there, in a function that was just a substraction <code>:-)</code>
</p>
<p>
The only difference will be at Python level, so it does not matter much.
</p>
</blockquote>
<p>
Hmm, I see what you mean though, keeping track of all this extra data could be expensive when people are searching through really large sets of relatively large graphs (which is when this was implemented in the first place). I wonder if that will impact efficiency or speed.
</p>
TicketncohenMon, 27 Oct 2014 12:59:12 GMT
https://trac.sagemath.org/ticket/17225#comment:8
https://trac.sagemath.org/ticket/17225#comment:8
<p>
Hello !
</p>
<blockquote class="citation">
<p>
Hmm, I see what you mean though, keeping track of all this extra data could be expensive when people are searching through really large sets of relatively large graphs (which is when this was implemented in the first place). I wonder if that will impact efficiency or speed.
</p>
</blockquote>
<p>
You should not worry too much about that. Performance is wasted in other places, so this probably will not become a problem anytime soon.
</p>
<p>
The additional caching is only an array of ints of size n (no Python involved, just real integers). You waste MUCH more ressources if your graph carries a layout for its vertices, for instance ! <code>:-)</code>
</p>
<p>
Besides, it is indeed good that static graphs are MUCH lighter in memory than Sage's usual graphs, but it is not why they were implemented: the low-level data structure was implemented mostly for speed, because at this level you can work on the graph directly without calling any function, everything is as fast as it should be. They were later turned into an immutable Python object because the algebraists wanted graphs as dictionary keys.
</p>
<p>
The "main" problem though, is that immutable graphs are immutable, and consequently you can only build an immutable graph from a mutable graph (and the mutable graph is MUCH heavier in memory).
</p>
<p>
This, to say that this caching is not really a problem. What I wanted to avoid was to add a useless "if" in the 'degree' function of the low-level data structure. Fortunately, there is no such function for those graphs are implemented to actually be ... digraphs ! And there we only have an <code>out_degree</code> method, which is perfectly defined and only returns a difference of pointers. In particular, no ugly 'if' there <code>:-P</code>
</p>
<p>
Nathann
</p>
TicketkcrismanTue, 28 Oct 2014 15:26:06 GMT
https://trac.sagemath.org/ticket/17225#comment:9
https://trac.sagemath.org/ticket/17225#comment:9
<blockquote class="citation">
<p>
HMmmmmm... Well, the thing is that it depends on what you want the degree to be. If you want the degree of a vertex to be equal to the number of edges incident to it, then it is correct.
</p>
<blockquote class="citation">
<p>
If you want the number of edges to be twice the sum of degrees, then it is wrong.
</p>
</blockquote>
</blockquote>
<p>
See <a class="ext-link" href="http://en.wikipedia.org/wiki/Loop_(graph_theory)"><span class="icon"></span>here</a> and <a class="ext-link" href="http://en.wikipedia.org/wiki/Degree_(graph_theory)#cite_note-1"><span class="icon"></span>here</a>, which <em>claim</em> that this is a standard convention. I don't recall ever hearing a different convention for loops either, and for directed situations we should still be correct, right? Let me know if I'm missing a controversy on this - sometimes there are mutually incompatible definitions, most notoriously in my own classes for $\mathbb{N}$.
</p>
TicketncohenTue, 28 Oct 2014 17:51:38 GMT
https://trac.sagemath.org/ticket/17225#comment:10
https://trac.sagemath.org/ticket/17225#comment:10
<p>
Hello !
</p>
<p>
I assume that what this patch implements is the convention, as it is also what is contained in Wikipedia and books. I just hate conventions that cost running time and make dirty code.
</p>
<p>
Also, I am old enough to understand that people make the conventions that are the easiest for them, so I don't like to pay the price of other person's conventions.
</p>
<p>
But well, this one was cheap in terms of running time, so let's not complain <code>:-P</code>
</p>
<p>
Nathann
</p>
TicketkcrismanFri, 07 Nov 2014 17:42:39 GMT
https://trac.sagemath.org/ticket/17225#comment:11
https://trac.sagemath.org/ticket/17225#comment:11
<p>
For some reason this isn't merging properly. And I was going to look at it this afternoon, too...
</p>
TicketncohenSat, 08 Nov 2014 11:21:33 GMT
https://trac.sagemath.org/ticket/17225#comment:12
https://trac.sagemath.org/ticket/17225#comment:12
<p>
Hello !
</p>
<p>
That was because the line that imports bitsets changed in <a class="closed ticket" href="https://trac.sagemath.org/ticket/17196" title="enhancement: Relax assumptions on bitset operations (closed: fixed)">#17196</a>. Now, 'for simplicity reasons', we have data structures in structures/, data_structures/ and misc/.
</p>
<p>
Rebased !
</p>
<p>
Nathann
</p>
TicketgitSat, 08 Nov 2014 11:22:06 GMTcommit changed
https://trac.sagemath.org/ticket/17225#comment:13
https://trac.sagemath.org/ticket/17225#comment:13
<ul>
<li><strong>commit</strong>
changed from <em>58cf24722664d1b299ab4de934455579125e3326</em> to <em>47eb00bef23182e301612f6f7f387ee0b44714b9</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="http://git.sagemath.org/sage.git/commit/?id=47eb00bef23182e301612f6f7f387ee0b44714b9"><span class="icon"></span>47eb00b</a></td><td><code>trac #17225: Merged with 6.4.rc1</code>
</td></tr></table>
TicketkcrismanThu, 13 Nov 2014 19:51:36 GMT
https://trac.sagemath.org/ticket/17225#comment:14
https://trac.sagemath.org/ticket/17225#comment:14
<p>
Should
</p>
<pre class="wiki">+ cdef int i, tmp
</pre><p>
be
</p>
<pre class="wiki">+ cdef int i, j, tmp
</pre><p>
or is that not helpful?
</p>
<p>
Otherwise this seems good and behaves correctly.
</p>
<p>
However, I found <a class="closed ticket" href="https://trac.sagemath.org/ticket/17340" title="defect: can't plot immutable graphs (closed: fixed)">#17340</a> while reviewing this... sigh.
</p>
TicketkcrismanThu, 13 Nov 2014 19:56:26 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/17225#comment:15
https://trac.sagemath.org/ticket/17225#comment:15
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Karl-Dieter Crisman</em>
</li>
</ul>
TicketncohenFri, 14 Nov 2014 04:12:08 GMT
https://trac.sagemath.org/ticket/17225#comment:16
https://trac.sagemath.org/ticket/17225#comment:16
<p>
Hello !
</p>
<p>
Right right, this 'j' should appear too.
</p>
<p>
Could you add a commit, or fix it in <a class="closed ticket" href="https://trac.sagemath.org/ticket/17340" title="defect: can't plot immutable graphs (closed: fixed)">#17340</a> ? I am backpacking in Mumbai right now <code>:-)</code>
</p>
<p>
Nathann
</p>
TicketkcrismanFri, 14 Nov 2014 13:05:01 GMTstatus changed
https://trac.sagemath.org/ticket/17225#comment:17
https://trac.sagemath.org/ticket/17225#comment:17
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
I don't know how to fix <a class="closed ticket" href="https://trac.sagemath.org/ticket/17340" title="defect: can't plot immutable graphs (closed: fixed)">#17340</a>, so I can't do that. I can try to add this here, though.
</p>
<p>
Are you visiting Tata? Lucky you!
</p>
TicketkcrismanFri, 14 Nov 2014 13:13:24 GMTstatus, commit, branch changed
https://trac.sagemath.org/ticket/17225#comment:18
https://trac.sagemath.org/ticket/17225#comment:18
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>positive_review</em>
</li>
<li><strong>commit</strong>
changed from <em>47eb00bef23182e301612f6f7f387ee0b44714b9</em> to <em>4ab489733862b2d251b65ffaa864b57d3a49a528</em>
</li>
<li><strong>branch</strong>
changed from <em>u/ncohen/17225</em> to <em>u/kcrisman/17225</em>
</li>
</ul>
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=e5aef5c4f14b119fc4fe4405ce74cb50c879988c"><span class="icon"></span>e5aef5c</a></td><td><code>Merge branch 'u/ncohen/17225' of trac.sagemath.org:sage into loops</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=4ab489733862b2d251b65ffaa864b57d3a49a528"><span class="icon"></span>4ab4897</a></td><td><code>Minor reviewer patch</code>
</td></tr></table>
TicketncohenFri, 14 Nov 2014 14:25:02 GMT
https://trac.sagemath.org/ticket/17225#comment:19
https://trac.sagemath.org/ticket/17225#comment:19
<p>
Yo !
</p>
<blockquote class="citation">
<p>
I don't know how to fix <a class="closed ticket" href="https://trac.sagemath.org/ticket/17340" title="defect: can't plot immutable graphs (closed: fixed)">#17340</a>, so I can't do that.
</p>
</blockquote>
<p>
Come ooooooon. I am sure it takes something like one line to fix.
</p>
<blockquote class="citation">
<p>
I can try to add this here, though.
</p>
</blockquote>
<p>
Thanks !
</p>
<blockquote class="citation">
<p>
Are you visiting Tata? Lucky you!
</p>
</blockquote>
<p>
I visited some Tata museum, but that's all <code>:-P</code>
</p>
<p>
Nathann
</p>
TicketncohenFri, 14 Nov 2014 14:27:45 GMT
https://trac.sagemath.org/ticket/17225#comment:20
https://trac.sagemath.org/ticket/17225#comment:20
<p>
Actually I was wrong. Looks like <a class="closed ticket" href="https://trac.sagemath.org/ticket/17340" title="defect: can't plot immutable graphs (closed: fixed)">#17340</a> has lready bee fixed in the latest release. Must be one of the 1000 one-line fixes I made about the same problem.
</p>
<p>
Nathann
</p>
TicketkcrismanFri, 14 Nov 2014 15:15:34 GMT
https://trac.sagemath.org/ticket/17225#comment:21
https://trac.sagemath.org/ticket/17225#comment:21
<blockquote class="citation">
<p>
Actually I was wrong. Looks like <a class="closed ticket" href="https://trac.sagemath.org/ticket/17340" title="defect: can't plot immutable graphs (closed: fixed)">#17340</a> has lready bee fixed in the latest release. Must be one of the 1000 one-line fixes I made about the same problem.
</p>
</blockquote>
<p>
No, it was a typo in the description, my bad.
</p>
TicketvbraunSat, 15 Nov 2014 16:22:23 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/17225#comment:22
https://trac.sagemath.org/ticket/17225#comment:22
<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/kcrisman/17225</em> to <em>4ab489733862b2d251b65ffaa864b57d3a49a528</em>
</li>
</ul>
Ticket