Opened 5 years ago

Closed 5 years ago

#16210 closed defect (fixed)

Bug in is_hamiltonian: wrong exceptions are caught

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.2
Component: graph theory Keywords:
Cc: Merged in:
Authors: Nathann Cohen Reviewers: Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: 0174081 (Commits) Commit: 0174081956989489785d578124675f22be0ed84c
Dependencies: Stopgaps:

Description (last modified by vdelecroix)

sage: g = graphs.CycleGraph(10)
sage: g.allow_loops(True)
sage: g.add_edge(0,0)
sage: g.is_hamiltonian()
False

This happens because in traveling_salesman_problem the call to _scream_is_not_simple raises a ValueError when the graph is not simple, and the same exception is raised when the graph is not hamiltonian.

We can use the EmptySetError to differentiate them, as we cannot optimize anything on an empty set.

Nathann

Change History (9)

comment:1 Changed 5 years ago by ncohen

  • Branch set to u/ncohen/16210
  • Description modified (diff)
  • Status changed from new to needs_review

comment:2 Changed 5 years ago by git

  • Commit set to 18122c535b0fe163cfa58d044b69c8b79849503a

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

18122c5trac #16210: Bug in is_hamiltonian: wrong exceptions are caught

comment:3 Changed 5 years ago by git

  • Commit changed from 18122c535b0fe163cfa58d044b69c8b79849503a to d69303cb818b864cc4d2ac95ccfb17f4cf9bf375

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

bf44a1ctrac #16210:: Merge into 6.2.rc0
d69303ctrac #16210: Broken doctest

comment:4 Changed 5 years ago by vdelecroix

  • Description modified (diff)
  • Reviewers set to Vincent Delecroix

Hi Nathann,

Why not a NonImplementedError (with a shorter message)?

Vincent

comment:5 Changed 5 years ago by ncohen

Because I am not sure that _scream_if_not_simple should always raise a NotImplementedError? in all functions that call it.

What is the problem with long messages ? They give more meaningful information.

Nathann

comment:6 Changed 5 years ago by vdelecroix

  • Branch changed from u/ncohen/16210 to public/16210

Let us go for long messages...

I simplified (I hope) the implementation of the function _scream... and correct the doctest in is_hamiltonian. Set it to positive review if you like it...

comment:7 Changed 5 years ago by git

  • Commit changed from d69303cb818b864cc4d2ac95ccfb17f4cf9bf375 to 0174081956989489785d578124675f22be0ed84c

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

0174081simpler implementation + corrected doctest

comment:8 Changed 5 years ago by ncohen

  • Status changed from needs_review to positive_review

AHahah. Well, it does more tests than in the first version, but I don't think this can ever become a very important problem :-P

Nathann

comment:9 Changed 5 years ago by vbraun

  • Branch changed from public/16210 to 0174081956989489785d578124675f22be0ed84c
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.