graph —

这是一个提供一系列高性能图算法的库。该包构建在 graph_builder 包之上，可以作为自定义图算法的构建块使用。

graph_builder 为有向和无向图提供了实现。图可以通过编程方式创建或以类型安全的方式从自定义输入格式中读取。该库使用 rayon 来并行化图创建过程中的所有步骤。实现使用压缩稀疏行 (CSR) 数据结构，该结构针对快速和并发访问图拓扑进行了优化。

graph 提供了以 graph_builder 创建的图作为输入的图算法。算法实现旨在在具有数十亿节点和边的大规模图上高效运行。

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

什么是图？

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

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

在无向图中，没有源节点和目标节点的区分。节点 u 的邻居是任何存在边 (u, v) 或 (v, u) 的节点 v。

如何使用图？

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

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

use graph::prelude::*;

let graph: DirectedCsrGraph<usize> = 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.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::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]);

查看 graph_builder crate 以获取更多有关如何从各种输入格式构建图的示例。

如何运行算法

以下我们将演示运行 Page Rank，这是一种基于节点入边数量和质量来确定图中节点重要性的图算法。

Page Rank 需要一个有向图，并为每个节点返回排名值。

use graph::prelude::*;

// https://en.wikipedia.org/wiki/PageRank#/media/File:PageRanks-Example.svg
let graph: DirectedCsrGraph<usize> = GraphBuilder::new()
    .edges(vec![
           (1,2), // B->C
           (2,1), // C->B
           (4,0), // D->A
           (4,1), // D->B
           (5,4), // E->D
           (5,1), // E->B
           (5,6), // E->F
           (6,1), // F->B
           (6,5), // F->E
           (7,1), // G->B
           (7,5), // F->E
           (8,1), // G->B
           (8,5), // G->E
           (9,1), // H->B
           (9,5), // H->E
           (10,1), // I->B
           (10,5), // I->E
           (11,5), // J->B
           (12,5), // K->B
    ])
    .build();

let (ranks, iterations, _) = page_rank(&graph, PageRankConfig::new(10, 1E-4, 0.85));

assert_eq!(iterations, 10);

let expected = vec![
    0.024064068,
    0.3145448,
    0.27890152,
    0.01153846,
    0.029471997,
    0.06329483,
    0.029471997,
    0.01153846,
    0.01153846,
    0.01153846,
    0.01153846,
    0.01153846,
    0.01153846,
];

assert_eq!(ranks, expected);

许可：MIT