1
$\begingroup$

I have an adjacency matrix, A. I want to check if there is a path (from any vertex) which can traverse all of the vertices such that no vertex is visited again.

A = {{0, 0, 0, 1, 1, 0, 0, 0, 0}, {0, 0, 0, 1, 1, 1, 0, 0, 0}, {0, 0, 0, 
  0, 1, 1, 0, 0, 0}, {1, 1, 0, 0, 0, 0, 1, 0, 0}, {1, 1, 1, 0, 0, 0, 
  1, 0, 1}, {0, 1, 1, 0, 0, 0, 0, 0, 1}, {0, 0, 0, 1, 1, 0, 0, 1, 
  0}, {0, 0, 0, 0, 0, 0, 1, 0, 1}, {0, 0, 0, 0, 1, 1, 0, 1, 0}};

I solved this by constructing an AdjancencyGraph and then using FindPath for all of the vertices to check if any path exists.

getPathsFromNode[adjMatrix_, node_] :=
  Flatten[#, 1]&@
  (FindPath[AdjacencyGraph[adjMatrix], node, #, {8}, 1] & /@ Range[9]);

Now, I check if there is any path from any vertex.

(getPathsFromNode[A, #]!={}) & /@ Range[9] // Flatten[#, 1] &
(*{True, True, True, False, False, False, True, False, True}*)

This process is very slow. Is there any other way to check if a path exits without contructing an Adjacency graph?

$\endgroup$
  • $\begingroup$ Have you seen FindHamiltonianCycle[]? $\endgroup$ – J. M. is away Apr 8 '17 at 5:22
  • $\begingroup$ @J.M. I tried FindHamiltonianCycle[A // AdjacencyGraph], It returns empty list. $\endgroup$ – Anjan Kumar Apr 8 '17 at 5:27
  • 2
    $\begingroup$ Use FindHamiltonianPath $\endgroup$ – Szabolcs Apr 8 '17 at 7:31
  • $\begingroup$ @Szabolcs Thanks. The speed has increased by an order. $\endgroup$ – Anjan Kumar Apr 8 '17 at 7:39
  • $\begingroup$ Szabolcs suggestion is probably the best method to use (for general $A$). Are there any restrictions on the graph/matrix? $\endgroup$ – Kellen Myers Apr 9 '17 at 7:32
3
$\begingroup$

This is the Hamiltonian path problem. Use FindHamiltonianPath.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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