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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

use crate::{Graph, Vertex};
use std::collections::HashSet;

/// Gets the connected groups in the graph
pub fn connected_groups(graph: &Graph) -> Vec<Vec<Vertex>> {
    let mut groups = vec![];
    let mut seen = HashSet::new();
    let mut todo = HashSet::new();

    loop {
        for &v in graph.vertices() {
            if seen.insert(v) {
                todo.insert(v);
                break;
            }
        }

        if todo.is_empty() {
            return groups;
        }

        while let Some(&v) = todo.iter().next() {
            todo.remove(&v);
            for &e in graph.vertices_from(v) {
                if seen.insert(e) {
                    todo.insert(e);
                }
            }
        }

        groups.push(seen.iter().cloned().collect());
    }
}

#[test]
fn two_groups() {
    let g: Graph = [
        (0, vec![1]),
        (1, vec![0, 2]),
        (2, vec![1]),
        (3, vec![4]),
        (4, vec![3]),
    ]
    .iter()
    .collect();
    assert_eq!(2, connected_groups(&g).len());
}