3
$\begingroup$

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:

simple directed graph

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

hamiltonian path

Improve this question
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Laurent Perron
    Commented Mar 7, 2022 at 9:28
  • $\begingroup$ 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). $\endgroup$
    – Michaël
    Commented Mar 7, 2022 at 21:57
  • $\begingroup$ 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. $\endgroup$
    – Laurent Perron
    Commented Mar 8, 2022 at 8:05
  • $\begingroup$ 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 ? $\endgroup$
    – Michaël
    Commented Mar 8, 2022 at 9:01
  • $\begingroup$ you can use it. It will blow up in memory very fast. $\endgroup$
    – Laurent Perron
    Commented Mar 8, 2022 at 9:03

2 Answers 2

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – Michaël
    Commented Mar 7, 2022 at 10:40
  • $\begingroup$ 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. $\endgroup$
    – Michaël
    Commented Mar 7, 2022 at 11:07
  • $\begingroup$ yes, exactly, this will work. $\endgroup$
    – Kuifje
    Commented Mar 7, 2022 at 12:39
  • $\begingroup$ 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). $\endgroup$
    – Michaël
    Commented Mar 7, 2022 at 15:47
  • 1
    $\begingroup$ ortools + routing solves the Hamiltonian path problem, just not necessarily optimally. No solver can guarantee this for every graph. $\endgroup$
    – Kuifje
    Commented Mar 7, 2022 at 20:40
2
$\begingroup$

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)]

model.AddAllDifferent(node_sequence)

for i, v in enumerate(node_sequence[:-1]):
    model.AddAllowedAssignments((node_sequence[i], node_sequence[i + 1]), allowed_edges)

solver = cp_model.CpSolver()

printer = cp_model.VarArraySolutionPrinter(node_sequence)

status = solver.SearchForAllSolutions(model, printer)

I'll try with bigger graphs to see when it blows up.

EDIT: As my answer is what I was looking for when I asked my question, and as there's nothing new on this post, I accept my own answer !

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.