发行说明#

0.17.1#

新功能#

向 rustworkx-core 新增了一个函数 rustworkx_core::shortest_path::distance_matrix。此函数相当于Python库中的distance_matrix()，但作为 rustworkx-core 的通用Rust函数。

0.17.0#

预备知识

这是rustworkx的一个新版本，包含库的错误修复和新功能。本次版本的亮点包括：

增强文档和测试

支持写入GraphML文件

加权紧密度中心性的一种新方法

此版本使用 Python 稳定ABI，并将与 Python 3.9 及以后的所有版本兼容。已发布的二进制文件已经过 Python 3.9 到 3.13 的测试，虽然预计它们也将与未来版本（如 3.14）兼容。特别鸣谢 Miroslav Šedivý、Etienne Wodey、Krishn Parasar 和 Barak Katzir 提供的拉取请求和 GitHub 问题报告！尽管未在个别条目中记录，我们非常感谢您帮助改进文档、类型注解和测试的工作。

新功能#

为 rustworkx.PyDiGraph 类新增了两个新函数：in_edge_indices() 和 out_edge_indices()。这两个函数分别返回有向图中给定节点的所有入边和出边的索引。

向rustworkx.PyGraph类添加了两个新函数：in_edge_indices()和out_edge_indices()。由于PyGraph是无向图，这两个函数都会返回连接到给定节点的所有边的索引。这保持了与有向图实现的API一致性。

新增了一个函数 local_complement()，它对图中的节点执行局部补操作。例如：

import rustworkx 

# 示例取自 https://arxiv.org/abs/1910.03969 中图 1 a)
graph = rustworkx.PyGraph(multigraph=False)
graph.extend_from_edge_list(
    [(0, 1), (0, 3), (0, 5), (1, 2), (2, 3), (2, 4), (3, 4), (3, 5)]
)

complement_graph = rustworkx.local_complement(graph, 0)

新增函数：find_successor_node_by_edge() 到 rustworkx.PyDiGraph 类中。该函数能找到通过符合给定条件的边连接的任意后继节点。

新增了两个函数: is_strongly_connected() 和 number_strongly_connected_components() 到 rustworkx.PyDiGraph 类中。这些函数分别检查有向图是否强连接, 以及此类组件的数量。它们是已有"弱连接"方法的"强连接"对应方法。

新增了一个适用于有向图和无向图的condensation()函数。对于有向图，它会返回凝结图（商图），其中每个节点代表一个强连通分量(SCC)。对于无向图，每个节点代表一个连通分量。返回的图具有一个'node_map'属性，该属性将每个原始节点索引映射到其所属的凝结节点索引。

all_simple_paths() 函数现在支持传入可迭代对象作为多个目标节点。您现在可以传递单个目标节点（整型）或多个目标节点（整型可迭代对象）来查找从源节点到任意指定目标的所有简单路径。例如：
```
import rustworkx as rx

graph = rx.generators.path_graph(4)
# 多个目标 - 新增功能
paths = rx.all_simple_paths(graph, 0, [2, 3])
# paths: [[0, 1, 2], [0, 1, 2, 3]]
```
此增强功能保持了向后兼容性，同时为 PyGraph 和 PyDiGraph 对象中的路径查找操作提供了更大的灵活性。

在 PyDiGraph 对象上公开了 can_contract_without_cycle 方法。该方法使用户能够在收缩之前检查将一组节点合并为单个节点是否会在图中引入循环。这对于需要维持无环特性的应用尤其有用，例如处理有向无环图（DAGs）。

新增了一个新函数newman_weighted_closeness_centrality()，用于计算加权PyGraph或PyDiGraph对象中所有节点的紧密度中心性。

加权紧密度中心性是标准紧密度中心性度量的扩展，其中边权重表示连接强度而非距离。为了正确计算最短路径，权重被反转，使得更强的连接对应于更短的有效距离。该算法遵循Newman（2001）在分析加权图时描述的方法。

边原本表示节点之间的连接强度。其思想是，如果两个节点之间有强连接，它们之间的计算距离应当较小（更短），反之亦然。请注意，这假设图正在建模某种连接强度度量（例如信任、协作或相似性）。

closeness_centrality() 方法现在支持并行计算以获得更好的性能。并行性通过新的可选参数 parallel_threshold 进行切换。

新增功能至 rustworkx-core 以计算无向和有向图的传递性。此功能移植了 rustworkx Python API 中已实现的算法。

rustworkx 现已对 Pyodide 提供实验性支持。 Pyodide 是一个可在浏览器中运行的 WebAssembly Python 发行版。这是首个支持 Pyodide 编译的版本，将允许用户在 Web 应用程序中运行 rustworkx。由于 PyPI 中未提供 Pyodide 轮包，我们正与 Pyodide 团队合作将其发布至 Pyodide 包索引。

新增了 single_source_all_shortest_paths 函数，使用 Dijkstra 算法计算从源节点到所有其他节点的所有最短路径。此函数支持 PyGraph 和 PyDiGraph，并提供一个选项以将有向图视为无向图。查看文档以了解使用方式和性能警告。

新增了subgraph_with_nodemap()和subgraph_with_nodemap() 方法到PyGraph和PyDiGraph类。这些方法扩展了现有的 subgraph()方法，通过返回一个NodeMap对象，该对象将子图的节点映射到原始图的节点。

新增了一个函数 write_graphml()，该函数可将 rustworkx 图对象列表以 GraphML 格式写入文件。

更新说明#

构建rustworkx和rustworkx-core的最低支持Rust版本已从1.70提升至1.79。您需要将Rust编译器版本升级到至少1.79版本才能继续从源码构建。在支持平台上安装rustworkx的Python库使用者无需做任何更改。

rustworkx-core 中使用的 petgraph 版本已从 0.7.1 更新至 0.8.1。这意味着对于 rustworkx-core 的用户来说，若要将使用 petgraph 构建的图对象传递给算法函数，需确保相应升级 petgraph 的使用方式。如果使用从 rustworkx_core::petgraph 重新导出的 petgraph，则会正确处理此问题。然而，围绕 petgraph 使用的任何 API 变更需要在升级使用方式时予以体现。详情请参阅 petgraph 0.8.0 的发布文档。

rustworkx-core 中的 closeness_centrality 函数现在需要 parallel_threshold 参数，该参数控制算法何时切换到并行执行。这是一个破坏性变更。

一些平台的支持层级发生了变动。这些变动反映了当前对每个底层平台的支持状况。
- Linux的aarch64架构已升级为第一层级，现在将在每次提交时作为上游开发的一部分进行构建和测试
  。
- x86_64 (musl) 和 aarch64 (musl) 架构的 Linux 已升级至第二级支持，
  将作为发布流程的一部分进行构建和测试。NumPy 同样为这些平台提供预编译包，因此我们预计大多数用户能够轻松地从 PyPI 进行安装。
- ppc64le架构的Linux系统已降级为第4级支持。我们仍会为该平台发布预构建包，但不再进行测试。这是由于现有CI基础设施的限制以及我们无法可靠测试该平台所致。
  该平台，但它们将不会经过测试。这归因于可用CI基础设施的限制和我们无法可靠测试该平台的能力不足。
- 适用于i686架构的Linux系统已降级为第4层级。我们仍将为此平台发布轮子文件
  但由于NumPy不再提供i686架构的轮子文件，这些平台上的rustworkx包将不会经过测试。由于我们依赖 NumPy，用户在这些平台上安装rustworkx时需要配备C/C++编译器。
- Windows 32位版本已降级为第四级支持。尽管NumPy发布了win32预编译包，
  但rust-numpy对win32的支持不稳定，可能随时会被取消。如果可能，我们建议在Windows上使用64位版本的Python，以获得第一级支持。

弃用说明#

我们正在告别作为rustworkx向后兼容别名的遗留retworkx包。它最初在0.12.0版本中被标记为已弃用，这将是它受支持的最后一个版本。rustworkx名称现已存在时间超过retworkx名称，且不再需要retworkx包。

此版本将解除retworkx包与rustworkx包的固定关联。历史上，我们同时发布retworkx和rustworkx，其中retworkx是同一个rustworkx包的别名。这种情况将不再继续。

我们鼓励用户迁移到新名称。感谢所有从项目早期就开始使用retworkx的用户！

Bug 修复 #

修复了一个随机图生成器函数中的错误， directed_barabasi_albert_graph() 和 barabasi_albert_graph() 在使用相同输入种子时会产生不同的图。

修复了当传递无效源节点到 ancenstors()和descendants()时出现的panic问题。详情请参见 #1381。

修复了向搜索方法（例如 bfs_search()）传递无效源节点时发生崩溃的问题。更多详情请参见 #1386。

其他说明#

当使用 read_graphml() 读取的图形包含ID时，这些ID现在会被存储在图形属性中。

0.16.0#

预备知识

这是Rustworkx的一个新版本发布，该库包含众多错误修复与新特性。本次发布的亮点包括：

提升了对 mypy 和 pyright 类型检查的支持

支持读取压缩的GraphML文件

新增的支配算法

此版本使用 Python 稳定 ABI，并将与 Python 3.9 及之后的所有版本兼容。发布的二进制文件已经过 Python 3.9 至 3.13 的测试，尽管它们很可能也能与未来的版本（如 3.14）兼容。我们要感谢所有报告问题并为此版本做出贡献的用户。这是 rustworkx 发布迄今拥有最多独立贡献者的版本！

新功能#

以下方法现在支持序列和生成器作为输入，除了现有的列表支持： * add_nodes_from() 和 add_nodes_from() * add_edges_from() 和 add_edges_from() * add_edges_from_no_data() 和 add_edges_from_no_data() * extend_from_edge_list() 和 extend_from_edge_list() * extend_from_weighted_edge_list() 和 extend_from_weighted_edge_list()

在 rustworkx-core crate 中添加了一个新函数 johnson_simple_cycles。该函数实现了 Johnson’s algorithm 用于在有向图中查找所有基本环。

新增了一个名为 EdgeFindable 的特质，用于根据一对节点索引从图中查找 EdgeIndex。

新增一个名为EdgeRemovable的特征，用于通过其EdgeIndex移除图中的边。

新增了一个函数 degree_centrality()，用于计算给定图中所有节点的度中心性。例如：

import rustworkx as rx
from rustworkx.visualization import mpl_draw

graph = rx.generators.hexagonal_lattice_graph(4, 4)
centrality = rx.degree_centrality(graph)

# 生成颜色列表
colors = []
for node in graph.node_indices():
    centrality_score = centrality[node]
    graph[node] = centrality_score
    colors.append(centrality_score)
mpl_draw(
    graph,
    with_labels=True,
    node_color=colors,
    node_size=650,
    labels=lambda x: "{0:.2f}".format(x)
)

添加了两个新函数，in_degree_centrality() 与 out_degree_centrality()，用于计算有向图的两种特殊类型的度数中心性。

添加用于计算有向图中所有节点的直接支配点的 rustworkx.immediate_dominators() 函数。此函数与 networkx.immediate_dominators 函数对应。

添加 rustworkx.dominance_frontiers() 函数，用于计算有向图中所有节点的支配边界。此函数与 networkx.dominance_frontiers 函数功能相同。

PyDiGraph() 和 PyGraph() 类现在对 PEP 560 有了更好的支持。基于之前版本引入的类型注解功能，以下代码片段现为有效：
import rustworkx as rx graph: rx.PyGraph[int, int] = rx.PyGraph()
之前，用户必须依赖 PEP 563 中类型注解的延迟评估功能才能使注解生效。

更多信息请参阅issue 1345。

新增了一个名为karate_club_graph()的函数，它返回Zachary的Karate Club图，常用于社交网络示例。

import rustworkx.generators
from rustworkx.visualization import mpl_draw

graph = rustworkx.generators.karate_club_graph()
layout = rustworkx.circular_layout(graph)
mpl_draw(graph, pos=layout)

新增了一个方法 neighbors_undirected() 以在有向图中获取节点的邻居，不考虑边方向性。

添加了使用函数 read_graphml() 读取经过 gzip 压缩的 GraphML 文件的功能。自动识别扩展名 .graphmlz 和 .gz，但可以使用“compression”可选参数强制启用 gzip 解压。

更新说明#

使用rustworkx的最低支持Python版本已提升至Python 3.9。 Python 3.8已到达其生命周期终点，将不再受支持。要使用rustworkx，您需要确保正在使用Python >=3.9版本。

Bug 修复 #

修复了在0.15版本中引入的一个错误：当在调用mpl_draw()时将边颜色指定为列表时，它们的顺序没有被正确遵守。相反，颜色的顺序会被打乱。这一点已被恢复，现在的行为应与0.14版本一致。

修复了类型提示中的一个错误，涉及 find_node_by_weight() 和 find_node_by_weight()。更多信息请参考 issue 1243。

修复了 layers() 类型提示中的一个错误更多信息请参考 issue 1340。

修复了node_link_json()中类型提示的错误。更多信息请参考issue 1243。

修复由typos检测到的拼写错误。将拼写检查器调用添加到Nox lint会话中。

修复了 rustworkx.visit 模块中类型提示可发现性的一个 bug。模块中声明的类现在也正确标注为接受泛型类型。更多信息请参考 issue 1352。

增强了类型标注与严格模式下pyright的兼容性。详情请见issue 1242。

0.15.1#

预备知识

本次发布是一个错误修复补丁版本，修复了在0.15.0版本中graphviz_draw()函数意外造成的API破坏性变更。

Bug 修复 #

修复了graphviz_draw()、PyGraph.to_dot()和 PyDiGraph.to_dot()中的一个问题，该问题在升级到0.15.0版本时错误地对字符串进行了转义。在早期版本的rustworkx中，如果您在字符串中手动添加引号以便通过attr回调传递到输出的dot文件中，这在rustworkx 0.15.0中被错误地转换为重复引号并进行转义。例如，如果您定义了如下回调：
```
def color_node(_node):
    return {
        "color": '"#422952"'
    }
```
要在输出的dot文件中使用字符串"#422952"（包含引号）设置颜色属性，此字符串被错误地转换为"\"#422952\""。该问题已修复，在rustworkx 0.16.0版本中，很可能会在graphviz_draw()、 PyGraph.to_dot()和PyDiGraph.to_dot()中暴露更多相关选项。

修复了生成器函数hexagonal_lattice_graph()和directed_hexagonal_lattice_graph()在with_positions = True时进行的节点位置计算中的两个错误:
- 修正了导致晶格中所有六边形不规则的缩放因子
- 修复了一个索引错误，该错误在periodic = False且cols为奇数时错误地定位了晶格最后一列中的节点

0.15.0#

预备知识

这是 Rustworkx 的一个新功能发布版本，为库添加了许多新功能。本次发布的亮点包括：

对先前仅存在于 Python API 中的 rustworkx-core 功能进行了扩展。

扩展图着色算法

此版本转向使用 Python Stable ABI，虽然此版本正式支持 Python 3.8 至 3.12，但发布的二进制文件也应兼容未来的 Python 版本。尽管对未来的版本不提供任何保证。此外，构建 rustworkx 以及更重要的 rustworkx-core 的最低支持 Rust 版本现在是 1.70.0。此外，在此版本中，macOS arm64 平台已从 Tier 4 升级为 Tier 1。

新功能#

新增了一个方法has_node() 到 PyGraph与PyDiGraph 类中，用于检查节点是否存在于图中。

在 rustworkx-core 中添加了新函数 rustworkx_core::dag_algo::layers 以获取有向无环图的层次。这相当于 Python API 中已有的 layers() 函数，但现在也向 Rust 用户开放了该功能。

添加了两个新函数，from_node_link_json_file() 和 parse_node_link_json()，用于解析节点链接 JSON 对象并从中生成一个 rustworkx PyGraph 或 PyDiGraph 对象。

为rustworkx_core::traversal模块新增了ancestors()函数。这是核心Rust库的通用Rust实现，为Rust用户提供ancestors()函数。

为 rustworkx_core::traversal 模块新增了函数 descendants()。这是一个针对 Rust 核心库的通用 Rust 实现，为 Rust 用户提供 descendants() 函数。

在 rustworkx_core::traversal 模块中新增了一个函数 bfs_predecessors()。这是核心 Rust 库的一个通用 Rust 实现，它为 Rust 用户提供了 bfs_predecessors() 函数。

在rustworkx_core::traversal模块中新增了bfs_successors()函数。这是为Rust核心库提供的一个通用Rust实现，向Rust用户提供bfs_successors()函数。

在rustworkx-core的dag_algo模块中添加了新函数collect_runs。此前，DAG的collect_runs()功能仅通过Python接口提供。现在Rust用户可以在rustworkx-core中使用此功能。

