Graph Theory: Hamiltonian's Path

Finding a Path in a Graph

An efficient solution to Hamiltonian's Path has eluded computer scientists for many years. Well first, what is Hamiltonian's Path? It is a path in an undirected or directed graph that visits each vertex exactly once (https://en.wikipedia.org/wiki/Hamiltonian_path).

For example, in the simple directed graph to the right, the only Hamiltonian's Path possible is from a to b to c to d. The hard part comes when creating algorithm to choose the right path to take and to make it efficient as possible. In this example, how would computer know what path to choose when starting at the point a? It could choose b or c, but there is only one correct choice.

My first attempt to create a solution to find the Hamiltonian Path was based off Depth First Search (DFS), a graph theory algorithm that uses recursion to go through all of the vertices of a graph using a specified starting point. I initially choose the starting point as the vertex with highest out-degree (number of edges leaving the vertex). I tried to make my version of DFS  simply run through all the solutions by breaking out of the recursion whenever it came to vertex with an out-degree of 0. This would theoretically make the algorithm stop right there, and I could simply keep a boolean array of all the marked (visited) vertices. The array then could be checked to see if it was all marked true (boolean 1), and if so then the algorithm has found a path, if not, then try again. However, this was very inefficient since the algorithm randomly choose a path and explored it, and there was no guarantee it wouldn't choose that path again. I looked at ways of storing the past paths, but quickly realized the enormous amount of space that would take if there were millions of vertices.

I then proceeded to explore alternative methods of considering vertices, so that if there was a path connecting those vertices, a Hamiltonian Path was guaranteed. My search for such a ordering lead me to consider topological ordering. Topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering (https://en.wikipedia.org/wiki/Topological_sorting). However, topological ordering only works on directed graphs, so I had to limit the graphs applicable to my plausible solution. Additionally, there may be many topological orderings available for a given graph, meaning that I had limit the applicable graphs even more to include only graphs with one topological ordering (these graphs are called directed acyclic graphs). With these limitations in mind, I set about devising a solution, again using DFS as the base. I finally found a (currently) working solution through creating array of the topological ordering of all the vertices in a given directed graph, and then considering the vertices in that order if they are adjacent line from one to other, (for e.g.,  in the graph above b is adjacent to a) to each other through DFS.

I kept the boolean array described earlier, and check to see if all vertices were marked, and if so, then there was Hamiltonian Path, and all you had to do was follow the vertices in topological order. An example of the (currently) working code is below:

public class HamiltonCircuit {
 private boolean marked[];
 private Digraph g;
 private int[] order;
 private boolean hasPath;
 private Topological top;
 private int c=1;
 public HamiltonCircuit(Digraph g){
  this.g =g;
  this.marked = new boolean[g.V()];
  this.top = new Topological(g);
  if(!top.hasOrder()){
   throw new IllegalArgumentException("Not Toplogical Order");
  }
  setOrder();
        hc(order[0]);
  this.hasPath = check(marked);
 }
 private void setOrder(){
  this.order =  new int[g.V()];
  int count =0;
  for(int x: top.order()){
   order[count] = x; 
   count++;
  }
 }
 public void hc(int v){
  marked[v] =true;
  for(int vertex: g.adj(v)){ 
   //System.out.println(vertex + " " + order[c]);  is the line 
   if(!marked[vertex]&&order[c]==vertex){
    c++;
    hc(vertex); 
   }
  }
 }
 private boolean check(boolean[] a){
  for(int i=0;i<a.length;i++){
   if(!a[i]){
    return false;
   }
  }
  return true;
 }
 public String toString(){
  if(!hasPath){
   throw new IllegalArgumentException("No path");
  }
  StringBuilder s = new StringBuilder();
  s.append("\n");
  for(int i =0;i<g.V()-1;i++){
   s.append(order[i]);
   s.append("-" );
  }
  s.append(order[order.length-1]);
  return s.toString();
 }
 public int[] order(){
  if(hasPath){
   return order;
  }
  else{
   throw new IllegalArgumentException("No path or Not DAG");
  }
 }
 public static void main(String[] args) {
  //to creat Diagraph and check your work
  
 }
}


Some notes on the code :
Digraph is a Java object representation of a directed graph. 
Topological is a class that simply returns the topological ordering of a graph