Re: [sage-devel] Chvátal graph is Hamiltonian so why hamiltonian_cycle() says otherwise?
David Joyner
On Wed, Jun 16, 2010 at 6:42 AM, Minh Nguyen <nguye...@gmail.com> wrote:
> Hi folks,
>
> Here's a little bug in the method hamiltonian_cycle() of
> graphs/generic_graph.py, indeed also in is_hamiltonian() and
> traveling_salesman_problem(). Create the Chvátal graph or any graph
> that is known to be Hamiltonian and then call the method
> hamiltonian_cycle() on that graph:
>
> sage: version()
> 'Sage Version 4.4.4.alpha0, Release Date: 2010-06-07'
> sage: C = graphs.ChvatalGraph(); C
> Chvatal Graph: Graph on 12 vertices
> sage: C.hamiltonian_cycle()
> ---------------------------------------------------------------------------
> ValueError Traceback (most recent call last)
>
> /dev/shm/mvngu/sage-4.4.4.alpha0/<ipython console> in <module>()
>
> /dev/shm/mvngu/sage-4.4.4.alpha0/local/lib/python2.6/site-packages/sage/graphs/generic_graph.pyc
> in hamiltonian_cycle(self)
> 3881 return self.traveling_salesman_problem(weighted = False)
> 3882 except:
> -> 3883 raise ValueError("The given graph is not hamiltonian")
> 3884
> 3885 def flow(self, x, y, value_only=True, integer=False,
> use_edge_labels=True, vertex_bound=False, solver=None, verbose=0):
>
> ValueError: The given graph is not hamiltonian
>
> But surely the complete graph K_3 is Hamiltonian?
>
> sage: K3 = graphs.CompleteGraph(3); K3
> Complete graph: Graph on 3 vertices
> sage: K3.hamiltonian_cycle()
> ---------------------------------------------------------------------------
> ValueError Traceback (most recent call last)
>
> /dev/shm/mvngu/sage-4.4.4.alpha0/<ipython console> in <module>()
>
> /dev/shm/mvngu/sage-4.4.4.alpha0/local/lib/python2.6/site-packages/sage/graphs/generic_graph.pyc
> in hamiltonian_cycle(self)
> 3881 return self.traveling_salesman_problem(weighted = False)
> 3882 except:
> -> 3883 raise ValueError("The given graph is not hamiltonian")
> 3884
> 3885 def flow(self, x, y, value_only=True, integer=False,
> use_edge_labels=True, vertex_bound=False, solver=None, verbose=0):
>
> ValueError: The given graph is not hamiltonian
>
> So where's the bug? First, the error message is misleading because K_3
> = (V, E) is Hamiltonian, where V = {0, 1, 2} and E = {01, 02, 12} with
> a Hamiltonian cycle being 0,1,2. Second, when hamiltonian_cycle()
> invokes traveling_salesman_problem(), the latter doesn't even both
> with checking that GLPK or CBC is installed. In the case of
> hamiltonian_cycle() and is_hamiltonian(), these two methods use
> traveling_salesman_problem(). And traveling_salesman_problem() in turn
> uses GLPK or CBC to do the hard work. So if both GLPK or CBC are not
> installed, then the error message should say so. If the required
> optional package is installed, but the graph in question is not
> Hamiltonian, then the error message should correspond to the
> situation.
>
> --
> Regards
> Minh Van Nguyen, the graph theory tester
>
> --
> To post to this group, send an email to sage-...@googlegroups.com
> To unsubscribe from this group, send an email to sage-devel+...@googlegroups.com
> For more options, visit this group at http://groups.google.com/group/sage-devel
> URL: http://www.sagemath.org
>
David Joyner
> Hi David,
>
> On Wed, Jun 16, 2010 at 9:32 PM, David Joyner <wdjo...@gmail.com> wrote:
>> Do you have GLPK, CBC, or CPLEX installed?
>
> bug is that when neither of them, nor even CPLEX, is installed, the
> error message is misleading.
Oops. I didn't read your original post carefully enough. I agree.
I'm happy to test a patch for this.
>
> --
> Regards
> Minh Van Nguyen
>
Nathann Cohen
it is just another "Except MIPSolverException" I forgot !!! Just
adding this will solve the bug, as the lack of any solver returns the
exception "No solver installed"
Have you created a patch for this already ? If not, I'll do it
immediately ! :-)
Nathann
On Jun 16, 1:53 pm, Minh Nguyen <nguyenmi...@gmail.com> wrote:
> Hi David,
> On Wed, Jun 16, 2010 at 9:32 PM, David Joyner <wdjoy...@gmail.com> wrote:
> > Do you have GLPK, CBC, or CPLEX installed?
>
> bug is that when neither of them, nor even CPLEX, is installed, the
> error message is misleading.
>
Nathann Cohen
MixedIntegerLinearProgram.solve returns a ValueError when there is no
solver installed, and the traveling_salesman_problem method also
returns a ValueError when there is no hamiltonian cycle, so the
is_hamiltonian function has no way to make any difference between the
two.
What would you think of raising a NotImplementedError when there is no
solver installed instead ?
Nathann
On 16 June 2010 14:20, Minh Nguyen <nguye...@gmail.com> wrote:
> Hi Nathann,
>
> On Wed, Jun 16, 2010 at 10:18 PM, Nathann Cohen <nathan...@gmail.com> wrote:
>
> <SNIP>
>
>> Have you created a patch for this already ?
>
> Not yet. I have been waiting for confirmation from an expert :-)
>
>
>> If not, I'll do it
>> immediately ! :-)
>
> Sure, thank you.
>
> --
> Regards
> Minh Van Nguyen
>
Nathann Cohen
http://trac.sagemath.org/sage_trac/ticket/9249
Nathann
daveloeffler
On Jun 16, 1:31 pm, Nathann Cohen <nathann.co...@gmail.com> wrote:
> What would you think of raising a NotImplementedError when there is no
> solver installed instead ?
it just isn't installed :-)
The most "pythonic" solution is probably to add a new exception class
"OptionalPackageNotInstalledError", probably deriving from the Python
library's EnvironmentError. Python exceptions are class instances and
can be subclassed in the normal way. This is very easy to do; compare
sage/structure/coerce_exceptions.py, whose entire code is
class CoercionException(TypeError):
"""
[docstring]
"""
pass
Nathann Cohen
implemented "in the running version of Sage" ? :-p
Nathann
Dima Pasechnik
"NotImplemented" would make the user think that he's out of luck, and
has to
write his own code...
Dima
On Jun 16, 5:17 pm, Nathann Cohen <nathann.co...@gmail.com> wrote:
> Could I escape through saying that the functionality is not
> implemented "in the running version of Sage" ? :-p
>
> Nathann
>
Nathann Cohen
I sent the following email to Minh about the modifications it may mean :
########################
Hello Minh !!!
Just a question about this "OptionalPackageNotInstalledError"
exception mentionned about the bug you found in is_hamiltonian... It
sounds like it should be used in a lot of places if it is to become
the standard way of saying "install this package first". So two
questions :
* Where do you think it should be defined ?
* Can I really write a patch updating the whole Sage library for this
change ? It is the kind of patch that would quickly become
uncompatible with plenty of other patches, as it will touch plenty of
different files...
Thanksssssss !! :-)
#######################
Nathann
Nathann Cohen
http://trac.sagemath.org/sage_trac/ticket/9249
Thank you all for your help ! :-)
Nathann