Function hopcroft_karp 

pub fn hopcroft_karp(adj: &[Vec<usize>], right_size: usize) -> BipartiteMatching

Computes the maximum bipartite matching using the Hopcroft-Karp algorithm.

The bipartite graph is described by an adjacency list for the left partition only: adj[u] contains the indices of right-partition nodes that left-node u is connected to.

Arguments

• adj — adjacency list for left nodes; adj[u] = list of right nodes adjacent to left node u. Left nodes are indexed 0..adj.len().
• right_size — the number of nodes in the right partition, indexed 0..right_size.

Returns

A BipartiteMatching with the match assignments and total matching size.

Algorithm

Hopcroft-Karp alternates between two phases:

1. BFS phase — finds the shortest augmenting paths layer by layer, producing a layered graph.
2. DFS phase — finds a maximal set of vertex-disjoint augmenting paths within the layered graph and augments all of them simultaneously.

Each round of BFS + DFS increases the length of the shortest remaining augmenting path. Since augmenting path lengths are odd integers bounded by V, there are at most √V rounds, each taking O(E) — giving O(E · √V) total.

Complexity

O(E · √V).

Examples

use graph_flow::hopcroft_karp;

// Bipartite graph:
//   Left 0 — Right 0
//   Left 0 — Right 1
//   Left 1 — Right 1
//   Left 2 — Right 2
//
// Maximum matching: (0,0), (1,1), (2,2) — size 3.
let adj = vec![
    vec![0usize, 1], // left 0 connects to right 0 and 1
    vec![1],         // left 1 connects to right 1
    vec![2],         // left 2 connects to right 2
];
let matching = hopcroft_karp(&adj, 3);
assert_eq!(matching.matching_size, 3);