Do you have GLPK, CBC, or CPLEX installed?
On Wed, Jun 16, 2010 at 6:42 AM, Minh Nguyen <nguyenmi...@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-devel@googlegroups.com
> To unsubscribe from this group, send an email to
> sage-devel+unsubscr...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/sage-devel
> URL: http://www.sagemath.org
>
--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
