Struct BipartiteMatching 

pub struct BipartiteMatching {
    pub match_left: Vec<Option<usize>>,
    pub match_right: Vec<Option<usize>>,
    pub matching_size: usize,
}

The result of a Hopcroft-Karp bipartite matching computation.

Fields

match_left: Vec<Option<usize>>

For each node in the left partition, the matched node in the right partition (Some(right_node)) or None if unmatched.

Indexed 0..left_size.

match_right: Vec<Option<usize>>

For each node in the right partition, the matched node in the left partition (Some(left_node)) or None if unmatched.

Indexed 0..right_size.

matching_size: usize

The size of the maximum matching (number of matched pairs).

Implementations

impl BipartiteMatching

pub fn pairs(&self) -> Vec<(usize, usize)>

Returns all matched pairs as (left_node, right_node) tuples.

Examples

use graph_flow::hopcroft_karp;

// Left: {0, 1}, Right: {0, 1}
// Edges: 0→0, 0→1, 1→1
let adj = vec![vec![0usize, 1], vec![1]];
let matching = hopcroft_karp(&adj, 2);
let pairs = matching.pairs();
assert_eq!(pairs.len(), 2);

Trait Implementations

impl Clone for BipartiteMatching

fn clone(&self) -> BipartiteMatching

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for BipartiteMatching

fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error>

Formats the value using the given formatter.