#edge #node #graph-algorithms #hypergraph #algorithm #node-id #undirected-graph

mhgl

Matts HyperGraph Library (MHGL)。一个用于超图数据结构的简单库。

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算法

Download history 271/week @ 2024-05-01 2/week @ 2024-05-15 10/week @ 2024-05-22 98/week @ 2024-06-19 1/week @ 2024-06-26 14/week @ 2024-07-03 3/week @ 2024-07-10 8/week @ 2024-07-17 90/week @ 2024-07-24 26/week @ 2024-07-31

127 每月下载量

MIT 许可证

105KB
2K SLoC

mhgl

Matt's HyperGraph Library (mhgl)

一个用于处理无向 超图 的库,超图是普通图的一般化。超图由一组节点 N 和一组边组成,其中每条边是 N 的子集。对于普通图,每条边的大小必须为 2,例如节点 uv 之间的边 (u, v),而在超图中,边的尺寸没有限制。每个节点和边都分配了ID,ID的类型取决于使用的结构。`HyperGraph` trait 提供了一个通用的 API,用于开发与结构无关的算法。

超图结构

  • ConGraph - 一个仅用于连接性的选项,使用 u32 作为节点的ID,使用 u64 作为边ID,每个ID都是从 0 开始的简单计数器。在 ConGraph 结构本身中不能存储任何数据。
  • HGraph - 一个泛型结构,泛型于四种类型:节点数据、边数据、节点ID和边ID。对节点和边类型没有特质的限制;此外,泛型于整数的大小,从 u8u128,以便使用 u32u64 作为默认的 ID 来存储 NodeIDs 和 EdgeIDs。
  • KVGraph - 一个键值超图,每个节点和边都允许你存储简单的 kvgraph::Value,该值是按照 Polars 的简单子集 AnyValue<'a> 模式建模的。

ConGraphKVGraph 实际上是围绕 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 │
│ ---------------      │
│ strstrstrstrf64      │
╞════════════╪═══════════════════════════════════╪═══════════════════════════════════╪═══════════════════╪══════════╡
│ 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 模块相关的特性

  • "uuid",以启用 KVGraph 的使用,因为它使用 Uuid 作为节点和边的 ID 类型。
  • "polars",以计算任何节点或边的集合的 polars 数据帧。

特质

  • HyperGraph - 一组用于查询超图邻接结构的函数。有几个主要函数,每个函数都接受一个边 ID 作为输入,并返回超图中的相关边。每个函数还有一个 "of_nodes" 变体,允许你找到相同的信息,但不需要输入超图的边,而是可以提供一个节点切片。

    • containing_edges 找到所有是输入边的严格超集的边。
    • maximal_edges 找到所有包含输入边但不包含在另一个边中的边。
    • link 取包含给定边的所有边,并计算该边内的输入补码。
    • boundary_up 边界上升算子来自拓扑和单纯复形术语。它接受输入边并找到仅比输入边多一个节点的所有边。
    • boundary_downboundary_up 算子类似,但删除一个节点。
  • HgNode - 一个标记特质,用于指示哪些类型可用于节点和边 ID(提示:u8u16, u32, u64,u132. 不要使用 'Uuid 即使它们实现了这个特质。)

算法

algs

目前大部分仍在建设中,目前只有一个简单的随机游走,可以使用链接,boundary_up * boundary_downboundary_down * boundary_up来决定下一个要移动到的子集。我计划在将来逐步将一些算法,例如连接组件、s_walk和同伦算法从HyperNetX移植到这个库。

替代的超图库

这个库应被视为一个alpha版本。以下是我找到的一些超图库,其中最成熟的是太平洋西北国家实验室(PNNL)开发的HyperNetX。

  • HyperNetX (Python):最完整的超图库,包含同伦计算的算法。基于Python,底层数据结构似乎是pandas数组。
  • HypergraphDB (Java):用于存储和查询数据的数据库后端,看起来已经停止维护,但可能当时领先于时代。
  • Hypergraph (Rust):在我看来,其范围有限且有点复杂。
  • Gudhi (C++):这个库专注于计算持久同伦条形图。因此,它具有单纯复形的结构和更多。

许可证:MIT

依赖项

~2–32MB
~484K SLoC