Another doctest failure in sage/graphs/graphs.py

[qed777]

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.

CC: @dimpase @kcrisman @nathanncohen @rhinton @jasongrout

Component: doctest coverage

Issue created by migration from https://trac.sagemath.org/ticket/10081

[qed777]

comment:1

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.

[nathanncohen]

comment:2

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)
#8744

When the add_edge method was modified to suit BipartiteGraph
#8425

[kcrisman]

comment:5

Replying to @qed777:
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.

[nathanncohen]

comment:6

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