Why my code for finding an Euler Circuit of a graph only works partially?

Question

So Ive managed to create a 'circuit' function that traverses through a graph untill it arrives back to the starting point. Now Im trying to run it for as long as theres free vertices to find all paths. For now Im just trying to add new paths to the path but Im aware that i need to inject it at the right point into the path in order to get a valid Eulerian Circuit. Unfortunately after a long trial and error session I failed to get the second part working.

I would appreciate some help with that. Thanks

heres my code:

verts = [(1, 2), (2, 3), (1, 6), (6, 5), (5, 3), (6, 3), (2, 5), (5, 4), (3, 4), (6,2)]


# find circles
def circuit(current, path = []):
    path.append(current)
    
    if current in verts:
        verts.remove(current)
    elif current[::-1] in verts:
        verts.remove(current[::-1])
    
    
    if path[0][0] == current[1]:
        return path
    
    for i in verts:
        if current[1] == i[0]:
            return circuit(i, path)
        elif current[1] == i[1]:
            return circuit((i[1], i[0]), path)
        
    
# loss = random.randint(0,10)
# print(circuit(verts[loss]))

start = (1, 2)
path = []
if path == []:
    path += circuit(start)

while len(list(verts)) > 0:
    for unusedVert in list(verts):
        
        for pathVerts in path:
            if unusedVert[0] == pathVerts[0]:
                print(1)
                path.append(circuit(unusedVert))
                break
            elif unusedVert[0] == pathVerts[1]:
                print(2)
                path.append(circuit((unusedVert[1], unusedVert[0])))
                break
            elif unusedVert[1] == pathVerts[0]:
                print(3)
                path.append(circuit(unusedVert))
                break
            elif unusedVert[1] == pathVerts[1]:
                print(4)
                path.append(circuit((unusedVert[1], unusedVert[0])))
                break

                    
print(path)

Answer 1

There are a few problems:

• The default parameter setting path = [] is dangerous, because in Python that default value is only created once, and that has an undesired effect on your code. See "Least Astonishment" and the Mutable Default Argument for details on this behaviour.

• path.append(circuit(unusedVert)) is not correct, because that only adds one entry to path, and because circuit returns a list, that element will be a list (nested inside path)

• By intending to extend the path, you will not collect the circuit edges in the right order, since the match in one of the four if conditions could be somewhere halfway the path, and so the next edge should be inserted at that spot in the path.

I would suggest using a deque which supports rotation, which facilitates the insertion that you would need to do (last bullet point). Also, I would first create an adjacency list, so to avoid the many iterations over the list of edges.

Here is how it could work:

from collections import defaultdict, deque

def create_graph(edges):
    adj = defaultdict(set)
    for a, b in edges:
        adj[a].add(b)
        adj[b].add(a)
    return adj

def has_circuit(adj):
    return all(len(neighbors) % 2 == 0 for neighbors in adj.values())

def get_circuit(edges):
    adj = create_graph(edges)
    if not has_circuit(adj):
        ValueError("Graph has no Euler circuit")

    node = edges[0][0] # Any starting vertex
    circuit = deque()
    for _ in range(len(edges)):  # Each iteration removes an edge
        if not adj[node]: # There is no more unused edge here
            # A circuit completed, but not including all edges
            # Find insertion point to extend current circuit
            while not adj[circuit[0]]:
                circuit.rotate()
            node = circuit[0]
        circuit.append(node)
        # Choose next edge
        neighbor = adj[node].pop()  # remove it in one direction
        adj[neighbor].remove(node)  # ...and in the other direction
        node = neighbor  # Traverse it
    return list(circuit)

Call it like this:

verts = [(1, 2), (2, 3), (1, 6), (6, 5), (5, 3), (6, 3), (2, 5), (5, 4), (3, 4), (6,2)]

circuit = get_circuit(verts)

The result will be a list of vertices (not edges), as that implies what the edges are -- the last vertex in the list is understood to link back to the first:

[6, 1, 2, 3, 4, 5, 2, 6, 3, 5]