Opened 8 years ago

Closed 8 years ago

#12244 closed defect (fixed)

Empty graphs and new distance computations

Reported by: ncohen Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-5.0
Component: graph theory Keywords:
Cc: dcoudert Merged in: sage-5.0.beta0
Authors: Nathann Cohen Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by 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

Attachments (1)

trac_12244.patch (3.9 KB) - added by ncohen 8 years ago.

Download all attachments as: .zip

Change History (10)

comment:1 Changed 8 years ago by ncohen

  • Description modified (diff)
  • Status changed from new to needs_review

comment:2 Changed 8 years ago by dcoudert

  • Reviewers set to David Coudert
  • Status changed from needs_review to needs_work

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

comment:3 Changed 8 years ago by ncohen

  • Status changed from needs_work to needs_review

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

Nathann

comment:4 Changed 8 years ago by ncohen

(and Happy new Year ! :-D)

Nathann

comment:5 Changed 8 years ago by dcoudert

  • Status changed from needs_review to needs_work

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: 

comment:6 Changed 8 years ago by ncohen

  • Status changed from needs_work to needs_review

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

Changed 8 years ago by ncohen

comment:7 Changed 8 years ago by dcoudert

  • Status changed from needs_review to positive_review

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.

comment:8 Changed 8 years ago by 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

comment:9 Changed 8 years ago by jdemeyer

  • Merged in set to sage-5.0.beta0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.