Opened 10 years ago
Closed 10 years ago
#10081 closed defect (fixed)
Another doctest failure in sage/graphs/graphs.py
Reported by: | mpatel | Owned by: | mvngu |
---|---|---|---|
Priority: | blocker | Milestone: | sage-4.6 |
Component: | doctest coverage | Keywords: | |
Cc: | dimpase, kcrisman, ncohen, rhinton, jason | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
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).
This is a followup to #9925.
Release Manager
Apply the patch at #9422.
Change History (8)
comment:1 follow-up: ↓ 2 Changed 10 years ago by
comment:2 in reply to: ↑ 1 Changed 10 years ago by
- Cc rhinton added
Ok, I'm replying here to a good comment Dmitrii made on #10067 and for which I only have bad excuses.
This patch looks pretty weird. It essentially says that methods is_even_hole_free() and is_forest() cannot be applied to an instance of BipartiteGraph??. Why is that? Isn't BipartiteGraph?? inheriting from Graph?
IMHO it looks like you cure a symptom rather than the root of the problem.
So, first of all, you're right these patches cure only symptoms. The second patch is there to improve the efficiency of is_forest, so it is also there to do something useful, but the other one just fixes the docstring. Why ?
From what I know, Ryan developped this sub-class of the Graph class (you are right, it originally inherited the add_edge method from that class) to handle BipartiteGraph? that are to *stay bipartite*. At the moment, if you are working on a Complete Bipartite Graph of size 10,10 then taking its complement, what you will get is an exception, as the complement of such a graph is not bipartite. Because the add_edge method is *not* inherited anymore from Graph, many, many, many Graph functions can not be expected to work correctly on BipartiteGraph?, and for example the subgraph method. I first wanted to fix more than the symptoms by creating ticket #10068, which was meant to modify the bipartite_graph class by listing unreliable methods inherited from Graph and return "NotImplementedError?" exceptions when any of them is called. I finally settled against this when I noticed this would have made the class totally useless, and that the best way was to take the time to rewrite those methods inside of bipartite_graph. When I noticed this, I added a comment on that ticket to get it closed, then wrote an email to Ryan Hinton, who is to my knowledge the Sage developper who took care of this class until now.
I will break the suspense, I do not intend to do it myself. I can help, as usual, but I do not intend to do such a task by myself when the first thing I do whenever I get an instance of BipartiteGraph? is to cast it toward a Graph insance. It is not useful at all for what I do on graphs : the problem is not about bipartite graphs, I like them very much as they tend to signify "You have solved the problem you were working on, because if you have a bipartite graph you can do whatever you want on them as they have the most wonderful properties". The problem is that using this class implicitly assumes that you want your graph to *STAY* bipartite (and it is a bit worse, as the add_edge method from bipartite graph is not "theoretically" correct). Perhaps the best way to solve the source instead of the symptoms for the moment is to change the natural type of CompleteBipartiteGraph? and BipartiteGNP constructors to "Graph", as while they are bipartite graphs, they are not necessarily been built with in mind that they should stay this way.
Not that the subgraph method should work on them anyway, this is just something different that has to be addressed to make the bipartitegraph class consistent. It would let us, at least, remove many Graph casts from the docstrings, to prevent what we are dealing with now.
Nathann
About how the BipartiteGraph? class has been built : http://groups.google.com/group/sage-devel/browse_thread/thread/6a2ed79ea3bd7a02/51e331eba4441840?lnk=gst&q=bipartite+graphs#51e331eba4441840
About a problem I had using the complement method on bipartite graphs: http://groups.google.com/group/sage-devel/browse_thread/thread/1a4107f06b984f8f/d4f99e17fbd067f1?lnk=gst&q=bipartite+graphs#d4f99e17fbd067f1
A ticket to fix the add_edge method from bipartite graph (it is not even *theoretically* correct at the moment, it depends on the current "left" and "right" set) http://trac.sagemath.org/sage_trac/ticket/8744
When the add_edge method was modified to suit BipartiteGraph? http://trac.sagemath.org/sage_trac/ticket/8425
comment:3 Changed 10 years ago by
- Cc jason added
comment:4 follow-up: ↓ 5 Changed 10 years ago by
- Status changed from new to needs_review
comment:5 in reply to: ↑ 4 ; follow-up: ↓ 6 Changed 10 years ago by
Replying to mpatel: It's not quite clear to me what I do to review this. Do I just apply these two tickets and see if the doctest passes? I don't intend to review intense graph theory tickets.
comment:6 in reply to: ↑ 5 Changed 10 years ago by
Replying to kcrisman:
It's not quite clear to me what I do to review this. Do I just apply these two tickets and see if the doctest passes? I don't intend to review intense graph theory tickets.
I will ask Leonardo whether he can review #9422... Any of these two tickets is enough to fix the bug, and they are 3 lines long so it should not be too time-consuming :-)
Nathann
comment:7 Changed 10 years ago by
- Description modified (diff)
- Status changed from needs_review to positive_review
comment:8 Changed 10 years ago by
- Resolution set to fixed
- Status changed from positive_review to closed
According to comment 21ff at #9925, the patches at #9422 and #10067 should fix this problem. If they do, we should close this ticket when they're merged.