#9698: Hamiltonian cycles in undirected graphs - backtracking algorithm.
----------------------------------+-----------------------------------------
Reporter: fidelbarrera | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-4.6
Component: graph theory | Keywords:
Author: Fidel Barrera-Cruz | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
----------------------------------+-----------------------------------------
Changes (by fidelbarrera):
* status: needs_work => needs_review
Comment:
Replying to [comment:11 ncohen]:
Hello Nathann,
> 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 :
Thanks!
I have fixed the doctest indentation, added an ALGORITHM: line and fixed
the OUTPUT: line.
The vertices are now cached in !``vertices!``. And every vertex is picked
randomly, not as before, where the first available vertex was chosen.
> * 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 :
Here we rely on the !``backtrack_bound!`` and !``reset_bound!``, we should
give "appropriate" values.
> * 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.
Now, the longest path is only updated if the path cannot be extended
anymore.
> * If your code finds a hamiltonian path whith is not a cycle, it ends
anyway.
I think that when a hamiltonian path is found, we check if the two ends
are adjacent, if so, then it ends. The test is done in:
{{{
done = g.has_arc( path[n-1], path[0] )
}}}
It also takes longer with non hamiltonian graphs, e.g. the Petersen graph,
i.e. it stops until it hits the max_iter bound.
I think the problem with the vertices not being integers is fixed now
Although I did not get error messages as yours, I just got as output a
list of integer vertices.
I think I have removed the word heuristic. It would be great to write the
longest_path method. The function is almost exactly the same as the one
that is written, in fact it might be possible to adapt this one to do both
;)
Thanks,
Fidel
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/9698#comment:12>
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.
