#matching #graph #algorithm #bipartite #edge #karp #hopcroft

hopcroft-karp

霍普克罗夫-卡尔帕二分图匹配算法的最小化实现

4个版本

0.2.1 2022年9月7日
0.2.0 2022年9月1日
0.1.1 2022年8月31日
0.1.0 2022年8月31日

1600算法 中排名

Download history 13/week @ 2024-03-11 18/week @ 2024-03-18 27/week @ 2024-04-01 14/week @ 2024-04-08 19/week @ 2024-04-15 13/week @ 2024-04-22 5/week @ 2024-04-29 8/week @ 2024-05-06 10/week @ 2024-05-13 15/week @ 2024-05-20 77/week @ 2024-05-27 30/week @ 2024-06-03 19/week @ 2024-06-10 14/week @ 2024-06-17 17/week @ 2024-06-24

每月86次下载
用于 shikane

MIT 协议

17KB
306

crates.io github

本软件包实现了霍普克罗夫-卡尔帕算法,用于在二分图中找到最大无权匹配。

基本用法

软件包提供了一个函数 hopcroft_karp::matching(以及一些变体),该函数接受一个边向量(表示二分图)作为输入,并返回一个边向量作为最大匹配。

示例用法

    use hopcroft_karp::matching;

    fn main() {
        let edges = vec![(0,10), (0,11), (0,12), (1,11), (2,12)];
        let res = matching(&edges);
        assert_eq!(res.len(), 3);
    }

matching 对顶点类型是通用的,其特征界限是 Hash + Copy + Eq。对于复制操作可能很昂贵的类型(例如字符串),软件包提供了一个函数 hopcrof_karp::matching_mapped,该函数内部将顶点映射到整数,并尽量避免复制类型。

use hopcroft_karp::{matching, matching_mapped};

fn main() {
    let edges = vec![("spiderman", "doc octopus"), ("spiderman", "sandman"), ("spiderman", "green goblin"),
                     ("silk", "doc octopus"), ("silk", "green goblin"),  ("daredevil", "sandman")];
    let res = matching(&edges);
    assert_eq!(res.len(), 3);

    // For types where copying is expensive, use this instead
    let res = matching_mapped(&edges);
    assert_eq!(res.len(), 3);
}

变体

软件包公开了一些针对特定用例的方法。如果只需要匹配的大小,hopcroft_karp::matching_size 会避免构建解决方案匹配。如果只需要大于一定大小的匹配,hopcroft_karp::bounded_matching 会在匹配大小超过提供的界限时立即返回结果。

这些变体有所有可能的组合,例如 hopcroft_karp::bounded_matching_mapped_size 返回大于提供的界限的匹配大小(如果界限大于最大匹配则返回较小的值),同时内部重新映射图顶点以避免昂贵的复制操作。

依赖项

~135KB