pub fn bipartite_maximum_matching<V: Eq + Hash + Clone + Debug>(
graph: &Graph<V>,
partition: &[i8],
) -> Vec<(usize, usize)>
Expand description
Finds the maximum cardinality matching in a bipartite graph by reducing it to a max-flow problem.
A matching is a set of edges without common vertices. A maximum matching is one with the largest possible number of edges. This function constructs a flow network from the bipartite graph and uses a max-flow algorithm to find the matching.
§Arguments
graph
- The bipartite graph.partition
- The partition of vertices into two sets (fromis_bipartite
).
§Returns
A Vec<(usize, usize)>
representing the edges (u, v)
in the maximum matching.