#9698: Hamiltonian cycles in undirected graphs - backtracking algorithm.
----------------------------------+-----------------------------------------
Reporter: fidelbarrera | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-4.5.3
Component: graph theory | Keywords:
Author: Fidel Barrera-Cruz | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
----------------------------------+-----------------------------------------
Changes (by ncohen):
* status: needs_review => needs_work
Comment:
Hello Fidel !!
Well, first let me say that I am very glad to see you rewrote this piece
of code in Cython, to find out it greatly improved its performances `:-)`
I have been spending some time reading your code. I began by fixing one or
two typo, then ended up having more important remarks, so I will list them
as they sometimes need your answers :
* Your doctest is "too" indented. The normal text should be aligned
with the initial `"""` as for the other methods
* Your explanation of the algorithm would deserve to follow a
``ALGORITHM:`` line, as in ``subgraph_search``
* we are used to write ``OUTPUT:`` then its contents on the following
lines, and not as you do on the same line. There is no good reason behind,
that's just to keep the whole syntax in the whole code
* If you have time, it would be nice to give several comments along
with the examples `:-)`
* it may be nice to cache the list of vertices instead of calling
``g.verts()`` very often. A
{{{
cdef list vertices = g.verts()
}}}
is all it requires, and it lets you replace ``g.verts()`` by
``vertices`` elsewhere in the code
* I do not get why you list the possible extensions this way :
{{{
for u in g.out_neighbors( path[ length-1 ] ):
}}}
I expected the algorithm to pick a random neighbor which is not
already in the path at this step. Why don't you first build the list of
such elements, then pick one if there exists any ? As it is written, you
algorithm may ignore some paths, as it always picks the "first one" as
returned by the list of neighbors.
* I understand the usefulness of path reversing, or resetting, or
removing the last 5 vertices, but there is something else I do not
understand in your code : let us imagine that your algorithm, at each
loop, is increasing the current path from one element at each time for a
long period. At some point, your algorithm will reset it, or remove the
last vertices, even while it may still be possible to extend the path. Why
so ? A way around :
Given a current "path", there could be a method named
"greedily_extend" which, for as long as there exists a possible extension
of the path (a neighbor of the last vertex not already in the path), picks
one randomly and adds it to the path. This method ends when it is not
possible to greedily extend the path anymore. It is not a very costly
method, and at each iteration of it increases the current path's legngth,
which is good. Your counters could then be "when this method has been
called 100 times, remove the last 5", or reset, etc, etc... It would be a
way to avoid the path to be increased while it is possible because of the
counters (which are useful -- I do not deny this !). This would also avoid
the following :
* Each time a new vertex is added to the longest path, it is copied to
be remembered. It is nice, but if your algorithm begins by building a path
of length 20, you copy it 20 times ! By having a method like the previous
one, you would call it just once, when the path can not be extended
anymore.
* If your code finds a hamiltonian path whith is not a cycle, it ends
anyway.
* About
{{{
for row in G.adjacency_matrix():
}}}
Why don't you prefer to list G's edges ?
The answer to that one may have to do with the following :
* Here is what happens when the vertices of your graph are not
integers :
{{{
sage: from sage.graphs.generic_graph_pyx import find_hamiltonian as
fh
sage: fh(graphs.Grid2dGraph(5,5))
ERROR: An unexpected error occurred while tokenizing input
The following traceback may be corrupted or invalid
The error message is: ('EOF in multi-line statement', (636, 0))
ERROR: An unexpected error occurred while tokenizing input
The following traceback may be corrupted or invalid
The error message is: ('EOF in multi-line statement', (555, 0))
---------------------------------------------------------------------------
TypeError Traceback (most recent
call last)
/home/ncohen/<ipython console> in <module>()
/home/ncohen/.Sage/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:9109)()
/home/ncohen/.Sage/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:7609)()
TypeError: an integer is required
}}}
I have been told this an incredible amount of times myself `^^;`
Overall, I stll do not understand why you call it an heuristic to find a
hamiltonian cycle ! What you have written in a heuristic to find a
hamiltonian path, which tries to return a hamiltonian cycle. What about
renaming all of it accordingly ? What about writing a ``longest_path``
method ? I could write such a LP as an exact solver, and you could add
your heuristic to it, exactly as you did for hamiltonian_cycle. You method
is not only useful for hamiltonian cycle, but also for hamiltonian/longest
paths ! Please give me your advice on this.
Ok, this was a long review... Sorry for the time it requires... `^^;`. I
was away for one month and a half, but I should be more reactive now, and
by email too if necessary... Thank you very much for your work, though
`:-)`
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/9698#comment:11>
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.
