Function gamma::matching::maximum_matching

pub fn maximum_matching<'a, G: Graph>(graph: &'a G, pairing: &'a mut Pairing)

Performs a maximum matching over the Graph.

A greedy matching can be used as a starting point to maximum matching, so it may be helpful to try a greedy matching, falling back to maximum matching if the matching isn't perfect.

For more on matching, see: The Maximum Matching Problem.

use std::convert::TryFrom;
use std::collections::BTreeSet;
use gamma::graph::{ Error, DefaultGraph };
use gamma::matching::{ maximum_matching, Pairing };
 
fn main() -> Result<(), Error> {
     let graph = DefaultGraph::try_from(vec![
         (0, 1), (1, 2), (2, 3)
     ]).unwrap();
     let mut pairing = Pairing::new();

     maximum_matching(&graph, &mut pairing);

     assert_eq!(
         pairing.edges().collect::<BTreeSet<_>>(),
           [ (0, 1), (2, 3) ].iter().cloned().collect::<BTreeSet<_>>()
     );

    Ok(())
}