On Wed, May 11, 2011 at 5:45 AM, Nathann Cohen <[email protected]> wrote:
> 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 ! :-)
I wrote the code but the reviewer was a non-programmer who was
an expert on Gale-Ryser. This was the format he wanted.
He knows more than me so I didn't argue:-)
> 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 [email protected]
To unsubscribe from this group, send an email to
[email protected]
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
