Sage: Ticket #23290: Graph.merge_vertices() destroys loops
https://trac.sagemath.org/ticket/23290
<p>
merge_vertices() accepts a list of vertices as input, but loops are lost unless they're on the first vertex.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/23290
Trac 1.1.6zgershkoffWed, 21 Jun 2017 02:14:07 GMTdescription, component, priority, type changed; author, cc set
https://trac.sagemath.org/ticket/23290#comment:1
https://trac.sagemath.org/ticket/23290#comment:1
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/23290?action=diff&version=1">diff</a>)
</li>
<li><strong>author</strong>
set to <em>Zachary Gershkoff</em>
</li>
<li><strong>cc</strong>
<em>dcoudert</em> <em>tscrim</em> <em>Stefan</em> added
</li>
<li><strong>component</strong>
changed from <em>PLEASE CHANGE</em> to <em>graph theory</em>
</li>
<li><strong>priority</strong>
changed from <em>major</em> to <em>minor</em>
</li>
<li><strong>type</strong>
changed from <em>PLEASE CHANGE</em> to <em>defect</em>
</li>
</ul>
<pre class="wiki">sage: edgelist = [(0,0,'a'), (0,1,'b'), (1,1,'c')]
sage: G = Graph(edgelist, loops=True, multiedges=True)
sage: G.merge_vertices([0,1]); G.edges()
[(0,0,'a')]
</pre><p>
It looks like merge_vertices() works by computing the edge boundary between the specified set of vertices and the rest of the graph, then deleting all the vertices except the first one, then putting the edges back in.
</p>
<p>
So there are actually two issues here. (1) Loops not on the first vertex will be lost (because they're not in the edge boundary and their vertices get deleted), and (2) we'll lose other edges that are not in the edge boundary so they should become loops.
</p>
<p>
(1) is certainly a defect. I'm not so certain about (2) because I don't know if it's appropriate for this method to create loops. In fact, it's probably not.
</p>
TicketdcoudertWed, 21 Jun 2017 07:23:17 GMT
https://trac.sagemath.org/ticket/23290#comment:2
https://trac.sagemath.org/ticket/23290#comment:2
<p>
It is not an easy task to decide on the good behavior. See <a class="closed ticket" href="https://trac.sagemath.org/ticket/10357" title="enhancement: merge_vertices does not respect loops (closed: duplicate)">#10357</a> <a class="new ticket" href="https://trac.sagemath.org/ticket/9807" title="defect: merge_vertices behavior in a graph with loops (new)">#9807</a> <a class="closed ticket" href="https://trac.sagemath.org/ticket/7304" title="enhancement: Contract edge in graph (closed: fixed)">#7304</a> <a class="closed ticket" href="https://trac.sagemath.org/ticket/7159" title="defect: Graph.merge_vertices, and a bug in edge_boundary (closed: fixed)">#7159</a>.
</p>
TicketzgershkoffWed, 21 Jun 2017 21:23:06 GMT
https://trac.sagemath.org/ticket/23290#comment:3
https://trac.sagemath.org/ticket/23290#comment:3
<p>
In that case, I'll fix (1) and leave (2) for one of the other tickets.
</p>
TicketzgershkoffWed, 21 Jun 2017 22:36:40 GMTbranch set
https://trac.sagemath.org/ticket/23290#comment:4
https://trac.sagemath.org/ticket/23290#comment:4
<ul>
<li><strong>branch</strong>
set to <em>u/zgershkoff/graph_merge_vertices___destroys_loops</em>
</li>
</ul>
TicketzgershkoffWed, 21 Jun 2017 22:43:15 GMTstatus changed; commit set
https://trac.sagemath.org/ticket/23290#comment:5
https://trac.sagemath.org/ticket/23290#comment:5
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>commit</strong>
set to <em>412dc9082deb4ed0c7f14cdbee7a37950e0e51a7</em>
</li>
</ul>
<p>
It now checks if any of the (di)graph's loops are on the vertices to be deleted before deleting them, and it only adds a few steps if loops are disabled.
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=412dc9082deb4ed0c7f14cdbee7a37950e0e51a7"><span class="icon"></span>412dc90</a></td><td><code>moved loops from vertices before the vertices get deleted</code>
</td></tr></table>
TicketzgershkoffThu, 22 Jun 2017 17:10:16 GMT
https://trac.sagemath.org/ticket/23290#comment:6
https://trac.sagemath.org/ticket/23290#comment:6
<p>
Before this gets closed: There's code at the beginning of <code>merge_vertices()</code> to check if the first vertex label is <code>None</code>, but I don't think this will ever happen because of <a class="closed ticket" href="https://trac.sagemath.org/ticket/9362" title="defect: Invalidate None as a vertex label. (closed: fixed)">#9362</a>. Should I take those lines out?
</p>
<p>
Nevermind. A user may wish to input <code>None</code> as the first item in the list because this will give the merged vertex a new name.
</p>
TicketStefanFri, 23 Jun 2017 04:07:42 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/23290#comment:7
https://trac.sagemath.org/ticket/23290#comment:7
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Stefan van Zwam</em>
</li>
</ul>
<p>
Works as advertised!
</p>
TicketdcoudertSat, 24 Jun 2017 08:12:42 GMTstatus, reviewer changed
https://trac.sagemath.org/ticket/23290#comment:8
https://trac.sagemath.org/ticket/23290#comment:8
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
<li><strong>reviewer</strong>
changed from <em>Stefan van Zwam</em> to <em>Stefan van Zwam, David Coudert</em>
</li>
</ul>
<p>
This could be more efficient
</p>
<pre class="wiki"> u = vertices[0]
for v in vertices[1:]:
if self.has_edge(v, v):
if self.allows_multiple_edges():
for l in self.edge_label(v, v):
self.add_edge(u, u, l)
else:
self.add_edge(u, u, self.edge_label(v, v))
</pre><p>
Could you add a test to do nothing when <code>len(vertices) < 2</code>.
</p>
<pre class="wiki">sage: G = Graph()
sage: G.merge_vertices([None])
sage: G
Graph on 1 vertex
sage: G.merge_vertices([None])
sage: G
Graph on 2 vertices
</pre><p>
Other issue: <code>TESTS::</code> -> <code>TESTS:</code>
</p>
TicketdcoudertSat, 24 Jun 2017 08:18:52 GMT
https://trac.sagemath.org/ticket/23290#comment:9
https://trac.sagemath.org/ticket/23290#comment:9
<p>
Also, when multiedges are not allowed, the behavior must be documented.
</p>
<pre class="wiki">sage: edgelist = [(0,0,'a'),(0,1,'b'),(1,1,'c')]
sage: G = Graph(edgelist, loops=True, multiedges=False)
sage: G.merge_vertices([0,1]); G.edges()
[(0, 0, 'c')]
sage: edgelist = [(0,0,'a'),(0,1,'b'),(1,1,'c'), (1, 2, 'd'), (2, 2, 'e')]
sage: G = Graph(edgelist, loops=True, multiedges=False)
sage: G.merge_vertices([0,1,2]); G.edges()
[(0, 0, 'e')]
sage: G = Graph(edgelist, loops=True, multiedges=False)
sage: G.merge_vertices([0,2,1]); G.edges()
[(0, 0, 'e')]
</pre>
TicketzgershkoffSun, 25 Jun 2017 16:28:45 GMT
https://trac.sagemath.org/ticket/23290#comment:10
https://trac.sagemath.org/ticket/23290#comment:10
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/23290#comment:8" title="Comment 8">dcoudert</a>:
</p>
<blockquote class="citation">
<p>
This could be more efficient
</p>
<pre class="wiki"> u = vertices[0]
for v in vertices[1:]:
if self.has_edge(v, v):
if self.allows_multiple_edges():
for l in self.edge_label(v, v):
self.add_edge(u, u, l)
else:
self.add_edge(u, u, self.edge_label(v, v))
</pre></blockquote>
<p>
Is this faster because it specifies the vertices, rather than iterating over a list of edges to get the loops?
</p>
<blockquote class="citation">
<p>
Could you add a test to do nothing when <code>len(vertices) < 2</code>.
</p>
<pre class="wiki">sage: G = Graph()
sage: G.merge_vertices([None])
sage: G
Graph on 1 vertex
sage: G.merge_vertices([None])
sage: G
Graph on 2 vertices
</pre></blockquote>
<p>
It's an undocumented feature that <code>None</code> as the first entry will give the vertex a new name, and a bug that it will create a new vertex if there's nothing to merge. I'll addressed both.
</p>
<blockquote class="citation">
<p>
Other issue: <code>TESTS::</code> -> <code>TESTS:</code>
</p>
</blockquote>
<p>
Is there a guide where I can see how to correctly mark up documentation? The developer's guide doesn't seem to cover it all, and many of the other methods I've looked at use <code>TESTS::</code> and not <code>TESTS:</code>. This doesn't seem to be a standard thing for Python docstrings so I'm not sure where to look.
</p>
TicketdcoudertSun, 25 Jun 2017 17:50:44 GMT
https://trac.sagemath.org/ticket/23290#comment:11
https://trac.sagemath.org/ticket/23290#comment:11
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/23290#comment:10" title="Comment 10">zgershkoff</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/23290#comment:8" title="Comment 8">dcoudert</a>:
</p>
<blockquote class="citation">
<p>
This could be more efficient
</p>
<pre class="wiki"> u = vertices[0]
for v in vertices[1:]:
if self.has_edge(v, v):
if self.allows_multiple_edges():
for l in self.edge_label(v, v):
self.add_edge(u, u, l)
else:
self.add_edge(u, u, self.edge_label(v, v))
</pre></blockquote>
<p>
Is this faster because it specifies the vertices, rather than iterating over a list of edges to get the loops?
</p>
</blockquote>
<p>
The <code>loop_edges</code> method calls the <code>loop_vertices</code> method which returns <code>[v for v in self if self.has_edge(v,v)]</code> if loops are allowed.
</p>
<p>
Since <code>vertices</code> is a subset of the vertices of the graph, and we can expect this set to be small most of the time (e.g., 2), what I propose should be faster than your first proposal.
</p>
<p>
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
Could you add a test to do nothing when <code>len(vertices) < 2</code>.
</p>
</blockquote>
</blockquote>
<p>
</p>
<blockquote class="citation">
<blockquote class="citation">
<pre class="wiki">sage: G = Graph()
sage: G.merge_vertices([None])
sage: G
Graph on 1 vertex
sage: G.merge_vertices([None])
sage: G
Graph on 2 vertices
</pre></blockquote>
<p>
It's an undocumented feature that <code>None</code> as the first entry will give the vertex a new name, and a bug that it will create a new vertex if there's nothing to merge. I'll addressed both.
</p>
</blockquote>
<p>
It's documented in the method, 3rd paragraph: <code>The new vertex is named after the first vertex in the list given in argument. If this first name is None, a new vertex is created.</code>
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
Other issue: <code>TESTS::</code> -> <code>TESTS:</code>
</p>
</blockquote>
<p>
Is there a guide where I can see how to correctly mark up documentation? The developer's guide doesn't seem to cover it all, and many of the other methods I've looked at use <code>TESTS::</code> and not <code>TESTS:</code>. This doesn't seem to be a standard thing for Python docstrings so I'm not sure where to look.
</p>
</blockquote>
<p>
To be honest, I don't know. I checked on recent ticket, and <a class="closed ticket" href="https://trac.sagemath.org/ticket/23255" title="enhancement: cleaning some wrong rst block syntax (closed: fixed)">#23255</a> suggests that <code>TESTS::</code> is the good form. So keep it as is.
</p>
TicketgitSun, 25 Jun 2017 18:03:37 GMTcommit changed
https://trac.sagemath.org/ticket/23290#comment:12
https://trac.sagemath.org/ticket/23290#comment:12
<ul>
<li><strong>commit</strong>
changed from <em>412dc9082deb4ed0c7f14cdbee7a37950e0e51a7</em> to <em>ff571d6699ab233eedaf3b9d4a417ef6a1f6c56f</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=ff571d6699ab233eedaf3b9d4a417ef6a1f6c56f"><span class="icon"></span>ff571d6</a></td><td><code>efficiency improvements; bug fix when input is [None]</code>
</td></tr></table>
TicketzgershkoffSun, 25 Jun 2017 18:09:43 GMT
https://trac.sagemath.org/ticket/23290#comment:13
https://trac.sagemath.org/ticket/23290#comment:13
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/23290#comment:11" title="Comment 11">dcoudert</a>:
</p>
<blockquote class="citation">
<p>
To be honest, I don't know. I checked on recent ticket, and <a class="closed ticket" href="https://trac.sagemath.org/ticket/23255" title="enhancement: cleaning some wrong rst block syntax (closed: fixed)">#23255</a> suggests that <code>TESTS::</code> is the good form. So keep it as is.
</p>
</blockquote>
<p>
Judging from that ticket, the convention is to use <code>::</code> when <code>sage:</code> follows and <code>:</code> when text follows. So in this instance, I should indeed use <code>TESTS:</code>. The usage isn't consistent throughout the file but I'm not going to try and fix it within this ticket.
</p>
<p>
I made the changes you suggested, but I had to change one of the tests:
</p>
<pre class="wiki">sage: edgelist = [(0,0,'a'),(0,1,'b'),(1,1,'c'), (1, 2, 'd'), (2, 2, 'e')]
sage: G = Graph(edgelist, loops=True, multiedges=False)
sage: G.merge_vertices([0,1,2]); G.edges()
[(0, 0, 'e')]
sage: G = Graph(edgelist, loops=True, multiedges=False)
sage: G.merge_vertices([0,2,1]); G.edges()
[(0, 0, 'e')]
</pre><p>
I think the last output should be <code>[(0, 0, 'c')]</code>, and that's what the code currently returns, since it evaluates vertex <code>1</code> last and finds the label <code>'c'</code> last.
</p>
TicketzgershkoffSun, 25 Jun 2017 18:09:51 GMTstatus changed
https://trac.sagemath.org/ticket/23290#comment:14
https://trac.sagemath.org/ticket/23290#comment:14
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
TicketdcoudertSun, 25 Jun 2017 19:03:22 GMTstatus changed
https://trac.sagemath.org/ticket/23290#comment:15
https://trac.sagemath.org/ticket/23290#comment:15
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
That's much better now. Thanks.
</p>
TicketvbraunMon, 26 Jun 2017 21:24:41 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/23290#comment:16
https://trac.sagemath.org/ticket/23290#comment:16
<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/zgershkoff/graph_merge_vertices___destroys_loops</em> to <em>ff571d6699ab233eedaf3b9d4a417ef6a1f6c56f</em>
</li>
</ul>
TicketjdemeyerTue, 24 Oct 2017 15:10:44 GMTauthor changed; commit deleted
https://trac.sagemath.org/ticket/23290#comment:17
https://trac.sagemath.org/ticket/23290#comment:17
<ul>
<li><strong>commit</strong>
<em>ff571d6699ab233eedaf3b9d4a417ef6a1f6c56f</em> deleted
</li>
<li><strong>author</strong>
changed from <em>Zachary Gershkoff</em> to <em>Zach Gershkoff</em>
</li>
</ul>
Ticket