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 )
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)
Change History (10)
comment:1 Changed 8 years ago by
- Description modified (diff)
- Status changed from new to needs_review
comment:2 Changed 8 years ago by
- Reviewers set to David Coudert
- Status changed from needs_review to needs_work
comment:3 Changed 8 years ago by
- 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
(and Happy new Year ! :-D
)
Nathann
comment:5 Changed 8 years ago by
- 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
- 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
comment:7 Changed 8 years ago by
- 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
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
- Merged in set to sage-5.0.beta0
- Resolution set to fixed
- Status changed from positive_review to closed
Hi Nathann,
The patch is OK but incomplete. This is what is expected with your patch.
This is a missing part of your patch.
Happy new year ;-)