添加了函数 connected_subgraphs() 用于以多项式延迟确定无向图中所有大小为 \(k\) 的连通子图。对于诸如 heavy-hex 的稀疏图，这相比暴力方法提高了两个数量级，使能够处理更大的图和更大的 \(k\)。所引入的方法基于 Christian Komusiewicz 和 Frank Sommer 的“枚举连通诱导子图：改进的延迟和实验比较”。具体来说，实现了过程 Simple。可通过在每个递归上进行并行化，或者遵循上述工作中引理 4 的讨论，从而实现更高效的中间集 \(X\) 和 \(P\)，来获得可能的运行时改进。

Rustworkx 函数中返回自定义可迭代对象的那些，例如 PyDiGraph.node_indices()，现在每个都关联了自定义迭代器与反向迭代器对象。这为遍历这些自定义可迭代对象带来了约40%的性能提升。

这些类型无法直接从 Python 空间命名或构造，除了性能提升以外，其行为在 Python 空间基本上不会被察觉到。

添加了 rustworkx.generators.dorogovtsev_goltsev_mendes_graph()，用于生成通过Dorogovtsev-Goltsev-Mendes迭代过程产生的确定性无标度图。
import rustworkx as rx from rustworkx.visualization import mpl_draw graph = rx.generators.dorogovtsev_goltsev_mendes_graph(2) mpl_draw(graph)

为 rustworkx-core 添加了一个新函数 rustworkx_core::generators::dorogovtsev_goltsev_mendes_graph，用于通过 Dorogovtsev-Goltsev-Mendes 迭代过程生成确定性无标度图。

在rustworkx-core中，现支持对petgraph类型StableGraph 和GraphMap进行节点收缩。使用方法：从graph_ext导入任一ContractNodes*特性并在图上调用contract_nodes方法。

所有当前的 petgraph 数据结构现在都支持在 rustworkx-core 中测试平行边。要使用此功能，请根据您的图形类型导入 HasParallelEdgesDirected 或 HasParallelEdgesUndirected，并在您的图上调用 has_parallel_edges 方法。

一个新特性 NodeRemovable 已添加到 graph_ext 模块中的 rustworkx-core，为在 petgraph 类型 Graph, StableGraph, GraphMap, 和 MatrixGraph 上执行节点移除操作提供了一致的接口。要使用它，从 graph_ext 导入 NodeRemovable.

新增随机图生成函数 hyperbolic_random_graph()，用于采样双曲随机图模型。例如：

import math

import rustworkx as rx
from rustworkx.visualization import mpl_draw

graph = rx.hyperbolic_random_graph(
  [[math.sinh(0.5), 0, 3.14159], [-math.sinh(1), 0, -3.14159]],
    2.55,
    None,
)
mpl_draw(graph)

为rustworkx-core模块rustworkx_core::generators新增函数 hyperbolic_random_graph()，该函数用于对双曲随机图模型进行采样。

lexicographical_topological_sort() 和 TopologicalSorter 现在都接受一个 initial 关键字参数，可用于将返回的拓扑排序限制为仅包含由 initial 集合支配的节点。这可以通过避免搜索所有图节点来确定初始零入度节点集来提高性能；这对于 TopologicalSorter 尤其相关，用户可能在仅检查部分顺序后终止搜索。

新增了一个函数 is_semi_connected()，该函数将检查一个 :class: ~rustworkx.PyDiGraph 对象是否为半连通。

在 rustworkx_core::dag_algo 模块中新增了一个函数 lexicographical_topological_sort。这是核心 Rust 库中的一个通用 Rust 实现，为 Rust 用户提供 lexicographical_topological_sort() 函数。

新增一个函数 digraph_maximum_bisimulation() 来计算图的最大双模拟或关系最粗划分. 该函数基于Paige和Tarjan发表在"Three partition refinement algorithms"中的算法实现. 此函数接收一个图并返回 RelationalCoarsestPartition.

添加了一个新类 RelationalCoarsestPartition 用于输出图的最大互模拟或关系最粗划分。该类包含 IndexPartitionBlock 的实例，并且可进行迭代。

新增了一个新类 IndexPartitionBlock 用于输出节点分区的块。该类是节点索引上的迭代器。

在 rustworkx-core 的 dag_algo 模块中新增了一个函数 collect_bicolor_runs。之前，DAG 的 collect_bicolor_runs() 功能仅通过 Python 接口暴露。现在 Rust 用户也可以在 rustworkx-core 中使用这一功能。

向 rustworkx-core 添加了新模块 dag_algo，该模块包含新函数 longest_path。之前 DAG 的 longest_path() 功能仅通过 Python 接口暴露，现在 Rust 用户可以在 rustworkx-core 中利用此功能。

为生成器函数hexagonal_lattice_graph()和directed_hexagonal_lattice_graph()新增了两个关键字参数：periodic和with_positions。如果periodic设置为True，晶格的边界将会被连接成一个周期性网格。如果with_positions参数设置为True，所有节点的数据载荷将被设置为一个形式为(x, y)的元组，其中x和y表示节点在晶格中的位置。例如：
import rustworkx as rx from rustworkx.visualization import mpl_draw graph = rx.generators.hexagonal_lattice_graph(4, 4, periodic=True, with_positions=True) mpl_draw(graph, with_labels=True, labels=str)

新增了一个新的 rustworkx-core 函数 rustworkx_core::generators::hexagonal_lattice_graph_weighted() 用于生成正六边形点阵图，其中会使用回调函数从形式为 (usize, usize) 的元组为每个节点生成节点权重。

新增了 PyDiGraph.remove_node_retain_edges_by_id() 和 remove_node_retain_edges_by_key() 方法，这些方法提供了一种节点移除操作，其时间复杂度与节点度数呈线性关系，而不像 remove_node_retain_edges() 那样是二次方。这些方法分别要求：如果要保留边权重，则边权重必须具有引用等同性（在Python中为 a is b），或者你可以提供一个 key 函数，该函数生成一个Python可哈希的结果，用于进行输入边和输出边之间的相等性匹配。

新增了一个新类 ColoringStrategy，用于指定贪心节点和边着色算法所使用的策略。Degree 策略优先对度数较高的节点进行着色。Saturation 策略动态选择已分配最多不同颜色给其邻接点的顶点，若出现平局，则选择拥有最多未着色邻接点的顶点。IndependentSet 策略寻找图的独立子集，并为每个子集分配不同颜色。

rustworkx-core coloring 模块新增了2个函数， greedy_node_color_with_coloring_strategy 和 greedy_edge_color_with_coloring_strategy。这些函数分别使用指定的着色策略对图的节点或边进行着色，并在提供预设颜色时处理这些颜色。

新增了一个关键字参数 strategy，用于 graph_greedy_color() 和 graph_greedy_edge_color() 来指定贪心着色策略。

例如：

import rustworkx as rx
from rustworkx.visualization import mpl_draw

graph = rx.generators.generalized_petersen_graph(5, 2)

coloring = rx.graph_greedy_color(graph, strategy=rx.ColoringStrategy.Saturation)
colors = [coloring[node] for node in graph.node_indices()]

layout = rx.shell_layout(graph, nlist=[[0, 1, 2, 3, 4],[6, 7, 8, 9, 5]])
mpl_draw(graph, node_color=colors, pos=layout)

新增了关键字参数preset_color_fn至graph_greedy_edge_color()，该参数用于在计算图着色时为特定边提供预设颜色。您可以选择向该参数传递一个可调用对象，该对象将接收图的边索引，并预期返回用于该边的整数颜色，或返回None以表示该边没有预设颜色。例如：

import rustworkx as rx
from rustworkx.visualization import mpl_draw

graph = rx.generators.generalized_petersen_graph(5, 2)

def preset_colors(edge_index):
    if edge_index == 0:
        return 3

coloring = rx.graph_greedy_edge_color(graph, preset_color_fn=preset_colors)
colors = [coloring[edge] for edge in graph.edge_indices()]

layout = rx.shell_layout(graph, nlist=[[0, 1, 2, 3, 4], [6, 7, 8, 9, 5]])
mpl_draw(graph, edge_color=colors, pos=layout)

在rustworkx中为随机分块模型新增随机图生成器。提供了有向图生成器 directed_sbm_random_graph() 和无向图生成器 undirected_sbm_random_graph()。

import numpy as np

import rustworkx as rx
from rustworkx.visualization import mpl_draw

graph = rx.undirected_sbm_random_graph(
    [2, 1],
    np.array([[1, 1], [1, 0]], dtype=float),
    False,
)
mpl_draw(graph)

在 rustworkx-core 模块 rustworkx_core::generators 中添加了新函数 sbm_random_graph，用于从随机块模型中采样图。

rustworkx 的轮子现在基于 Python 的稳定应用程序二进制接口（ABI）构建。对于 rustworkx 用户而言，这意味着我们通过 PyPI 分发的轮子将继续适用于更新版本的 Python，而无需重新编译代码。这一变更也将简化开发者的发布流程，并减少镜像 rustworkx 轮子所需的存储空间。

TopologicalSorter 现在有一个 check_args 关键字参数，可以设置为 False 来禁用对无效参数的运行时检测到 done()。这为在线排序器提供了内存和运行时的改进，但代价是如果提供了无效值，结果将是未定义且可能毫无意义的。

TopologicalSorter.done() 现在除了整数列表外，也可以接受单整数。这对于迭代节点并仅条件性地将其标记为done的算法来说，可能带来显著的性能提升；不再需要分配临时的Python数组。

lexicographical_topological_sort() 和 TopologicalSorter 现在接受 reverse 关键字参数，可以设置为 True 来寻找“反向”拓扑排序。这是一种拓扑排序，如果图中所有边的方向反转，就会得到这种排序。

PyGraph 和 PyDiGraph 现在在其构造函数中分别接受关键字参数 node_count_hint 和 edge_count_hint，这些参数可用于为给定数量的节点和边预分配空间。

更新说明#

构建 rustworkx 和 rustworkx-core 所支持的最低 Rust 版本已从 1.64 提升至 1.70。您需要将编译器版本升级到至少 1.70 才能继续从源代码构建。在受支持平台上安装 rustworkx 的 Python 库用户无需进行任何更改。

rustworkx-core 函数 rustworkx_core::connectivity::find_cycle 现在要求其输入参数 graph 具有 petgraph::visit::Visitable 特性。这是为了修复当 source 为 None 时的行为，确保如果存在环，我们总能找到一个环。

rustworkx_core::generators::hexagonal_lattice_graph() 函数的接口已发生变更，新增了一个必需的布尔参数 periodic，该参数用于指示输出图是否应连接晶格边界以形成周期性网格。在先前版本的 rustworkx-core 中此参数不存在，升级至该新版本时需要添加此参数。

Bug 修复 #

修复了当未提供源节点时 digraph_find_cycle() 的行为。之前，该函数会从一个任意节点开始寻找环，这不能保证会返回一个环。现在，该函数会智能选择一个源节点来开始搜索，以确保如果环存在，就能被找到。

修复了 graphviz_draw() 中的一个问题，该问题曾导致无法在所有场景下正确转义特殊字符。现已修正，因此您现在可以在函数中使用特殊字符，例如：

import rustworkx as rx
from rustworkx.visualization import graphviz_draw

graphviz_draw(
    rx.generators.path_graph(2),
    node_attr_fn=lambda x: {"label": "the\nlabel", "tooltip": "the\ntooltip"},
)

修复：#750

修正了使用mpl_draw()绘制多重图的问题。先前，多重图的平行边会相互重叠绘制，箭头与标签彼此覆盖。现在，对于draw_edges()中支持connectionstyle这一参数的情况，多重图平行边的半径被固定为0.25。在draw_edge_labels()中，边标签的偏移量调整至0.25，以便与对应的边对齐。可通过以下代码测试此修复：
import rustworkx from rustworkx.visualization import mpl_draw graph = rustworkx.PyDiGraph() graph.add_node('A') graph.add_node('B') graph.add_node('C') graph.add_edge(1, 0, 2) graph.add_edge(0, 1, 3) graph.add_edge(1, 2, 4) mpl_draw(graph, with_labels=True, labels=str, edge_labels=str, alpha=0.5)
修复#774

修复了 mpl_draw() 的类型提示中的一个错误。此前，类型提示表明在调用此方法时所有 kwargs 参数都是必需的。类型注释已更新为指示允许使用部分参数的 kwargs。

修复了Dijkstra路径函数的一个问题：
where a PanicException was raised without much detail when an invalid node index was passed in to the source argument. This has been corrected so an IndexError is raised instead. Fixed #1117

修复了bfs_search(), dfs_search() 和 dijkstra_search()的类型提示错误。更多信息请参阅#1130。

修复了在read_graphml()函数中处理来自输入GraphML的Long类型属性的支持。修复了#1140。

其他说明#

对 arm64 macOS 平台的支持已从 Tier 4 提升至 Tier 1。此前该平台处于 Tier 4 级别，因为当时没有可用的 CI 环境用于在该平台上测试 rustworkx。如今 GitHub 已向开源项目提供 arm64 macOS 环境 [1]，我们正与其他 Tier 1 支持的平台一同测试该平台。

[1]
https://github.blog/changelog/2024-01-30-github-actions-introducing-the-new-m1-macos-runner-available-to-open-source/

对于 rustworkx 的开发，所使用的自动化测试环境工具已从 Tox 切换为 Nox。这对最终用户没有影响，仅在你向 rustworkx 贡献代码时才相关。

0.14.0#

预备知识

这是 Rustworkx 的一个新功能发布版本，它为库添加了许多新特性。此版本的亮点包括：

完全支持带 mypy 及其他工具的类型注解

对图着色功能的改进

本次版本支持在Python 3.8至3.12环境下运行。从源码构建rustworkx和rustworkx-core的最低Rust版本要求现已提升至1.64.0。本版本对macOS的最低支持版本已从10.9升级至10.12。同时，Linux ppc64le和s390x平台的支持等级已从Tier 3降级为Tier 4。

新功能#

新增了两个随机图生成函数： directed_barabasi_albert_graph() 和 barabasi_albert_graph()，用于通过Barabási–Albert优先连接机制扩展输入图以生成随机图。例如：

import rustworkx
from rustworkx.visualization import mpl_draw

starting_graph = rustworkx.generators.path_graph(10)
random_graph = rustworkx.barabasi_albert_graph(20, 10, initial_graph=starting_graph)
mpl_draw(random_graph)

在rustworkx-core模块中新增了一个函数 rustworkx_core::generators barabasi_albert_graph()，用于通过Barabási–Albert优先连接算法生成随机图，以扩展输入图。

新增了一个新函数 all_shortest_paths() (以及特定图形类型的变体： graph_all_shortest_paths() 与 digraph_all_shortest_paths())，用于搜寻图中任意两个节点间的每一条简单最短路径。

在rustworkx-core模块中新增一个功能 rustworkx_core::shortest_path模块中的all_shortest_path()函数，用于寻找图中的每一条简单最短路径。

为 rustworkx-core rustworkx_core::coloring模块新增了一个名为two_color的函数。该函数用于计算图的二着色方案，也可用于判断图是否为二分图，因为当无法进行二着色时会返回None。

新增了一个函数 two_color()，用于计算图的二色着色。例如：

import rustworkx as rx
from rustworkx.visualization import mpl_draw

graph = rx.generators.heavy_square_graph(5)
colors = rx.two_color(graph)
mpl_draw(graph, node_color=[colors[i] for i in range(len(graph))])

新增了一个新函数 is_bipartite() 来判断给定的图对象是否为二分图。

新增一个函数 bridges()，用于查找无向 PyGraph 的桥梁。桥梁是指那些如果被移除，会增加图的连通分量数量的边。例如：

import rustworkx
from rustworkx.visualization import mpl_draw

graph = rustworkx.PyGraph()
graph.extend_from_edge_list([
    (0, 1), (1, 2), (0, 2), (1, 3)
])
bridges = rustworkx.bridges(graph)
bridges_set = [set(edge) for edge in bridges]

colors = []
for edge in graph.edge_list():
  color = "red" if set(edge) in bridges_set else "black"
  colors.append(color)
mpl_draw(graph, edge_color=colors)

在 rustworkx_core:connectivity:biconnected 模块中新增了一个函数 bridges，用于查找无向图中的桥梁。桥梁指的是移除后会增加图连通组件数量的边。例如：

新增了一个新函数 clear() ，可用于从 PyGraph 或 PyDiGraph 中清除所有节点和边。

新增函数 clear_edges()，用于清除 PyGraph 或 rustworkx.PyDiGraph 的所有边而不修改节点。

新增了方法 edge_indices_from_endpoints()，该方法返回指定端点之间的所有边的索引。对于 PyDiGraph，有一个对应的方法返回有向边。

PyGraph 和 PyDiGraph 类有一个新方法 filter_nodes() (或 filter_nodes()). 该方法返回一个 NodeIndices 对象，其中包含满足过滤函数所指定的某些抽象条件的节点。例如：

from rustworkx import PyGraph

