graph_mate

为graph crates集提供Python绑定。

graph_mate是一个Python API，提供了一组高性能图算法。它提供了有向和无向图的实现。

图可以通过编程创建或从Graph500输入格式读取。

该库用Rust实现，并使用rayon在并行运行图创建和算法执行时，不持有全局解释器锁或使用多进程。

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

graph_mate提供了一些图算法。算法实现旨在在大规模图（具有数十亿个节点和边）上高效运行。

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

用法

安装

graph_mate可在PyPI上找到

pip install graph-mate

当前版本适用于Windows、Mac/Linux上的x86_64架构，并对苹果硅Mac进行通用适配。

如果您需要为不同的架构或系统使用graph_mate，请参考手动安装。

用法

什么是图？

图由节点和边组成，其中边恰好连接两个节点。图可以是有向的，即边具有源节点和目标节点，也可以是无向的，没有这种区别。

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

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

如何创建图

目前有两种构建图的方法。您可以从Graph500格式中load图，例如从LDBC Graphalytics网站下载。或者，您可以使用from_numpy提供numpy边列表。

import graph_mate as gm
import numpy as np

# Let's load a small graph:
#    (a)-->(b)-->(c)-->(d), (a)-->(c), (b)-->(d)
# To load from an edge list, we need to create a 2d numpy array of `uint32`s.
edge_list = np.array([
    # (a)-->(b)
    [0, 1],
    # (a)-->(c)
    [0, 2],
    # (b)-->(c)
    [1, 2],
    # (b)-->(d)
    [1, 3],
    # (c)-->(d)
    [2, 3]
], dtype=np.uint32)

要构建有向图，您可以使用graph_mate.DiGraph和一个无向图graph_mate.Graph。

# We can load a directed graph from the edge list
directed = gm.DiGraph.from_numpy(edge_list)

# Or we can load an undirected graph
undirected = gm.Graph.from_numpy(edge_list)

为了使断言更容易，我们可以通过提供一个可选的第二个参数graph_mate.Layout来创建具有排序邻接表的图。

directed = gm.DiGraph.from_numpy(edge_list, gm.Layout.Sorted)

undirected = gm.Graph.from_numpy(edge_list, gm.Layout.Sorted)

从numpy边列表加载时，数据不会共享，而是复制到图中。numpy数组之后可以删除。

我们可以使用一些方法来检查图。

assert directed.node_count() == 4
assert directed.edge_count() == 5

assert directed.out_degree(1) == 2
assert directed.in_degree(1) == 1

assert np.array_equal(directed.out_neighbors(1), [2, 3])
assert np.array_equal(directed.in_neighbors(1), [0])

邻居以numpy数组视图的形式返回，这意味着我们无法修改该数组。

neighbors = directed.out_neighbors(1)
try:
    neighbors[0] = 42
except ValueError as e:
    assert str(e) == "assignment destination is read-only"

为了将邻居用作Python列表而不是numpy数组，我们可以使用copy_方法。

neighbors = directed.copy_out_neighbors(1)

assert neighbors == [2, 3]
assert type(neighbors) == list

对于无向图，我们没有针对度或邻居的方向方法。

assert undirected.node_count() == 4
assert undirected.edge_count() == 5

assert undirected.degree(1) == 3

assert np.array_equal(undirected.neighbors(1), [0, 2, 3])

如何运行算法

以下我们将演示运行PageRank，一种基于节点进入边数量和质量确定图节点重要性的图算法。PageRank需要一个有向图，并为每个节点返回排名值。

# https://en.wikipedia.org/wiki/PageRank#/media/File:PageRanks-Example.svg

graph = gm.DiGraph.from_numpy(np.array([
    (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
], dtype=np.uint32))

pr_result = graph.page_rank(max_iterations=10, tolerance=1e-4, damping_factor=0.85)

assert pr_result.ran_iterations == 10

expected = np.array([
    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,
], dtype=np.float32)

assert np.array_equal(pr_result.scores(), expected)

示例笔记本

有关更多示例和演示，请参阅notebooks目录中的笔记本。

开发

Python扩展是用PyO3和maturin一起编写的。

一次性设置

# Run the command from the extension directory, not the git root
# cd crates/mate

python -m venv .env
source .env/bin/activate
pip install -r requirements/dev.txt

每次新终端设置

确保在每个您希望进行开发的新的终端中激活venv。

source .env/bin/activate

构建扩展

以调试模式构建。

maturin develop

以发布模式构建。

maturin develop --release

在最后文件更改后2秒内重新构建扩展（可选步骤）。

cargo watch --shell 'maturin develop --release' --delay 2

测试

运行测试

pytest tests

格式化和代码审查

# Runs code formatter https://pypi.ac.cn/project/black/
black tests

# Sort imports using https://pypi.ac.cn/project/isort/
isort tests

# Verify with https://pypi.ac.cn/project/flake8/
flake8 tests

# Very types using http://mypy-lang.org
mypy .

许可证：MIT