Function petgraph::algo::matching::maximum_matching
source · pub fn maximum_matching<G>(graph: G) -> Matching<G>
Expand description
[Generic] Compute the maximum matching using Gabow’s algorithm.
The input graph is treated as if undirected. The algorithm runs in O(|V|³). An algorithm with a better time complexity might be used in the future.
Panics if g.node_bound()
is std::usize::MAX
.
§Examples
use petgraph::prelude::*;
use petgraph::algo::maximum_matching;
// The example graph:
//
// +-- b ---- d ---- f
// / | |
// a | |
// \ | |
// +-- c ---- e
//
// Maximum matching: { (a, b), (c, e), (d, f) }
let mut graph: UnGraph<(), ()> = UnGraph::new_undirected();
let a = graph.add_node(());
let b = graph.add_node(());
let c = graph.add_node(());
let d = graph.add_node(());
let e = graph.add_node(());
let f = graph.add_node(());
graph.extend_with_edges(&[(a, b), (a, c), (b, c), (b, d), (c, e), (d, e), (d, f)]);
let matching = maximum_matching(&graph);
assert!(matching.contains_edge(a, b));
assert!(matching.contains_edge(c, e));
assert_eq!(matching.mate(d), Some(f));
assert_eq!(matching.mate(f), Some(d));