graph = PyGraph()
graph.add_nodes_from(list(range(5))) # 添加从0到5的节点

def my_filter_function(node):
  return node > 2

indices = graph.filter_nodes(my_filter_function)
print(indices)

NodeIndices[3, 4]

PyGraph 和 PyDiGraph 类新增了一个方法 filter_edges()（或 filter_edges()）。此方法返回一个 EdgeIndices 对象，其中包含符合过滤器函数指定的某些抽象条件的结果边。例如：

from rustworkx import PyGraph
from rustworkx.generators import complete_graph

graph = PyGraph()
graph.add_nodes_from(range(3))
graph.add_edges_from([(0, 1, 'A'), (0, 1, 'B'), (1, 2, 'C')])

def my_filter_function(edge):
  if edge:
    return edge == 'B'
  return False  
  
indices = graph.filter_edges(my_filter_function)
print(indices)

EdgeIndices[1]

新增了一个算法函数， rustworkx.floyd_warshall_successor_and_distance()，用于计算 PyGraph 和 PyDiGraph 图中所有节点对之间的最短路径距离和后续节点。

Added a new function, graph_line_graph() to construct a line graph of a PyGraph object.

The line graph \(L(G)\) of a graph \(G\) represents the adjacencies between edges of G. \(L(G)\) contains a vertex for every edge in \(G\), and \(L(G)\) contains an edge between two vertices if the corresponding edges in \(G\) have a vertex in common.

import rustworkx as rx
from rustworkx.visualization import mpl_draw

graph = rx.PyGraph()
node_a = graph.add_node("a")
node_b = graph.add_node("b")
node_c = graph.add_node("c")
node_d = graph.add_node("d")
edge_ab = graph.add_edge(node_a, node_b, 1)
edge_ac = graph.add_edge(node_a, node_c, 1)
edge_bc = graph.add_edge(node_b, node_c, 1)
edge_ad = graph.add_edge(node_a, node_d, 1)

out_graph, out_edge_map = rx.graph_line_graph(graph)
assert out_graph.node_indices() == [0, 1, 2, 3]
assert out_graph.edge_list() == [(3, 1), (3, 0), (1, 0), (2, 0), (2, 1)]
assert out_edge_map == {edge_ab: 0, edge_ac: 1, edge_bc: 2, edge_ad: 3}
mpl_draw(out_graph, with_labels=True)

添加了一个新函数graph_greedy_edge_color()来使用贪心方法对PyGraph对象的边进行着色。

该函数通过贪婪地对给定图的线图着色来实现。

import rustworkx as rx
from rustworkx.visualization import mpl_draw

graph = rx.generators.cycle_graph(7)
edge_colors = rx.graph_greedy_edge_color(graph)
assert edge_colors == {0: 0, 1: 1, 2: 0, 3: 1, 4: 0, 5: 1, 6: 2}
mpl_draw(graph, edge_color=[edge_colors[i] for i in range(graph.num_edges())])

新增一个函数，graph_misra_gries_edge_color()，用于通过Misra-Gries边着色算法为PyGraph对象的边着色。

上述算法在论文"A constructive proof of Vizing’s theorem"（Misra和Gries，1992年）中有详细描述。

着色最多产生\(d + 1\)种颜色，其中\(d\)是图的最大度数。

import rustworkx as rx
from rustworkx.visualization import mpl_draw

graph = rx.generators.cycle_graph(7)
edge_colors = rx.graph_misra_gries_edge_color(graph)
assert edge_colors == {0: 0, 1: 1, 2: 2, 3: 0, 4: 1, 5: 0, 6: 2}
mpl_draw(graph, edge_color=[edge_colors[i] for i in range(graph.num_edges())])

新增了一个名为isolates()的功能，用于在PyDiGraph或PyGraph中寻找孤立节点（度数为0的节点）。

在rustworkx-core的rustworkx_core::connectivity模块中新增了一个函数isolates()，用于查找孤立节点（度为0的节点）。

为 PyGraph 类新增了 substitute_node_with_subgraph 方法。

import rustworkx
from rustworkx.visualization import * # 需要 matplotlib/

graph = rustworkx.generators.complete_graph(5)
sub_graph = rustworkx.generators.path_graph(3)

# 在这个图谱中将节点4替换为子图谱
# 确保在子图谱的节点2处进行图谱连接
# 通过传递一个返回2的函数实现

graph.substitute_node_with_subgraph(4, sub_graph, lambda _, __, ___: 2)

# 绘制更新后的图谱
mpl_draw(graph, with_labels=True)

新增了一个函数 topological_generations()，该函数将 PyDiGraph 分层为拓扑代次。

新增加了一个异常类 GraphNotBipartite，当图形不是二分图时会抛出此异常。该异常的唯一使用者是 graph_bipartite_edge_color()，当用户提供的图形不是二分图时，它会抛出此异常。

新增了一个函数 graph_bipartite_edge_color()，用于对 PyGraph 对象的边进行着色。该函数首先检查图是否为二分图，如果不是，则抛出类型为 GraphNotBipartite 的异常。否则，该函数会调用二分图边着色算法，并返回一个字典，其中键为边的索引，值为分配的颜色。

实现的算法基于 Noga Alon 于 2003 年发表的论文《A simple algorithm for edge-coloring bipartite multigraphs》（一种简单的二分多重图边着色算法）。

着色最多使用 \(d\) 种颜色，其中 \(d\) 是图中节点的最大度数。该算法的时间复杂度为 \(\mathcal{O}(n + m\log{}m)\)，其中 \(n\) 是顶点数，\(m\) 是边数。
import rustworkx as rx from rustworkx.visualization import mpl_draw graph = rx.generators.cycle_graph(8) edge_colors = rx.graph_bipartite_edge_color(graph) assert edge_colors == {0: 0, 1: 1, 2: 0, 3: 1, 4: 0, 5: 1, 6: 0, 7: 1} mpl_draw(graph, edge_color=[edge_colors[i] for i in range(graph.num_edges())])

新增了两个随机图形生成器函数， directed_random_bipartite_graph() 和 undirected_random_bipartite_graph()，用于生成随机二分图。例如：

import rustworkx as rx
from rustworkx.visualization import mpl_draw

random_graph = rx.undirected_random_bipartite_graph(10, 5, 0.5, seed=20)
layout = rx.bipartite_layout(random_graph, set(range(10)))
mpl_draw(random_graph, pos=layout)

The functions graph_adjacency_matrix() and digraph_adjacency_matrix() now have the option to adjust parallel edge behavior. Instead of just the default sum behavior, the value in the output matrix can be the minimum (“min”), maximum (“max”), or average (“avg”) of the weights of the parallel edges. For example:

import rustworkx as rx
graph = rx.PyGraph()
a = graph.add_node("A")
b = graph.add_node("B")
c = graph.add_node("C")

graph.add_edges_from([
    (a, b, 3.0),
    (a, b, 1.0),
    (a, c, 2.0),
    (b, c, 7.0),
    (c, a, 1.0),
    (b, c, 2.0),
    (a, b, 4.0)
])

print("Adjacency Matrix with Summed Parallel Edges")
print(rx.graph_adjacency_matrix(graph, weight_fn= lambda x: float(x)))
print("Adjacency Matrix with Averaged Parallel Edges")
print(rx.graph_adjacency_matrix(graph, weight_fn= lambda x: float(x), parallel_edge="avg"))

Adjacency Matrix with Summed Parallel Edges
[[0. 8. 3.]
 [8. 0. 9.]
 [3. 9. 0.]]
Adjacency Matrix with Averaged Parallel Edges
[[0.         2.66666667 1.5       ]
 [2.66666667 0.         4.5       ]
 [1.5        4.5        0.        ]]

Python 包 rustworkx 现已完全支持 mypy 类型检查。基于之前 0.13.0 版本向库中引入部分类型注解的基础，rustworkx 现在包含了整个公共 API 的类型注解。

新增了一个异常类 InvalidMapping，当函数接收到无效映射时会抛出此异常。该异常的唯一使用者是 graph_token_swapper()，当用户提供的映射在给定图上不可行时，该函数将抛出此异常。

添加了 has_path()，该函数接受 PyGraph 或 PyDiGraph 作为参数，并检查是否存在从源节点到目标节点的路径

from rustworkx import PyDiGraph, has_path

graph = PyDiGraph()
a = graph.add_node("A")
b = graph.add_node("B")
c = graph.add_node("C")
edge_list = [(a, b, 1), (b, c, 1)]
graph.add_edges_from(edge_list)

path_exists = has_path(graph, a, c)
assert(path_exists == True)

path_exists = has_path(graph, c, a)
assert(path_exists == False)

在x86_64架构上增加对musl Linux平台的支持，级别为第三级，在aarch64架构上为第四级。

新增了一个关键字参数 preset_color_fn 到 graph_greedy_color() 中，该参数用于在图着色计算时为特定节点提供预设颜色。你可以选择向该参数传递一个可调用对象，该对象将接收图中的节点索引，并预期返回一个用于该节点的整数颜色，或返回 None 表示该节点没有预设颜色。例如：

import rustworkx as rx
from rustworkx.visualization import mpl_draw

graph = rx.generators.generalized_petersen_graph(5, 2)

def preset_colors(node_index):
    if node_index == 0:
        return 3

coloring = rx.graph_greedy_color(graph, preset_color_fn=preset_colors)
colors = [coloring[node] for node in graph.node_indices()]

layout = rx.shell_layout(graph, nlist=[[0, 1, 2, 3, 4],[6, 7, 8, 9, 5]])
mpl_draw(graph, node_color=colors, pos=layout)

在 rustworkx-core 模块 coloring 中新增了一个函数 greedy_node_color_with_preset_colors。这个新函数与 rustworkx_core::coloring::greedy_node_color 基本相同，区别在于它具有第二个预置参数，该参数接收一个可调用对象，用于为特定节点标识提供预置颜色。

新增了一个函数 transitive_reduction()，它返回指定 PyDiGraph 的传递归约，以及一个包含从给定图到返回图的索引映射字典。给定图必须是一个有向无环图（DAG）。例如：

from rustworkx import PyDiGraph
from rustworkx import transitive_reduction

graph = PyDiGraph()
a = graph.add_node("a")
b = graph.add_node("b")
c = graph.add_node("c")
d = graph.add_node("d")
e = graph.add_node("e")

graph .add_edges_from([
    (a, b, 1),
    (a, d, 1),
    (a, c, 1),
    (a, e, 1),
    (b, d, 1),
    (c, d, 1),
    (c, e, 1),
    (d, e, 1)
])

tr, _ = transitive_reduction(graph)
list(tr.edge_list())

[(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]

参考：https://en.wikipedia.org/wiki/Transitive_reduction

更新说明#

rustworkx和rustworkx-core的最小支持Rust版本（MSRV）已提升至1.64.0。此前你可以使用1.56.1的MSRV来构建rustworkx或rustworkx-core。这一变更是必要的，因为rustworkx的上游依赖项已经采用了更新的MSRV。

最低要求的 Python 版本已提升至 Python 3.8。使用 rustworkx 前，请确保您使用的是 Python >= 3.8。

rustworkx函数 graph_token_swapper() 现在会在请求无效映射时引发 InvalidMapping 异常，而非 PanicException 异常。此举是因为 PanicException 由于其设计用途是表示未处理的错误，因此难以捕获。使用

rustworkx-core 函数 token_swapper() 的返回类型已由 Vec<(NodeIndex, NodeIndex)> 更改为 Result NodeIndex)>, MapNotPossible>。这一变更是为了在请求的映射对于不可能实现的图时返回预期的错误条件。例如，如果你有一个不连通的图，并试图映射没有任何连接性的节点：

use rustworkx_core::token_swapper;
use rustworkx_core::petgraph;

let g = petgraph::graph::UnGraph::<(), ()>::from_edges(&[(0, 1), (2, 3) ]);
let mapping = HashMap::from([
    (NodeIndex::new(2), NodeIndex::new(0)),
    (NodeIndex::new(1), NodeIndex::new(1)),
    (NodeIndex::new(0), NodeIndex::new(2)),
    (NodeIndex::new(3), NodeIndex::new(3)),
]);
token_swapper(&g, mapping, Some(10), Some(4), Some(50));

现在会返回 Err(MapNotPossible) 而不是发生恐慌。如果你之前使用过这个函数，你需要处理结果类型。

对于Linux ppc64le平台的支持已从第三层级变更至第四层级（如平台支持文档中所记录）。这一变更是由于可用CI基础设施的约束，导致无法在预编译wheel发布任务期间运行测试。希望这一变更不会带来任何实质性影响，但由于发布前不再运行测试以验证二进制文件，因此无法再保证ppc64le的wheel具备完整功能（尽管它们能正常运作的可能性仍然很高，因为它在其他平台上运行良好）。如果在Linux ppc64le上遇到任何问题，请提交一个issue。

对于macOS系统，最低macOS版本现为10.12。先前，针对macOS x86_64平台发布的预编译二进制wheel包支持版本为≥10.9。然而，由于支持政策在Rust编程语言方面的变更，所需最低版本需提升至macOS 10.12。若您在macOS 10.9上使用Qiskit，在rustworkx MSRV（最低支持的Rust版本）低于1.74期间，或许可以从源码构建Qiskit，但发布至PyPI的预编译二进制文件仅与macOS ≥10.12兼容。

对Linux s390x平台的支持已从第3级调整为第4级（如平台支持文档中所述）。这是由于在预编译轮发布作业中因现有CI基础设施限制而无法运行测试所致。此次变更应该不会产生任何实质性影响，但由于在发布二进制文件前不再运行验证测试，因此无法保证s390x平台轮包功能完整（尽管其正常工作概率仍然很高，因为该工具在其他平台上运行良好）。若遇到任何s390x Linux相关问题，请提交问题报告。

弃用说明#

传统的 retworkx 包作为 rustworkx 的向后兼容别名现已被标记为弃用。如果你正在使用 retworkx 包，现在导入时会发出 DeprecationWarning。

Bug 修复 #

修复了当 min_depth 设置为 0 时， graph_all_simple_paths() 和 digraph_all_simple_paths() 的行为。更多信息请参考 #955。

修复了一个问题，即对于有向图，directed_gnp_random_graph() 和gnp_random_graph()函数生成的图中，较低节点编号的边数比预期要少。

其他说明#

该版本的rustworkx明确固定使用Numpy 1.x系列，因为其中包含的编译扩展尚未针对尚未发布的Numpy 2.x系列进行编译。我们将尽快发布支持Numpy 2.x的新版本rustworkx。

如果我们尚未发布兼容版本，而您强制尝试将rustworkx与Numpy 2一起安装，我们无法阻止软件包管理器解析到旧版本的rustworkx （这些旧版本没有相同的版本固定，但仍然可能不兼容）。

0.13.0#

预备知识

这次发布是 Rustworkx 的一次主要特性发布，为该库添加了一些新功能。本次发布的亮点包括：

rustworkx-core 暴露的功能得到扩展，包含了一个新的图生成器模块。

新的链接分析函数，如页面排名

扩展的中心性度量函数

为库添加了部分类型注解，包括对 PyDiGraph 和 PyGraph 类。这使得能够使用 mypy 进行类型检查

这也是支持Python 3.7运行的最终rustworkx版本。从0.14.0版本开始，使用rustworkx需要Python >= 3.8。此版本还将编译rustworkx和rustworkx-core的最低支持Rust版本提升至1.56.1。

新功能#

为 PyDiGraph 类新增了一个方法 make_symmetric()。此方法用于使图中所有边对称（图中每条边都有一个反向边）。例如：

import rustworkx as rx
from rustworkx.visualization import graphviz_draw

graph = rx.generators.directed_path_graph(5, bidirectional=False)
graph.make_symmetric()
graphviz_draw(graph)

添加了一个新函数 edge_betweenness_centrality() 用于计算 PyGraph 或 PyDiGraph 对象中所有边的边介数中心性。该函数使用的算法基于： Ulrik Brandes, On Variants of Shortest-Path Betweenness Centrality and their Generic Computation. Social Networks 30(2):136-145, 2008。边 \(e\) 的边介数中心性是通过该边 \(e\) 的所有节点对最短路径比例的总和

\[c_B(e) =\sum_{s,t \in V} \frac{\sigma(s, t|e)}{\sigma(s, t)}\]

其中 \(V\) 是节点集合，\(\sigma(s, t)\) 是最短 \((s, t)\) 路径的数量，\(\sigma(s, t|e)\) 是通过边 \(e\) 的这些路径的数量。例如，以下代码计算一个 5x5 网格图中所有边的边介数中心性，并使用结果在图的可视化中为边上色：
import rustworkx from rustworkx.visualization import mpl_draw graph = rustworkx.generators.grid_graph(5, 5) btw = rustworkx.edge_betweenness_centrality(graph) # 使用边介数中心性为图中的边上色 colors = [] for i in graph.edge_indices(): colors .append(btw[i]) mpl_draw(graph, edge_color=colors)

