blossom 0.4.0

Implementation of the Blossom algorithm to get a maximum matching in an undirected graph
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

use std::iter;
use std::iter::FromIterator;

use crate::Vertex;

use crate::graph::AnnotatedGraph;

pub type Graph = AnnotatedGraph<()>;

impl FromIterator<(Vertex, Vec<Vertex>)> for Graph {
    fn from_iter<I: IntoIterator<Item = (Vertex, Vec<Vertex>)>>(iter: I) -> Self {
        Self::new(
            iter.into_iter()
                .map(|(v, e)| {
                    let len = e.len();
                    (v, (e, iter::repeat(()).take(len).collect()))
                })
                .collect(),
        )
    }
}

impl<'a> FromIterator<&'a (Vertex, Vec<Vertex>)> for Graph {
    fn from_iter<I: IntoIterator<Item = &'a (Vertex, Vec<Vertex>)>>(iter: I) -> Self {
        iter.into_iter().cloned().collect()
    }
}