#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 )
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)
Change History (14)
comment:1 Changed 9 years ago by
- Description modified (diff)
- Status changed from new to needs_review
comment:2 Changed 9 years ago by
- Description modified (diff)
comment:3 Changed 9 years ago by
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: ↓ 5 Changed 9 years ago by
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
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
What do you think of this ? :-)
Nathann
Changed 9 years ago by
comment:7 Changed 9 years ago by
- 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: ↓ 9 Changed 9 years ago by
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
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
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
- Reviewers set to Robert Miller
comment:12 Changed 9 years ago by
- 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
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.
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