为rustworkx-core新增了一个功能，在rustworkx_core:centrality模块中添加了edge_betweenness_centrality函数，用以计算给定图中所有边的边介数中心性。

新增了两个新函数，find_cycle 和 cycle_basis，这些函数已被添加到rustworkx-core箱的connectivity模块中。这些函数可以用于在petgraph图中查找循环或查找图的循环基础。

新增了一个函数hits()，用于计算给定有向图中所有节点的枢纽值和权威值。示例如下：

import rustworkx as rx
from rustworkx.visualization import mpl_draw

graph = rx.generators.directed_hexagonal_lattice_graph(2, 2)
hubs, _ = rx.hits(graph)

# 生成颜色列表
colors = []
for node in graph.node_indices():
    hub_score = hubs[node]
    graph[node] = hub_score
    colors.append(hub_score)
mpl_draw(
    graph,
    with_labels=True,
    node_color=colors,
    node_size=650,
    labels=lambda x: "{0:.2f}".format(x)
)

新增了一个函数 katz_centrality()，用于计算给定图中所有节点的Katz中心性。例如：

import rustworkx as rx
from rustworkx.visualization import mpl_draw

graph = rx.generators.hexagonal_lattice_graph(4, 4)
centrality = rx.katz_centrality(graph)

# 生成颜色列表
colors = []
for node in graph.node_indices():
    centrality_score = centrality[node]
    graph[node] = centrality_score
    colors .append(centrality_score)
mpl_draw(
    graph,
    with_labels=True,
    node_color=colors,
    node_size=650,
    labels=lambda x: "{0:.2f}".format(x)
)

为 rustworkx-core 的 katz_centrality 新增功能到 rustworkx_core::centrality 模块，该功能用于计算给定图中所有节点的 Katz 中心性。

新添了一个功能 longest_simple_path() ，它被用来搜索图中所有节点对之间的所有简单路径，并返回找到的最长路径。例如：

import rustworkx as rx

graph = rx.generators.binomial_tree_graph(5)
longest_path = rx.longest_simple_path(graph)
print(longest_path)

NodeIndices[31, 30, 28, 24, 16, 0, 8, 12, 14, 15]

然后将找到的最长路径中的节点可视化：

from rustworkx.visualization import mpl_draw

path_set = set(longest_path)
colors = []
for index in range(len(graph)):
    if index in path_set:
      colors.append('r')
    else:
      colors.append('#1f78b4')
mpl_draw(graph, node_color=colors)

在rustworkx-core中新添了一个函数longest_simple_path_multiple_targets()。此函数将返回从源节点到一系列目标节点的最长简单路径，这些目标节点被存储在HashSet中。

新增了一个函数 pagerank()，用于计算给定有向图中所有节点的PageRank分数。例如：

import rustworkx as rx
from rustworkx.visualization import mpl_draw

graph = rx.generators.directed_hexagonal_lattice_graph(2, 2)
ranks = rx.pagerank(graph)

# 生成颜色列表
colors = []
for node in graph.node_indices():
    pagerank_score = ranks[node]
    graph[node] = pagerank_score
    colors .append(pagerank_score)
mpl_draw(
    graph,
    with_labels=True,
    node_color=colors,
    node_size=650,
    labels=lambda x: "{0:.2f}".format(x)
)

新增了三个新的随机图生成器：gnp_random_graph、gnm_random_graph和random_geometric_graph，它们被添加至rustworkx-core包的generators模块中。其中，gnp_random_graph接收节点数量和添加边的概率作为输入参数；gnp_random_graph则接收节点数量和边数作为输入；而random_geometric_graph会在一个n维立方体内创建一个随机图。

新增了一个函数，bfs_predecessors()，用于在从指定节点开始的逆向广度优先遍历中返回前驱节点列表。这与现有的bfs_successors()方法类似。

新增方法 find_predecessor_node_by_edge() 用于获取通过指定边连接的节点的直接前驱节点。

新增了一个函数 graph_token_swapper()，它基于以下论文执行近似最优的令牌交换算法：

Miltzow等人（2016）的《令牌交换的近似与难度》 https://arxiv.org/abs/1602.05150

该算法支持存在缺失令牌的图中的部分映射（即非排列）。

在新模块 rustworkx_core::token_swapper 中添加了一个新函数 token_swapper()。该函数执行一个基于以下论文的近似最优令牌交换算法：

Approximation and Hardness for Token Swapping by Miltzow et al. (2016) https://arxiv.org/abs/1602.05150

支持包含缺失令牌的图中部分映射（即非排列）。

Added a new function, closeness_centrality() to compute the closeness centrality of all nodes in a PyGraph or PyDiGraph object.

The closeness centrality of a node \(u\) is defined as the the reciprocal of the average shortest path distance to \(u\) over all \(n-1\) reachable nodes. In it’s general form this can be expressed as:

\[C(u) = \frac{n - 1}{\sum_{v=1}^{n-1} d(v, u)},\]

where \(d(v, u)\) is the shortest-path distance between \(v\) and \(u\), and \(n\) is the number of nodes that can reach \(u\). For example, to visualize the closeness centrality of a graph:

import matplotlib.pyplot as plt

import rustworkx as rx
from rustworkx.visualization import mpl_draw

graph = rx.generators.hexagonal_lattice_graph(4, 4)
centrality = rx.closeness_centrality(graph)
# Generate a color list
colors = []
for node in graph.node_indices():
    colors.append(centrality[node])
# Generate a visualization with a colorbar
plt.rcParams['figure.figsize'] = [15, 10]
ax = plt.gca()
sm = plt.cm.ScalarMappable(norm=plt.Normalize(
    vmin=min(centrality.values()),
    vmax=max(centrality.values())
))
plt.colorbar(sm, ax=ax)
plt.title("Closeness Centrality of a 4 x 4 Hexagonal Lattice Graph")
mpl_draw(graph, node_color=colors, ax=ax)

新增了生成器函数，empty_graph()，以及directed_empty_graph()到 rustworkx.generators模块，用于生成空图。例如：

import rustworkx.generators
from rustworkx.visualization import mpl_draw

graph = rustworkx.generators.empty_graph(4)
mpl_draw(graph)

新增生成器函数complete_graph()和directed_complete_graph()至rustworkx.generators模块，用于生成完全图。这些函数等效于调用mesh_graph()和directed_mesh_graph()函数。例如：
import rustworkx.generators from rustworkx.visualization import mpl_draw graph = rustworkx.generators.complete_graph(4) mpl_draw(graph)

为 rustworkx-core crate 添加了一个新的 generators 模块。该模块包含用于生成图的函数。这些函数在输出图类型上是通用的，可用于为任何实现了所需 petgraph 特性的类型创建图对象。

为库添加了部分类型注解，包括对 PyDiGraph 和 PyGraph 类的注解。这实现了对使用 mypy 进行静态类型检查的支持。

添加了一个新函数greedy_node_color到rustworkx-core中的一个新 coloring模块。它使用贪心图着色算法对图进行着色。

函数 core_number 已添加到 rustworkx-core 包的 connectivity 模块中。它用于计算图中节点的k-core数。

更新说明#

Passing a negative value to the probability argument to the gnp_directed_random_graph() or the gnp_undirected_random_graph() function will now cause an OverflowError to be raised. Previously, a ValueError would be raised in this situation. This was changed to be consistent with other similar error conditions in other functions in the library.

最低支持的 Rust 版本已从 1.48 提升至 1.56.1。这一变动适用于从源代码构建 rustworkx 包以及 rustworkx-core crate。此变动的目的是为了便于使用我们上游依赖项的新版本，并利用更新的 Rust 语言特性。

Bug 修复 #

修复了当使用copy.copy()和copy.deepcopy()复制PyDiGraph时，check_cycle属性未被保留的问题。已修复#836

修复了对PyDiGraph和PyGraph对象使用copy.deepcopy()时，在图对象中存在已删除边的情况下出现的问题。此前，如果边索引因删除操作存在任何空缺，图对象的输出副本会错误地压平索引。现已经修正，确保在deepcopy()后准确重建边索引。修复#585

修复了在构建 rustworkx-core 时与 priority-queue 1.3.0 的兼容性问题。修复了 #744

修复了多个PyDiGraph和PyGraph 方法中移除节点的问题，此前调用这些方法时，PyDiGraph.node_removed属性不会更新以反映节点已被移除。

修复了自定义序列返回类型的一个问题， BFSSuccessors, NodeIndices, EdgeList, WeightedEdgeList, EdgeIndices, 和 Chains 之前缺少某些属性，导致它们无法被用作某些内置函数的序列，例如 reversed()。已修复 #696。

rustworkx.PyGraph.add_edge() and rustworkx.PyDiGraph.add_edge() and now raises an IndexError when one of the nodes does not exist in the graph. Previously, it caused the Python interpreter to exit with a PanicException

0.12.0#

预备知识

这个版本引入了对Rustworkx（之前称为retworkx）项目的一些重大变更。首个更改是库从retworkx重命名为rustworkx，且retwork-core rust crate已更名为rustworkx-core。此举是为了尊重NetworkX库维护者的请求。在当前版本中，retworkx库仍将继续正常工作，不会有任何通知，但从0.13.0版本开始，当从retworkx导入时会发出DeprecationWarning，而在1.0.0版本中，我们将不再支持旧名称。对于retworkx-core crate，crates.io上不会再以该名称发布任何版本，未来所有版本的库都将以rustworkx-core发布。

此外，此版本增加对 Python 3.11 的支持，并为我们发布到 PyPI 的所有预编译 Linux 二进制文件改用 manylinux2014。从源码构建 rustworkx 所需的最低支持 Rust 版本已提升至 Rust 1.48。

此版本还包含了数个新功能，部分亮点如下：

支持在attrs属性下定义图属性

新序列化格式支持（一个graphml解析器，read_graphml()，和一个节点链接JSON生成器，node_link_json())

新算法函数包括：

特征向量中心性

Stoer–Wagner 最小割算法

Bellman-Ford最短路径算法

新功能#

新增了一个函数，eigenvector_centrality()，用于计算给定图中所有节点的特征向量中心性。例如：

import rustworkx as rx
from rustworkx.visualization import mpl_draw

graph = rx.generators.hexagonal_lattice_graph(4, 4)
centrality = rx.eigenvector_centrality(graph)

# 生成一个颜色列表
colors = []
for node in graph.node_indices():
    centrality_score = centrality[node]
    graph[node] = centrality_score
    colors.append(centrality_score)
mpl_draw(
    graph,
    with_labels=True,
    node_color=colors,
    node_size=650,
    labels=lambda x: "{0:.2f}".format(x)
)

在rustworkx-core中新增了一个函数 eigenvector_centrality，位于 rustworkx_core::centrality 模块，用于计算给定图中所有节点的特征向量中心性。

添加了一个新的关键字参数index_output到layers() 函数。当设置为True时，函数的输出是一个以节点索引表示的层级列表。默认输出依然与之前一样，是节点数据负载的层级列表。

Added a new function, node_link_json(), which is used to generate JSON node-link data representation of an input PyGraph or PyDiGraph object. For example, running:

import rustworkx

graph = rustworkx.generators.path_graph(weights=['a', 'b', 'c'])
print(rustworkx.node_link_json(graph, node_attrs=lambda n: {'label': n}))

will output a JSON payload equivalent (identical except for whitespace) to:

{
  "directed": false,
  "multigraph": true,
  "attrs": null,
  "nodes": [
    {
      "id": 0,
      "data": {
        "label": "a"
      }
    },
    {
      "id": 1,
      "data": {
        "label": "b"
      }
    },
    {
      "id": 2,
      "data": {
        "label": "c"
      }
    }
  ],
  "links": [
    {
      "source": 0,
      "target": 1,
      "id": 0,
      "data": null
    },
    {
      "source": 1,
      "target": 2,
      "id": 1,
      "data": null
    }
  ]
}

添加了一个新的算法函数，rustworkx.stoer_wagner_min_cut()，使用Stoer Wagner算法来计算一个无向的PyGraph中的加权最小切割。例如：

import rustworkx
from rustworkx.visualization import mpl_draw

graph = rustworkx.generators.grid_graph(2, 2)
cut_val, partition = rustworkx.stoer_wagner_min_cut(graph)

colors = [
    'orange' if node in partition else 'blue' for node in graph.node_indexes()
]
mpl_draw(graph, node_color=colors)

新增两个计算两个图的张量积的函數 graph_tensor_product() 用于无向图，及 digraph_tensor_product() 用于有向图。例如:

import rustworkx
from rustworkx.visualization import mpl_draw
graph_1 = rustworkx.generators.path_graph(2)
graph_2 = rustworkx.generators.path_graph

新增函数用于计算带负权边图中的全对最短路径，使用带有SPFA启发式方法的Bellman-Ford算法：
- rustworkx.all_pairs_bellman_ford_path_lengths()
- rustworkx.all_pairs_bellman_ford_shortest_paths()

新增了一个函数 all_pairs_all_simple_paths()，用于返回图中所有节点对之间的所有简单路径。它还可以配合可选的 min_depth 和 cutoff 参数，根据路径长度过滤结果。例如：
```
from rustworkx.generators import grid_graph
from rustworkx import all_pairs_all_simple_paths

g = grid_graph(2, 3)
paths = all_pairs_all_simple_paths(g, min_depth=3, cutoff=3)
```
将返回一个字典的字典，其中两个字典键是节点索引，内部值是两个节点之间所有长度为3的简单路径列表。

rustworkx-core rustworkx_core::connectivity 模块新增了一个函数 all_simple_paths_multiple_targets，这类似于 petgraph的algo模块中的all_simple_paths()方法，但不同之处在于它不会返回一个迭代器用于生成从源节点到目标节点的所有简单路径，而是会构建一个DictMap，包含从源节点到提供的HashSet中所有目标节点索引的所有简单路径。

新增功能以计算含负边权图中的负环与最短路径，通过Bellman-Ford算法结合SPFA启发式方法实现：

向 PyDiGraph 和 PyGraph 类添加了图属性的概念。这些属性可以通过图对象的 attrs 属性访问，并可以就地修改。此外，也可以通过构造函数在创建对象时初始设置它们。例如：
```
import rustworkx as rx

graph = rx.PyGraph(attrs=dict(day="Friday"))
graph.attrs['day'] = "Monday"
```
属性可以包含任何 Python 对象，而不仅仅是字典。例如：
```
class Day:

    def __init__(self, day):
        self.day = day

graph = rx.PyGraph(attrs=Day("Friday"))
graph.attrs = Day("Monday")
```
如果未设置 attrs，它将默认为 None。

PyGraph.subgraph() 和 PyDiGraph.subgraph() 方法新增了一个关键词参数 preserve_attributes，可将其设置为 True 来通过引用复制图的 attrs 属性内容到子图的 attrs 属性中。

实现了一个新函数 is_planar()，用于检查无向图 PyGraph 是否是平面图。

import rustworkx as rx

graph = rx.generators.mesh_graph(5)
print('Is K_5 graph planar?', rx.is_planar(graph))

Is K_5 graph planar? False

rustworkx-core 的 connectivity 模块新增了3个函数： connected_components、number_connected_components 以及 bfs_undirected。这些函数是基于 rustworkx 中现有的 connected_components()、number_connected_components() 和 bfs_undirected() 实现的。

新增了一个新函数 read_graphml()，可从GraphML格式的文件生成rustworkx图对象（PyGraph 或 PyDiGraph）。GraphML是一种用于表示图形文件的XML序列化格式。

新增了一个新函数 simple_cycles()，该函数实现了 Johnson 算法用于在有向图中查找所有基本环。

更新说明#

PyGraph 方法 add_edges_from() 和 add_edges_from_no_data() 的返回类型已从整数边索引的 list 更改为 EdgeIndices 对象。EdgeIndices 类是一种只读的整数边索引序列类型。在大多数情况下，这应该是完全兼容的，除非您之前对输出列表进行修改或显式进行类型检查。在这些情况下，您只需使用 list() 将 EdgeIndices 对象进行转换。

此版本不再提供支持manylinux2010打包规范的二进制文件。所有针对Linux平台的预编译二进制文件都是基于manylinux2014构建的。这一变更是必需的，因为最新版本的Rust编译器支持的GLIBC版本发生了变化，再加上manylinux2010平台已不再受支持。如果您需要在此版本之后继续在仅兼容manylinux2010的平台上运行Rustworkx，您将需要从源代码构建并安装（这包含发布到PyPI的sdist，因此 pip install rustworkx在您安装了Rust编译器的情况下仍然可以正常工作），并且需要使用版本< 1.64.0的Rust编译器。

构建 rustworkx 所需的最低支持 Rust 版本已从 1.41 升级至 1.48。要从源代码编译 rustworkx，您需要确保已安装 Rustc >=1.48。

