Euler paths and circuits

Euler paths and circuits answer one question about a graph: can a single walk use every edge exactly once? An Euler path may end anywhere; an Euler circuit must end where it began. In an undirected graph whose edges form one connected piece, an Euler circuit exists exactly when every vertex has even degree, and an Euler path exactly when zero or two vertices have odd degree; with two, the path runs from one odd vertex to the other. In a directed graph every vertex needs as many edges in as out for a circuit, and for a path one start vertex may have one extra edge out and one end vertex one extra edge in. Hierholzer’s algorithm builds Euler circuits and paths in O(E) time. Visiting every vertex once instead, the Hamiltonian problem, sounds similar and is NP-complete.

Every street once: the degree test

A road-inspection truck must drive every street of a small map exactly once. Map B has seven junctions and nine two-way streets:

Each time a route passes through a junction, it uses two of its streets, one to arrive and one to leave. Only where the route starts and where it ends is a single street used without a partner. So every junction where the route neither starts nor ends must have even degree, and a route that drives every street once can exist only if zero or two junctions have odd degree. Map B has two, junctions 0 and 4, so its route must run between them. Map A, the same map with one more street from 1 to 3, has four odd junctions, so no such route exists, however it is searched for.

The degree test needs one more condition: all the streets must lie in one connected piece. A junction with no streets does not matter, but two separate groups of streets can never be driven in one walk, even when every degree is even. When the test fails, the shortest route that drives every street at least once, the Chinese postman route, repeats a few streets.

Hierholzer’s algorithm, step by step

Start at an odd junction, or anywhere when every degree is even, and keep a stack of junctions.

1. Look at the junction on top of the stack. If it still has an unused street, mark the street used, and push the junction at its other end.
2. If it has no unused street left, pop it and add it to the route.
3. Repeat until the stack is empty, then reverse the route.

A walk that gets stuck before every street is used is not a failure. The stack still holds the junctions of the walk, and the first one with an unused street starts a new loop, which the route takes in at that junction:

# A road-inspection truck must drive every street of a small map exactly once. First the degree test on two versions
# of the map, then Hierholzer's algorithm builds the route with an explicit stack: walk along unused streets until
# stuck, and add a junction to the route only when it has no unused street left. The trace prints each walk.

def degrees(n, streets):
    deg = [0] * n
    for u, v in streets:
        deg[u] += 1
        deg[v] += 1
    return deg


def inspection_route(n, streets, trace=False):
    """A route that uses every street once, as a list of junctions, or None."""
    adj = [[] for _ in range(n)]
    for i, (u, v) in enumerate(streets):
        adj[u].append((v, i))
        adj[v].append((u, i))
    odd = [v for v in range(n) if len(adj[v]) % 2 == 1]
    if len(odd) not in (0, 2):
        return None
    start = odd[0] if odd else next(v for v in range(n) if adj[v])
    used, nxt = [False] * len(streets), [0] * n      # nxt[v]: the first street of v that may still be unused
    stack, route, walk = [start], [], [start]
    while stack:
        v = stack[-1]
        while nxt[v] < len(adj[v]) and used[adj[v][nxt[v]][1]]:
            nxt[v] += 1
        if nxt[v] == len(adj[v]):
            if trace and len(walk) > 1:
                print(f"  walk {' '.join(map(str, walk))}: stuck at {walk[-1]}")
            walk = []
            route.append(stack.pop())                 # stuck: v is final, from the end of the route backwards
        else:
            if trace and not walk:
                print(f"  back up to {v}, which still has an unused street")
                walk = [v]
            w, i = adj[v][nxt[v]]
            used[i] = True
            stack.append(w)
            walk.append(w)
    if len(route) != len(streets) + 1:
        return None                                   # some streets lie in another piece of the map
    return route[::-1]


