Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

Found this bug-like behaviour today: if the order of edges is changed so that VertexList does not return the vertices in canonical order, FindHamiltonianCycle is not always able to find the Hamiltonian cycle, that is obviously there.

edges = {1 -> 2, 2 -> 3, 3 -> 1, 1 -> 3, 3 -> 4, 4 -> 1};
g1 = Graph[edges, VertexLabels -> "Name", ImagePadding -> 10];
g2 = Graph[RotateLeft@edges, VertexLabels -> "Name", ImagePadding -> 10];

{g1, FindHamiltonianCycle[g1, All], VertexList@g1}
{g2, FindHamiltonianCycle[g2, All], VertexList@g2}

enter image description here enter image description here

If a vertex list is specified, that might help, but not always:

g3 = Graph[{1, 4, 2, 3}, RotateLeft@edges, VertexLabels -> "Name", ImagePadding -> 10];
g4 = Graph[{4, 1, 3, 2}, RotateLeft@edges, VertexLabels -> "Name", ImagePadding -> 10];

{g3, FindHamiltonianCycle[g3, All], VertexList@g3}
{g4, FindHamiltonianCycle[g4, All], VertexList@g4}

enter image description here enter image description here

Is this a bug? If so, at least it is consistent with HamiltonianGraphQ:

HamiltonianGraphQ /@ {g1, g2, g3, g4} ==> {True, False, True, False}

Mathematica 9.0.1, Windows 7, x64.

share|improve this question
    
It seems to work OK if you also specify the vertex set: g2 = Graph[Range@4, RotateLeft@edges, VertexLabels -> "Name", ImagePadding -> 10];{g2, FindHamiltonianCycle[g2, All], VertexList@g2} –  belisarius Sep 8 '13 at 18:58
    
@belisarius As you can see in my g3 and g4 examples, that is not always true. Surely, if the vertex list and the edge list comply in some undocumented sense (even if it is simply canonical ordering) it works, I think it is unwanted behaviour. Waiting for TechSupport at the moment... –  István Zachar Sep 8 '13 at 20:50
    
You should probably report it to support. –  Szabolcs Sep 12 '13 at 15:24
    
@Szabolcs I did, with several other issues still in the pipeline, but the TechSupport web interface is broken (throws error when submitted), and they were unable to help me via the chat. No reply to emails yet. Perhaps someone knows what is going on at WRI support...? –  István Zachar Sep 12 '13 at 15:27
1  
I tagged this as a bug. According to the docs, FindHamiltonianCycle only returns {} if no such cycle exists. Unfortunately I couldn't get the Combinatorica version to work on directed graphs. Did you receive a reply from support? –  Szabolcs Sep 16 '13 at 17:04
show 1 more comment

1 Answer

up vote 2 down vote accepted

This is a bug: Technical Support gave the following answer acknowledging the problem:

"It does appear that the input you mention is not behaving properly, and I have forwarded an incident report to our developers [...]"

No workaround solution was offered, but there are at least two ways to overcome the problem:

  1. Supply correctly sorted vertex names with Graph (as in Graph[{1, 2, 3, 4}, ...]). Since we don't know what is the required vertex order (might not be standard sorting), this is not sure to succeed.
  2. Undirect the graph using UndirectedGraph and check for Hamiltonian cycles in the undirected graph. If it finds any, convert UndirectedEdge-s to DirectedEdges in the found cycles, and check for all found cycle whether the original directed graph contains
    1. all the re-directed edges AND/OR
    2. all the re-directed edges in reverse order.

The latter should be failsafe.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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