# 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:

![](/files/-LoJI2Uhf02XVClsgDyo)

Our DFS tree for vertex 1 looks like follows:

![](/files/-LoJI2UjwfL_-bXdA-VZ)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.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/ecs122a-algorithm-design-lecture-notes/basic_graph_algorithms/hamiltonian-path/implementation.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.