#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 ncohen):
> 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.
Hmm.. I was about to answer "yes" when I noticed that your algorithm, even
though it may return an hamiltonian cycle when it finds one, will return
the longest path it found otherwise.. Hence, here is a proposition :
there is a file named graphs/generic_graph_pyx.pyx (which is a Cython
file), into which you could add your algorithm (using Cython to optimize
it if possible). The methods added to this class are not directly
accessible through the Graph class, which means that if you add your
algorithm there, it will not appear as methods of the graphs objects. What
you could do then, is add a method hamilton_cycle_heuristic and
longest_path_heuristic to the generic_graph class (unifying both directed
and undirected graphs), which would call your algorithm. The
hamilton_cycle_heuristic would call this algorithm and return the
hamiltonian path if found, and nothing otherwise. The hamiltonian_path
method would call your algorithm, and return its result as the longest
path found.
This, because otherwise people may not notice your
hamiltonian_cycle_heuristic can also be useful to find longest paths...
Well, this may be quite some work, but if I can help you at any step,
please tell me :-)
> 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.
Hmmm... I hope this could be very different after the algorithm is
rewritten using Cython :-)
> This sounds great! I have never implemented anything in Cython, but I'll
give it a try. :)
Well, if you know C, then Cython iss "just" a wonderful way to write C
instructions among Python code.. And the C parts are.. FAST :-D
I wrote an enumerative algorithm to find a given induced subgraph in a
large graph. If you want to give a look to its source code, it is located
in graphs/generic_graph_pyx.pyx. You will find there other examples of
Cython code, but it is mainly that : you can write C code in Python file.
Here again, send me an email if you think I can be of any assistance. Or
you can post on sage-devel, to obtain answers from more knowledgeable
developpers.
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/9698#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.