使用 rustworkx 的最低支持 Python 版本已提升至 Python 3.7。要使用 rustworkx，您需要确保正在使用 Python >=3.7。

retworkx 程序包已更名为 rustworkx。这一更名是出于对 NetworkX 库维护者的请求的尊重。目前，retworkx 名称仍然有效，但所有使用 retworkx 的程序包需求或导入都应更名为 rustworkx。

Bug 修复 #

自定义序列返回类型：
- BFSSuccessors
- 节点索引
- 边列表
- 加权边列表
- EdgeIndices
- 链式
now correctly handle slice inputs to __getitem__. Previously if you tried to access a slice from one of these objects it would raise a TypeError. For example, if you had a NodeIndices object named nodes containing [0, 1, 3, 4, 5] if you did something like:
```
nodes[0:3]
```
它将返回一个新的 NodeIndices 对象，包含 [0, 1, 3] 修复 #590

0.11.0#

预备知识

此版本包含许多新功能和错误修复。亮点包括：为 PyGraph 和 PyDiGraph 添加了改进边操作的额外方法、多个新的图生成器，以及一套新的交互式遍历函数：bfs_search(), dfs_search(), dijkstra_search()，和 TopologicalSorter，这些函数可在不同类型的遍历过程中实现与图的迭代交互。

此版本还引入了一个新的独立 Rust 库 rustworkx-core，它是一个基于 petgraph 构建的 Rust 库，扩展了 petgraph 提供的功能。该库中的功能是通用的，可以与任何 petgraph 图配合使用，而不仅仅是 PyGraph 和 PyDiGraph。

0.11.0版本完全支持Python 3.10。针对Python 3.10的预编译二进制文件已发布在PyPI上（之前的版本虽然能在3.10上运行，但需要从源代码编译安装）。这也是最后一个支持Python 3.6的版本。从rustworkx 0.12.0开始，运行rustworkx将需要Python >=3.7。此外，对于从源代码编译rustworkx的用户来说，这将是最低支持的Rust版本（MSRV）为1.41的最后一个版本。在rustworkx 0.12.0中，MSRV将提高到1.48。

新功能#

新增了一个函数cartesian_product()（及其针对特定类型的变体digraph_cartesian_product()和graph_cartesian_product()），用于计算两个图形的笛卡尔积。例如：

import rustworkx
from rustworkx.visualization import mpl_draw

graph_1 = rustworkx.generators.path_graph(2)
graph_2 = rustworkx.generators.path_graph(3)

graph_product, _ = rustworkx.cartesian_product(graph_1, graph_2)

mpl_draw(graph_product)

添加了一个新方法 node_indices() 到 PyDiGraph 和 PyGraph 类中。该方法与之前存在的 node_indexes() 方法完全相同，但更改了名称以与rustworkx其余部分使用的"indices"保持一致。node_indexes() 可能会在未来的版本中被弃用，直到最终在1.0版本中移除。

unweighted_average_shortest_path_length() 函数新增了一个关键字参数 disconnected。当 disconnected 设为 True 时，该函数计算得到的输出值将只考虑已连接的节点对。

为 rustworkx.generators 模块新增了一个生成器函数 barbell_graph()，用于生成杠铃图。例如：

import rustworkx.generators
from rustworkx.visualization import mpl_draw

graph = rustworkx.generators.barbell_graph(4, 3)
mpl_draw(graph)

新增了一个 bfs_search()（及其按类型变体 graph_bfs_search() 和 digraph_bfs_search()），该方法以广度优先方式遍历图并在指定点发出事件。这些事件通过相应的回调函数，由继承 BFSVisitor 的访问者对象处理。例如：

import rustworkx
from rustworkx.visit import BFSVisitor


class TreeEdgesRecorder(BFSVisitor):

    def __init__(self):
        self.edges = []

    def tree_edge(self: 边缘):
        self.edges.append(edge)

graph = rustworkx.PyGraph()
graph.extend_from_edge_list([(1: 3): (0: 1): (2: 1): (0: 2)])
vis = TreeEdgesRecorder()
rustworkx.bfs_search(graph: [0]: vis)
print('树状边：': vis.edges)

树状边： [(0, 2, None), (0, 1, None), (1, 3, None)]

新增了一个函数：articulation_points()，用于查找无向PyGraph的连接点。连接点或切割顶点是指移除后会增加图中连体分量数量的任何节点。例如：

import rustworkx
from rustworkx.visualization import mpl_draw

graph = rustworkx.PyGraph()
graph.extend_from_edge_list([
    (0, 1), (1, 2), (0, 2), (1, 3)
])
points = rustworkx.articulation_points(graph)

colors = ['black'] * len(graph)
for node in points:
    colors[node] = 'blue'

mpl_draw(graph, node_color=colors)

新增一个函数 biconnected_components()，用于返回一个无向 PyGraph 的双连通分量。双连通分量是一个在移除节点后仍保持连通的最大子图。例如：

import rustworkx
from rustworkx.visualization import mpl_draw

graph = rustworkx.PyGraph()
graph .extend_from_edge_list([
    (0, 1), (1, 2), (0, 2), (1, 3), (2, 4)
])
components = rustworkx.biconnected_components(graph)

COLORS = ["blue", "red", "orange"]
edge_colors = []
for (u, v) in graph.edge_list():
  if (u, v) in components:
      comp = components[(u, v)]
  else:
      comp = components[(v, u)]
  edge_colors += [COLORS[comp]] 

mpl_draw(graph, node_color='black', node_size=150,
        edge_color

Added a new function chain_decomposition() that finds a chain decomposition of an undirected PyGraph. A chain decomposition is a set of cycles or paths derived from the set of fundamental cycles of a depth-first tree. It’s defined in https://doi.org/10.1016/j.ipl.2013.01.016 For example:

import rustworkx
from rustworkx.visualization import mpl_draw

graph = rustworkx.PyGraph()
graph.extend_from_edge_list([
    (0, 1), (0, 2), (1, 2), (2, 3),
    (3, 4), (3, 5), (4, 5),
])
chains = rustworkx.chain_decomposition(graph)

def color_edges(graph, chains): 
    COLORS = ['blue', 'red']

    edges_in_chain = {}
    for idx, chain in enumerate(chains):
        for edge in chain:
            edge = tuple(sorted(edge))
            edges_in_chain[edge] = COLORS[idx]
        
    edge_colors = []
    for edge in graph.edge_list():
        edge = tuple(sorted(edge))
        edge_colors += [edges_in_chain.get(edge, 'black')]

    return edge_colors

mpl_draw(graph, node_color='black', node_size=150,
        edge_color=color_edges(graph, chains))

新增构造函数方法 rustworkx.PyDiGraph.from_complex_adjacency_matrix() 和 rustworkx.PyGraph.from_complex_adjacency_matrix()，用于从具有复数数据类型 complex dtype 的 numpy 邻接矩阵分别创建 PyDiGraph 和 PyGraph。例如：

import numpy as np

import rustworkx
from rustworkx.visualization import mpl_draw

adj_matrix = np.array([
    [0, 0 - 1j, 0, 1 + 2j],
    [0 - 1j, 0, 1 + 0j, 0],
    [0, 1 + 0j, 0, 2 + 0.5j],
    [1 + 2j, 0, 2 + 0.5j, 0]
], dtype=complex)
graph = rustworkx.PyDiGraph.from_complex_adjacency_matrix(adj_matrix)

mpl_draw（graph, with_labels=True, edge_labels=str）

增加了 connected_components() 用于查找无向 PyGraph 图中的连通分量。

添加 number_connected_components() 用于查找无向图 PyGraph 中的连接组件数量。

增加 node_connected_component() 用于查找节点在无向PyGraph图中所属的连通分量。

添加 is_connected() 用于检查无向 PyGraph 图是否连通。

新增图方法 rustworkx.PyDiGraph.contract_nodes() 和 rustworkx.PyGraph.contract_nodes()。这些方法可用于将一组图节点替换为单个等效的新节点。被替换集合的入边和出边分别成为新节点的入边和出边。在多图中，默认保留所有边。对于所有图类型，可通过用户指定的Python可调用项可选地合并平行边。rustworkx.PyDiGraph.contract_nodes() 支持循环检查/防护，以防止收缩引入循环。在以下示例中，两个节点被收缩为单个新节点。首先，创建一个新图：
import rustworkx from rustworkx.visualization import mpl_draw graph = rustworkx.generators.directed_path_graph(5) mpl_draw(graph, with_labels=True)
执行收缩：
graph.contract_nodes([2, 3], "abc") mpl_draw(graph, with_labels=True)

增加了一个新的dfs_search()（及其特定类型变体graph_dfs_search()和digraph_dfs_search()），它以深度优先方式遍历图并在指定点发出事件。事件通过适当的回调函数由继承DFSVisitor的访问者对象处理。例如：

import rustworkx
from rustworkx.visit import DFSVisitor

class TreeEdgesRecorder(DFSVisitor):

    def __init__(self):
        self.edges = []

    def tree_edge(self, edge):
        self.edges.append(edge)

graph = rustworkx.PyGraph()
graph.extend_from_edge_list([(1, 3), (0, 1), (2. 1), (0, 2)])
vis = TreeEdgesRecorder()
rustworkx.dfs_search(graph, [0], vis)
print('Tree edges:', vis.edges)

Tree edges: [(0, 2, None), (2, 1, None), (1, 3, None)]

Added a new dijkstra_search() (and it’s per type variants graph_dijkstra_search() and digraph_dijkstra_search()) that traverses the graph using dijkstra algorithm and emits events at specified points. The events are handled by a visitor object that subclasses DijkstraVisitor through the appropriate callback functions. For example:

import rustworkx
from rustworkx.visit import DijkstraVisitor


class DijkstraTreeEdgesRecorder(rustworkx.visit.DijkstraVisitor):

    def __init__(self):
        self.edges = []
        self.parents = dict()

    def discover_vertex(self, v, _):
        u = self.parents.get(v, None)
        if u is not None:
            self.edges.append((u, v))

    def edge_relaxed(self, edge):
        u, v, _ = edge
        self.parents[v] = u

graph = rustworkx.PyGraph()
graph.extend_from_weighted_edge_list([(1, 3, 1), (0, 1, 10), (2, 1, 1), (0, 2, 1)])
vis = DijkstraTreeEdgesRecorder()
rustworkx.graph_dijkstra_search(graph, [0], float, vis)
print('Tree edges:', vis.edges)

Tree edges: [(0, 2), (2, 1), (1, 3)]

为PyGraph和PyDiGraph类新增了一个方法incident_edges()。此方法返回与指定节点相连的边索引列表。

为 PyGraph 和 PyDiGraph 类新增了一个方法 incident_edge_index_map()。该方法返回一个边索引映射，针对连接到指定节点的边，映射到该边索引的端点和权重元组。例如：

import rustworkx
graph = rustworkx.PyGraph()
graph . extend_from_weighted_edge_list ([(0, 1, "A"), (0, 2, "B")])
print (graph.incident_edge_index_map(0))

EdgeIndexMap{1: (0, 2, B), 0: (0, 1, A)}

为 PyGraph 和 PyDiGraph 类添加了一个新方法 get_edge_data_by_index()。该方法通过边的索引返回图中该边的数据负载。

为 PyGraph 和 PyDiGraph 类添加了新方法 get_edge_endpoints_by_index()。该方法根据索引返回图中某条边的端点元组。

为 PyGraph 类新增了两个方法：out_edges() 和 in_edges()。这些方法是 PyDiGraph 方法中 out_edges() 和 in_edges() 的对偶，并返回节点的关联边的 WeightedEdgeList。

steiner_tree() 实现所使用的算法已被替换为一个更快的算法，其依据为： https://doi.org/10.1016/0020-0190(88)90066-X。这个新的实现达到了与先前算法相同的近似比率，因此在功能上应该没有变化。

添加了一个新函数 full_rary_tree()，用于支持生成具有\(n\)个节点的完整\(r\)叉树。例如：

import rustworkx.generators
from rustworkx.visualization import mpl_draw

graph = rustworkx.generators.full_rary_tree(3, 5)
mpl_draw(graph)

新增了一个函数 lollipop_graph()，增加了对生成棒棒糖图的支持。例如：

import rustworkx.generators
from rustworkx.visualization import mpl_draw

graph = rustworkx.generators.lollipop_graph(4, 3)
mpl_draw(graph)

添加了一个新类，TopologicalSorter，它提供了对有向图进行拓扑排序的功能。它能够在节点就绪时处理节点，然后将它们标记为已完成，从而释放更多节点。

betweenness_centrality()（以及它的按类型变体 graph_betweenness_centrality()和 digraph_betweenness_centrality()）现在已经支持多线程。对于较大的图，这会显著提升该函数的运行时性能。默认情况下，任何节点数少于50的图仍将在单个线程中执行，而更大的图将并行执行。可以使用新的parallel_threshold关键字参数来调整开始并行运行的图的尺寸。此外，环境变量RAYON_NUM_THREADS可以用于设置在并行运行时将使用多少个线程。默认情况下，它将使用本地系统中每个CPU一个线程。

新增了一个函数 generalized_petersen_graph()，支持生成广义 Petersen 图。例如：

import rustworkx.generators
from rustworkx.visualization import mpl_draw

graph = rustworkx.generators.generalized_petersen_graph(5, 2)
layout = rustworkx.shell_layout(graph, nlist=[[0, 1, 2, 3, 4], [6, 7, 8, 9, 5]])
mpl_draw（graph, pos=layout)

添加了一个新的工作空间crate， rustworkx-core作为rustworkx的一部分。这是一个独立的Rust库，构建在petgraph之上，提供rustworkx所需的通用算法和图功能。这个新crate仅暴露了一个通用接口，适用于任何petgraph图，并且可以被任何下游Rust项目使用，这些项目想要rustworkx提供的额外功能，但不需要Python。

另外值得注意的是，由于这是rustworkx-core的首次发布，后续版本中可能会有破坏性的API变更。虽然我们会尝试遵循标准的弃用和稳定性策略，但由于我们不一定完全承诺当前的API，并且除了rustworkx之外还没有其他用户，可能存在需要破坏性变更的漏洞或问题。

新增加了一个键参参数keep_attributes到NetworkX图转换函数networkx_converter()中。当该参数设为True时，来自输入NetworkX图的节点属性将被保留。输出rustworkx图的数据载荷将是一个包含属性的字典，其中额外含有一个"__networkx_node__"键来存放来自NetworkX的节点。例如：

import networkx as nx
import rustworkx as rx

