#9925 closed defect (fixed)
Doctest error in sage/graphs/graph.py
Reported by: | mpatel | Owned by: | mvngu |
---|---|---|---|
Priority: | major | Milestone: | sage-4.6 |
Component: | doctest coverage | Keywords: | |
Cc: | dimpase, edward.scheinerman, jason, kcrisman, mvngu, ncohen | Merged in: | sage-4.6.alpha2 |
Authors: | Nathann Cohen | Reviewers: | Dmitrii Pasechnik |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
I've seen this doctest error with a trial 4.6.alpha1 on sage.math and the Skynet machine cicero (x86-Linux-pentium4-fc):
sage -t -long devel/sage/sage/graphs/graph.py ********************************************************************** File "/mnt/usb1/scratch/mpatel/tmp/sage-4.6.alpha1/devel/sage-main/sage/graphs/graph.py", line 1347: sage: cycle.order() % 2 == 0 Exception raised: Traceback (most recent call last): File "/mnt/usb1/scratch/mpatel/tmp/sage-4.6.alpha1/local/bin/ncadoctest.py", line 1231, in run_one_test self.run_one_example(test, example, filename, compileflags) File "/mnt/usb1/scratch/mpatel/tmp/sage-4.6.alpha1/local/bin/sagedoctest.py", line 38, in run_one_example OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags) File "/mnt/usb1/scratch/mpatel/tmp/sage-4.6.alpha1/local/bin/ncadoctest.py", line 1172, in run_one_example compileflags, 1) in test.globs File "<doctest __main__.example_6[9]>", line 1, in <module> cycle.order() % Integer(2) == Integer(0)###line 1347: sage: cycle.order() % 2 == 0 AttributeError: 'bool' object has no attribute 'order' ********************************************************************** File "/mnt/usb1/scratch/mpatel/tmp/sage-4.6.alpha1/devel/sage-main/sage/graphs/graph.py", line 1349: sage: cycle.is_isomorphic(graphs.CycleGraph(cycle.order())) Exception raised: Traceback (most recent call last): File "/mnt/usb1/scratch/mpatel/tmp/sage-4.6.alpha1/local/bin/ncadoctest.py", line 1231, in run_one_test self.run_one_example(test, example, filename, compileflags) File "/mnt/usb1/scratch/mpatel/tmp/sage-4.6.alpha1/local/bin/sagedoctest.py", line 38, in run_one_example OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags) File "/mnt/usb1/scratch/mpatel/tmp/sage-4.6.alpha1/local/bin/ncadoctest.py", line 1172, in run_one_example compileflags, 1) in test.globs File "<doctest __main__.example_6[10]>", line 1, in <module> cycle.is_isomorphic(graphs.CycleGraph(cycle.order()))###line 1349: sage: cycle.is_isomorphic(graphs.CycleGraph(cycle.order())) AttributeError: 'bool' object has no attribute 'is_isomorphic' **********************************************************************
Attachments (1)
Change History (30)
comment:1 Changed 10 years ago by
comment:2 Changed 10 years ago by
Is this repeatable? I think I've seen this before, but it's always passed on the second try.
comment:3 Changed 10 years ago by
- Description modified (diff)
Oops. You're right. I confused this with a different error. I got error above only on sage.math and cicero.skynet (x86-Linux-pentium4-fc) and it's not reproducible.
I apologize for the noise. Does anyone know why this test might be "flaky"?
comment:4 Changed 10 years ago by
- Resolution set to worksforme
- Status changed from new to closed
comment:5 Changed 10 years ago by
Hmmm..... If cycle
is a boolean, it means it is equal to True (the method called returns "True", or a certificate that it is not true otherwise -- a graph object). I have already seen this method to return wrong answers (and this is fixed in #9420), but the code *IS* deterministic and in this case I do not understand why you would not get an error at the previous docstring :
sage: g.is_even_hole_free() True
which uses the same graph. Of course, this doctest is another one of the kind I'm trying to get rid off these days : it theoretically fails with a probability of 1/9999999999999999.... which means that it "can happen"... But once again, this would mean an error at the previous docstring too O_o
if you are finding yourself on one of the machines on which you have seen it failing, could you give this a try ?
sage: all( isinstance(graphs.RandomBipartite(10, 10, .5).is_even_hole_free(certificate = True), "Graph") for i in range(10000) )
Nathann
comment:6 Changed 10 years ago by
Hmmm.... It looks like it's not --so-- rare O_o
sage: sum( not isinstance(graphs.RandomBipartite(10, 10, .5).is_even_hole_free(certificate = True), Graph) for i in range(10000) ) 96
something like 1%...:-/
And with this :
sage: t = lambda x: Graph(x).is_forest() or isinstance(x.is_even_hole_free(certificate = True), Graph) sage: sum( not t(graphs.RandomBipartite(10, 10, .5)) for i in range(10000) ) 111
Which means it comes from .... the bug in the method subgraph_search, and not from the theoretical probability :-/
With the patch applied :
sage: sage: t = lambda x: Graph(x).is_forest() or isinstance(x.is_even_hole_free(certificate = True), Graph) sage: sage: sum( not t(graphs.RandomBipartite(10, 10, .5)) for i in range(10000) ) 0
Which relieved me. I should post a patch to add this is_forest condition anyway. Can I put it on this ticket ?
Nathann
comment:7 Changed 10 years ago by
- Status changed from closed to needs_work
go ahead, Nathann, add the patch...
comment:8 Changed 10 years ago by
Nathann, could you also add a doctest that does *boom* to the unpatched code?
comment:9 Changed 10 years ago by
I can do that, but this patch will require #9925 to be applied first... Here is the explanation : for the moment, the docstring works by generating a random bipartite graph, and looking for a cycle inside it. With a (very small) probability, this graph can be a forest, which means there is no cycle --> the doctest fails. This is not checked right now, and means that even though veeeery unlikely, it may fail because the generated graph is a forest. I can write a patch for this, and it will be available here in a second. The problem now, is that even if the graph is not a forest, a bug in subgraph_search may appear during the doctests (and does, with a probability of 1%). Even when the patch checking whether the graph is a forest will be applied, these errors will *STILL* appear until #9420 is applied.
I will then add a patch right now to test for forests, just in case, and another patch based upon #9420, to check this never appears again :-)
Nathann
Changed 10 years ago by
comment:10 Changed 10 years ago by
- Status changed from needs_work to needs_review
comment:11 Changed 10 years ago by
- Priority changed from blocker to major
comment:12 Changed 10 years ago by
- Status changed from needs_review to needs_work
I don't get how these lines in the doctest test anything.
... 1354 sage: print "Everything is Fine !" 1355 Everything is Fine !
Unless I am mistaken, they only indicate that the coder was in a jolly good mood while writing them :-)
comment:13 Changed 10 years ago by
First, you are right, then it was also to avoid having a docstring returning nothing on success, and returning "Error" on failure... It is just meant to say "this section has been run", and check that it was not bypassed for some reason.. Do you prefer it without this part ?
If so, tell me and I update it.
But I consider it a very pertinent information that Sage developpers have fun writing docstring, and the user may like to know it :-D
Nathann
comment:14 follow-up: ↓ 15 Changed 10 years ago by
Nathan, you do not *return* error, you just *print* "Error"! All that print stuff gets lost when running "sage -t", imho...
comment:15 in reply to: ↑ 14 Changed 10 years ago by
Nathan, you do not *return* error, you just *print* "Error"! All that print stuff gets lost when running "sage -t", imho...
Yes, but if the message "Error" is printed and the docstring doesn't expect it, an error will reported, won't it ? O_o
In case of failure, this piece of code will print :
Error ! Everything is fine !
While the code only expects to find "Everything is fine !".
Nathann
comment:17 Changed 10 years ago by
- Reviewers set to Dimitrii Pasechnik
comment:18 Changed 10 years ago by
- Reviewers changed from Dimitrii Pasechnik to Dmitrii Pasechnik
Typo, my apologies.
comment:19 Changed 10 years ago by
- Merged in set to sage-4.6.alpha2
- Resolution changed from worksforme to fixed
- Status changed from positive_review to closed
comment:20 follow-up: ↓ 22 Changed 10 years ago by
- Cc kcrisman added
Karl-Dieter Crisman reported this error on sage-release:
On OS X 10.4 PPC, I get a variant on #10042 (I put this on the ticket) and the toric divisor one, and a known Maxima timeout due to tab- completion. I also got the following non-repeating failure: File "/Users/student/Desktop/sage-4.6.alpha2/devel/sage/sage/graphs/graph.py", line 1346: sage: if not g.is_forest(): cycle = g.is_even_hole_free(certificate = True) if cycle.order() % Integer(2) == Integer(1): print "Error !" if not cycle.is_isomorphic( graphs.CycleGraph(cycle.order())): print "Error !" Exception raised: Traceback (most recent call last): File "/Users/student/Desktop/sage-4.6.alpha2/local/bin/ncadoctest.py", line 1231, in run_one_test self.run_one_example(test, example, filename, compileflags) File "/Users/student/Desktop/sage-4.6.alpha2/local/bin/sagedoctest.py", line 38, in run_one_example OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags) File "/Users/student/Desktop/sage-4.6.alpha2/local/bin/ncadoctest.py", line 1172, in run_one_example compileflags, 1) in test.globs File "<doctest __main__.example_6[8]>", line 1, in <module> if not g.is_forest():###line 1346: sage: if not g.is_forest(): File "/Users/student/Desktop/sage-4.6.alpha2/local/lib/python/site-packages/sage/graphs/generic_graph.py", line 1823, in is_forest for g in self.connected_components_subgraphs(): File "/Users/student/Desktop/sage-4.6.alpha2/local/lib/python/site-packages/sage/graphs/generic_graph.py", line 3136, in connected_components_subgraphs list.append(self.subgraph(c, inplace=False)) File "/Users/student/Desktop/sage-4.6.alpha2/local/lib/python/site-packages/sage/graphs/generic_graph.py", line 8170, in subgraph edge_property=edge_property) File "/Users/student/Desktop/sage-4.6.alpha2/local/lib/python/site-packages/sage/graphs/generic_graph.py", line 8279, in _subgraph_by_adding G.add_vertices(vertices) File "/Users/student/Desktop/sage-4.6.alpha2/local/lib/python/site-packages/sage/graphs/bipartite_graph.py", line 534, in add_vertices raise RuntimeError("Partition must be specified (e.g. left=True).") RuntimeError: Partition must be specified (e.g. left=True).
Dima and Nathann, could you look into this? If it's a new problem, please open a new 4.6 blocker with this in the description.
comment:21 Changed 10 years ago by
It's another of this SERGHLIGHLWIEUGH BipartiteGraph?-related errors --> they overload methods like add-edge to stay compatible. Usually wrapping the graph inside Graph(g) to cast it toward a regular graph is enough, but I'll give it a look only tomorrow. I have far too much of this wonderful red wine in the brain at the moment. You'll have a patch tomorrow -- sorry for that !
Nathann
comment:22 in reply to: ↑ 20 Changed 10 years ago by
Replying to mpatel:
Karl-Dieter Crisman reported this error on sage-release:
I saw the same non-repeating error on Skynet's fulvia (x86_64-SunOS-core2). The full log is here.
comment:23 follow-up: ↓ 24 Changed 10 years ago by
comment:24 in reply to: ↑ 23 Changed 10 years ago by
comment:25 Changed 10 years ago by
To be honest I have no idea at all of the probability in this case. I just followed the path of the code, and saw where it can only have happened. With patch #9422, the method is_forest does not call connected_components_subgraphs anymore, which clearly avoids the bug (caused by the subgraph method. adding edges in a BipartiteGraph? can lead to such exceptions). With #10067, the BipartiteGraph? class is not used anymore, which means that these checks when adding edges (creating the failure) are not done anymore.
My previous checks were all about being sure there was no mistake in subgraph_search, which is some not-so-trivial Cython code. In this case, the cause of the error is crystal clear :-)
Nathann
comment:26 Changed 10 years ago by
I don't have time to apply the patches, but without them, the code:
def example(verbose=False): try: g = graphs.RandomBipartite(10, 10, .5) g.is_even_hole_free() and not g.is_forest() if not g.is_forest(): cycle = g.is_even_hole_free(certificate = True) if cycle.order() % 2 == 1: print "Error !" if not cycle.is_isomorphic(graphs.CycleGraph(cycle.order())): print "Error !" error = False except RuntimeError as exc: error = True if verbose: print exc return error def runner(n=1000): fail = 0 for i in xrange(n): fail += example() return fail runner()
gives 20 or so failures. Could you check your patches against this or a similar statistical diagnostic?
comment:27 Changed 10 years ago by
You could also try, e.g.,
env SAGE_TEST_ITER=100 ./sage -tp -long devel/sage/sage/graphs/graph.py
on various files. I believe this will "break" on the first failure in a file. There's also SAGE_TEST_GLOBAL_ITER
. For this, I recommend capturing the output in a file and checking later for failures. Note: sage -tp
uses these variables, but sage -t
does not.
comment:28 Changed 10 years ago by
I've opened #10081 as a 4.6 blocker for the problem in comment 20.
comment:29 Changed 10 years ago by
Well, as you had taken the time to write this testing function, I tested it against the patches (with n = 10 000, as I was working on a sheet of paper at the same time and did not mind forgetting it for several minutes :-D
) :
With #9422 applied :
sage: runner(10000) 0
With no patch applied, but with
g = graphs.RandomBipartite(10, 10, .5)
replaced by
g = Graph(graphs.RandomBipartite(10, 10, .5))
in your code (which is exactly what the docstring in #10067 does) :
sage: runner(10000) 0
Be sure that this is not just a statistical proof : #9422 "disconnects" the call to the is_subgraph
command, so there is really no path left leading to this exception from BipartiteGraph? !
Nathann
P.S. : Thank you for this #!python
trick ! Very nice
;-)
If it's feasible to create a patch now, I can merge it into 4.6.alpha1, while I wait for a response to a build error at #4000.
Edward, could you add yourself to the account name-real name map?