Opened 9 years ago

Closed 9 years ago

Last modified 9 years ago

#9249 closed defect (fixed)

Wrong answer in is_hamiltonian if no LP solver available

Reported by: ncohen Owned by: jason, mvngu, ncohen, rlm
Priority: major Milestone: sage-4.5
Component: graph theory Keywords:
Cc: mvngu Merged in: sage-4.5.alpha1
Authors: Nathann Cohen Reviewers: Robert Miller
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by ncohen)

is_hamiltonian always returned False when no LP solver was installed (as reported by Minh http://groups.google.com/group/sage-devel/browse_frm/thread/66b6459477590590)

This is fixed by the current patch. It also introduces a new module defining special Sage exceptions, as discussed in the same thread.

requires #9230

Nathann

Attachments (1)

trac_9249.patch (6.2 KB) - added by ncohen 9 years ago.

Download all attachments as: .zip

Change History (14)

comment:1 Changed 9 years ago by ncohen

  • Description modified (diff)
  • Status changed from new to needs_review

comment:2 Changed 9 years ago by ncohen

  • Description modified (diff)

Here it is ! We should also take care of updating the Developper's guide concerning the use of this new exceptions in another ticket.

Nathann

comment:3 Changed 9 years ago by wdj

This seems to be installing and passing tests okay but I'm not seeing any new docstring tests that correspond to the new code. Am I missing something? If not, I think more tests should be added (eg, Minh's OP on sage-devel in the thread cited above).

comment:4 follow-up: Changed 9 years ago by ncohen

Hmmm.... It is a bit hard to test, though. Minh's commands fails when no LP solver is installed. If we make a docstring for it, the docstring will pass when there is no solver installed, but as soon as a solver is, the doctest will fails. The problem is that we have a flag "optional CBC", but nothing like "optional NOT CBC" ;

Nathann

comment:5 in reply to: ↑ 4 Changed 9 years ago by wdj

Replying to ncohen:

Hmmm.... It is a bit hard to test, though. Minh's commands fails when no LP solver is installed. If we make a docstring for it, the docstring will pass when there is no solver installed, but as soon as a solver is, the doctest will fails. The problem is that we have a flag "optional CBC", but nothing like "optional NOT CBC" ;

Nathann

Good point!

I wonder what you think about this idea:

Add a not tested docstring (I've forgotten how you do that though) which has one test in the case when the package is loaded and another test in the case when the package is not. There there could be a remark that only one of these will trigger an error exception?

comment:6 Changed 9 years ago by ncohen

What do you think of this ? :-)

Nathann

Changed 9 years ago by ncohen

comment:7 Changed 9 years ago by rlm

  • Status changed from needs_review to positive_review

This looks good for now... Applies and passes tests. However, we should use dancing links (exact cover) for is_hamiltonian in general. It may actually turn out to be faster than MILP, I'm not sure. But then it would be a standard feature.

comment:8 follow-up: Changed 9 years ago by ncohen

You think it can be reduced to dancing links ?? O_o

How so ? O_o

I'm *very* interested !!

Nathann

comment:9 in reply to: ↑ 8 Changed 9 years ago by rlm

Replying to ncohen:

You think it can be reduced to dancing links ?? O_o

How so ? O_o

I'm *very* interested !!

Nathann

It might be a bit of a challenge. As Tom Boothby points out, bipartite matching can easily be reduced to dancing links. We should use that where we can, instead of using optional packages.

comment:10 Changed 9 years ago by ncohen

Well, I clearly agree for bipartite perfect matching, but for is_hamiltonian ? How the hell could we translate the "connexity" constraint ?

And... Well... :p

I know LP is optional in Sage, but... Well, there are now many important functions that use LP, so even if it is optional because of license problems, it is more and more part of Sage's graph library :p

Nathan

comment:11 Changed 9 years ago by davidloeffler

  • Authors set to Nathann Cohen
  • Reviewers set to Robert Miller

comment:12 Changed 9 years ago by rlm

  • Merged in set to sage-4.5.alpha1
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:13 Changed 9 years ago by mpatel

The patch here leads to a docbuild warning:

Warning: Missing title for sage.misc.exceptions

Please see #9571, a blocker for Sage 4.5.2.

Note: See TracTickets for help on using tickets.