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.