#9698: Hamiltonian cycles in undirected graphs - backtracking algorithm.
----------------------------------+-----------------------------------------
Reporter: fidelbarrera | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_info
Priority: major | Milestone: sage-4.5.3
Component: graph theory | Keywords:
Author: Fidel Barrera-Cruz | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
----------------------------------+-----------------------------------------
Comment(by fidelbarrera):
Replying to [comment:2 ncohen]:
> Wow !!! This sounds great !! I promise I will give this patch a look as
soon as possible ! :-)
>
> I have a few questions already...
>
> * I noticed you mentionned in the doc that the backtrack algorithm may
not return an optimal hamiltonian path, but don't you think it may be
better to create another function for it, rather than having a method
whose answer may be exact or not depending on the algorithm used ?
Yes, this sounds OK. Would you think it is OK to call it
`hamilton_cycle_heuristic`? Please let me know if you have a better
suggestion for the name.
> * If your algorithm is fast enough, could it be interesting to check
when calling is_hamiltonian the answer given by your algorithm before
solving the actual tsp problem (which is sometimes veeeeeery long) ?
I am not sure about this. I believe the algorithm is pretty fast on
hamiltonian graphs whose vertices have low degree. But if not, the amount
of time spent searching depends on `max_iter`. For the current default
value of `max_iter`, it takes more than 20 seconds to stop searching for a
hamilton cycle in the Petersen graph. Trying with the tsp algorithm it
takes only 1/100 of a second.
> * Main question : as it is a backtracking algorithm, and this may
require a lot of computational work... What would you think of making it a
Cython function, to give t more energy ? :-)
This sounds great! I have never implemented anything in Cython, but I'll
give it a try. :)
>
> Thaaaanksssssssss ! :-)
>
> Nathann
Cheers,
Fidel
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/9698#comment:4>
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.
