# Implementation

```python
class HamiltonianPath:
    def __init__(self, edges):
        self.g = HamiltonianPath.__create_graph(edges)

    @ staticmethod
    def __create_graph(edges):
        g = {}
        for u, v in edges:
            g[u] = set()
            g[v] = set()
        for u, v in edges:
            g[u].add(v)
        return g

    def getHamiltonianPath(self):
        def dfs(start):
            s = [(start, None)]
            h_path = []
            visited = set()
            while s:
                top, parent = s.pop()
                h_path.append(top)
                visited.add(top)
                if len(h_path) == len(self.g):
                    return h_path

                none = True
                for edge in self.g[top]:
                    if edge not in visited:
                        none = False
                        s.append((edge, top))
                if none:
                    if not s:
                        return []
                    # back track until we reach the next element in the stack
                    # backtracking in this context means iterating backwards
                    # through the current path we collected
                    #
                    # our stopping condition is when:
                    # 1. The current element in the path is connected to the top of the stack
                    # 2. The parent of the top of the stack is current path element
                    while h_path and s[-1][0] not in self.g[h_path[-1]] or s[-1][1] != h_path[-1]:
                        tmp = h_path.pop()
                        visited.remove(tmp)
            return []

        for vertex, _ in self.g.items():
            s = dfs(vertex)
            if s:
                return s
        return []
```

**Testing**

```
hg1 = HamiltonianPath(edges = [
    [0, 1], [1, 0],
    [1, 2], [2, 1],
    [1, 3], [3, 1]
])
print(hg1.getHamiltonianPath())


hg2 = HamiltonianPath(edges = [
    [0, 1], [1, 0],
    [1, 2], [2, 1],
    [1, 3], [3, 1],
    [3, 2]
])
print(hg2.getHamiltonianPath())


hg3 = HamiltonianPath(edges = [
    [10, 6], [6, 10],
    [6, 3], [3, 6],
    [3, 1], [1, 3],
    [1, 8], [8, 1],
    [3, 13], [13, 3],
    [13, 12], [12, 13],
    [12, 4], [4, 12],
    [4, 5], [5, 4],
    [5, 11], [11, 5],
    [11, 14], [14, 11],
    [14, 2], [2, 14],
    [2, 7], [7, 2],
    [7, 9], [9, 7]
])
print(hg3.getHamiltonianPath())


hg4 = HamiltonianPath(edges = [
    [10, 6], [6, 10],
    [6, 3], [3, 6],
    [3, 1], [1, 3],
    [1, 8], [8, 1],
    [3, 13], [13, 3],
    [13, 12], [12, 13],
    [12, 4], [4, 12],
    [4, 5], [5, 4],
    [5, 11], [11, 5],
    [11, 14], [14, 11],
    [14, 2], [2, 14],
    [2, 7], [7, 2],
    [7, 9], [9, 7],
    [15, 1], [1, 15],
    [15, 10], [10, 15]
])
print(hg4.getHamiltonianPath())


hg4 = HamiltonianPath(edges = [
    [10, 6], [6, 10],
    [6, 3], [3, 6],
    [3, 1], [1, 3],
    [1, 8], [8, 1],
    [3, 13], [13, 3],
    [13, 12], [12, 13],
    [12, 4], [4, 12],
    [4, 5], [5, 4],
    [5, 11], [11, 5],
    [11, 14], [14, 11],
    [14, 2], [2, 14],
    [2, 7], [7, 2],
    [7, 9], [9, 7],
    [15, 1], [1, 15],
    [15, 10], [10, 15],
    [9, 16], [16, 9],
    [17, 8], [8, 17],
    [7, 18], [18, 7]
])
print(hg4.getHamiltonianPath())

hg5 = HamiltonianPath(edges = [
    ['E', 'D'], ['D', 'E'],
    ['D', 'C'], ['C', 'D'],
    ['D', 'A'], ['A', 'D'],
    ['C', 'B'], ['B', 'C'],
    ['C', 'A'], ['A', 'C'],
    ['A', 'B'], ['B', 'A'],
])
print(hg5.getHamiltonianPath())

# output
# []
# [0, 1, 3, 2]
# []
# [8, 1, 15, 10, 6, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9]
# []
# ['E', 'D', 'C', 'A', 'B']
```

**Discussion**

The biggest challenge for me when implementing this iteratively, was knowing when stop backtracking. Consider the graph that does not have a Hamiltonian Path:

![](https://4248470099-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LoJHphnGN5n2jKpXzYL%2F-LoJHqLx4tZP9WYw_RQZ%2F-LoJI2Uhf02XVClsgDyo%2Fhamiltonian%20path3.png?generation=1568003603870695\&alt=media)

Our DFS tree for vertex 1 looks like follows:

![](https://4248470099-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LoJHphnGN5n2jKpXzYL%2F-LoJHqLx4tZP9WYw_RQZ%2F-LoJI2UjwfL_-bXdA-VZ%2Fhamiltonian%20path4.PNG?generation=1568003603563802\&alt=media)At this point in time, the stack has elements `[8,3]`. Once the algorithm discovers that path `1...9` is not a Hamiltonian path, it must backtrack to find the top element in the stack `[3]`. However we can see that vertex `13` is connected to vertex `3`. We need another piece of information, which is that `[3]` has come from parent `[1]`. So we backtrack until our path contains this parent element as well.
