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
