Learn about Hamiltonian paths and cycles and how to find both in Python!

Implementing Hamiltonian Algorithms in Python

We have just reviewed Hamiltonian algorithms. As a reminder, the algorithm consists of two parts:

* A Hamiltonian path: a path in a graph that visits each vertex (or node) exactly once.
* A Hamiltonian cycle (or circuit): contains a Hamiltonian path **and** the starting and ending vertices are the same.

There are several ways to determine if a Hamiltonian path or cycle exists in a graph programmatically. The method we will be implementing in this lesson is a brute force approach in Python. This approach allows us to visit every vertex and its connected, neighboring vertices recursively. We can then backtrack out to traverse the next unvisited vertex to see if more paths or cycles exist, until we have visited all vertices.
 
As we move through implementing the algorithm, it may be helpful to consider how we can use this algorithm in a real-world scenario. Take a look at the graph to the right. A school district could try to find Hamiltonian cycles when mapping out bus stops between students' houses. This would allow for finding the most efficient bus route that visits each student's house exactly once.


Introduction to the Hamiltonian Algorithm

We will create a custom Hamiltonian class responsible for traversing a graph to determine if a Hamiltonian path or cycle exists.
 
When defining our Hamiltonian class, we should define the following within the constructor. Let's connect each of these defined class members back to our bus route graph to see why we should define these components.
 
* `vertices`: a list of the vertices in the graph.
   * *In our bus route graph, we need to know what students need to be picked up.*
* `adj_matrix`: the adjacency matrix.
   * *We need to know which roads connect to each house to see the possible route options.*
* `start`: the index of the starting vertex of the graph.
   * *We need to know where the bus departs from (this location is also our final end point for a Hamiltonian cycle). In this case, the bus departs from the school and should end up back at the school.*
* `path`:  a list of the path vertices' indexes we have currently traversed (this list will be modified as we backtrack throughout the graph to find different paths).
   * *As the bus moves to each student's house, we add each student vertex to the possible path.*
* `visited_vertices`: a list to indicate if each vertex has been visited. Since a Hamiltonian path and cycle must visit each vertex only, this will help us keep track of which vertex has been visited. If a vertex has been visited, it should be assigned the value of 1 and 0 otherwise. At the start, all vertices should have a 0 value in this list.
   * *We only want to visit each student's house once and need to keep track if the student has been picked up yet or not.*
* `hpaths`: a list containing all Hamiltonian paths in this graph. If empty, none exist.
   * *If we've found an eligible path where each student has been visited once, we keep track of that path here.*
* `cycles`: a list containing all Hamiltonian cycles in this graph. If empty, none exist.
   * *If we find an eligible path where each student has been visited once and end up back at the school, we keep track of that path here.*
 
Before we start traversing the path, in our `traverse()` method, we should:
*  First, add our `start` vertex index to the `path` list since it is the start of our path
*  Call the recursive `search()` function, that we will implement in the next exercise.



Starting the Path Traversal

Since the `search()` method is recursive, we need to provide an exit condition, otherwise we could end up in an infinite loop searching the graph. We should add this exit condition to the beginning of our `search()` method.
 
The exit condition should be checked first in the `search()` method. Before exiting the recursion, we should check if:
* All vertices have been visited, and there are no duplicate vertices in the `path` list. This means that a Hamiltonian path has been found. Append it to the `hpaths` list if so.
  * *In our bus route scenario, this means that we have started at "School" and every student has been picked up and that we may or may not be back at the "School" vertex by the end of the path.*
* The current vertex equals the `start` vertex **and** the number of vertices we have visited in our `path` list equals the number of vertices in our vertices list, plus 1. We must add 1 here since the starting vertex will show in this list twice. If we meet this condition, we should add the path to the `cycles` list.
   * *This means we have started at "School", picked up every student, and are back at the "School" vertex.*



Stop Condition for `search()`

Before we implement the Hamiltonian algorithm, let's look at our starter code from the previous exercise closer. The information provided in this code will be our input data and will change depending on what graph we are testing with, so this data does not need to be a part of our custom Hamiltonian class. In our test graph, we have vertices labeled "School", "Sanjay", "Marquis", "Marisol", and "Lisa". Each vertex has an assigned index from 0 to 4, respectively.
 
Our input data provides:
 
* `vertices`: a list of vertices (nodes) that are in the graph
* `adjacency_matrix`: matrix, or nested lists, that represents the adjacency matrix of the graph.
 
The adjacency matrix tells us what vertices are connected to which. In the matrix: 
* a 1 indicates that the vertices are connected, and 
* a 0 indicates that they are not connected.
 
