Sage: Ticket #12244: Empty graphs and new distance computations
https://trac.sagemath.org/ticket/12244
<p>
This patch fixes a "problem" with empty graphs when fed to the new distances computation methods added in <a class="closed ticket" href="https://trac.sagemath.org/ticket/12052" title="enhancement: Some distance computations remained *slow* (closed: fixed)">#12052</a>.
</p>
<p>
The cases "n == 0" are avoided, and some flags are added so that the exceptions are indeed forwarded by the C methods. They were not, which is the reason why it was not found before <code>:-p</code>
</p>
<p>
Nathann
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/12244
Trac 1.1.6ncohenSun, 01 Jan 2012 10:30:45 GMTstatus, description changed
https://trac.sagemath.org/ticket/12244#comment:1
https://trac.sagemath.org/ticket/12244#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/12244?action=diff&version=1">diff</a>)
</li>
</ul>
TicketdcoudertSun, 01 Jan 2012 21:37:29 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/12244#comment:2
https://trac.sagemath.org/ticket/12244#comment:2
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>reviewer</strong>
set to <em>David Coudert</em>
</li>
</ul>
<p>
Hi Nathann,
</p>
<p>
The patch is OK but incomplete.
This is what is expected with your patch.
</p>
<pre class="wiki">sage: G.shortest_path_all_pairs()
({}, {})
</pre><p>
This is a missing part of your patch.
</p>
<pre class="wiki">sage: G = Graph()
sage: G.distance_all_pairs()
---------------------------------------------------------------------------
ValueError Traceback (most recent call last)
/path-to-sage/sage-4.8.alpha5/devel/sage-myclone/<ipython console> in <module>()
/path-to-sage/sage-4.8.alpha5/local/lib/python2.6/site-packages/sage/graphs/generic_graph.pyc in distance_all_pairs(self, algorithm)
10574 elif algorithm == "Floyd-Warshall":
10575 from sage.graphs.distances_all_pairs import floyd_warshall
> 10576 return floyd_warshall(self,paths = False, distances = True)
10577
10578 else:
/path-to-sage/sage-4.8.alpha5/local/lib/python2.6/site-packages/sage/graphs/distances_all_pairs.so in sage.graphs.distances_all_pairs.floyd_warshall (sage/graphs/distances_all_pairs.c:6711)()
ValueError: max() arg is an empty sequence
sage:
</pre><p>
Happy new year ;-)
</p>
TicketncohenSun, 01 Jan 2012 22:41:14 GMTstatus changed
https://trac.sagemath.org/ticket/12244#comment:3
https://trac.sagemath.org/ticket/12244#comment:3
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
Arggggg !!! Right, for graphs of small size the default algorithm is Floyd-Warshall... Sorry about that ! The patch is updated <code>:-)</code>
</p>
<p>
Nathann
</p>
TicketncohenSun, 01 Jan 2012 22:42:13 GMT
https://trac.sagemath.org/ticket/12244#comment:4
https://trac.sagemath.org/ticket/12244#comment:4
<p>
(and Happy new Year ! <code>:-D</code>)
</p>
<p>
Nathann
</p>
TicketdcoudertMon, 02 Jan 2012 00:14:26 GMTstatus changed
https://trac.sagemath.org/ticket/12244#comment:5
https://trac.sagemath.org/ticket/12244#comment:5
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Sorry Nathann, but it's not enough :-p
All functions related to distances have to be fixed according to the proposed patch. I tried only one and get the following error, but for sure other functions are impacted.
</p>
<pre class="wiki">sage: G = Graph()
sage: G.average_distance()
---------------------------------------------------------------------------
ZeroDivisionError Traceback (most recent call last)
/path-to-sage/sage-4.8.alpha5/devel/sage-myclone/<ipython console> in <module>()
/path-to-sage/sage-4.8.alpha5/local/lib/python2.6/site-packages/sage/graphs/generic_graph.pyc in average_distance(self)
11634 """
11635
> 11636 return Integer(self.wiener_index())/Integer((self.order()*(self.order()-1))/2)
11637
11638 def szeged_index(self):
/path-to-sage/sage-4.8.alpha5/local/lib/python2.6/site-packages/sage/structure/element.so in sage.structure.element.RingElement.__div__ (sage/structure/element.c:12744)()
/path-to-sage/sage-4.8.alpha5/local/lib/python2.6/site-packages/sage/rings/integer.so in sage.rings.integer.Integer._div_ (sage/rings/integer.c:11987)()
/path-to-sage/sage-4.8.alpha5/local/lib/python2.6/site-packages/sage/rings/integer_ring.so in sage.rings.integer_ring.IntegerRing_class._div (sage/rings/integer_ring.c:5350)()
ZeroDivisionError: Rational division by zero
sage:
</pre>
TicketncohenMon, 02 Jan 2012 10:08:58 GMTstatus changed
https://trac.sagemath.org/ticket/12244#comment:6
https://trac.sagemath.org/ticket/12244#comment:6
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
Helloooooo !!!
</p>
<p>
Well, actually this bug has a different source : the "average distance" in a graph is the sum of the distances between each pair of nodes, divided by the number of pairs, and of course the "number of pairs" is zero when the graph has less than 2 vertices. It also seemed like "radius" had no meaning on empty graphs so I changed it too, but the other ones I checked were ok <code>:-)</code>
</p>
<p>
Nathann
</p>
TicketncohenMon, 02 Jan 2012 10:09:14 GMTattachment set
https://trac.sagemath.org/ticket/12244
https://trac.sagemath.org/ticket/12244
<ul>
<li><strong>attachment</strong>
set to <em>trac_12244.patch</em>
</li>
</ul>
TicketdcoudertMon, 02 Jan 2012 10:57:41 GMTstatus changed
https://trac.sagemath.org/ticket/12244#comment:7
https://trac.sagemath.org/ticket/12244#comment:7
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
OK, the patch is working correctly.
</p>
<p>
Concerning the radius / diameter / .... of the empty graph, this is a question of definitions: should it raise an error, or return 0, or +infty ???
I propose to let such question for future patchs according to others preferences.
</p>
<p>
Best,
D.
</p>
TicketncohenMon, 02 Jan 2012 11:01:15 GMT
https://trac.sagemath.org/ticket/12244#comment:8
https://trac.sagemath.org/ticket/12244#comment:8
<p>
Hellooooooo !!!
</p>
<p>
Agreed ! As for whether we should return 0 or +infty, I think the best behaviour is to raise an exception meaning "We could have returned 0, or returned +oo, but what you need to know is that the code probably isn't doing what you expect" <code>:-)</code>
</p>
<p>
Thanks for the review !!!
</p>
<p>
Nathann
</p>
TicketjdemeyerSun, 15 Jan 2012 21:57:59 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/12244#comment:9
https://trac.sagemath.org/ticket/12244#comment:9
<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.0.beta0</em>
</li>
</ul>
Ticket