Fleury's algorithm in Python
Builds an Eulerian trail of an undirected multigraph edge by edge, never crossing a bridge of the unused edges unless it is the only edge left at the current vertex.
- File
fleury_algorithm.py, 91 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/fleury-algorithm/. The authors are listed in prov/CVA0RG.jsonl.
def _reachable(inc: list[list[int]], edges: list[tuple[int, int]], used: list[bool], s: int, t: int) -> bool:
"""Is t reachable from s through edges that are not used? Iterative search."""
if s == t:
return True
seen = {s}
stack = [s]
while stack:
x = stack.pop()
for e in inc[x]:
if used[e]:
continue
a, b = edges[e]
y = b if a == x else a
if y == t:
return True
if y not in seen:
seen.add(y)
stack.append(y)
return False
def fleury_algorithm(n: int, edges: list[tuple[int, int]]) -> tuple[list[int], list[int]] | None:
"""Return an Eulerian trail of an undirected multigraph, or None if it has none.
The vertices are 0 .. n-1 and edge i is edges[i] = (u, v). Parallel edges, self-loops
and isolated vertices are allowed. The result is (walk, trail): walk lists the m + 1
vertices and trail the m edge numbers, and trail[i] joins walk[i] to walk[i+1].
The trail starts at an odd vertex if there is one, so it is closed when all degrees
are even. At each step it leaves the current vertex by an edge that is not a bridge
of the unused edges, unless that edge is the only one. Time O(m (n + m)).
"""
m = len(edges)
if n == 0:
return ([], []) if m == 0 else None
if m == 0:
return ([0], [])
inc: list[list[int]] = [[] for _ in range(n)]
deg = [0] * n
for e, (u, v) in enumerate(edges):
inc[u].append(e)
if u != v:
inc[v].append(e)
deg[u] += 1
deg[v] += 1 # a loop adds 2
used = [False] * m
odd = [v for v in range(n) if deg[v] % 2 == 1]
# The Euler condition: 0 or 2 odd vertices and all edges in one component. @line L1
if len(odd) > 2:
return None
start = odd[0] if odd else edges[0][0] # @line L2
if not all(_reachable(inc, edges, used, start, edges[e][0]) for e in range(m)):
return None
walk = [start] # @line L3
trail: list[int] = []
left = deg[:] # the degrees in the graph H of unused edges
ptr = [0] * n # unused edges before ptr[u] in inc[u] are skipped for good
u = start
while left[u] > 0: # @line L4
while used[inc[u][ptr[u]]]:
ptr[u] += 1
if left[u] == 1: # @line L5
e = inc[u][ptr[u]]
else:
# An edge at u that is not a bridge of H. At most one edge at u is a bridge,
# so at most two candidates are tested. @line L6
e = -1
for i in range(ptr[u], len(inc[u])):
f = inc[u][i]
if used[f]:
continue
a, b = edges[f]
v = b if a == u else a
used[f] = True
ok = _reachable(inc, edges, used, u, v) # f is a bridge iff this fails
used[f] = False
if ok:
e = f
break
used[e] = True # @line L7
trail.append(e)
a, b = edges[e]
w = b if a == u else a
left[u] -= 1
left[w] -= 1
u = w # @line L8
walk.append(u)
return walk, trail # @line L9
test_fleury_algorithm.py 96 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/fleury-algorithm/. The authors are listed in prov/CVA0RG.jsonl.
import random
from fleury_algorithm import fleury_algorithm
def is_trail(n: int, edges: list[tuple[int, int]], walk: list[int], trail: list[int]) -> bool:
if sorted(trail) != list(range(len(edges))) or len(walk) != len(trail) + 1:
return False
for i, e in enumerate(trail):
if sorted(edges[e]) != sorted((walk[i], walk[i + 1])):
return False
return True
def has_trail_brute(n: int, edges: list[tuple[int, int]]) -> bool:
"""Try every order and orientation of the edges, by depth-first search."""
m = len(edges)
if m == 0:
return True
inc: list[list[int]] = [[] for _ in range(n)]
for e, (u, v) in enumerate(edges):
inc[u].append(e)
if u != v:
inc[v].append(e)
for s in range(n):
stack = [(s, 0, (1 << m) - 1)]
while stack:
u, k, free = stack.pop()
if free == 0:
return True
for e in inc[u]:
if free >> e & 1:
a, b = edges[e]
stack.append((b if a == u else a, k + 1, free & ~(1 << e)))
return False
def test_example() -> None:
# A triangle 0, 1, 2 with a pendant edge to 3 listed first at vertex 0.
edges = [(0, 3), (0, 1), (1, 2), (2, 0)]
assert fleury_algorithm(4, edges) == ([0, 1, 2, 0, 3], [1, 2, 3, 0])
def test_house_of_nicholas() -> None:
# The house of Nicholas: a square 0, 1, 2, 3 with both diagonals and a roof vertex 4.
edges = [(0, 1), (1, 2), (2, 3), (3, 0), (0, 2), (1, 3), (2, 4), (3, 4)]
walk, trail = fleury_algorithm(5, edges)
assert walk == [0, 1, 2, 3, 0, 2, 4, 3, 1]
assert trail == [0, 1, 2, 3, 4, 6, 7, 5]
def test_edge_cases() -> None:
assert fleury_algorithm(0, []) == ([], [])
assert fleury_algorithm(3, []) == ([0], [])
assert fleury_algorithm(1, [(0, 0)]) == ([0, 0], [0]) # one self-loop
assert fleury_algorithm(2, [(0, 1), (0, 1)]) == ([0, 1, 0], [0, 1]) # parallel edges
# isolated vertex 0 does not matter
walk, trail = fleury_algorithm(4, [(1, 2), (2, 3), (3, 1)])
assert walk[0] == walk[-1] and sorted(trail) == [0, 1, 2]
# two components with edges: no trail
assert fleury_algorithm(4, [(0, 1), (2, 3)]) is None
# four odd vertices: the star K_{1,3} has no trail
assert fleury_algorithm(4, [(0, 1), (0, 2), (0, 3)]) is None
# a loop on a path
walk, trail = fleury_algorithm(3, [(0, 1), (1, 1), (1, 2)])
assert walk == [0, 1, 1, 2]
def test_trap_bridge_is_avoided() -> None:
# Two triangles joined at vertex 0. From 0, any first edge is fine, but at the far
# vertex of the first triangle, the walk must not cross back before the triangle ends.
edges = [(0, 1), (1, 2), (2, 0), (0, 3), (3, 4), (4, 0)]
walk, trail = fleury_algorithm(5, edges)
assert is_trail(5, edges, walk, trail) and walk[0] == walk[-1]
def test_random_against_brute_force() -> None:
rng = random.Random(20261105)
for case in range(1500):
n = rng.randint(1, 6)
m = rng.randint(0, 8)
edges = [(rng.randrange(n), rng.randrange(n)) for _ in range(m)]
res = fleury_algorithm(n, edges)
expected = has_trail_brute(n, edges)
assert (res is not None) == expected, (n, edges)
if res is not None and m > 0:
walk, trail = res
assert is_trail(n, edges, walk, trail)
odd = [v for v in range(n) if sum((a == v) + (b == v) for a, b in edges) % 2]
if not odd:
assert walk[0] == walk[-1]
else:
assert {walk[0], walk[-1]} == set(odd)
What the next level needs
- the tests did not run in this build