Opened 6 years ago

Closed 6 years ago

#14412 closed defect (fixed)

Bug in DiGraph.longest_path

Reported by: ncohen Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-5.10
Component: graph theory Keywords:
Cc: nthiery Merged in: sage-5.10.beta2
Authors: Nathann Cohen Reviewers: Nicolas M. Thiéry
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

Reported by Nicolas Thiery :

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

Attachments (1)

trac_14412.patch (10.5 KB) - added by ncohen 6 years ago.

Download all attachments as: .zip

Change History (13)

comment:1 Changed 6 years ago by ncohen

  • Status changed from new to needs_review

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)

comment:2 Changed 6 years ago by ncohen

  • Status changed from needs_review to needs_work

comment:3 Changed 6 years ago by ncohen

  • Status changed from needs_work to needs_review

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

Nathann

comment:4 Changed 6 years ago by nthiery

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.

comment:5 follow-up: Changed 6 years ago by chapoton

  • Status changed from needs_review to needs_work

This breaks the function "a_long_simple_root", see bot report

comment:6 in reply to: ↑ 5 Changed 6 years ago by ncohen

This breaks the function "a_long_simple_root", see bot report

That's crazy O_o

Nathann

Changed 6 years ago by ncohen

comment:7 follow-up: Changed 6 years ago by ncohen

  • Status changed from needs_work to needs_review

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

Last edited 6 years ago by ncohen (previous) (diff)

comment:8 in reply to: ↑ 7 ; follow-up: Changed 6 years ago by nthiery

Replying to ncohen:

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.

Last edited 6 years ago by nthiery (previous) (diff)

comment:9 Changed 6 years ago by nthiery

  • Status changed from needs_review to positive_review

comment:10 in reply to: ↑ 8 Changed 6 years ago by ncohen

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

comment:11 Changed 6 years ago by jdemeyer

  • Reviewers set to Nicolas M. Thiéry

comment:12 Changed 6 years ago by jdemeyer

  • Merged in set to sage-5.10.beta2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.