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:

Status badges

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 charpent

  • Branch set to u/charpent/unambiguously_doctest_longest_path__

comment:2 Changed 6 years ago by charpent

  • Commit set to c39b6807ccd7662739eb02e9df5ced511c41ff39
  • Status changed from new to needs_review

Passes "make ptestlong"

New commits:

​c39b680Trac #17410: unambiguously doctest longest_path()

comment:3 Changed 6 years ago by vdelecroix

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

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

comment:4 Changed 6 years ago by git

  • Commit changed from c39b6807ccd7662739eb02e9df5ced511c41ff39 to fcc15b40f515eef263f8afdc6c4d848fa28fead0

Branch pushed to git repo; I updated commit sha1. New commits:

​fcc15b4Trac #17410: unambiguously doctest longest_path()

comment:5 Changed 6 years ago by charpent

  • Authors changed from Emmanuel Charpentier to Emmanuel Charpentier, Vincent Delecroix

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 vdelecroix

  • Authors changed from Emmanuel Charpentier, Vincent Delecroix to Emmanuel Charpentier
  • 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 git

  • Commit changed from fcc15b40f515eef263f8afdc6c4d848fa28fead0 to 52c5c08ea0e189c25b2513f80a0355ecb421c713

Branch pushed to git repo; I updated commit sha1. New commits:

​52c5c08Trac #17410: unambiguously doctest longest_path()

comment:8 Changed 6 years ago by charpent

New commit, up to reviewer's cosmetic wishes.

Passes "make ptestlong".

comment:9 Changed 6 years ago by vdelecroix

  • Status changed from needs_review to positive_review

Wonderful ;-) Thanks.

Vincent

comment:10 Changed 6 years ago by vbraun

  • Branch changed from u/charpent/unambiguously_doctest_longest_path__ to 52c5c08ea0e189c25b2513f80a0355ecb421c713
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.