Opened 6 years ago
Closed 6 years ago
#17410 closed defect (fixed)
unambiguously doctest longest_path()
Reported by: | charpent | Owned by: | |
---|---|---|---|
Priority: | trivial | Milestone: | sage-6.5 |
Component: | graph theory | Keywords: | |
Cc: | Merged in: | ||
Authors: | Emmanuel Charpentier | Reviewers: | Vincent Delecroix |
Report Upstream: | N/A | Work issues: | |
Branch: | 52c5c08 (Commits, GitHub, GitLab) | Commit: | 52c5c08ea0e189c25b2513f80a0355ecb421c713 |
Dependencies: | Stopgaps: |
Description
A doctest or longest_path() is ambiguous :
sage: l = [(0, 1), (0, 3), (2, 0)] sage: G = DiGraph(l) sage: G.longest_path().edges() [(0, 3, None), (2, 0, None)]
Starting with sage 6.5beta1, sage gives the equally valid answer
[(0, 1, None), (2, 0, None)]
but this is detected as a failure by sage ptestlong.
So let's use a problem with a unique solution.
Change History (10)
comment:1 Changed 6 years ago by
- Branch set to u/charpent/unambiguously_doctest_longest_path__
comment:2 Changed 6 years ago by
- Commit set to c39b6807ccd7662739eb02e9df5ced511c41ff39
- Status changed from new to needs_review
comment:3 Changed 6 years ago by
Hello,
Are you sure that it is unique ? Why the output can not be the same path in the other direction
[(3, 4, None), (2, 0, None), (0, 3, None)]
EDIT: it is not even sure that the list of edges is output in any sorted way, is it ?
You can at least test the length, or the vertices/edges as a set.
Vincent
comment:4 Changed 6 years ago by
- Commit changed from c39b6807ccd7662739eb02e9df5ced511c41ff39 to fcc15b40f515eef263f8afdc6c4d848fa28fead0
Branch pushed to git repo; I updated commit sha1. New commits:
fcc15b4 | Trac #17410: unambiguously doctest longest_path()
|
comment:5 Changed 6 years ago by
Damn. You're right. The path is unique (G is directed). But edges() has no special reason to sort them in any specified way. So the new version tests only set equality.
This passes "make ptestlong".
And you're co-author.
comment:6 Changed 6 years ago by
- Reviewers set to Vincent Delecroix
Hi Emmanuel,
I changed my status from author to reviewer. That's more reasonable.
why bool(something)
instead of something
like in
sage: p = G.longest_path() sage: set(p.edges(labels=False)) == {(0,3), (2,0), (3,4)} True
(and by the way, the option labels=False
of the method .edges
is really cool)
Sorry for being so picky.
Vincent
comment:7 Changed 6 years ago by
- Commit changed from fcc15b40f515eef263f8afdc6c4d848fa28fead0 to 52c5c08ea0e189c25b2513f80a0355ecb421c713
Branch pushed to git repo; I updated commit sha1. New commits:
52c5c08 | Trac #17410: unambiguously doctest longest_path()
|
comment:8 Changed 6 years ago by
New commit, up to reviewer's cosmetic wishes.
Passes "make ptestlong".
comment:9 Changed 6 years ago by
- Status changed from needs_review to positive_review
Wonderful ;-) Thanks.
Vincent
comment:10 Changed 6 years ago by
- Branch changed from u/charpent/unambiguously_doctest_longest_path__ to 52c5c08ea0e189c25b2513f80a0355ecb421c713
- Resolution set to fixed
- Status changed from positive_review to closed
Passes "make ptestlong"
New commits:
Trac #17410: unambiguously doctest longest_path()