Opened 6 years ago
Closed 6 years ago
#17410 closed defect (fixed)
unambiguously doctest longest_path()
Reported by:  charpent  Owned by:  

Priority:  trivial  Milestone:  sage6.5 
Component:  graph theory  Keywords:  
Cc:  Merged in:  
Authors:  Emmanuel Charpentier  Reviewers:  Vincent Delecroix 
Report Upstream:  N/A  Work issues:  
Branch:  52c5c08 (Commits)  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 coauthor.
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()