geometric-traits 0.2.0

Trait-based algebraic and graph algorithms for Rust, supporting no_std environments
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

//! Submodule providing the `Blossom` trait for maximum cardinality matching
//! in general (non-bipartite) graphs using the Edmonds blossom algorithm.
use alloc::vec::Vec;

mod inner;

use inner::BlossomState;

use crate::traits::SparseSquareMatrix;

/// Maximum cardinality matching in general graphs via the Edmonds blossom
/// algorithm.
pub trait Blossom: SparseSquareMatrix {
    /// Returns a maximum cardinality matching as a list of edge pairs `(u, v)`
    /// with `u < v`.
    ///
    /// The input matrix is expected to be symmetric (representing an undirected
    /// graph). Self-loops are ignored. Non-symmetric input will not panic but
    /// the result is unspecified.
    ///
    /// # Complexity
    ///
    /// O(V² · E) time, O(V) space.
    #[inline]
    fn blossom(&self) -> Vec<(Self::Index, Self::Index)> {
        BlossomState::new(self).solve()
    }
}

impl<M: SparseSquareMatrix + ?Sized> Blossom for M {}