Bug in DiGraph.longest_path

[nathanncohen]

Reported by Nicolas Thiery :

        sage: l = [(0, 1), (0, 3), (2, 0)]
        sage: G = DiGraph(l)
        sage: G.longest_path().edges()
        []

CC: @nthiery

Component: graph theory

Author: Nathann Cohen

Reviewer: Nicolas M. Thiéry

Merged: sage-5.10.beta2

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

[nathanncohen]

comment:1

Most stupig bug ever. I fixed it without noticing what I did, and it turns out that DiGraph.incoming_edges() can be called without any argument, which has no sensible meaning at all. Turns out that the code should have been calling incoming_edges(v) but called incoming_edges() instead -_-

Needs a review !

Nathann

(I also moved a "solver" argument from one place to another, as this is the way things are done nowadays with the LP backends)

[nathanncohen]

comment:3

(this patch also rewrites many lines using <= instead of min/max arguments. Easier to read.)

Nathann

[nthiery]

comment:4

Hi Nathann,

I just went through your patch, and it looks good. Thanks!

So positive review assuming all tests pass. I am going to kick to bot.

[fchapoton]

comment:5

This breaks the function "a_long_simple_root", see bot report

[nathanncohen]

comment:6

This breaks the function "a_long_simple_root", see bot report

That's crazy O_o

Nathann

[nathanncohen]

Attachment: trac_14412.patch.gz

[nathanncohen]

comment:7

Fixed ! I also had the pleasure to read things like that in root_lattice_realizations.py...

Caveat: this may be break in affine type `A_{2n}^{(2)}`
Caveat: meaningful/broken for non irreducible?
.. TODO:: This implementation is only valid in the root or weight lattice 

It's a long way.... >_<

Nathann

[nthiery]

comment:8

Replying to @nathanncohen:

Fixed !

Thanks! I checked it, and it's good.

I also had the pleasure to read things like that in root_lattice_realizations.py...

Caveat: this may be break in affine type `A_{2n}^{(2)}`
Caveat: meaningful/broken for non irreducible?
.. TODO:: This implementation is only valid in the root or weight lattice 

It's a long way.... >_<

Yes, the limitations of the algorithms are precisely documented. This in particular to prompt creative people to find better algorithms that will work in a more general setting (it's non trivial).

Amitiés.

[nathanncohen]

comment:10

Yoooooooooooo !

Yes, the limitations of the algorithms are precisely documented. This in particular to prompt creative people to find better algorithms that will work in a more general setting (it's non trivial).

(with birds singing in the background) it is indeed a delight to see this small piece of software grow everyday, becoming more powerful and accurate. Wouldn't it be nice though if those cases raised an exception ? Some forgetful users may not read the documentation. Some functions that use this one may not contain the warning in their docstring. Our innocent users may be led to believe that this method and those that may depend on it always returns correct results even though its docstring states the opposite.

And (without birds singing in the background) : it's not "other people's job" to add these tests in a code they did not write.

Nicolas. C'est dangereux ces trucs, tu sais bien... C'est des choses qu'on fait dans son code perso, pas dans du code qu'on partage.

Nathann

[jdemeyer]

Reviewer: Nicolas M. Thiéry

[jdemeyer]

Merged: sage-5.10.beta2