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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

use std::collections::HashMap;

use crate::Edge;
use crate::Vertex;

/// Represents a matching in a graph.
#[derive(Clone, Debug)]
pub struct Matching {
    edges: HashMap<Vertex, Vertex>,
}

impl Matching {
    /// Create a new matching from given edges
    pub fn new(edges: &[Edge]) -> Matching {
        let mut map = HashMap::new();
        for &(v, w) in edges {
            map.insert(v, w);
            map.insert(w, v);
        }
        Matching { edges: map }
    }

    /// Returns a value indicating whether the matching is empty.
    pub fn is_empty(&self) -> bool {
        self.edges.is_empty()
    }

    /// Returns the number of edges in the graph.
    pub fn len(&self) -> usize {
        self.edges.len() / 2
    }

    /// Exports all edges in a vector.
    pub fn edges(&self) -> Vec<Edge> {
        self.edges
            .iter()
            .filter(|&(&v, &w)| v < w)
            .map(|(&v, &w)| (v, w))
            .collect()
    }

    /// Exports all edges in a vector.
    pub fn vertices(&self) -> Vec<Vertex> {
        self.edges.keys().cloned().collect()
    }

    /// Gets the vertex that `vertex` is connected to.
    /// Panics if matching does not contain a vertex `vertex`.
    pub fn partner(&self, vertex: Vertex) -> Vertex {
        self.edges[&vertex]
    }

    /// Creates a contracted matching with edges between `leafs` removed.
    pub fn contract(&self, leafs: &[Vertex]) -> Matching {
        let mut edges = self.edges.clone();
        for leaf in leafs {
            edges.remove(leaf);
        }
        Matching { edges }
    }

    /// Creates a expanded matching using the augmenting `path`.
    pub fn augment(&self, path: &[Vertex]) -> Matching {
        let mut edges = self.edges.clone();
        for leaf in path {
            edges.remove(leaf);
        }
        for (i, j) in (0..path.len() / 2).map(|i| (2 * i, 2 * i + 1)) {
            edges.insert(path[i], path[j]);
            edges.insert(path[j], path[i]);
        }
        Matching { edges }
    }

    /// Adds a matching
    pub fn add(&self, other: &Matching) -> Matching {
        let mut edges = self.edges.clone();
        for (&v, &w) in &other.edges {
            edges.insert(v, w);
        }
        Matching { edges }
    }
}