AlgoVerse

Hopcroft–Karp algorithm

Maximum bipartite matching in phases: each phase layers the graph with BFS, then finds several short, separate augmenting paths with DFS.

The simple matching method (one augmenting path per node) costs O(V · E) in the worst case. Hopcroft and Karp (1973) find several augmenting paths together in each phase:

Read the full explanation ↓
Input:
V=8 · E=8 · src=APDF export

The same workers and jobs as bipartite matching; phase 1 matches several at once and phase 2 finds the rest with longer paths.

  1. from collections import deque
  3. INF = float("inf")
  6. def hopcroft_karp(graph, src):
  7. # Side 0 is found by two-colouring each component (the input is bipartite).
  8. side = {}
  9. for s in graph:
  10. if s in side:
  11. continue
  12. side[s] = 0
  13. stack = [s]
  14. while stack:
  15. u = stack.pop()
  16. for v, _ in graph[u]:
  17. if v not in side:
  18. side[v] = 1 - side[u]
  19. stack.append(v)
  20. left = [v for v in graph if side[v] == 0]
  21. match = {v: None for v in graph}
  22. size = 0
  23. phase = 0
  24. while True:
  25. phase = phase + 1
  26. dist, found = layers(graph, left, match)
  27. if not found:
  28. break
  29. for u in left:
  30. if match[u] is None:
  31. if augment(graph, u, match, dist):
  32. size = size + 1
  33. return size, match
  36. def layers(graph, left, match):
  37. dist = {}
  38. queue = deque()
  39. for u in left:
  40. if match[u] is None:
  41. dist[u] = 0
  42. queue.append(u)
  43. found = False
  44. while queue:
  45. u = queue.popleft()
  46. for v, _ in graph[u]:
  47. w = match[v]
  48. if w is None:
  49. found = True
  50. elif w not in dist:
  51. dist[w] = dist[u] + 1
  52. queue.append(w)
  53. return dist, found
  56. def augment(graph, u, match, dist):
  57. for v, _ in graph[u]:
  58. w = match[v]
  59. if w is None:
  60. match[u] = v
  61. match[v] = u
  62. return True
  63. if dist.get(w) == dist[u] + 1:
  64. if augment(graph, w, match, dist):
  65. match[u] = v
  66. match[v] = u
  67. return True
  68. dist[u] = INF
  69. return False

Invariant: In each phase, all augmenting paths found have the shortest possible length and share no node.

Start

ABCDWXYZ
  • Current node (u)
  • Matched edges
  • Edge being checked

Recursion tree

Filled orange = running call · Orange outline = still on the stack · Grey = finished

Local variables

src'A'

Orange = changed in this step

graph dict
  • 'A': [('W', 1), ('X', 1)]
  • 'B': [('W', 1)]
  • 'C': [('X', 1), ('W', 1), ('Y', 1)]
  • 'D': [('Y', 1), ('Z', 1)]
  • 'W': [('A', 1), ('B', 1), ('C', 1)]
  • 'X': [('A', 1), ('C', 1)]
  • 'Y': [('C', 1), ('D', 1)]
  • 'Z': [('D', 1)]

Call stack

  1. hopcroft_karp()line 6
Step 1 of 372
Black = phase · Orange = key stepfree: 0/5 · reach_free: 0/9 · phase: 0/3 · take: 0/4 · grown: 0/4 · dead_end: 0/1 · layer: 0/3 · reroute: 0/3 · no_path: 0/1

    How the work grows with input size

    Average of 5 random graphs per n (fixed seeds). Hollow marker = the input on screen.

    • phase
    • layer
    • current input (n=8)
    051048121620n = number of nodeslayerphase
    Show as a table
    nphaselayer
    420
    82.82.4
    122.42
    163.28.2
    2038
    Explanation

    The idea

    The simple matching method (one augmenting path per node) costs O(V · E) in the worst case. Hopcroft and Karp (1973) find several augmenting paths together in each phase:

    1. A BFS from every free left node layers the graph until it reaches a free right node. A node's layer is the length of the shortest augmenting path to it.
    2. A DFS from each free left node only goes one layer deeper at a time; so only shortest paths are found. A node that hits a dead end is set aside for the rest of the phase.

    Why it is fast

    After each phase the shortest augmenting path gets at least one step longer, and one can show only O(√V) phases are needed. Each phase costs O(E): O(E √V) in total.

    What to watch in the trace

    • The number by each left node is its BFS layer; the coloured edges are the current matching.
    • Use the "every loop round" detail level to go phase by phase.