9 个版本
0.2.2 | 2024年6月19日 |
---|---|
0.2.1 | 2024年5月2日 |
0.1.5 | 2024年3月5日 |
0.1.4 | 2023年4月19日 |
0.1.1 | 2023年1月26日 |
#211 在 算法
127 每月下载量
105KB
2K SLoC
mhgl
Matt's HyperGraph Library (mhgl)
一个用于处理无向 超图 的库,超图是普通图的一般化。超图由一组节点 N
和一组边组成,其中每条边是 N
的子集。对于普通图,每条边的大小必须为 2,例如节点 u
和 v
之间的边 (u, v)
,而在超图中,边的尺寸没有限制。每个节点和边都分配了ID,ID的类型取决于使用的结构。`HyperGraph
` trait 提供了一个通用的 API,用于开发与结构无关的算法。
超图结构
ConGraph
- 一个仅用于连接性的选项,使用u32
作为节点的ID,使用u64
作为边ID,每个ID都是从 0 开始的简单计数器。在ConGraph
结构本身中不能存储任何数据。HGraph
- 一个泛型结构,泛型于四种类型:节点数据、边数据、节点ID和边ID。对节点和边类型没有特质的限制;此外,泛型于整数的大小,从u8
到u128
,以便使用u32
和u64
作为默认的 ID 来存储 NodeIDs 和 EdgeIDs。KVGraph
- 一个键值超图,每个节点和边都允许你存储简单的kvgraph::Value
,该值是按照 Polars 的简单子集AnyValue<'a>
模式建模的。
ConGraph
和 KVGraph
实际上是围绕 HGraph
的包装,其函数签名略有调整,以添加和删除节点或边(例如,向 ConGraph
添加节点时不需要提供数据,但对于 HGraph
则需要)。
示例
use mhgl::*;
let mut cg = ConGraph::new();
let nodes = cg.add_nodes(5);
let mut edges = Vec::new();
for ix in 1..nodes.len() {
let edge = cg.add_edge(&nodes[0..=ix]);
edges.push(edge);
}
let maxs_of_edge = cg.maximal_edges(&edges[0]);
let maxs_of_nodes = cg.maximal_edges_of_nodes([0, 1, 2]);
assert_eq!(maxs_of_edge[0], edges[edges.len() - 1]);
assert_eq!(maxs_of_nodes[0], edges[edges.len() - 1]);
assert_eq!(cg.boundary_up(&edges[0]), vec![edges[1]]);
#[derive(Debug)]
struct Foo(u8);
#[derive(Debug)]
struct Bar(u32);
let mut hg = HGraph::<Foo, Bar>::new();
let n0 = hg.add_node(Foo(1));
let n1 = hg.add_node(Foo(2));
let e = hg.add_edge(&[n0, n1], Bar(42)).unwrap();
let e_mut = hg.borrow_edge_mut(&e).unwrap();
e_mut.0 = 12;
let bar = hg.remove_edge(e).unwrap();
assert_eq!(bar.0, 12);
let mut kvgraph = KVGraph::new();
let n0 = kvgraph.add_node_with_label("toronto");
let n1 = kvgraph.add_node_with_label("seattle");
let edge = kvgraph.add_edge_with_label(&[n0, n1], "AC123").unwrap();
kvgraph.insert(&n0, "darkness", 0.6);
kvgraph.insert(&n1, "darkness", 0.8);
let df = kvgraph.dataframe();
println!("{:}", df);
上述代码的最后一行在运行时输出
┌────────────┬───────────────────────────────────┬───────────────────────────────────┬───────────────────┬──────────┐
│ label ┆ id ┆ nodes ┆ labelled_nodes ┆ darkness │
│ --- ┆ --- ┆ --- ┆ --- ┆ --- │
│ str ┆ str ┆ str ┆ str ┆ f64 │
╞════════════╪═══════════════════════════════════╪═══════════════════════════════════╪═══════════════════╪══════════╡
│ toronto ┆ 6347a42e-0bde-4d80-aad3-7e8c59d3… ┆ [6347a42e-0bde-4d80-aad3-7e8c59d… ┆ [toronto] ┆ 0.6 │
│ seattle ┆ 032e1a16-ec39-4045-8ebd-381c2b06… ┆ [032e1a16-ec39-4045-8ebd-381c2b0… ┆ [seattle] ┆ 0.8 │
│ AC123 ┆ 1b233128-22d2-4158-850d-b4b814d5… ┆ [1b233128-22d2-4158-850d-b4b814d… ┆ [seattle,toronto] ┆ null │
└────────────┴───────────────────────────────────┴───────────────────────────────────┴───────────────────┴──────────┘
目前数据模式在节点和边之间是共享的,这很遗憾。
特性
有 2 个与 KVGraph
模块相关的特性
特质
-
HyperGraph
- 一组用于查询超图邻接结构的函数。有几个主要函数,每个函数都接受一个边 ID 作为输入,并返回超图中的相关边。每个函数还有一个 "of_nodes" 变体,允许你找到相同的信息,但不需要输入超图的边,而是可以提供一个节点切片。containing_edges
找到所有是输入边的严格超集的边。maximal_edges
找到所有包含输入边但不包含在另一个边中的边。link
取包含给定边的所有边,并计算该边内的输入补码。boundary_up
边界上升算子来自拓扑和单纯复形术语。它接受输入边并找到仅比输入边多一个节点的所有边。boundary_down
与boundary_up
算子类似,但删除一个节点。
-
HgNode
- 一个标记特质,用于指示哪些类型可用于节点和边 ID(提示:u8
、u16,
u32,
u64, 和
u132. 不要使用 'Uuid 即使它们实现了这个特质。)
算法
目前大部分仍在建设中,目前只有一个简单的随机游走,可以使用链接,boundary_up
* boundary_down
和boundary_down
* boundary_up
来决定下一个要移动到的子集。我计划在将来逐步将一些算法,例如连接组件、s_walk和同伦算法从HyperNetX
移植到这个库。
替代的超图库
这个库应被视为一个alpha版本。以下是我找到的一些超图库,其中最成熟的是太平洋西北国家实验室(PNNL)开发的HyperNetX。
- HyperNetX (Python):最完整的超图库,包含同伦计算的算法。基于Python,底层数据结构似乎是pandas数组。
- HypergraphDB (Java):用于存储和查询数据的数据库后端,看起来已经停止维护,但可能当时领先于时代。
- Hypergraph (Rust):在我看来,其范围有限且有点复杂。
- Gudhi (C++):这个库专注于计算持久同伦条形图。因此,它具有单纯复形的结构和更多。
许可证:MIT
依赖项
~2–32MB
~484K SLoC