g = nx.Graph()
g .add_nodes_from([
  ("A", {"color": "turquoise", "size": "extra large"}),
  ("B", {"color": "fuchsia", "size": "tiny"}),
])
g .add_edge("A", "B")
rx_graph = rx .networkx_converter (g, keep_attributes = True )
print (rx_graph .nodes ()
print (rx_graph .weighted_edge_list ()

将会输出：

[{'color': 'turquoise', 'size': 'extra large', '__networkx_node__': 'A'}, {'color': 'fuchsia', 'size': 'tiny', '__networkx_node__': 'B'}]
WeightedEdgeList[(0, 1, {})]

更新说明#

关于 unweighted_average_shortest_path_length() 函数处理非连通图的默认行为已被更改。之前，非连通节点对被假定具有零距离，这可以说是错误的/非预期的行为。为了使其更符合用户期望，这已更改为一个无限值。此外，添加了一个额外的关键字参数 disconnected，如果设置为 True，则平均仅针对连通的节点对进行计算。默认情况下，它设置为 False。如果希望保留先前将非连通节点对视为距离为零的行为，可以使用 rustworkx 的其他 API 来重现，例如：
```
import rustworkx

graph = rustworkx.undirected_gnm_random_graph(20, 10, seed=42)
n = len(graph)
d_mat = rustworkx.distance_matrix(graph, null_value=0.0)
avg_shortest_path = d_mat.sum() / (n * (n - 1.0))
```

graphviz_draw() 的可选依赖项（如 graphviz 可选扩展的文档所述，可通过 pip install rustworkx[graphviz] 安装）不再需要 pydot 库。现在仅需 pillow 库即可使用 graphviz 生成可视化图像。

Bug 修复 #

Fixed an issue with the binomial_tree_graph() and directed_binomial_tree_graph() generator functions in rustworkx.generators where passing an order value >= 60 would cause an overflow and raise a PanicException caused by the internal Rust panic when overflowing or exceeding the max Vec size. Instead the function will raise an OverflowError and indicate the specified order is too large. Fixed #457

修复了一个问题，distance_matrix() 和 k_shortest_path_lengths() 之前会在输入图的节点索引中存在空洞时发生panic。

修正了rustworkx.PyGraph.degree()方法在运行具有自循环的节点时的问题。之前，该方法对自循环节点的度会增加一而不是二。修复#517。

修复了 dfs_edges() 函数中的 source 参数，使其默认值为 None，与文档描述一致。先前，source 参数被错误地设为必需且没有默认值。已修复 #515。

修复了union()函数中的一个疏忽，即忽略了用户为merge_nodes和merge_edges参数自定义的值。

修复了在最短路径算法函数中的一个疏忽，例如： dijkstra_shortest_paths(), dijkstra_shortest_path_lengths(), all_pairs_dijkstra_path_lengths(), all_pairs_dijkstra_shortest_paths(), astar_shortest_path(), 以及 k_shortest_path_lengths()，这些函数之前会错误地接受具有负值或NaN值的边权重。修复了#525。

修复了 heavy_hex_graph(), directed_heavy_hex_graph(), heavy_square_graph(), 和 directed_heavy_square_graph() 生成器函数的问题。当输入参数 d 设置为1时，这些函数之前会抛出 pyo3_runtime.PanicException 异常，而不是返回预期的图（单节点）。已修复 #452

0.10.2#

预备知识

此版本是一个bug修复版本,解决了自0.10.1版本以来发现的一些问题。本版本中的修复主要在vf2实现中,最重要的是修复了vf2_mapping()对于空输入图的输出结果,以及vf2_mapping(), is_isomorphic(), 和is_subgraph_isomorphic()对于具有平行边的图的输出结果。

新功能#

新增一个函数 graph_union()，用于返回两个 PyGraph 对象的并集。这相当于 digraph_union() 函数的无向图版本，用于 PyGraph 而非 PyDiGraph。同时新增一个统一函数 union()，同时支持 PyDiGraph 和 PyGraph。例如：

import rustworkx
from rustworkx.visualization import mpl_draw

first = rustworkx.generators.path_graph(3, weights=["a_0", "node", "a_1"])
second = rustworkx.generators.cycle_graph(3, weights=["node", "b_0", "b_1"])
graph = rustworkx.graph_union(first, second, merge_nodes=True)
mpl_draw(graph)

digraph_union() 的关键字参数 merge_nodes 和 merge_edges 现在是可选择性的，默认设置为 False。

新增一个 find_node_by_weight() 方法，用于通过指定权重查找节点的索引。

Bug 修复 #

修复了adj()的输出，使其包含与指定节点之间存在边的邻居节点，包括双向连接。之前，只包含出站节点。

之前，当参数 merge_edges 设置为 true 时，digraph_union() 会错误地保留或删除边缘。这个问题已经修复，如果第二个图中的某条边的两个端点都被合并到第一个图的节点中，并且这些节点已经共享了一条具有相同权重数据的边，那么该边将被跳过。修复了 #432

修复了当输入图存在平行边时，is_subgraph_isomorphic() 的输出结果。修复了 #429

修复了当输入图具有平行边且指定了edge_matcher时，is_isomorphic()的输出结果。已修复 #429

通过利用条目数量随图中边数线性增长的哈希映射，而不是构建完整的邻接矩阵，来减少VF2图同构算法的内存需求。修复了#367

此前，比较两个空图对象时，vf2_mapping()函数会错误地返回空迭代器。这个问题已经修复，现在会返回包含唯一有效映射（即空映射）的迭代器。

0.10.1#

预备知识

这是一个错误修复版本，修复了先前0.10.0版本中引入的一个回归问题。在0.10.0版本中，当比较两个空图对象时，is_isomorphic()函数会错误地返回False。

0.10.0#

预备知识

本次版本包含众多新功能和错误修复。本版本的亮点包括一系列新的算法函数，如steiner_tree()和betweenness_centrality()；对同构函数的改进，例如新增vf2_mapping()以获取两个图之间的同构映射；以及对图对象操作的改进，比如rustworkx.PyDiGraph.substitute_node_with_subgraph()用于将节点替换为子图。

新功能#

添加了一个新算法函数， rustworkx.unweighted_average_shortest_path_length() 用于计算 PyDiGraph 或 PyGraph 对象的平均最短路径长度。平均最短路径长度的定义为

\[a =\sum_{s,t \in V} \frac{d(s, t)}{n(n-1)}\]

其中 \(V\) 表示图中的节点集合，\(d(s, t)\) 是从 \(s\) 到 \(t\) 的最短路径长度，\(n\) 是图中的节点数量。

新增了一个新功能, betweenness_centrality() 用于计算 PyGraph 或 PyDiGraph 对象中所有节点的中介中心性。该函数使用的算法基于:

Ulrik Brandes, "一种更快的中介中心性算法"。社会数学杂志 25(2):163-177, 2001. DOI: 10.1080/0022250X.2001.9990249

节点 \(v\) 的中介中心性是所有节点对最短路径中经过 \(v\) 的路径所占比例的总和

\[c_B(v) =\sum_{s,t \in V} \frac{\sigma(s, t|v)}{\sigma(s, t)}\]

其中 \(V\) 是节点集合, \(\sigma(s, t)\) 是最短 \((s, t)\) 路径数，而 \(\sigma(s, t|v)\) 是经过某个不是 \(s, t\) 的节点 \(v\) 的那些路径数。如果 \(s = t\), \(\sigma(s, t) = 1\), 且如果 \(v \in {s, t}\), \(\sigma(s, t|v) = 0\)

例如，计算一个5x5网格图中所有节点的中介中心性，并用其在图可视化中为节点着色：
import rustworkx from rustworkx.visualization import mpl_draw graph = rustworkx.generators.grid_graph(5, 5) btw = rustworkx.betweenness_centrality(graph) # 在图可视化中使用中介中心性为节点着色 colors = [] for i in range(len(graph)): colors .append(btw[i]) mpl_draw(graph, node_color=colors)

新增了两个算法函数， dag_weighted_longest_path_length()和 dag_weighted_longest_path()，用于在无环的PyDiGraph对象中查找最长路径及其长度。这些新函数基本上等同于 dag_longest_path()和 dag_longest_path_length()，但有两个关键区别。首先，对于dag_weighted_longest_path_length()和 dag_weighted_longest_path()，weight_fn参数是必需的，而在dag_longest_path()和 dag_longest_path_length()中是可选的。其次， dag_weighted_longest_path()和 dag_weighted_longest_path_length()处理float 类型的权重（dag_weighted_longest_path_length()返回一个浮点数，且两者的weight_fn回调函数预期返回float类型），而dag_longest_path()和 dag_longest_path_length()处理无符号int类型。

为 PyDiGraph 和 PyGraph 新增了一个方法 edge_subgraph() (edge_subgraph()), 用于从给定图对象中获取边诱导子图。

新增了用于构建重型六边形图的新生成器函数： rustworkx.generators.heavy_hex_graph() 和 rustworkx.generators.directed_heavy_hex_graph()，该图源自： https://journals.aps.org/prx/abstract/10.1103/PhysRevX.10.011022 例如：
import rustworkx from rustworkx.visualization import mpl_draw graph = rustworkx.generators.directed_heavy_hex_graph(3) mpl_draw(graph)

新增了生成器函数， rustworkx.generators.heavy_square_graph() 和 rustworkx.generators.directed_heavy_square_graph()，用于生成来自以下的重方图: https://journals.aps.org/prx/abstract/10.1103/PhysRevX.10.011022 例如:
import rustworkx from rustworkx.visualization import mpl_draw graph = rustworkx.generators.directed_heavy_square_graph(3) mpl_draw（graph）

新增了一个名为 labels 的 kwarg 参数，已添加到 rustworkx.PyDiGraph.read_edge_list() 和 rustworkx.PyGraph.read_edge_list() 的构造方法中。当此 kwarg 被设置为 True 时，边列表文件中的一行前两个元素将被当作字符串标签而不是整型节点索引来处理，用于唯一标识一个节点。例如:

import tempfile

import rustworkx
from rustworkx.visualization import mpl_draw

with tempfile.NamedTemporaryFile("wt") as fd:
  fd.write('a b first_edge\n')
  fd.write('b c second_edge\n')
  fd.flush()
  graph = rustworkx.PyDiGraph.read_edge_list(fd.name, labels=True)

mpl_draw(graph, with_labels=True, labels=str, edge_labels=str)

adjacency_matrix() 函数新增了一个关键字参数 null_value，用于调整输出矩阵中表示边不存在的值。该参数可设置为任意浮点数值，若未指定则仍使用默认值 0.0。例如：

import numpy as np
import rustworkx

graph = rustworkx.generators.cycle_graph(4)
distance_matrix = rustworkx.adjacency_matrix(graph, null_value=np.inf)
print(distance_matrix)

[[inf  1. inf  1.]
 [ 1. inf  1. inf]
 [inf  1. inf  1.]
 [ 1. inf  1. inf]]

distance_matrix() 函数新增了一个关键字参数 null_value，用于调整输出矩阵中表示路径不存在时使用的值。该参数可设置为任意浮点值，若未指定，则仍默认使用 0.0。例如：

import numpy as np
import rustworkx

graph = rustworkx.generators.cycle_graph(4)
graph.add_node(None)
graph.add_node(None)
distance_matrix = rustworkx.distance_matrix(graph, null_value=np.inf)
print(distance_matrix)

[[ 0.  1.  2.  1. inf inf]
 [ 1.  0.  1.  2. inf inf]
 [ 2.  1.  0.  1. inf inf]
 [ 1.  2.  1.  0. inf inf]
 [inf inf inf inf  0. inf]
 [inf inf inf inf inf  0.]]

一个新方法 substitute_node_with_subgraph(), 添加到 PyDiGraph 类中。此方法用于将 PyDiGraph 对象中的节点替换为另一个 PyDiGraph 对象。例如，首先创建一个新图：

import rustworkx
from rustworkx.visualization import mpl_draw

original_graph = rustworkx.generators.directed_path_graph(5)
mpl_draw(original_graph, with_labels=True)

然后创建另一个图以替换节点：

other_graph = rustworkx.generators.directed_star_graph(25)
mpl_draw(other_graph)

最后用第二个图替换原图中的节点：

def edge_map_fn(_source, _target, _weight):
    return 0

node_mapping = original_graph.substitute_node_with_subgraph(2, other_graph, edge_map_fn)
print(node_mapping)
mpl_draw(original_graph, with_labels=True)

NodeMap{0: 5, 1: 6, 2: 7, 3: 8, 4: 9, 5: 10, 6: 11, 7: 12, 8: 13, 9: 14, 10: 15, 11: 16, 12: 17, 13: 18, 14: 19, 15: 20, 16: 21, 17: 22, 18: 23, 19: 24, 20: 25, 21: 26, 22: 27, 23: 28, 24: 29}

为 PyGraph 类新增了一个名为 to_directed() 的方法。该方法用于从无向的 PyGraph 对象生成一个新的有向图对象 rustworkx.PyDiGraph。输出的 rustworkx.PyDiGraph 对象将为原始 PyGraph 对象中的每条边生成一对双向边。

为 rustworkx.PyDiGraph.from_adjacency_matrix() 和 rustworkx.PyGraph.from_adjacency_matrix() 添加了一个新的关键字参数 null_value，用于可选地改变矩阵中的空值，该空值被视为没有边的存在。默认情况下使用 0.0。例如：

import numpy as np  
import rustworkx  
from rustworkx.visualization import mpl_draw  

matrix = np.array([[np.nan, 1, 1], [1, np.nan, 1], [1, 1, 0]], dtype=np.float64)  
graph = rustworkx.PyDiGraph.from_adjacency_matrix(matrix, null_value=np.nan)  
mpl_draw(graph, with_labels=True, edge_labels=str)  

floyd_warshall() 函数进行了完全重构，目前除了已经支持的 PyDiGraph 对象外，还能处理 PyGraph 对象。它新增了一个关键字参数 weight_fn，用于支持自定义边权重，同时还实现了并行执行。

添加了两个新函数，graph_floyd_warshall() 和 digraph_floyd_warshall()，它们是现有 floyd_warshall() 的类型化版本。

两个新的关键字参数，multigraph和weight_combo_fn，被添加到了 rustworkx.PyDiGraph.to_undirected()方法中。这两个选项可用于将平行边压缩为输出图中的单一边。通过设置multigraph为True，任何平行边将被压缩到输出的PyGraph中的单一边。 weight_combo_fn参数用于控制如何压缩平行边。如果未指定，将使用具有最大边索引的边的权重/数据负载。如果指定了weight_combo_fn，它将被传递图中所有平行边的权重对象，返回的对象将被用作压缩边的权重。例如：
import rustworkx from rustworkx.visualization import mpl_draw graph = rustworkx.PyDiGraph() graph.extend_from_weighted_edge_list([ (0, 1, 25), (1, 0, 10), (1, 2, 10), (2, 1, 100), (2, 3, 50), (3, 2, 40), ]) undirected_graph = graph.to_undirected( multigraph=False, weight_combo_fn=max ) mpl_draw(undirected_graph, with_labels=True, edge_labels=str)

新增了一个关键字参数 induced 到 is_subgraph_isomorphic() 中。如果设置为 True，该函数将检查第二个图是否与第一个图的节点诱导子图同构。如果设置为 False，它将检查第二个图是否与第一个图的子图同构。默认情况下，此参数设置为 True。

新增了一个新函数，num_shortest_paths_unweighted() （及其特定类型变体 digraph_num_shortest_paths_unweighted() 和 graph_num_shortest_paths_unweighted()），用于获取图中从给定节点到所有其他节点（存在路径的情况下）未加权最短路径的计数。

为 PyDiGraph 和 PyGraph (has_parallel_edges()) 类新增了一个方法 has_parallel_edges(). 该方法返回 True 如果图中存在平行边，否则返回 False。

新增了一个函数 metric_closure()，用于生成给定图的度量闭包。该函数在通过 Kou、Markowsky & Berman (1981) 的算法计算 Steiner 树时使用，论文题为“A fast algorithm for Steiner trees”。https://link.springer.com/article/10.1007/BF00288961

新增了一个新函数 steiner_tree()，该函数用于通过以下算法生成最小Steiner树的近似解： Kou, Markowsky & Berman (1981)的论文《一种快速的Steiner树算法》。 https://link.springer.com/article/10.1007/BF00288961

新增了一个函数 rustworkx.vf2_mapping()，它将使用 vf2 同构算法（该算法也用于 rustworkx.is_isomorphic() 和 rustworkx.is_subgraph_isomorphic()）返回一个迭代器，用于遍历两个图之间所有有效的同构映射。例如：

import rustworkx

graph = rustworkx.generators.directed_grid_graph(10, 10)
other_graph = rustworkx.generators.directed_grid_graph(4, 4)
vf2 = rustworkx.vf2_mapping(graph, other_graph, subgraph=True)
try:
  mapping = next(vf2)
  print(mapping)
except StopIteration:
  pass

NodeMap{0: 0, 1: 1, 2: 2, 3: 3, 10: 4, 11: 5, 12: 6, 13: 7, 20: 8, 21: 9, 22: 10, 23: 11, 30: 12, 31: 13, 32: 14, 33: 15}

新增了一个关键字参数 call_limit 到 rustworkx.is_isomorphic() 和 rustworkx.is_subgraph_isomorphic()，该参数用于设置 VF2 算法在搜索解时访问状态数量的上限。如果超过这个限制，算法将停止并返回 false。

为函数 rustworkx.dag_longest_path() 和 rustworkx.dag_longest_path_length() 添加了一个新的参数 weight_fn。该参数用于设定一个可调用的权重函数，当函数遍历图时会调用它来动态调整边的权重。例如：

import retwork as rx

dag = rx.PyDiGraph()
dag .extend_from_weighted_edge_list (
      [
          (0, 1, 1),
          (0, 3, 1),
          (3, 4, 1),
          (4, 5, 1),
          (1, 2, 1),
          (0, 1, 3),
      ]
  )
  longest_path = rx . dag_longest_path (dag, lambda _, __, weight: weight)
  path_length = rx . dag_longest_path_length (dag, lambda_, __, weight: weight)
  assert [0, 1, 2] == longest_path
  assert 4 == weight

更新说明#

floyd_warshall() 函数不再返回 dict，而是会返回一个 rustworkx.AllPairsPathLengthMapping 对象。这个新的返回类型在构建时更加高效，并且以只读方式实现了 Python 映射协议。除非进行了显式类型检查或对输出进行了修改，这个变更基本上应该是兼容的。

Bug 修复 #

rustworkx.PyDiGraph.from_adjacency_matrix() 和 rustworkx.PyGraph.from_adjacency_matrix() 方法中对负权重的支持已修复。此前，如果使用了负权重，它会被错误地视为空值并且不会将边添加到图中。现已修正此问题，输入矩阵中的负值现在会被视为带有负权重的边。例如：
import numpy as np import rustworkx from rustworkx.visualization import mpl_draw matrix = np.array([[0, -1, -1], [1

修复了Dijkstra路径函数的一个问题：
在节点之间存在多条路径且指定了边权重回调函数的情况下，返回的路径可能不正确。已修复 #387

修复了在图形节点索引中存在空洞情况下 number_weakly_connected_components() 的输出结果。

此前，由 rustworkx.generators.directed_hexagonal_lattice_graph() 和 rustworkx.generators.hexagonal_lattice_graph() 创建的图形在节点索引中存在空白。现通过生成具有连续节点索引的图形已修复此问题。修复 #373

由graph_greedy_color()返回的输出dict的迭代顺序以前不是确定性的，多次使用相同输入执行会返回具有不同插入顺序的相同字典，这会导致不同的迭代顺序。此问题已修复，以使输出字典的迭代顺序现在是确定性的。修复 #347

0.9.0#

预备知识

此版本是一个新特性发布，包含了大量新功能和错误修复。本版本的亮点是引入了 retwork.visualization 模块，其中包含一个基于 matplotlib 的绘图器 (mpl_draw()) 和一个基于 graphviz 的绘图器 (graphviz_draw())，以及布局函数如 spring_layout() 用于在可视化中生成布局。此外，rustworkx.generators 中的生成器函数已扩展以包含新的图生成器，并添加了许多新的算法函数。

新功能#

新增生成器函数, rustworkx.generators.binomial_tree_graph() 和 rustworkx.generators.directed_binomial_tree_graph(), 用于构建二项树图。例如：

import rustworkx
from rustworkx.visualization import mpl_draw

graph = rustworkx.generators.binomial_tree_graph(4)
mpl_draw(graph)

import rustworkx
from rustworkx.visualization import mpl_draw

graph = rustworkx.generators.directed_binomial_tree_graph(4)
mpl_draw(graph)

新增了一个方法 copy()，应用于 PyDiGraph 和 PyGraph (copy()) 类中。该方法将返回图对象的一个浅拷贝。

添加一个新的函数 core_number()，用于计算 PyGraph 或 PyDiGraph 中每个节点的核心数，在有向图中，度数的计算方式为入度加出度。

新增了一个方法 edge_indices() 至 PyDiGraph 与 PyGraph (edge_indices())，该方法将返回图对象中每条边的边索引列表。

新增了一个自定义返回类型 EdgeIndices，该类型由 rustworkx.PyDiGraph.edge_indices 和 rustworkx.PyGraph.edge_indices 返回。它等同于一个表示边索引列表的只读整数列表。

为 PyDiGraph 和 PyGraph 新增了一个方法 num_nodes() （num_nodes()），用于返回图中的节点数量。

新增了一个方法，num_edges()，到PyDiGraph和PyGraph（num_edges()）中，用于返回图中的边数。

新增了一个函数 rustworkx.networkx_converter()。该函数接收一个networkx的Graph对象，并会生成一个等效的PyGraph或PyDiGraph 对象。虽然此函数是为了方便同时使用rustworkx和networkx的用户提供的，但networkx不会被添加为rustworkx的依赖项 (这使得无法提供rustworkx->networkx的转换器，具体示例代码请参阅Converting from a networkx graph了解如何自行构建)。

新增了random_geometric_graph()函数，可用于生成随机几何图。例如：

import rustworkx
from rustworkx.visualization import mpl_draw


graph = rustworkx.random_geometric_graph(8, .95, 5)
mpl_draw(graph)

Added a new layout function, rustworkx.random_layout() (and it’s equivalent per type variants rustworkx.graph_random_layout() and rustworkx.diraph_random_layout()) to generate a random layout which can be used for visualizations. For example:

import rustworkx
from rustworkx.visualization import mpl_draw

graph = rustworkx.generators.directed_grid_graph(5, 5)
layout = rustworkx.random_layout(graph)
mpl_draw(graph, pos=layout)

or with the graphviz_draw() function:

import rustworkx
from rustworkx.visualization import graphviz_draw

graph = rustworkx.generators.directed_grid_graph(5, 5)
layout = rustworkx.random_layout(graph)
for i in range(25):
  graph[i] = i

def node_attr_fn(node):
    point = layout[node]
    return {
        "shape": "circle",
        "pos": '"%s,%s!"' % (point[0], point[1]),
        "fillcolor": "yellow",
        "style": "filled",
        "fixedsize": "true"
    }

graphviz_draw(graph, node_attr_fn=node_attr_fn, method='fdp')

新增了一个自定义返回类 rustworkx.Pos2DMapping。该类将由布局函数返回，并可完全替代如下形式的不可变只读字典：
```
{1: [0.1, 0.5]}
```
其中键为节点索引，值为一个包含两个元素的序列，表示该节点的位置。

新增了一个新函数 is_subgraph_isomorphic()，用于判断两个相同类型（无论是 PyGraph 还是 PyDiGraph）的图是否为导出子图同构。

新增了一个函数 transitivity()，用于计算 PyGraph 或 PyDiGraph 对象的传递系数。

新增了一个函数 complement() 用于计算 PyGraph 或 PyDiGraph 的图补。

两个新返回类型 PathMapping 和 PathLengthMapping。这些类从先前返回路径字典或路径长度字典的函数中返回。它们都实现了Python映射协议，并可作为只读字典使用。

已新增函数，用于计算图对象中所有节点的最短路径及最短路径长度：

为PyDiGraph和PyGraph 新增了一个名为edge_index_map()的方法，该方法将返回一个只读的边索引映射，针对图对象中的每条边，映射形式为 (source_node_index, target_node_index, weight/data payload)元组。

新增了一个新的自定义返回类型 EdgeIndexMap，它由 rustworkx.PyDiGraph.edge_index_map() 和 rustworkx.PyGraph.edge_index_map() 返回。它相当于一个只读的字典/映射，表示边索引到边元组的映射。

is_isomorphic() 函数已经扩展，现在除了已支持的 PyDiGraph 之外，它也可以接收 PyGraph。

is_isomorphic() 函数现在有两个新的可选 kwargs node_matcher 和 edge_matcher，可用于指定用于比较节点和边数据载荷的函数。

is_isomorphic_node_match() 函数已扩展功能，现在除了原先支持的 PyDiGraph 外，还能接受 PyGraph 作为输入。

新增生成器函数， rustworkx.generators.directed_hexagonal_lattice_graph() 和 rustworkx.generators.hexagonal_lattice_graph()，用于构建六边形晶格图。例如：

import rustworkx
from rustworkx.visualization import mpl_draw

graph = rustworkx.generators.directed_hexagonal_lattice_graph(3, 3)
mpl_draw(graph)

import rustworkx
from rustworkx.visualization import mpl_draw

graph = rustworkx.generators.hexagonal_lattice_graph(3, 3)
mpl_draw(graph)

新增了两个新方法，find_successors_by_edge() 和find_predecessors_by_edge()，到 PyDiGraph中。这些方法能够高效检索图中与节点相连、且边符合过滤函数条件的邻居节点。

is_isomorphic() 和 is_isomorphic_node_match() 函数有了一个新的关键字参数, id_order ，用于调整所用的节点匹配顺序。如果设置 id_order=False，则使用的匹配顺序是 VF2++ 论文中提出的启发式匹配顺序。如果想要保持基于节点id的顺序，可以设置 id_order=True，这是默认行为。

新增函数 minimum_spanning_tree()，用于计算 PyGraph 对象的最小生成树，并将最小生成树作为新的 PyGraph 对象返回。

新增了一个函数minimum_spanning_edges()，用于计算 PyGraph对象的最小生成树并返回图的MST加权边列表的WeightedEdgeList。

已新增一个名为 rustworkx.visualization 的模块。该模块将包含用于可视化 rustworkx 图的各种功能。

新增了一个新的可视化函数 rustworkx.visualization.mpl_drawer()，用于通过 Matplotlib 可视化图。此函数需要安装 matplotlib，它不是 rustworkx 的依赖项。要安装 matplotlib，你可以使用 pip install matplotlib 或在安装 rustworkx 时使用 pip install 'rustworkx[mpl]'。此函数可以接受任何 rustworkx 图对象，一个 PyGraph 或 PyDiGraph 并使用各种选项来调整输出以进行可视化。例如，一个没有任何标签的基础图如下：
import rustworkx from rustworkx.visualization import mpl_draw graph = rustworkx.generators.grid_graph(4, 6) mpl_draw(graph)
或者更改颜色：
import rustworkx from rustworkx.visualization import mpl_draw graph = rustworkx.generators.grid_graph(4, 6) mpl_draw(graph, node_color='r', edge_color='#00FFFF')
有关完整的选项列表，请参阅函数文档。

新增了一个关键字参数multigraph到PyDiGraph生成器函数中:
这可用于设置生成的 PyDiGraph对象是否为多重图（即设置是否可以添加平行边）。默认情况下，此值设置为 True。

新增了一个基于 Graphviz 的绘图功能， graphviz_draw()，该功能位于 rustworkx.visualization 模块中。此功能要求 Graphviz 已本地安装，并新增了两个可选依赖项： pydot（用于调用 Graphviz）和 Pillow（用于处理生成的图像文件）。可以通过 pip install pydot pillow` 或安装 rustworkx 时执行 ``pip install 'rustworkx[graphviz]' 来安装这些可选的依赖项。此功能封装了 to_dot() 方法来生成图的 dot 表达形式，并会调用 Graphviz 来生成图的可视化效果。例如：
import rustworkx from rustworkx.visualization import graphviz_draw def node_attr(node): if node == 0: return {'color': 'yellow', 'fillcolor': 'yellow', 'style': 'filled'} if node % 2: return {'color': 'blue', 'fillcolor': 'blue', 'style': 'filled'} else: return {'color': 'red', 'fillcolor': 'red', 'style': 'filled'} graph = rustworkx.generators.directed_star_graph(weights=<list(range(32))) graphviz_draw(graph, node_attr_fn=node_attr, method='sfdp')

添加了四种简单的布局函数：

bipartite_layout()

circular_layout()

shell_layout()

spiral_layout()

这些可用于调整可视化中所使用的布局，例如：

import rustworkx
from rustworkx.visualization import mpl_draw

graph = rustworkx.generators.path_graph(weights=list(range(24)))
layout = rustworkx.bipartite_layout(graph, set(range(12)))
mpl_draw(graph, pos=layout)

import rustworkx
from rustworkx.visualization import mpl_draw

graph = rustworkx.generators.path_graph(weights=list(range(24)))
layout = rustworkx.circular_layout(graph)
mpl_draw(graph, pos=layout)

import rustworkx
from rustworkx.visualization import mpl_draw

graph = rustworkx.generators.star_graph(25)
layout = rustworkx.shell_layout(graph)
mpl_draw(graph, pos=layout)

import rustworkx
from rustworkx.visualization import mpl_draw

graph = rustworkx.generators.path_graph(weights=list(range(24)))
layout = rustworkx.spiral_layout(graph)
mpl_draw(graph, pos=layout)

或者使用 graphviz_drawer() 函数：

import rustworkx
from rustworkx.visualization import graphviz_draw

graph = rustworkx.generators.path_graph(weights=list(range(24)))
layout = rustworkx.spiral_layout(graph)

def node_attr_fn(node):
    point = layout[node]
    return {
        "shape": "circle",
        "pos": '"%s,%s!"' % (point[0], point[1]),
        "fillcolor": "yellow",
        "style": "filled",
    }

graphviz_draw(graph, node_attr_fn=node_attr_fn, method='fdp')

Added a new function, spring_layout() to generate layouts for PyGraph and PyDiGraph using the Fruchterman-Reingold force-directed algorithm. This layout method is used by default for the mpl_drawer() visualization function. You can also explicitly use it when calling mpl_drawer() and graphviz_drawer(). For example:

import rustworkx
from rustworkx.visualization import mpl_draw

graph = rustworkx.random_geometric_graph(15, 1.42)
layout = rustworkx.spring_layout(graph, adaptive_cooling=False)
mpl_draw(graph, pos=layout)

and with the graphviz drawer:

import rustworkx
from rustworkx.visualization import graphviz_draw

graph = rustworkx.random_geometric_graph(15, 1.42)
layout = rustworkx.spring_layout(graph, adaptive_cooling=False)
for i in range(15):
  graph[i] = i

def node_attr_fn(node):
    point = layout[node]
    return {
        "shape": "circle",
        "pos": '"%s,%s!"' % (point[0], point[1]),
        "fillcolor": "yellow",
        "style": "filled",
        "fixedsize": "true"
    }

graphviz_draw(graph, node_attr_fn=node_attr_fn, method='fdp')

新增了一个新方法，write_edge_list()，已在PyDiGraph和PyGraph （write_edge_list()）类中添加。此方法用于写入表示图对象的边列表文件。输出格式设计为可作为 rustworkx.PyDiGraph.read_edge_list()和 rustworkx.PyGraph.read_edge_list()的输入使用。

更新说明#

功能：
不再返回dict，而是返回 rustworkx.PathLengthMapping对象。这种新的返回类型构建速度更快，并且以只读方式实现了python映射协议，除非进行显式类型检查或修改结果，否则应该不会注意到差异。

其中的函数：
不再返回 dict，而是返回 rustworkx.PathMapping 对象。这种新的返回类型构建速度要快得多，并且以只读方式实现了 Python 映射协议，除非进行显式类型检查或修改结果，否则应该不会注意到差异。

Bug 修复 #

Fixed an issue where calling rustworkx.PyDiGraph.successor_indices() or rustworkx.PyDiGraph.predecessor_indices() would raise a RuntimeError exception if they were called in a context where rustworkx is already working with a reference to a PyDiGraph (primarily if it were called in a callback function for another PyDiGraph method).

修复 floyd_warshall_numpy() 中的 bug，该错误导致调度器错误地调用了 adjacency_matrix() 而不是 graph_floyd_warshall_numpy() 和 digraph_floyd_warshall_numpy()。

0.8.0#

预备知识

此版本包含了若干新功能和错误修复。本版本的主要特性是一些可用性改进，包括引入新的边交互方法、从邻接矩阵构建图以及不严格类型化且适用于PyGraph或PyDiGraph对象的通用函数。它还包含了针对PyGraph的匹配问题的新算法函数，包括查找最大权重匹配的函数。这也是首次支持并发布针对MacOS上苹果Arm CPU的预编译二进制文件的版本。

新功能#

A new constructor method from_adjacency_matrix() has been added to the PyDiGraph and PyGraph (from_adjacency_matrix()) classes. It enables creating a new graph from an input adjacency_matrix. For example:

import os
import tempfile

import numpy as np
import pydot
from PIL import Image

import rustworkx


# Adjacency matrix for directed outward star graph:
adjacency_matrix = np.array([
    [0., 1., 1., 1., 1.],
    [0., 0., 0., 0., 0.],
    [0., 0., 0., 0., 0.],
    [0., 0., 0., 0., 0.],
    [0., 0., 0., 0., 0.]])
# Create a graph from the adjacency_matrix:
graph = rustworkx.PyDiGraph.from_adjacency_matrix(adjacency_matrix)
# Draw graph
dot_str = graph.to_dot(
    lambda node: dict(
    color='black', fillcolor='lightblue', style='filled'))
dot = pydot.graph_from_dot_data(dot_str)[0]
with tempfile.TemporaryDirectory() as tmpdirname:
    tmp_path = os.path.join(tmpdirname, 'dag.png')
    dot.write_png(tmp_path)
    image = Image.open(tmp_path)
    os.remove(tmp_path)
image

新增了一个算法函数 is_matching()，用于检查某个匹配集对于给定的 PyGraph 对象是否有效。

新增一个算法函数 is_maxmimal_matching()，用于检查给定 PyGraph 对象中的匹配集是否有效且为最大匹配。

添加一项新函数max_weight_matching()，用于计算PyGraph对象的最大权重匹配。

The PyGraph and PyDiGraph constructors now have a new kwarg multigraph which can optionally be set to False to disallow adding parallel edges to the graph. With multigraph=False if an edge is attempted to be added where one already exists it will update the weight for the edge with the new value. For example:

import os
import tempfile

import pydot
from PIL import Image

import rustworkx as rx

graph = rx.PyGraph(multigraph=False)
graph.extend_from_weighted_edge_list([(0, 1, -1), (1, 2, 0), (2, 0, 1)])
dot = pydot.graph_from_dot_data(
    graph.to_dot(edge_attr=lambda e:{'label': str(e)}))[0]

with tempfile.TemporaryDirectory() as tmpdirname:
    tmp_path = os.path.join(tmpdirname, 'dag.png')
    dot.write_png(tmp_path)
    image = Image.open(tmp_path)
    os.remove(tmp_path)
image

Then trying to add an edge between 0 and 1 again will update its weight/payload.

graph.add_edge(0, 1, 42)
dot = pydot.graph_from_dot_data(
    graph.to_dot(edge_attr=lambda e:{'label': str(e)}))[0]

with tempfile.TemporaryDirectory() as tmpdirname:
    tmp_path = os.path.join(tmpdirname, 'dag.png')
    dot.write_png(tmp_path)
    image = Image.open(tmp_path)
    os.remove(tmp_path)
image

You can query whether a PyGraph allows multigraphs with the boolean attribute multigraph. The attribute can not be set outside of the constructor.

rustworkx.generators 模块中的函数 cycle_graph(), path_graph(), star_graph(), mesh_graph() 和 grid_graph() 现在有一个新的关键字参数 multigraph，它接受一个布尔值，默认为 True。当设置为 False 时，生成的 PyGraph 对象将把 multigraph 属性设置为 False，这意味着它将禁止添加平行边。

现在 rustworkx API 中新增了可接受PyGraph或PyDiGraph作为输入的通用函数，不再局限于特定类。这些新函数包括：

从这个版本开始，将为 macOS arm64 发布 wheels。最初仅支持 Python 3.9，因为这是唯一一个原生支持 arm64 macOS 的 Python 版本。

自定义返回类型 BFSSuccessors, NodeIndices, EdgeList, 以及 WeightedEdgeList 现在实现了 __str__ 方法，因此运行 str()（例如在对对象调用 print() 时）将返回一个包含自定义返回类型内容的人类可读字符串。

The custom return types BFSSuccessors, NodeIndices, EdgeList, and WeightedEdgeList now implement __hash__ so that running hash() (for example when insert them into a dict) will return a valid hash for the object. The only exception to this is for BFSSuccessors and WeightedEdgeList if they contain a Python object that is not hashable, in those cases calling hash() will raise a TypeError, just like as you called hash() on the inner unhashable object.

update_edge() 和 update_edge_by_index() 两个新方法被添加到 rustworkx.PyDiGraph 和 rustworkx.PyGraph ( update_edge() 和 update_edge_by_index()) 类中。这些方法用于通过边的节点或边索引来更新图中边的数据负载/权重。

更新说明#

最低支持的 Rust 版本已提升至 1.41.1，你现在需要 rustc >=1.41.1 才能构建 rustworkx。之前的最低支持版本 1.39.0 将无法再编译 rustworkx。这是由于新版pyo3和rust-numpy库中的变更导致的。

Bug 修复 #

在之前的版本中，Python垃圾回收器不知道如何与PyDiGraph或PyGraph 对象交互，因此这些对象可能在Python退出前一直未被释放。为了解决这个问题，PyDiGraph和 PyGraph类现已与Python的垃圾回收器集成，这样当图中对象不再被引用时，它们会被正确地清除。

rustworkx.PyDiGraph.neighbors() 和 rustworkx.PyGraph.neighbors() 方法的输出将不再包含节点间平行边情况下的重复项。更多详情请参见 #250。

在之前的版本中，Python 垃圾回收器不知道如何与自定义返回类型 BFSSuccessors、NodeIndices、EdgeList 和 WeightedEdgeList 互动，因此这些对象可能直到 Python 退出时才会被释放。为了解决这个问题，自定义返回类型类现已与 Python 的垃圾回收器集成，从而在没有任何 Python 对象引用时能够正确清理它们。

0.7.1#

本次发布修复了先前0.7.0和0.6.0版本中的一个疏忽。这两个版本都新增了自定义返回类型 BFSSuccessors, NodeIndices, EdgeList, 以及 WeightedEdgeList，这些类型实现了Python序列协议，并在某些函数和方法中替代了列表使用。然而，这些类都不支持被序列化(pickled)，这导致在使用返回值的场景中（例如作为多进程处理函数的参数或返回值）会出现兼容性问题。本次发布相对于0.7.0版本只有一个变更，即为BFSSuccessors, NodeIndices, EdgeList, 和 WeightedEdgeList添加缺失的序列化支持，从而修复了该问题。

0.7.0#

此版本包含若干新特性和错误修复。

此版本也停止了对 Python 3.5 的支持。如果你想在 Python 3.5 环境下使用 rustworkx，最后一个支持 Python 3.5 的版本是 0.6.0。

新功能#

为两种新的生成器类型，mesh和grid，新增了生成器函数到rustworkx.generators中，分别用于生成全连接图和网格图。这些函数是： mesh_graph(), directed_mesh_graph(), grid_graph(), 以及 directed_grid_graph()
新增了一个新函数 rustworkx.digraph_union()，用于获取两个 PyDiGraph 对象之间的并集。
新增了一个 PyDiGraph 方法 merge_nodes()。该方法可用于在图中合并两个节点，前提是它们的权重/数据负载相同。
一个新的PyDiGraph方法 find_node_by_weight()，可用于通过给定的权重/数据负载查找节点索引。
新增了一个新的返回类型NodeIndices。该类由返回节点索引列表的函数和方法返回。它实现了Python序列协议，并且可以当作列表使用。
两个新的返回类型 EdgeList 和 WeightedEdgeList。这些类从返回边元组列表及带权重的边元组列表的函数和方法中返回。它们都实现了Python序列协议，并且可以当作列表使用
新增了一个函数 collect_runs()。该函数用于查找符合给定条件的节点线性路径。

更新说明#

支持在Python 3.5上运行rustworkx的功能已被停止。最后一个支持Python 3.5的版本是0.6.0。
rustworkx.PyDiGraph.node_indexes(), rustworkx.PyDiGraph.neighbors(), rustworkx.PyDiGraph.successor_indices(), rustworkx.PyDiGraph.predecessor_indices(), rustworkx.PyDiGraph.add_nodes_from(), rustworkx.PyGraph.node_indexes(), rustworkx.PyGraph.add_nodes_from(), 以及 rustworkx.PyGraph.neighbors() 方法和 dag_longest_path(), topological_sort(), graph_astar_shortest_path(), 和 digraph_astar_shortest_path() 函数现在返回一个 NodeIndices 对象而不是整数列表。这不需要任何更改，除非明确对列表进行了类型检查。
方法 rustworkx.PyDiGraph.edge_list() 和 rustworkx.PyGraph.edge_list() 以及函数 digraph_dfs_edges(), graph_dfs_edges(), 和 digraph_find_cycle() 现在返回 EdgeList 对象，而非整数列表。这通常无需改动，除非明确地进行了列表类型检查。
rustworkx.PyDiGraph.weighted_edge_list()、 rustworkx.PyDiGraph.in_edges()、rustworkx.PyDiGraph.out_edges() 以及rustworkx.PyGraph.weighted_edge_list方法现在返回一个 WeightedEdgeList对象，而不是整数列表。除非明确使用了列表类型检查，否则这不需要任何更改。

修复内容#

BFSSuccessors 对象现在可以与任何其他 Python 序列类型进行比较（使用 == 和 !=）。
之前构建并发布的rustworkx sdist包未包含Cargo.lock文件。这意味着rust依赖项的可重现构建版本未传递至源代码。现已修复此问题，因此从sdist构建将始终使用我们在CI测试中使用的已知可用版本。

0.6.0#

此版本包含多项新功能和错误修复。本次发布的主要目标是扩展rustworkx API功能，增添一些先前缺失的常用函数。

此版本也是首个完全支持在Python 3.9上运行的版本。在之前的版本中，Python 3.9可能可以运行，但需要从源代码构建rustworkx。另外，这很可能是支持Python 3.5的最终版本。

新功能#

两个新函数，digraph_k_shortest_path_lengths() 和 graph_k_shortest_path_lengths()，用于在 PyDiGraph 和 PyGraph 中从节点查找 k 个最短路径长度。
为 PyDiGraph 类新增了一个方法 is_symmetric()。这个方法将检查图是否为对称的。
新增了一个关键字参数 as_undirected 到 digraph_floyd_warshall_numpy() 函数中。这可以用于将输入的 PyDiGraph 对象视为无向图以生成输出矩阵。
新增函数 digraph_find_cycle()，该函数将在对 PyDiGraph 对象进行深度优先搜索时返回第一个循环。
两个新函数，directed_gnm_random_graph() 和 undirected_gnm_random_graph()，用于生成随机 \(G(n, m)\) 图。
一个新方法, remove_edges_from(), 被添加到 PyDiGraph 和 PyGraph (removed_edges_from()). 这可用于在单次调用中从图中移除多个边.
新增了一个方法 subgraph() 到 PyDiGraph 和 PyGraph (subgraph())，该方法接收节点索引列表并返回一个相同类型的新对象，表示包含该列表中节点索引的子图。
支持使用Python 3.9运行
新增一个方法 to_undirected() 到 PyDiGraph 中。该方法将从 PyDiGraph 对象生成一个无向的 PyGraph 对象。
向有向图生成器函数新增了一个关键字参数 bidirectional， directed_cycle_graph()， directed_path_graph()，以及 directed_star_graph()。当设置为 True 时，这些函数生成的有向图将会在双向添加边。
新增了两个功能函数：is_weakly_connected() 和 weakly_connected_components()，分别用于检查 PyDiGraph 对象是否为弱连通的，或返回输入 PyDiGraph 的弱连通组件列表。
graph_adjacency_matrix(), digraph_adjacency_matrix(), graph_floyd_warshall_numpy() 和 digraph_floyd_warshall_numpy() 的 weight_fn 关键字参数现在变为可选。之前，调用这些函数时必须指定此参数。但现在，您可以依赖默认权重浮点数（默认为 1.0）来用于图中所有边。
向 PyGraph 和 PyDiGraph 添加一个 neighbors() 方法（neighbors()）。此函数将返回给定输入节点的邻居节点的索引。
新增两个方法：successor_indices() 和 predecessor_indices()，它们被添加到 PyDiGraph中。这些方法将返回给定输入节点的后继节点和前驱节点的索引。
新增了两个新函数：graph_distance_matrix() 和 digraph_distance_matrix()，用于从输入的 PyGraph 和 PyDiGraph 生成距离矩阵。
新增了两个新函数, digraph_dijkstra_shortest_paths() 和 graph_dijkstra_shortest_path(), 用于返回 PyDiGraph 和 PyGraph 对象中节点的最短路径。
新增了四个新方法：insert_node_on_in_edges(), insert_node_on_out_edges(), insert_node_on_in_edges_multiple()，以及 insert_node_on_out_edges_multiple()，它们被添加至 PyDiGraph。这些函数用于在参考节点及其所有前驱或后继节点之间插入一个现有节点。
新增了两个函数：graph_dfs_edges() 和 digraph_dfs_edges()，用于从PyGraph和 PyDiGraph中获取按深度优先排序的边列表。

更新说明#

graph_floyd_warshall_numpy()、 digraph_floyd_warshall_numpy()、 digraph_adjacency_matrix()和 graph_adjacency_matrix()返回的numpy数组现在将采用连续的C数组内存布局。之前，它们会返回列优先的fortran 布局的数组。这一变更是为了更轻松地将这些函数返回的数组与其他C Python扩展接口。通过numpy的API与numpy数组交互时应该没有变化。
bfs_successors() 方法现在返回一个自定义类型 BFSSuccessors 的对象，而不是列表。BFSSuccessors 类型实现了 Python 序列协议，因此可以像列表一样使用（除了显式类型检查的情况）。这样做是为了推迟 Rust 和 Python 之间的类型转换，因为一次性完成所有转换可能会成为性能瓶颈，特别是对于大型图。BFSSuccessors 类只在访问元素时才会进行类型转换。

修复内容#

当对 PyDiGraph 对象进行序列化时，原始节点索引将在序列化过程中保留。
随机的\(G(n, p)\)函数， directed_gnp_random_graph()和 undirected_gnp_random_graph()现在也将处理精确的是0或 1的概率。以前在这些情况下它会失败。修复了 #172

0.5.0#

此版本包含多项新功能和错误修复。本次发布改进的主要重点是提升与图对象互动的便捷性。其中包括添加支持生成可与 graphviz（或类似工具）配合使用的 dot 输出以可视化图形，添加更多方法来查询图的状态，添加生成器模块以便轻松创建特定形状的图，以及实现映射协议以便直接与图对象互动。

新功能#

新方法 to_dot() 已添加到 PyGraph 和 PyDiGraph (to_dot())。它将生成该对象的 dot 格式表示，可用于 Graphivz（或类似工具）来生成图的可视化。
添加了一个新函数：strongly_connected_components()，用于获取PyDiGraph对象的强连通组件列表。
一个新的方法 compose() 被添加到 PyGraph 和 PyDiGraph 中，用于将另一个相同类型的图对象组合到图中（compose()）。
PyGraph 和 PyDigraph 类现在实现了 Python 映射协议以与图节点进行交互。您现在可以通过使用 Python 中的标准映射访问模式直接访问并与节点数据交互。例如，像 graph[1] 这样访问图将返回索引为 1 的节点的权重/数据有效负载。
新增了一个名为 rustworkx.generators 的模块。此模块中的函数可用于快速生成特定形状的图。当前包含：
在 PyDiGraph 类中新增了一个名为 remove_node_retain_edges() 的方法。该方法可用于删除节点，并将其前驱节点和后继节点之间添加边。
新增了两个新方法 edge_list() 和 weighted_edge_list() 用于获取包含边源节点和目标节点的元组列表（带或不带边权重），这两个方法已被添加到 PyGraph 和 PyDiGraph （edge_list() 和 weighted_edge_list()）中
一项新的功能，cycle_basis()，用于获取构成PyGraph对象循环基底的循环列表。
增加了两个新函数：graph_floyd_warshall_numpy()和 digraph_floyd_warshall_numpy()，用于运行 Floyd Warshall算法并将所有最短路径长度返回为距离矩阵。
一个新的构造方法 read_edge_list() 已被添加至 PyGraph 与 PyDigraph (read_edge_list())。该方法将接收一个边列表文件的路径，读取该文件并根据内容生成一个新对象。
为PyGraph和PyDiGraph添加了两个新方法：extend_from_edge_list()和extend_from_weighted_edge_list()（分别是extend_from_edge_list()和extend_from_weighted_edge_list()）。该方法接收一个边列表，并将列表中的边和节点（如果使用的节点索引尚不存在）添加到图中。

修复内容#

在比较包含节点删除的图表时，is_isomorphic() 和 is_isomorphic_node_match() 函数会引发段错误的限制已被修复。现在，您可以使用任意 PyDiGraph/PyDAG 对象运行任何一个函数，即便存在节点删除的情况。修复了 #27
If an invalid node index was passed as part of the first_layer argument to the layers() function it would previously raise a PanicException that included a Rust backtrace and no other user actionable details which was caused by an unhandled error. This has been fixed so that an IndexError is raised and the problematic node index is included in the exception message.

0.4.0#

该版本包含多项新特性与修复，包括改进的性能与更完善的文档。但本次发布的最大变化在于，这是rustworkx首个支持通过稳定版Rust进行编译的版本。这一成果得益于PyO3维护者与贡献者在PyO3 0.11.0版本中的辛勤工作。

新功能#

为无向图新增了一个类：PyGraph。
2 个新增函数 graph_adjacency_matrix() 和 digraph_adjacency_matrix() 用于获取 PyGraph 和 PyDiGraph 对象的邻接矩阵。
新增了一个PyDiGraph方法， find_adjacent_node_by_edge()，该方法用于根据两节点间边的条件来定位相邻节点。
新增方法：add_nodes_from()、 add_edges_from()、 add_edges_from_no_data()以及 remove_nodes_from()已添加到 PyDiGraph。这些方法允许通过单次调用从图中添加（和移除）多个节点或边。
一个新函数，graph_greedy_color()，用于从PyGraph对象返回着色图。
2 个新函数：graph_astar_shortest_path() 以及 digraph_astar_shortest_path()，用于通过 A* 搜索算法寻找从一个节点到指定目标的最短路径。
新增了两个函数，graph_all_simple_paths() 和 digraph_all_simple_paths()，用于返回 PyGraph 或 PyDiGraph 对象中两个节点之间的所有简单路径列表。
新增2个函数，directed_gnp_random_graph() 和 undirected_gnp_random_graph(), 用于生成\(G_{np}\) 随机PyDiGraph 和 PyGraph对象。
新增了两个函数：graph_dijkstra_shortest_path_lengths() 与 digraph_dijkstra_shortest_path_lengths()，用于通过 Dijkstra 算法查找 PyGraph 或 PyDiGraph 对象中节点之间的最短路径长度。

更新说明#

PyDAG 类已重命名为 PyDiGraph，以更好地反映其功能。为了向后兼容性， PyDAG 仍然作为 PyDiGraph 的 Python 子类存在。现有用户无需进行任何更改。
numpy 现已成为 rustworkx 的依赖项。该库被用于邻接矩阵函数以返回 numpy 数组。所支持的 numpy 最低版本为 1.16.0。

修复内容#

rustworkx异常类现在已从rustworkx模块中正确导出。在之前的发布版本中，无法导入异常类（通常用于捕获被引发的异常），这需要用户捕获基类Exception。现已修复此问题，可以使用专门的rustworkx异常类。