Skip to main content

maximum_bipartite_matching_weighted

Function maximum_bipartite_matching_weighted 

Source
pub fn maximum_bipartite_matching_weighted(
    graph: &Graph,
    types: &[bool],
    weights: &[f64],
    eps: f64,
) -> IgraphResult<MatchingResult>
Expand description

Compute a maximum weight matching in a weighted bipartite graph.

Uses the Hungarian algorithm (Kuhn-Munkres) with push-relabel initialization on tight edges. weights[e] gives the weight of edge e (by edge id). eps controls floating-point tolerance for “tight” edge detection; pass 0.0 for integer weights.

use rust_igraph::{create, maximum_bipartite_matching_weighted};

let g = create(&[(0, 2), (0, 3), (1, 2), (1, 3)], 4, false).unwrap();
let types = vec![false, false, true, true];
let weights = vec![1.0, 10.0, 10.0, 1.0];
let r = maximum_bipartite_matching_weighted(&g, &types, &weights, 0.0).unwrap();
assert_eq!(r.matching_size, 2);
assert!((r.matching_weight - 20.0).abs() < 1e-9);