MAP_A = [(0, 1), (1, 2), (2, 4), (4, 5), (5, 6), (6, 4), (2, 3), (3, 0), (0, 2), (1, 3)]
MAP_B = MAP_A[:-1]                                    # the same map without the street from 1 to 3
for name, streets in [("map A", MAP_A), ("map B", MAP_B)]:
    deg = degrees(7, streets)
    odd = [v for v in range(7) if deg[v] % 2]
    print(f"{name}: {len(streets)} streets, degrees {deg}, odd junctions {odd}")
print("map B, Hierholzer's walks:")
route = inspection_route(7, MAP_B, trace=True)
print("map B route:", " -> ".join(map(str, route)))
driven = sorted(tuple(sorted(p)) for p in zip(route, route[1:]))
print("every street exactly once:", driven == sorted(tuple(sorted(s)) for s in MAP_B))
print("map A route:", inspection_route(7, MAP_A))

map A: 10 streets, degrees [3, 3, 4, 3, 3, 2, 2], odd junctions [0, 1, 3, 4]
map B: 9 streets, degrees [3, 2, 4, 2, 3, 2, 2], odd junctions [0, 4]
map B, Hierholzer's walks:
  walk 0 1 2 4 5 6 4: stuck at 4
  back up to 2, which still has an unused street
  walk 2 3 0 2: stuck at 2
map B route: 0 -> 1 -> 2 -> 3 -> 0 -> 2 -> 4 -> 5 -> 6 -> 4
every street exactly once: True
map A route: None

The first walk, 0 1 2 4 5 6 4, ends at junction 4 with three streets still unused. Backing up the stack, junction 2 still has the street to 3, so a second walk, 2 3 0 2, starts there and closes a loop. The finished route, read backwards from the pops, drives the loop when it reaches 2: 0, 1, 2, 3, 0, 2, 4, 5, 6, 4. Each street is pushed once and each junction popped once per visit, so the work is O(V + E).

Euler or Hamiltonian

The two look alike in a problem statement, so read which one it asks for. Covering every vertex is the travelling salesman’s world, where Karp’s 1972 list of NP-complete problems puts the Hamiltonian circuit, while covering every edge needs only degrees and one search.

Exercise and self-check

Return a path through every edge of a directed graph, or report that none exists, up to a cycle of 100,000 edges.

def euler_path(n, edges):
    """The vertices of a path that uses every edge exactly once, or [] if there is none."""
    raise NotImplementedError("write euler_path")

import random
from collections import Counter

from euler import euler_path


def is_euler_path(path, edges):
    return len(path) == len(edges) + 1 and Counter(zip(path, path[1:])) == Counter(map(tuple, edges))


def test_lesson_example():
    """six edges with one start and one end"""
    edges = [(0, 1), (1, 2), (2, 0), (0, 3), (3, 1), (1, 4)]
    path = euler_path(5, edges)
    assert is_euler_path(path, edges), path
    assert path[0] == 0 and path[-1] == 4


def test_degree_test_fails():
    """two edges out of one vertex, and two separate starts"""
    assert euler_path(3, [(0, 1), (0, 2)]) == []
    assert euler_path(4, [(0, 1), (2, 3)]) == []


def test_two_pieces():
    """every degree balanced, but the edges form two loops that never meet"""
    assert euler_path(6, [(0, 1), (1, 2), (2, 0), (3, 4), (4, 5), (5, 3)]) == []


def test_loops_and_repeats():
    """a loop at a vertex and an edge given twice"""
    for edges in ([(0, 0)], [(0, 1), (1, 0), (0, 1), (1, 0)], [(2, 2), (2, 0), (0, 2)], [(1, 1), (1, 2), (2, 1), (1, 1)]):
        path = euler_path(3, edges)
        assert is_euler_path(path, edges), (edges, path)


def test_random_walks():
    """200 random walks: their edges, shuffled, always have an Euler path"""
    rng = random.Random(23)
    for _ in range(200):
        n = rng.randint(1, 6)
        walk = [rng.randrange(n) for _ in range(rng.randint(2, 12))]
        edges = list(zip(walk, walk[1:]))
        rng.shuffle(edges)
        assert is_euler_path(euler_path(n, edges), edges), (n, edges)


