Testing a Hamiltonian Path finder implementation

Question

I am implementing an algorithm which finds an optimal Hamiltonian path in a directed graph. I have implemented an algorithm which appears to work reasonably well, however I am not entirely sure if there are subtle bugs or other issues in certain cases. Therefore, I need a few diverse networks where the solution is known, to check if my implementation is also solving them as it should.

Since Wikipedia implies Hamiltonian paths is only an appropriate term for undirected graphs, assume that "Hamiltonian path" means a path which visits every node once and exactly once on a given network, directed or otherwise.

For simplicity, we can assume that every connection (or "edge") has a positive integer value (or "length"). We can also assume that no node is connected to itself, and there can be no more than one edge in each direction between any two nodes.

I happen to be interested in the path which has the highest total length, so "optimal" means longest, although it probably makes little difference if I wanted the shortest total length (as in the traditional TSP). I also happen to be using a greedy algorithm.

Where or how might I obtain directed networks for which TSP has been solved? It would be even better if the actual solution and the greedy (or other heuristic) solution was available. The networks should be large enough to make for an informative test, but small enough for me to manually check the solution (if the solution is initially unknown). They should be topologically diverse enough to cover both "easy" and "problematic" networks.

For anyone else looking for the same; the best I have is the following network:

  A B C D E
A 0 1 2 0 1
B 1 0 0 0 1
C 0 3 0 1 2
D 4 0 0 0 0
E 1 0 0 2 0

This is an adjacency list, the rows are edge origins and columns are destinations. The numbers are lengths of each edge, and 0s indicate "no edge". For instance, the 4 shows that the length of the edge from D to A is 4, and there is no connection from A to D (length 0).

The maximum length path in this network is E->D->A->C->B. Its total length is 2+3+3+3=11. I believe a greedy algorithm is able to find the best solution in this case, and it happens to be possible to be obvious that it IS the best possible solution.

Answer 1

As you have read the Wiki entry on Hamiltonian path, you should have noticed that finding a Hamiltonian path is NP-hard (To be precise, what you're solving is TSP - but that doesn't change much). That single fact suggests that a greedy algorithm won't give you optimal solution for the problem.

If your greedy algorithm works like

take edges ordered by descending value/length,

add the edge to the path-in-construction, unless it

(a) creates a cycle

(b) creates a node of deg=3 in the path-in-construction

otherwise skip it

here's the minimal counter-example I can think of where the greediness makes it fail:

  A B C D E F
A 0 5 4 0 0 0
B 5 0 5 0 4 0
C 4 5 0 1 0 0
D 0 0 1 0 5 4
E 0 4 0 5 0 5
F 0 0 0 4 5 0

Greedy algorithm finds a path A-B-C-D-E-F with total length of 21, while the optimal path is A-C-B-E-D-F with total length of 22 (there's more of them with the same length).

If your algorithm works differently it may work well for this example, but there will still be a counter-example if it is greedy. Post your code if that's the case and you're interested.