#10205: Random test in sage.graphs.generic_graph_pyx.find_hamiltonian takes a
very
long time
-------------------------------+--------------------------------------------
Reporter: jdemeyer | Owner: mvngu
Type: defect | Status: needs_review
Priority: blocker | Milestone: sage-4.6.1
Component: doctest | Keywords: graph find_hamiltonian
Author: Minh Van Nguyen | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
-------------------------------+--------------------------------------------
Changes (by newvalueoldvalue):
* status: new => needs_review
* author: => Minh Van Nguyen
Comment:
The test can take a very long time because it's possible that a randomly
generated graph has a vertex of degree one. The warning in the
documentation of `find_hamiltonian()` says that the function could loop
endlessly when the input graph has a vertex of degree one. So something
like the following is likely to loop endlessly.
{{{
#!python
sage: from sage.graphs.generic_graph_pyx import find_hamiltonian as fh
sage: def long_test(n):
....: for i in range(n):
....: G = graphs.RandomGNP(20, 0.1)
....: _ = fh(G, find_path=True)
....:
sage: long_test(1)
}}}
We need to avoid using graphs that have a vertex of degree one. Something
like the following should reduce the runtime of the doctest.
{{{
#!python
sage: from sage.graphs.generic_graph_pyx import find_hamiltonian as fh
sage: for i in range(100): # long time
... G = graphs.RandomGNP(20, 0.1)
... while 1 in G.degree():
... G = graphs.RandomGNP(20, 0.1)
... _ = fh(G, find_path=True)
}}}
But even then, `graphs.RandomGNP(20, 0.1)` could generate a graph with a
vertex that has no out-neighbours. An exception similar to the following
would then be returned (see #10206):
{{{
#!python
sage: from sage.graphs.generic_graph_pyx import find_hamiltonian as fh
sage: G = graphs.RandomGNP(20, 0.1)
sage: while 1 in G.degree():
....: G = graphs.RandomGNP(20, 0.1)
....:
sage: fh(G, find_path=True)
(False, [1, 11, 16, 15, 12, 10, 9, 19, 13, 2, 7, 14, 8, 3, 0, 18, 5])
sage: fh(G, find_path=True)
(False, [14, 8, 3, 0, 18, 5, 7, 2, 13, 19, 1, 11, 16, 15, 12, 10, 9])
sage: fh(G, find_path=True)
(False, [9, 10, 12, 15, 16, 11, 1, 19, 13, 2, 7, 5, 18, 0, 3, 8, 14])
sage: fh(G, find_path=True)
---------------------------------------------------------------------------
ValueError Traceback (most recent call
last)
/dev/shm/mvngu/sage-4.6.1.alpha0/<ipython console> in <module>()
/dev/shm/mvngu/sage-4.6.1.alpha0/local/lib/python2.6/site-
packages/sage/graphs/generic_graph_pyx.so in
sage.graphs.generic_graph_pyx.find_hamiltonian
(sage/graphs/generic_graph_pyx.c:9771)()
/dev/shm/mvngu/sage-4.6.1.alpha0/local/lib/python2.6/site-
packages/sage/graphs/generic_graph_pyx.so in
sage.graphs.generic_graph_pyx.find_hamiltonian
(sage/graphs/generic_graph_pyx.c:8106)()
/dev/shm/mvngu/sage-4.6.1.alpha0/local/lib/python2.6/site-
packages/sage/misc/prandom.pyc in randint(a, b)
114 -46
115 """
--> 116 return _pyrand().randint(a, b)
117
118 def choice(seq):
/dev/shm/mvngu/sage-4.6.1.alpha0/local/lib/python/random.pyc in
randint(self, a, b)
226 """
227
--> 228 return self.randrange(a, b+1)
229
230 def _randbelow(self, n, _log=_log, int=int, _maxwidth=1L<<BPF,
/dev/shm/mvngu/sage-4.6.1.alpha0/local/lib/python/random.pyc in
randrange(self, start, stop, step, int, default, maxwidth)
202 return int(istart + int(self.random()*width))
203 if step == 1:
--> 204 raise ValueError, "empty range for randrange() (%d,%d,
%d)" % (istart, istop, width)
205
206 # Non-unit step argument supplied.
ValueError: empty range for randrange() (0,0, 0)
}}}
The attached patch makes sure that when choosing a random vertex, the
chosen vertex must have at least one out-neighbour. It also reduces the
runtime to a "reasonable" amount.
[[BR]][[BR]]
I came across a non-reproducible segfault with the following code:
{{{
#!python
sage: from sage.graphs.generic_graph_pyx import find_hamiltonian as fh
sage: def long_test(n):
....: for i in range(n):
....: G = graphs.RandomGNP(20, 0.1)
....: while 1 in G.degree():
....: G = graphs.RandomGNP(20, 0.1)
....: _ = fh(G, find_path=True)
....:
sage: %time long_test(200)
------------------------------------------------------------
Unhandled SIGSEGV: A segmentation fault occurred in Sage.
This probably occurred because a *compiled* component
of Sage has a bug in it (typically accessing invalid memory)
and is not properly wrapped with sig_on(), sig_off().
You might want to run Sage under gdb with 'sage -gdb' to debug this.
Sage will now terminate (sorry).
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10205#comment:5>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
