bipartite_maximum_matching

Function bipartite_maximum_matching 

Source
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 (from is_bipartite).

§Returns

A Vec<(usize, usize)> representing the edges (u, v) in the maximum matching.