Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Python directed Euler trail: consume every edge identity exactly once

Last updated: 30 Sept 20264 min read
tutorial
IntermediateBy AITrove Editorial

An Euler trail traverses every edge of a graph exactly once, while vertices may appear repeatedly.

Download Python source kit

Operation contract

The owned directed multigraph tracks each edge by its input position. Degree differences select a start for an open trail or reject an impossible degree pattern. A stack consumes outgoing edges and records edges when backtracking; reversing that list produces the trail. The final consumed-edge count rejects disconnected edge-bearing regions even when every local degree difference is balanced. Empty input returns no edges rather than inventing a starting vertex.

Failure and ownership boundary

Parallel edges and self-loops remain distinct through their IDs. A Hamiltonian path visits vertices instead and is a different problem. The fixture accepts at most 32 vertices and 128 edges and chooses a deterministic outgoing order. Python graph BFS: mark a vertex when it enters the queue, Python topological sort: dependency order and cycle rejection and Python graph bridges: track edge identity when parallel links are allowed supply the related contracts.

Working program

python
def euler_trail(vertex_count, edges):
    if type(vertex_count) is not int or not 0 <= vertex_count <= 32 or type(edges) is not list or len(edges) > 128:
        raise ValueError("bounded graph required")
    outgoing, incoming = [[] for _ in range(vertex_count)], [0] * vertex_count
    for edge_id, pair in enumerate(edges):
        if type(pair) is not tuple or len(pair) != 2 or any(type(vertex) is not int or not 0 <= vertex < vertex_count for vertex in pair):
            raise ValueError("valid endpoints required")
        source, target = pair
        outgoing[source].append((target, edge_id))
        incoming[target] += 1
    if not edges:
        return []
    differences = [len(outgoing[vertex]) - incoming[vertex] for vertex in range(vertex_count)]
    starts = [vertex for vertex, degree in enumerate(differences) if degree == 1]
    ends = [vertex for vertex, degree in enumerate(differences) if degree == -1]
    if any(abs(degree) > 1 for degree in differences) or not (len(starts) == len(ends) == 0 or len(starts) == len(ends) == 1):
        raise ValueError("trail degree pattern required")
    start = starts[0] if starts else next(vertex for vertex in range(vertex_count) if outgoing[vertex])
    for neighbors in outgoing:
        neighbors.reverse()
    stack, reversed_edges = [(start, None)], []
    while stack:
        vertex, edge_id = stack[-1]
        if outgoing[vertex]:
            target, next_id = outgoing[vertex].pop()
            stack.append((target, next_id))
        else:
            stack.pop()
            if edge_id is not None:
                reversed_edges.append(edge_id)
    if len(reversed_edges) != len(edges):
        raise ValueError("edge-bearing regions disconnected")
    return list(reversed(reversed_edges))

edges = [(0, 1), (1, 0), (0, 1), (1, 2)]
print("edge IDs:", euler_trail(3, edges))
try:
    euler_trail(4, [(0, 1), (1, 0), (2, 3), (3, 2)])
except ValueError:
    print("disconnected edges rejected")

Output

Output
edge IDs: [0, 1, 2, 3]
disconnected edges rejected

Costs and limits

Adjacency construction and stack traversal take O(V + E) time and storage; each accepted edge is consumed once. This function owns its adjacency lists and preserves the caller edge list. It returns an ordering, not an executed delivery route or cost-optimal route.

Common Mistakes

  • Balanced degree counts alone do not connect separate edge regions.
  • Preserve edge IDs when the graph permits parallel edges.

Connected lessons

Python graph BFS: mark a vertex when it enters the queue, Python graph bridges: track edge identity when parallel links are allowed, Python graph condensation: collapse directed cycles into an acyclic component graph.

python
directed-euler-trail
Storage details