Sage: Ticket #14856: Bug in GenericGraph.vertex_connectivity when the digraph is a tournament
https://trac.sagemath.org/ticket/14856
<p>
The vertex-connectivity of a complete graph on k elements is defined to be equal to k-1. Unfortunately, this special case is also triggered when the input graph is directed, and that is a problem.
</p>
<p>
Nathann
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/14856
Trac 1.1.6ncohenFri, 05 Jul 2013 13:37:21 GMTstatus changed
https://trac.sagemath.org/ticket/14856#comment:1
https://trac.sagemath.org/ticket/14856#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
TicketdcoudertSun, 15 Sep 2013 09:31:56 GMTreviewer set
https://trac.sagemath.org/ticket/14856#comment:2
https://trac.sagemath.org/ticket/14856#comment:2
<ul>
<li><strong>reviewer</strong>
set to <em>David Coudert</em>
</li>
</ul>
<p>
Hello,
</p>
<p>
For me the patch is already good to go, but I have a few remarks
</p>
<ul><li>For directed graphs: can't we say that when <code>D.allows_loops()==False and D.allows_multiple_edges()==False and D.size()==D.order()*(D.order()-1)</code> then we can safely return N-1?
</li><li>Could you also get rid of the 0.0 and 1.0?
</li></ul><p>
David.
</p>
TicketncohenSun, 15 Sep 2013 12:44:20 GMT
https://trac.sagemath.org/ticket/14856#comment:3
https://trac.sagemath.org/ticket/14856#comment:3
<p>
What about this one ? The LP is actually infeasible when the input graph is complete, so it isn't only about optimization after all.
</p>
<p>
Nathann
</p>
TicketdcoudertSun, 15 Sep 2013 13:35:03 GMT
https://trac.sagemath.org/ticket/14856#comment:4
https://trac.sagemath.org/ticket/14856#comment:4
<p>
In the test <code>(g.is_directed() and g.size() >= (g.order()-1*g.order()) and all(g.has_edge(u,v) for u in g for v in g if v != u)))</code> you should add () around g.order()-1.
</p>
<p>
Furthermore, you should add the simple test I have proposed because it is way faster for digraphs without loops or multiple edges.
</p>
<p>
So the test could be:
</p>
<pre class="wiki">( g.is_directed() and g.size()>=(g.order()-1)*g.order() and
( (not g.allows_loops() and not g.allows_multiple_edges())
or all(g.has_edge(u,v) for u in g for v in g if v != u) ) )
</pre>
TicketncohenSun, 15 Sep 2013 14:13:05 GMT
https://trac.sagemath.org/ticket/14856#comment:5
https://trac.sagemath.org/ticket/14856#comment:5
<p>
Yoooooooooo !!
</p>
<blockquote class="citation">
<p>
In the test <code>(g.is_directed() and g.size() >= (g.order()-1*g.order()) and all(g.has_edge(u,v) for u in g for v in g if v != u)))</code> you should add () around g.order()-1.
</p>
</blockquote>
<p>
Oops.
</p>
<blockquote class="citation">
<p>
Furthermore, you should add the simple test I have proposed because it is way faster for digraphs without loops or multiple edges.
</p>
</blockquote>
<p>
Create a complete digraph, add a loop and compute the vertex connectivity --> an exception is raised by the LP solver. That's why I wrote this version instead.
</p>
<p>
Nathann
</p>
TicketdcoudertSun, 15 Sep 2013 14:29:47 GMT
https://trac.sagemath.org/ticket/14856#comment:6
https://trac.sagemath.org/ticket/14856#comment:6
<blockquote class="citation">
<blockquote class="citation">
<p>
Furthermore, you should add the simple test I have proposed because it is way faster for digraphs without loops or multiple edges.
</p>
</blockquote>
<p>
Create a complete digraph, add a loop and compute the vertex connectivity --> an exception is raised by the LP solver. That's why I wrote this version instead.
</p>
</blockquote>
<p>
Hmmmm.... I think you went too quickly on what I wrote: If you know that the digraph has N*(N-1) arcs <strong>and</strong> that loops and multiple arcs are forbidden, then you know that the digraph is a clique, isn't it? If loops or multiple edges are allowed, clearly you have to go through all edges.
</p>
<p>
Adding this simple test could save a lot of time.
</p>
TicketncohenSun, 15 Sep 2013 14:34:14 GMT
https://trac.sagemath.org/ticket/14856#comment:7
https://trac.sagemath.org/ticket/14856#comment:7
<blockquote class="citation">
<p>
Hmmmm.... I think you went too quickly on what I wrote:
</p>
</blockquote>
<p>
If the graph is a clique plus a loop, it does not satisfy your condition and gets solved by the LP. Which then raises an exception.
</p>
<p>
Do you mean that you want me to add both sets of constraints to the list ?
</p>
<p>
Nathann
</p>
TicketdcoudertSun, 15 Sep 2013 14:38:06 GMT
https://trac.sagemath.org/ticket/14856#comment:8
https://trac.sagemath.org/ticket/14856#comment:8
<blockquote class="citation">
<p>
Do you mean that you want me to add both sets of constraints to the list ?
</p>
</blockquote>
<p>
Yes! Testing these two booleans could avoid testing all edges, so it is interesting.
</p>
TicketncohenSun, 15 Sep 2013 14:42:52 GMT
https://trac.sagemath.org/ticket/14856#comment:9
https://trac.sagemath.org/ticket/14856#comment:9
<p>
Done. But that's very ugly code.
</p>
<p>
Nathann
</p>
TicketncohenSun, 15 Sep 2013 14:43:10 GMTattachment set
https://trac.sagemath.org/ticket/14856
https://trac.sagemath.org/ticket/14856
<ul>
<li><strong>attachment</strong>
set to <em>trac_14856.patch</em>
</li>
</ul>
TicketdcoudertSun, 15 Sep 2013 15:13:17 GMTstatus changed
https://trac.sagemath.org/ticket/14856#comment:10
https://trac.sagemath.org/ticket/14856#comment:10
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
I agree this is an ugly test, but it is efficient ;-)
</p>
<pre class="wiki">sage: G = DiGraph(graphs.CompleteGraph(10))
sage: %timeit G.vertex_connectivity()
100000 loops, best of 3: 4.98 us per loop
sage: G.allow_loops(True)
sage: G.add_edge(0,0)
sage: %timeit G.vertex_connectivity()
1000 loops, best of 3: 266 us per loop
</pre><p>
Install OK, functionality OK, test OK => the patch is good to go.
</p>
TicketjdemeyerTue, 01 Oct 2013 07:16:36 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/14856#comment:11
https://trac.sagemath.org/ticket/14856#comment:11
<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>merged</strong>
set to <em>sage-5.12.rc0</em>
</li>
</ul>
Ticket