Hello again !
So, the problem is clear !
It comes from an error in the method gale_ryser_theorem. This theorem is
actually about filling a matrix with 0 and 1 when you know the number of 1
in each column and in each row, and this is totally equivalent to creating a
bipartite graph with a given degree sequence.
In the end, the function DegreeSequenceBipartite is almost an empty shell,
and here is its code :
from sage.combinat.integer_vector import gale_ryser_theorem
from sage.graphs.bipartite_graph import BipartiteGraph
s1 = sorted(s1, reverse = True)
s2 = sorted(s2, reverse = True)
m = gale_ryser_theorem(s1,s2)
if m is False:
raise ValueError("There exists no bipartite graph corresponding
to the given degree sequences")
else:
return BipartiteGraph(m)
So it just calls gale_ryser_theorem and lets it do its job. There is no
error in this function, just in the gale_ryser_theorem, as you can see :
sage: gale_ryser_theorem([2,2,1],[2,2,1])
[1 1 0]
[1 0 1]
[1 0 0]
There is a column with three 1, and that shouldn't happen.
Luckily, there are two different implementations of this gale_ryser_theorem
function. So if instead of this, you call :
sage: gale_ryser_theorem([2,2,1],[2,2,1], algorithm="gale")
[1 1 0]
[1 0 1]
[0 1 0]
It works way better ! :-)
Besides, this method is faster, at least on this example :
sage: %timeit gale_ryser_theorem([2,2,1],[2,2,1], algorithm="ryser")
25 loops, best of 3: 12.3 ms per loop
sage: %timeit gale_ryser_theorem([2,2,1],[2,2,1], algorithm="gale")
125 loops, best of 3: 5.25 ms per loop
We can fix this bug by just adding algorithm="gale" in this
DegreeSequenceBipartite function, but of course this wouldn't fix the
problem in the gale_ryser_theorem function, which requires more care.
Well, in the end, and before a patch is written for this bug (thank you very
much for reporting it -- don't hesitate to do it again), you can create the
bipartite graphs you want by using this code :
def degree_sequence_bipartite(s1, s2):
from sage.combinat.integer_vector import gale_ryser_theorem
from sage.graphs.bipartite_graph import BipartiteGraph
s1 = sorted(s1, reverse = True)
s2 = sorted(s2, reverse = True)
m = gale_ryser_theorem(s1,s2, algorithm="gale")
if m is False:
raise ValueError("There exists no bipartite graph corresponding
to the given degree sequences")
else:
return BipartiteGraph(m)
Oh, and by the way, creating a graph
using A=BipartiteGraph(graphs.DegreeSequence([2,2,2,2,1,1])) is incorrect.
The DegreeSequence function gives you "a graph that matches the given degree
sequence". You are right, there is a bipartite graph matching this sequence,
but this specific method just returns "a graph (any)" that matches the
degree sequence. And there are also non-bipartite graphs matching this
degree sequence (for example the one it returns :-D).
Of course, when you type BipartiteGraph(a_non_bipartite_graph), Sage does
not know how to make a BipartiteGraph out of a non-bipartite Graph. That's
just a conversion problem, but that's how it is meant to work :-)
Have fuuuuuuuuun !!!
Nathann
--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
