Empty graphs and new distance computations

[ncohen]

This patch fixes a "problem" with empty graphs when fed to the new distances computation methods added in #12052.

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 :-p

Nathann

[dcoudert]

Hi Nathann,

The patch is OK but incomplete. This is what is expected with your patch.

sage: G.shortest_path_all_pairs()
({}, {})

This is a missing part of your patch.

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: 

Happy new year ;-)

[ncohen]

Arggggg !!! Right, for graphs of small size the default algorithm is Floyd-Warshall... Sorry about that ! The patch is updated :-)

Nathann

[ncohen]

(and Happy new Year ! :-D)

Nathann

[dcoudert]

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.

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: 

[ncohen]

Helloooooo !!!

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 :-)

Nathann

[dcoudert]

OK, the patch is working correctly.

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.

Best, D.

[ncohen]

Hellooooooo !!!

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" :-)

Thanks for the review !!!

Nathann