#10081: Another doctest failure in sage/graphs/graphs.py
-----------------------+----------------------------------------------------
Reporter: mpatel | Owner: mvngu
Type: defect | Status: new
Priority: blocker | Milestone: sage-4.6
Component: doctest | Keywords:
Author: | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
-----------------------+----------------------------------------------------
Changes (by ncohen):
* cc: rhinton (added)
Comment:
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
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10081#comment:2>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