Our input data provides the following adjacency matrix. In this matrix, the numbers in the parentheses will represent the index for that student. So, when we access `adjacency_matrix[1]`, we retrieve a list of all values in that column, or `[1, 0, 1, 0, 0]`.
 
```tex
\begin{pmatrix}
 & School(0) & Sanjay(1) & Marquis(2) & Marisol(3) & Lisa(4) \\
 School(0) & 0 & 1 & 0 & 0 & 1 \\
 Sanjay(1) & 1 & 0 & 1 & 0 & 0 \\
 Marquis(2) & 0 & 1 & 0 & 1 & 0  \\
 Marisol(3) & 0 & 0 & 1 & 0 & 1  \\
 Lisa(4) & 1 & 0 & 0 & 1 & 0
\end{pmatrix}
 ```

To understand this matrix, let's look at vertex "School". "School" is connected to "Sanjay", index 1 and "Lisa", index 4 since it has values 1 for each of these vertices. Since "School" is not connected to any other vertex, it has 0 for all other vertices. To learn more about adjacency matrices, click [here](https://www.codecademy.com/courses/complex-data-structures/lessons/conceptual-graphs/exercises/conceptual-graphs-representation).
 
Now that we have a better understanding of the starting code, we are ready to implement the Hamiltonian algorithm to find all Hamiltonian paths and cycles!


Understanding the Starter Code

Once we have completed and recursively traversed a neighbor vertex, we should backtrack from that vertex to explore other paths and cycles that may exist in the graph.
 
Backtracking allows us to find additional solutions to our problem by removing (backtracking from) failed candidates and trying a different path that may lead to a solution that meets all constraints.
 
For example, consider a graph that leads to a dead-end vertex where there is no edge to connect us to the remainder of vertices in the graph. Once we reach this dead-end vertex, we will want to backtrack so that we can potentially find another path that will allow us to visit all vertices. Consider this graph:
 
![Bridge graph](https://drive.google.com/file/d/1867mm3QQsdAxIw3a2xXf_vOTfYycKIcn/view?usp=sharing)

If we first searched the path A > C > D > E, we would see that not all nodes have been visited and will need to backtrack to find another path that meets the criteria for a Hamiltonian path.
 
To implement this backtracking:
 
* After calling the recursive `search()` on the neighbor node, set the neighbor index back to unvisited in the visited_vertices list. This is done by setting the value back to 0.
* Pop the neighbor node from the path list.
 
Imagine to the left of our "School" vertex is a connected 6th vertex "Ben" that isn't connected to anything else. 
* If we started at "School" and visited "Ben", we would reach a dead-end and have several unvisited nodes left.
* This path would not be an eligible bus route, so we would need to backtrack back to "School" and visit "Sanjay" instead.

Let's modify our `search()` method to include this backtracking.


Implementing Backtracking

The traversal `search()` method will be recursive, so we can backtrack and explore multiple paths within the graph. There are a few components for implementing this search:
 
* The `search()` method should take in the vertex we are currently on as input. In its first iteration, this would be the `start` vertex.
* We should first loop through the `vertices` list so that we can access the index for each vertex in the graph.
* On each loop iteration, access the `adj_matrix` value for the current vertex and the neighbor vertex to check against.
   * If this value is 1, that means this neighbor is connected to the current vertex.
   * If `visited_vertices` at this index is 0, that means this neighbor has not yet been visited in the path.
   * If both of these above conditions are met, we should mark this neighbor as visited within `visited_vertices` by setting the value to 1. We should also add this neighbor to the `path` list. Next, traverse the neighbor by recursively calling `search()` on this neighbor vertex.
 
Let's walk through one iteration of this implementation. In our bus route example, we start at "School." As we loop through the vertices:

* We first come across index 0 ("School"). 
* Since "School" is not connected to "School", we continue on to index 1 ("Sajay")
* "School" is connected to "Sanjay" and "Sanjay" has not been visited yet, so we can set `visited_vertices[1] = 1` to 1 and add "Sanjay" to the path
* We now search what vertices are connected to "Sanjay" to find the next house along the road/route.


Traversing the Path

Congratulations! You've implemented the Hamiltonian algorithm to find both Hamiltonian paths and cycles within a graph!

In this lesson, you have learned:

*   What a Hamiltonian path is
*   What a Hamiltonian cycle (circuit) is
*   How to convert a graph into input data for the Hamiltonian algorithm via a vertex list and adjacency matrix
*   How to implement the Hamiltonian algorithm to search for paths and cycles programmatically
