Lib.rs

› 算法 › graph
#graph-algorithms #graph-node #graph #undirected-graph #directed-graph #algorithm #csr

graph_builder

高性能图算法的构建块

由Martin Junghanns、Paul Horn 以及 5位贡献者 完成

6个版本 (3个重大更新)

0.4.0 2023年11月17日
0.3.1 2023年2月19日
0.3.0 2022年11月17日
0.2.1 2022年10月1日
0.1.13 2022年1月14日

#684 in 算法

Download history 331/week @ 2024-03-14 313/week @ 2024-03-21 469/week @ 2024-03-28 391/week @ 2024-04-04 306/week @ 2024-04-11 332/week @ 2024-04-18 315/week @ 2024-04-25 398/week @ 2024-05-02 600/week @ 2024-05-09 276/week @ 2024-05-16 362/week @ 2024-05-23 259/week @ 2024-05-30 522/week @ 2024-06-06 476/week @ 2024-06-13 366/week @ 2024-06-20 303/week @ 2024-06-27

1,731 每月下载量
在 4 个crate中使用 (通过 graph)

MIT 许可证

195KB
4K SLoC

graph_builder

一个库，可以用作高性能图算法的构建块。

Graph提供了有向和无向图的实现。图可以通过编程方式创建，或者以类型安全的方式从自定义输入格式中读取。该库使用rayon并行化图创建过程中的所有步骤。

该实现使用压缩稀疏行（CSR）数据结构，适用于快速并发访问图拓扑。

注意：该库的开发主要是由Neo4j的开发者驱动的。然而，该库不是Neo4j的官方产品。

什么是图？

图由节点和边组成，其中边恰好连接两个节点。图可以是定向的，即边有一个源节点和一个目标节点，或者是无向的，其中没有这样的区分。

在有向图中，每个节点u都有一个出度和入度邻居。节点u的出度邻居是任何存在边(u, v)的节点v。节点u的入度邻居是任何存在边(v, u)的节点v。

在无向图中，源节点和目标节点之间没有区别。节点 u 的邻居是任何节点 v，对于这个节点，存在一条边 (u, v) 或 (v, u)。

如何构建图

库提供了一个构建器，可以用于从给定的边列表中构建图。

例如，要创建一个使用 usize 作为节点标识符的有向图，可以使用构建器如下所示

use graph_builder::prelude::*;

let graph: DirectedCsrGraph<usize> = GraphBuilder::new()
    .edges(vec![(0, 1), (0, 2), (1, 2), (1, 3), (2, 3)])
    .build();

assert_eq!(graph.node_count(), 4);
assert_eq!(graph.edge_count(), 5);

assert_eq!(graph.out_degree(1), 2);
assert_eq!(graph.in_degree(1), 1);

assert_eq!(graph.out_neighbors(1).as_slice(), &[2, 3]);
assert_eq!(graph.in_neighbors(1).as_slice(), &[0]);

要构建一个使用 u32 作为节点标识符的无向图，我们只需要更改期望的类型

use graph_builder::prelude::*;

let graph: UndirectedCsrGraph<u32> = GraphBuilder::new()
    .csr_layout(CsrLayout::Sorted)
    .edges(vec![(0, 1), (0, 2), (1, 2), (1, 3), (2, 3)])
    .build();

assert_eq!(graph.node_count(), 4);
assert_eq!(graph.edge_count(), 5);

assert_eq!(graph.degree(1), 3);

assert_eq!(graph.neighbors(1).as_slice(), &[0, 2, 3]);

边可以附加值来表示加权图

use graph_builder::prelude::*;

let graph: UndirectedCsrGraph<u32, (), f32> = GraphBuilder::new()
    .csr_layout(CsrLayout::Sorted)
    .edges_with_values(vec![(0, 1, 0.5), (0, 2, 0.7), (1, 2, 0.25), (1, 3, 1.0), (2, 3, 0.33)])
    .build();

assert_eq!(graph.node_count(), 4);
assert_eq!(graph.edge_count(), 5);

assert_eq!(graph.degree(1), 3);

assert_eq!(
    graph.neighbors_with_values(1).as_slice(),
    &[Target::new(0, 0.5), Target::new(2, 0.25), Target::new(3, 1.0)]
);

还可以从特定的输入格式创建图。在下面的示例中，我们使用 EdgeListInput，这是一种输入格式，其中文件中的每一行都包含图的一条边。

use std::path::PathBuf;

use graph_builder::prelude::*;

let path = [env!("CARGO_MANIFEST_DIR"), "resources", "example.el"]
    .iter()
    .collect::<PathBuf>();

let graph: DirectedCsrGraph<usize> = GraphBuilder::new()
    .csr_layout(CsrLayout::Sorted)
    .file_format(EdgeListInput::default())
    .path(path)
    .build()
    .expect("loading failed");

assert_eq!(graph.node_count(), 4);
assert_eq!(graph.edge_count(), 5);

