title: Randomized algorithm for finding hamiltonian path in a directed graph
body: <p>From this Wikipedia article:</p>
  
  <p><a href="http://en.wikipedia.org/wiki/Hamiltonian_path_problem" rel="noreferrer">http://en.wikipedia.org/wiki/Hamiltonian_path_problem</a></p>
  
  <blockquote>
    <p>A randomized algorithm for Hamiltonian
    path that is fast on most graphs is
    the following: Start from a random
    vertex, and continue if there is a
    neighbor not visited. If there are no
    more unvisited neighbors, and the path
    formed isn't Hamiltonian, pick a
    neighbor uniformly at random, and
    rotate using that neighbor as a pivot.
    (That is, add an edge to that
    neighbor, and remove one of the
    existing edges from that neighbor so
    as not to form a loop.) Then, continue
    the algorithm at the new end of the
    path.</p>
  </blockquote>
  
  <p>I don't quite understand how this pivoting process is supposed to work.  Can someone explain this algorithm in more detail?  Perhaps we can eventually update the Wiki article with a more clear description.</p>
  
  <p><strong>Edit 1:</strong> I think I understand the algorithm now, but it seems like it only works for undirected graphs.  Can anyone confirm that?</p>
  
  <p>Here's why I think it only works for undirected graphs:</p>
  
  <p><a href="http://www.michaelfogleman.com/static/images/graph.png" rel="noreferrer">alt text http://www.michaelfogleman.com/static/images/graph.png</a></p>
  
  <p>Pretend the vertices are numbered like so:</p>
  
  <pre><code>123
  456
  789
  </code></pre>
  
  <p>Let's say my path so far is: <code>9, 5, 4, 7, 8</code>.  8's neighbors have all been visited.  Let's say I choose 5 to remove an edge from.  If I remove (9, 5), I just end up creating a cycle: <code>5, 4, 7, 8, 5</code>, so it seems I have to remove (5, 4) and create (8, 5).  If the graph is undirected, that's fine and now my path is 9, 5, 8, 7, 4.  But if you imagine those edges being directed, that's not necessarily a valid path, since (8, 5) is an edge but (5, 8) might not be.</p>
  
  <p><strong>Edit 2:</strong> I guess for a directed graph I could create the (8, 5) connection and then let the new path be just <code>4, 7, 8, 5</code>, but that seems counter productive since I have to chop off everything that previously led up to vertex 5.</p>