ANSI C: Hamiltonian cycle

Introduction

A Hamiltonian path (or traceable path) is a path in an undirected graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a Hamiltonian path that is a cycle.

In this post, we will implement an ANSI C program that will display all Hamiltonian cycle of a given graph array.

The Program

hamiltonian.c

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>

/**
 * A Hamiltonian path (or traceable path)
 * is a path in an undirected graph that
 * visits each vertex exactly once.
 * A Hamiltonian cycle (or Hamiltonian circuit) is
 * a Hamiltonian path that is a cycle.
 * From wiki: http://en.wikipedia.org/wiki/Hamiltonian_path
 */

// the number of nodes in the test graphic
int node_amount = 12;
// the number of Hamiltonian cycles
int hamiltonian_cycle_amount = 0;

// Graph Representation with nodes
// not use [0][x] and [x][0]
int graph_array[13][13] = {
                 0,0,0,0,0,0,0,0,0,0,0,0,0,
                 0,0,1,0,0,1,0,0,0,0,0,0,0,
                 0,1,0,1,0,0,0,1,1,0,0,0,0,
                 0,0,1,0,1,0,0,0,1,0,0,0,0,
                 0,0,0,1,0,1,0,0,0,1,0,0,0,
                 0,1,0,0,0,0,1,0,0,0,1,0,0,
                 0,0,0,0,0,1,0,1,0,0,0,1,0,
                 0,0,1,0,0,0,1,0,1,0,0,0,0,
                 0,0,1,1,0,0,0,1,0,1,0,0,0,
                 0,0,0,0,1,0,0,0,1,0,1,0,1,
                 0,0,0,0,0,1,0,0,0,0,0,1,0,
                 0,0,0,0,0,0,1,0,0,0,1,0,1,
                 0,1,0,0,0,0,0,0,0,1,0,1,0
                };

// the array store the result through recursive
int result_array[13] = {0};

/**
 * The function that find all Hamiltonian cycle
 * and output to console
 * param node_index: int, nth node in path
 */
void hamiltonian ( int node_index );
/**
 * The function that check whether current node
 * is valid in Hamiltonian cycle.
 */
bool promising ( int node_index );

int main()
{
  printf("\n");
  result_array[1] = 1;  // start from first node
  hamiltonian( 1 );  // start to find all Hamiltonian cycles recursively

  if( hamiltonian_cycle_amount == 0 )  // no Hamiltonian cycles found
   printf("\nThere is no Hamiltonian cycles in this graph\n\n");

  printf("\n");

  system("PAUSE");
  return 0;
}

void hamiltonian ( int node_index )
{
  int j, k;
  if( promising(node_index) )  // current node is valid in a Hamiltonian cycles
  {
     if( node_index == (node_amount) )  // at latest node
     {  hamiltonian_cycle_amount = 1;  // increase hamiltonian_cycle_amount
        printf(" v%d", result_array[1]);  // print out the result
        for( k = 2;k <= node_amount;k ++ )
          printf(" → v%d", result_array[k]);
        printf("\n\n");
     }
     else  // not latest node
     {
        for( j = 2;j <= node_amount;j ++ )  // recursively scan from second node to latest node
        {
           result_array[node_index+1] = j; // store result
           hamiltonian( node_index+1 );  // call function recursively
        }
     }
  }

}

bool promising ( int node_index )
{
  int j, k;
  bool isValid = true; // default to valid

  j = 1;

  if (node_index == 1) // first node, valid
    isValid =  true;
  if( (node_index == (node_amount)) && (!graph_array[result_array[node_index]][result_array[1]]) )
     isValid =  false;  // latest node but not connected to first node, invalid

  else if( ( node_index > 1 ) && (!graph_array[result_array[node_index-1]][result_array[node_index]]) )
     isValid =  false;  // not connected between current node and previous node, invalid

  else
  {
    while( (j < node_index) && isValid)  // check all previous nodes
    {
       if( result_array[node_index] == result_array [j] )
         isValid = false;  // current point already in path, invalid
       j++;
    }
  }
  return isValid;  // return whether current node is valid
}

The Result

Reference
http://en.wikipedia.org/wiki/Hamiltonian_path

Download
The files at github
https://github.com/benbai123/C_Cplusplus_Practice/tree/master/C_Algorithm/Hamiltonian_Cycle