graphs.hopcroft_karp

Hopcroft-Karp algorithm for finding maximum cardinality matching in bipartite graphs.

Reference:

https://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm

The Hopcroft-Karp algorithm finds a maximum cardinality matching in an unweighted bipartite graph in O(|E| * sqrt(|V|)) time.

Key Concepts and Conditions: 1. Bipartite Condition:

A graph G = (U union V, E) is bipartite if its vertices can be partitioned into two disjoint sets U (left partition) and V (right partition) such that every edge connects a vertex in U to a vertex in V. No edges may exist between two vertices within the same partition (U intersect V = empty set). Vertices cannot be None.

  1. Matching Condition: A matching M is a subset of edges such that no two edges share a common vertex. A vertex is ‘free’ (unmatched) if it is not incident to any edge in M.

  2. Alternating and Augmenting Paths: - Alternating path: A path whose edges alternate between unmatched edges

    (not in M) and matched edges (in M).

    • Augmenting path: An alternating path that starts and ends at distinct free vertices.

    • Berge’s Lemma: A matching is of maximum cardinality if and only if no augmenting paths exist.

  3. Hopcroft-Karp Layering and Augmentation Conditions: Instead of searching for augmenting paths one-by-one (O(|V| * |E|)), Hopcroft-Karp operates in phases: - BFS Phase (Layering): Simultaneously searches from all free vertices in U to

    find the length of the shortest augmenting paths. It builds a layered DAG of alternating levels. If no free vertex in V is reachable, the algorithm terminates.

    • DFS Phase (Augmentation): Discovers a maximal set of vertex-disjoint augmenting paths of the shortest length found by BFS. It only traverses edges satisfying: distance_map[matched_left] == distance_map[curr_left] + 1.

    • Symmetric Difference: Matching edges along each augmenting path are flipped (unmatched becomes matched, matched becomes unmatched).

    • Iterative DFS: The DFS phase is implemented iteratively using an explicit stack to prevent RecursionError on graphs with large alternating path diameters.

Complexity:

Time Complexity: O(|E| * sqrt(|V|)) Space Complexity: O(|V| + |E|)

Attributes

_NIL

Classes

HopcroftKarp

Class implementing the Hopcroft-Karp maximum bipartite matching algorithm.

Functions

hopcroft_karp(→ dict[T, T])

Find a maximum cardinality matching in a bipartite graph using Hopcroft-Karp.

test_hopcroft_karp(→ None)

Pytest test function to verify maximum bipartite matching functionality.

Module Contents

class graphs.hopcroft_karp.HopcroftKarp[T](graph: dict[T, list[T]])

Class implementing the Hopcroft-Karp maximum bipartite matching algorithm.

>>> hk = HopcroftKarp({"u1": ["v1", "v2"], "u2": ["v1"], "u3": ["v2", "v3"]})
>>> hk.maximum_matching()
{'u1': 'v2', 'u2': 'v1', 'u3': 'v3'}

BFS Phase: Layer the graph and find shortest augmenting path length.

Returns:

True if at least one augmenting path to a free vertex in V exists, False otherwise (termination condition).

>>> hk = HopcroftKarp({"u1": ["v1"]})
>>> hk.breadth_first_search()
True
>>> hk.pair_left["u1"] = "v1"
>>> hk.pair_right["v1"] = "u1"
>>> hk.breadth_first_search()
False

DFS Phase: Find and augment along shortest augmenting paths iteratively.

Implemented iteratively with an explicit stack to prevent RecursionError on graphs with deep alternating paths (diameter > 1000).

Parameters:

start_left: The free vertex in the left partition to start the search from.

Returns:

True if an augmenting path was found and augmented, False otherwise.

>>> hk = HopcroftKarp({"u1": ["v1"]})
>>> _ = hk.breadth_first_search()
>>> hk.depth_first_search("u1")
True
>>> hk.pair_left["u1"]
'v1'
>>> hk.depth_first_search("u1")
False
maximum_matching() → dict[T, T]

Compute and return the maximum cardinality matching.

>>> hk = HopcroftKarp({"u1": ["v1"], "u2": ["v1"]})
>>> hk.maximum_matching()
{'u1': 'v1'}
distance_map: dict[T | object, float]
graph
left_vertices
pair_left: dict[T, T | object]
pair_right: dict[T, T | object]
right_vertices
graphs.hopcroft_karp.hopcroft_karp[T](graph: dict[T, list[T]]) → dict[T, T]

Find a maximum cardinality matching in a bipartite graph using Hopcroft-Karp.

Parameters:
graph: An adjacency list mapping each vertex in the left partition (U) to

a list of adjacent vertices in the right partition (V). The two partitions must be disjoint, and vertices cannot be None.

Returns:

A dictionary representing the matching, mapping each matched vertex in the left partition to its matched partner in the right partition.

Raises:

ValueError: If any vertex appears in both partitions or if any vertex is None.

Examples:
>>> # Standard bipartite matching
>>> graph = {"u1": ["v1", "v2"], "u2": ["v1"], "u3": ["v2", "v3"]}
>>> hopcroft_karp(graph)
{'u1': 'v2', 'u2': 'v1', 'u3': 'v3'}

>>> # Empty graph condition
>>> hopcroft_karp({})
{}

>>> # Isolated vertices (no incident edges)
>>> hopcroft_karp({"u1": []})
{}

>>> # Competing vertices (more left vertices than right vertices)
>>> hopcroft_karp({"u1": ["v1"], "u2": ["v1"]})
{'u1': 'v1'}

>>> # Bipartite cycle (6 vertices)
>>> cycle_graph = {
...     "u1": ["v1", "v2"],
...     "u2": ["v2", "v3"],
...     "u3": ["v3", "v1"],
... }
>>> hopcroft_karp(cycle_graph)
{'u1': 'v1', 'u2': 'v2', 'u3': 'v3'}

>>> # Error condition: Overlapping partitions (not a valid bipartite graph)
>>> hopcroft_karp({"A": ["A"]})
Traceback (most recent call last):
    ...
ValueError: Partitions must be disjoint: found vertices in both sets: ['A']

>>> # Error condition: None vertex
>>> hopcroft_karp({"u": [None]})
Traceback (most recent call last):
    ...
ValueError: Vertices cannot be None
graphs.hopcroft_karp.test_hopcroft_karp() → None

Pytest test function to verify maximum bipartite matching functionality.

>>> test_hopcroft_karp()
graphs.hopcroft_karp._NIL