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)
Change History (13)
comment:1 Changed 6 years ago by
- Status changed from new to needs_review
comment:2 Changed 6 years ago by
- Status changed from needs_review to needs_work
comment:3 Changed 6 years ago by
- 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
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: ↓ 6 Changed 6 years ago by
- 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
This breaks the function "a_long_simple_root", see bot report
That's crazy O_o
Nathann
Changed 6 years ago by
comment:7 follow-up: ↓ 8 Changed 6 years ago by
- 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
comment:8 in reply to: ↑ 7 ; follow-up: ↓ 10 Changed 6 years ago by
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 latticeIt'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.
comment:9 Changed 6 years ago by
- Status changed from needs_review to positive_review
comment:10 in reply to: ↑ 8 Changed 6 years ago by
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
- Reviewers set to Nicolas M. Thiéry
comment:12 Changed 6 years ago by
- Merged in set to sage-5.10.beta2
- Resolution set to fixed
- Status changed from positive_review to closed
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 callingincoming_edges(v)
but calledincoming_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)