geometric-traits 0.1.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
31

//! Submodule providing the `Gabow1976` trait for maximum cardinality matching
//! in general (non-bipartite) graphs using Gabow's 1976 implementation of
//! Edmonds' algorithm.
use alloc::vec::Vec;

mod inner;

use inner::Gabow1976State;

use crate::traits::SparseSquareMatrix;

/// Maximum cardinality matching in general graphs via Gabow's 1976
/// implementation of Edmonds' algorithm.
pub trait Gabow1976: 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^3) time, O(V) auxiliary space.
    #[inline]
    fn gabow_1976(&self) -> Vec<(Self::Index, Self::Index)> {
        Gabow1976State::new(self).solve()
    }
}

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