Sage-Problem

[Hamed Sarvari]

Dear receiver,

please follow the attached file,
It is about a bug I encountered while using sage,
yours,
Hamed Sarvari

[Nathann Cohen]

Ooch ! That's bad indeed, and it is probably my fault...

Going to take a look at it !

By the way, please try to precise what the bug is about in the subject... For example "something wrong about graphs.DegreeSequenceBipartite".

(though it's very nice to report bugs in the first place !)

I'll tell you when I know where it comes from O_o

Nathann

[Nathann Cohen]

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

[Nathann Cohen]

There is now a track ticket for this bug !

http://trac.sagemath.org/sage_trac/ticket/11324

Nathann