def test_long_cycle():
    """a single cycle of 100,000 edges"""
    n = 100_000
    edges = [(i, (i + 1) % n) for i in range(n)]
    path = euler_path(n, edges)
    assert is_euler_path(path, edges)

/** The vertices of a path that uses every edge exactly once, or [] if there is none. */
export function eulerPath(n, edges) {
  throw new Error('write eulerPath');
}

import { test, assert } from 'mysmartcopilot:test';
import { eulerPath } from './euler.mjs';

/** Whether consecutive vertices of the path use every edge exactly once. */
function isEulerPath(path, edges) {
  if (!Array.isArray(path) || path.length !== edges.length + 1) return false;
  const count = new Map();
  for (const [u, v] of edges) count.set(`${u},${v}`, (count.get(`${u},${v}`) ?? 0) + 1);
  for (let i = 0; i + 1 < path.length; i++) {
    const key = `${path[i]},${path[i + 1]}`;
    const left = count.get(key) ?? 0;
    if (left === 0) return false;
    count.set(key, left - 1);
  }
  return true;
}

test('six edges with one start and one end', () => {
  const edges = [[0, 1], [1, 2], [2, 0], [0, 3], [3, 1], [1, 4]];
  const path = eulerPath(5, edges);
  assert.ok(isEulerPath(path, edges), JSON.stringify(path));
  assert.equal(path[0], 0);
  assert.equal(path[path.length - 1], 4);
});

test('two edges out of one vertex, and two separate starts', () => {
  assert.deepEqual(eulerPath(3, [[0, 1], [0, 2]]), []);
  assert.deepEqual(eulerPath(4, [[0, 1], [2, 3]]), []);
});

test('every degree balanced, but the edges form two loops that never meet', () => {
  assert.deepEqual(eulerPath(6, [[0, 1], [1, 2], [2, 0], [3, 4], [4, 5], [5, 3]]), []);
});

test('a loop at a vertex and an edge given twice', () => {
  for (const edges of [[[0, 0]], [[0, 1], [1, 0], [0, 1], [1, 0]], [[2, 2], [2, 0], [0, 2]], [[1, 1], [1, 2], [2, 1], [1, 1]]]) {
    const path = eulerPath(3, edges);
    assert.ok(isEulerPath(path, edges), JSON.stringify([edges, path]));
  }
});

test('200 random walks: their edges, shuffled, always have an Euler path', () => {
  let seed = 23;
  const random = () => (seed = (seed * 48271) % 2147483647) / 2147483647;
  const pick = (k) => Math.floor(random() * k);
  for (let t = 0; t < 200; t++) {
    const n = 1 + pick(6);
    const walk = Array.from({ length: 2 + pick(11) }, () => pick(n));
    const edges = walk.slice(1).map((v, i) => [walk[i], v]);
    for (let i = edges.length - 1; i > 0; i--) {
      const j = pick(i + 1);
      [edges[i], edges[j]] = [edges[j], edges[i]];
    }
    assert.ok(isEulerPath(eulerPath(n, edges), edges), JSON.stringify([n, edges]));
  }
});

test('a single cycle of 100,000 edges', () => {
  const n = 100000;
  const edges = [];
  for (let i = 0; i < n; i++) edges.push([i, (i + 1) % n]);
  assert.ok(isEulerPath(eulerPath(n, edges), edges));
});

Why the degree test is enough, proved, and why the walk must back up Pro: opens with a Pro, Premium or Ultimate pass

The alphabetically first directed path in five languages, and texts rebuilt from fragments Pro: opens with a Pro, Premium or Ultimate pass

Four bugs reproduced, the shortest route that repeats streets, and a practice set Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

Key takeaways

• Euler paths and circuits use every edge exactly once; Hamiltonian ones visit every vertex once, a far harder problem.
• Undirected: a circuit needs every degree even, a path zero or two odd degrees, with the edges in one piece.
• Directed: in-degree equals out-degree everywhere, except one start and one end that differ by one.
• Hierholzer’s algorithm walks until stuck, pops vertices into the route and splices loops in, in O(E).