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 在 算法 中排名
每月86次下载
用于 shikane
17KB
306 行
本软件包实现了霍普克罗夫-卡尔帕算法,用于在二分图中找到最大无权匹配。
基本用法
软件包提供了一个函数 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