# Simple example of finding Hamiltonian path using Google OR-Tools?

I'd like to test how good/fast OR-Tools is in finding hamiltonian paths on some (big) directed graphs. But I can't find simple enough (for me) examples.

Something like these ones (or even simpler), usuable by beginners like me:

I made a very basic example to illustrate my question, could someone show me how to code it with OR-tools (a Python example would be easier for me, but I’ll probably be able to understand an example in another language):

Given this directed graph:

I want OR-tools to give me the hamiltonian path connecting all the vertices (that is: A->C->B) :

• Note that the routing solver is not tuned for large pure TSP. It is meant for more complex problems (time windows, capacity, pickup and delivery) with small to medium size. As is, it is not a competitor of the like of Concorde. Mar 7 at 9:28
• Maybe my question was not clear, but if there's no way or option in the routing solver which guarantees (for not-too-big graphs, or given enough time or ressources ...) to give a hamiltonian path when one exists, then I don't want a "nearly hamiltonian path", I prefer to have nothing. I'm new to or-tools, but given the class name "HamiltonianPathSolver", I thought that this class might be the good tool to find hamiltonian paths in graphs. I'm just looking for very simple examples to start (like the one I'm suggesting in my question). Mar 7 at 21:57
• The hamiltonian path solver is a Dynamic Programming implementation. It scales up to 23 nodes I believe, and is used as a sub-procedure during solver. Mar 8 at 8:05
• Do you mean that HamiltonianPathSolver is not a class meant to be used by the user/programmer, but is only used (internally) by the or-tools solver ? Mar 8 at 9:01
• you can use it. It will blow up in memory very fast. Mar 8 at 9:03

You can use OR-tools' routing library, and more specifically the TSP solver, with the Python API.

Note that since you do not want the last arc in your example, you are solving an open TSP. You can modify the distance matrix, as explained here.

• I'm not sure this TSP example can be adapted to my case. How can we specify that we can't go from B to A ? A 0-value, a negative or a None value ? Because with just a lot of 0 in distance_matrix, it should lead to bad solutions like B->C->A (where path length = 0) ? And are there not more efficient libraries to do the job ? Something in the HamiltonianPathSolver class maybe ? Something more topological than euclidean ? And I'm adding a "graph" tag to my question, I should have thought about that earlier. Mar 7 at 10:40
• Oh, I could use huge numbers (or some Python infinity number, maybe) in distance_matrix to pratically forbid the use of some edges. But that does't seem very clean... I'll try that. Mar 7 at 11:07
• yes, exactly, this will work. Mar 7 at 12:39
• Can I specify that I (really) want a/the best solution (which has to be a hamiltonian path, even it takes much time to compute), or nothing, rather than some good-TSP-solution which is not a hamiltonian path ? I can't find it in the options there : developers.google.com/optimization/routing/routing_options. I used a 40-nodes graph, which I know has a hamiltonian path, but OR-tools immediately gives me a bad solution (not a hamiltonian path, but 2 strangely glued hamiltonian paths). Mar 7 at 15:47
• ortools + routing solves the Hamiltonian path problem, just not necessarily optimally. No solver can guarantee this for every graph. Mar 7 at 20:40

After reading some examples, I thought that I could use the AddAllowedAssignments constraint. I found some examples, and came up with a solution to my question, so here it is (I just renamed the nodes 0,1,2 instead of A,B,C).

Adapting it to the ~40 nodes graph I mentionned in a comment, this also (instantly) gave me the exact hamiltonian path I expected for that graph.

# Goal : To find a hamiltonian path in a directed graph
# The vertices are 0, 1 and 2
# The intented (and unique) solution is 0 -> 2 -> 1

from ortools.sat.python import cp_model

number_of_vertices = 3
allowed_edges = [
(0,1),
(0,2),
(2,1),
]

model = cp_model.CpModel()

node_sequence = [model.NewIntVar(0, number_of_vertices - 1, "node_%i" % i) for i in range(number_of_vertices)]

for i, v in enumerate(node_sequence[:-1]):