assert_eq!(graph.out_degree(1), 2);
assert_eq!(graph.in_degree(1), 1);

assert_eq!(graph.out_neighbors(1).as_slice(), &[2, 3]);
assert_eq!(graph.in_neighbors(1).as_slice(), &[0]);

EdgeListInput 格式还支持加权边。这可以通过图类型的单个类型参数来控制。注意，边的值类型需要实现 crate::input::ParseValue。

use std::path::PathBuf;

use graph_builder::prelude::*;

let path = [env!("CARGO_MANIFEST_DIR"), "resources", "example.wel"]
    .iter()
    .collect::<PathBuf>();

let graph: DirectedCsrGraph<usize, (), f32> = GraphBuilder::new()
    .csr_layout(CsrLayout::Sorted)
    .file_format(EdgeListInput::default())
    .path(path)
    .build()
    .expect("loading failed");

assert_eq!(graph.node_count(), 4);
assert_eq!(graph.edge_count(), 5);

assert_eq!(graph.out_degree(1), 2);
assert_eq!(graph.in_degree(1), 1);

assert_eq!(
    graph.out_neighbors_with_values(1).as_slice(),
    &[Target::new(2, 0.25), Target::new(3, 1.0)]
);
assert_eq!(
    graph.in_neighbors_with_values(1).as_slice(),
    &[Target::new(0, 0.5)]
);

图类型

该软件包目前提供了两种图实现

压缩稀疏行 (CSR)

CSR 是一种用于表示稀疏矩阵的数据结构。由于图可以建模为邻接矩阵，并且通常非常稀疏，即不是所有可能的节点对都通过边连接，因此 CSR 表示非常适合表示现实世界的图拓扑。

在我们的当前实现中，我们使用两个数组来模拟边。一个数组存储所有节点的邻接表，这是连续的，需要 O(edge_count) 空间。另一个数组存储第一个数组中每个节点的偏移量，其中可以找到相应的邻接表，这需要 O(node_count) 空间。可以从偏移量数组中推断出节点的度。

我们的 CSR 实现是不可变的，即一旦构建，图拓扑就不能更改，因为这需要插入目标 ID 并将所有元素向右移动，这既昂贵又无效化随后所有偏移量。然而，从边列表构建 CSR 数据结构是通过多线程实现的，非常高效。

然而，由于在一个 Vec 中内联所有邻接表，访问变得非常缓存友好，因为有机会在缓存中找到下一个节点的邻接表。此外，从多个线程中读取图是安全的，因为将永远不会发生并发可变访问。

可以使用 DirectedCsrGraph 或 UndirectedCsrGraph 来构建基于 CSR 的图

use graph_builder::prelude::*;

let graph: DirectedCsrGraph<usize> = GraphBuilder::new()
    .edges(vec![(0, 1), (0, 2), (1, 2), (1, 3), (2, 3)])
    .build();

assert_eq!(graph.node_count(), 4);
assert_eq!(graph.edge_count(), 5);

assert_eq!(graph.out_degree(1), 2);
assert_eq!(graph.in_degree(1), 1);

assert_eq!(graph.out_neighbors(1).as_slice(), &[2, 3]);
assert_eq!(graph.in_neighbors(1).as_slice(), &[0]);

邻接表 (AL)

在邻接表实现中，我们基本上将图存储为 Vec<Vec<ID>>。最外层的 Vec 的长度为 node_count，在每个索引处，我们存储特定节点的邻居，它们在自己的、堆分配的 Vec 中。

这种表示的缺点是——与 CSR 相比——它在构建和读取时都预计会慢，因为由于为单个邻接表进行隔离的堆分配，缓存未命中变得更加可能。

然而，与 CSR 相比，邻接表是可变的，即，在构建图之后仍然可以向图中添加边。这使得数据结构对更灵活的图构建框架或需要作为计算一部分添加新边的算法很有趣。目前，添加边的限制是源节点和目标节点已存在于图中。

内部，每个节点的单个邻接表由一个 Mutex 保护，以支持对图拓扑的并行读写操作。

可以使用 DirectedALGraph 或 UndirectedALGraph 来构建基于邻接表的图

use graph_builder::prelude::*;

let graph: DirectedALGraph<usize> = GraphBuilder::new()
    .edges(vec![(0, 1), (0, 2), (1, 2), (1, 3), (2, 3)])
    .build();

assert_eq!(graph.node_count(), 4);
assert_eq!(graph.edge_count(), 5);

assert_eq!(graph.out_degree(1), 2);
assert_eq!(graph.in_degree(1), 1);

assert_eq!(graph.out_neighbors(1).as_slice(), &[2, 3]);
assert_eq!(graph.in_neighbors(1).as_slice(), &[0]);

// Let's mutate the graph by adding another edge
graph.add_edge(1, 0);
assert_eq!(graph.edge_count(), 6);
assert_eq!(graph.out_neighbors(1).as_slice(), &[2, 3, 0]);

许可证：MIT

依赖关系

~5–11MB
~121K SLoC