Hamiltonian Path in a simple DAG

205 Views Asked by At

I am trying to implement a recursive search for a Hamiltonian Path in a simple DAG. Here's my toy data and code:

DAG in edge-list format

4 5
1 2
3 1
3 2
4 3
4 2

DAG in dictionary format after converting

{1: [2], 3: [1, 2], 4: [3, 2]}

Code: G is the graph, size is the number of vertices in the graph, v is the current vertex, v_next is the neighbor vertex.

def hamilton(G, size, v, path=[]):
    if v not in set(path):  
        path.append(v)
        if len(path) == size:
            return path
        for v_next in G.get(v, []):
            cur_path = [i for i in path]
            result = hamilton(G, size, v_next, cur_path)
            if result is not None:  
                return result
    else:
        print('')

When I looped through the vertex (from 1 to 4) and run the function at each loop, the result is kind of weird.

for vertex in range(1, v+1):
    result = hamilton(graph, v, vertex)
    print(result)

None
None
None
[1, 2, 3, 4]

I expect the result would be [4, 3, 1, 2] when starting from 4. One post mentioned before this is because "mutable default arguments" problem. But I do not know how to solve in this case. Any hints?

0

There are 0 best solutions below