# Determining if paths are Hamiltonian in C++

A Hamiltonian path in a graph is a path whereby each node is visited exactly once.

A number of graph-related problems require determining if the interconnections between its edges and vertices form a proper Hamiltonian tour, such as traveling salesperson type problems. Such a problem is NP-Complete, that is, the effort required to solve the problem increases dramatically as the size of the problem grows.

This C++ implementation borrows heavily from the ideas and algorithms used in the following article:

http://www.geeksforgeeks.org/backtracking-set-7-hamiltonian-cycle/

The main differences are that I prefer to use smart pointers over conventional pointers where possible and I use the `Graph` data structure to contain the edges and vertices, and methods to insert new edges, output results, test for the presence of edges etc.

In the `Graph` class network interconnections are represented by an adjacency list for example, uses `std::unique_ptr` instead:

```std::unique_ptr<std::list<int>> adj;
```

instead of a two-dimensional array representing the presence or absence of link between nodes:

```bool graph1[V][V] = {{0, 1, 0, 1, 0},
{1, 0, 1, 1, 1},
{0, 1, 0, 0, 1},
{1, 1, 0, 0, 1},
{0, 1, 1, 1, 0},
};
```

Here is the complete C++ code sample used to determine if the graph contains a Hamiltonian Cycle or not, and output the path vertices if it does:

`Graph.h`

```#include <list>
#include <vector>
#include <memory>

class Graph
{
int _V;
bool _directed;
std::vector<int> pathstore;

public:

Graph(int V, bool directed);
int V();
bool hasEdge(int v, int w);
void ShowPath();
void StorePath(const std::vector<int>& path);
};```

`Graph.cpp`

```#include "Graph.h"
#include <iostream>
#include <algorithm>
#include <iterator>

Graph::Graph(int V, bool directed) : adj(new std::list<int>[V])
{
_V = V;
_directed = directed;
}

{

if (!_directed)
{
}
}

int Graph::V()
{
return _V;
}

bool Graph::hasEdge(int v, int w)
{
}

void Graph::ShowPath()
{
std::vector<int>::const_iterator start = pathstore.begin();
std::vector<int>::const_iterator end = pathstore.end();

if (start != end)
{
std::for_each(start, end, [](const int& n){ std::cout << n << " "; });
std::cout << *start;
}
}

void Graph::StorePath(const std::vector<int>& path)
{
pathstore = path;
}
```

`main.cpp`

```#include<stdio.h>
#include "Graph.h"
#include <vector>
#include <iostream>
#include <algorithm>

bool isSafe(int v, Graph* graph, const std::vector<int>& path, int pos)
{
if (!graph->hasEdge( path[pos - 1], v ))
return false;

for (int i = 0; i < pos; i++)
if (path[i] == v)
return false;

return true;
}

bool hamiltonianCycleUtility(Graph* graph, std::vector<int> path, int pos)
{
if (pos == graph->V())
{
if (graph->hasEdge(path[pos - 1], path[0]))
{
graph->StorePath(path);
return true;
}
else
{
return false;
}
}

for (int v = 1; v < graph->V(); v++)
{
if (isSafe(v, graph, path, pos))
{
path[pos] = v;

if (hamiltonianCycleUtility(graph, path, pos + 1) == true)
{
return true;
}

path[pos] = -1;
}
}

return false;
}

void PrintTour(Graph* graph)
{
std::cout << "Hamiltonian tour exists: " << std::endl;
graph->ShowPath();
std::cout << std::endl;
}

bool IsHamiltonian(Graph* graph)
{
std::vector<int> path(graph->V());
std::transform(path.begin(), path.end(),
path.begin(), [](int n) -> int { return -1; } );

path[0] = 0;
if (hamiltonianCycleUtility(graph, path, 1) == false)
{
std::cout << "Solution does not exist" << std::endl;
return false;
}

PrintTour(graph);
return true;
}

int main()
{
//  Create the following graph
//  (0)--(1)--(2)
//  |          |
//  |          |
//  |          |
//  (3)-------(4)
Graph g1(5, false);

bool isHamiltonianTour = IsHamiltonian(&g1);

//  Create the following graph
//  (0)--(1)--(2)
//  |          |
//  |          |
//  |          |
//  (3)       (4)
Graph g2(5, false);

isHamiltonianTour = IsHamiltonian(&g2);

//  Create the following graphs
//  (0)--(1)--(2)--(0)
//  (3)--(4)--(5)--(3)
Graph g3(6, false);

isHamiltonianTour = IsHamiltonian(&g3);

return 0;
}
```

The following example contains a Hamiltonian path since it is possible to visit each node:

```(0)--(1)--(2)
|         |
|         |
|         |
(3--------(4)
```

While the following examples do not contain any Hamiltonian paths:

```(0)--(1)--(2)
|         |
|         |
|         |
(3)       (4)
```

and

```(0)--(1)--(2)--(0)
(3)--(4)--(5)--(3)
```

Which gives the following console output: