rustworkx 介绍

rustworkx 库是一个用于处理图（或称网络）和图论的 Python 库。

本指南是rustworkx的入门介绍。如果您是当前或曾经的NetworkX用户，正考虑将rustworkx作为NetworkX的替代品，也可参考面向NetworkX用户的rustworkx获取详细对比。

安装 rustworkx

安装 rustworkx 需要一个 Python 环境。Rustworkx 可在任意 Python 环境中运行。如果您已安装 Python，可通过以下方式安装 rustworkx：

pip install rustworkx

（如果您在受支持的平台上运行，如果不是，您需要参考在没有预编译二进制文件的平台上安装来了解如何构建和安装）

如何导入rustworkx

要访问rustworkx及其功能，请像这样将其导入到您的Python代码中：

import rustworkx as rx

为了在使用Rustworkx时提高代码的可读性，我们将其名称简写为rx。 这是一个已被广泛采用的约定，你可以遵循。

创建图形

要创建一个没有节点和边的空无向图 \(G\)，你可以运行以下代码：

G = rx.PyGraph()

一个 PyGraph 由节点（顶点）及节点的无序配对（称为边、链接等）组成。rustworkx 中的节点和边都具有指定的数据负载（在API和文档中也称为权重），它可以是任何Python对象（例如数值、字符串、图像、XML对象、另一个图、自定义节点对象等）。节点和边通过整数 索引 来唯一标识，该索引在节点或边存在于图中的整个生命周期内是稳定的。这些索引不保证是连续的，因为被移除的节点或边会在已分配索引序列中留下空缺，并且索引在移除后可被重复使用。

节点

图 \(G\) 可以通过多种方式增长。还有图的生成函数以及以不同格式读写图的函数。

开始操作时我们可以添加一个节点：

G.add_node(1)

0

add_node() 方法会返回一个整数。 这个整数是在图中唯一标识此新节点的索引。只要该节点仍存在于图中，您就可以使用 此索引来识别该节点。

也可以从任意元素序列（例如 list 或 range）向 \(G\) 添加节点：

indices = G.add_nodes_from(range(5))
print(indices)

NodeIndices[1, 2, 3, 4, 5]

与 add_node() 类似， add_nodes_from() 方法返回所添加节点的索引，作为 NodeIndices 对象，这是一个自定义序列类型，包含每个节点根据输入序列添加顺序的索引。

在上述情况中，我们添加了数据载荷为整数类型的节点（例如 G.add_node(1)）。 然而，rustworkx 不对节点数据载荷施加限制， 因此您可以使用更复杂的对象，包括不可 哈希的类型。 例如，我们可以添加一个数据载荷为 字典的节点：

G.add_node({
    "color": "green",
    "size": 42,
})

6

关于如何选择用于数据负载的内容，请参见What to use for node and edge data payload 章节。

边

图 \(G\) 也可以通过一次添加一条边的方式来扩展

G.add_edge(1, 2, None)

0

这将在节点索引 1 和节点索引 2 之间添加一条边，数据负载为 None。类似于 add_node()，add_edge() 方法返回新边的唯一索引。

检验图的相关元素

我们可以在rustworkx中相当容易地检查图的节点和边。首先要做的是使用 node_indices() 和 edge_indices() 获取节点和边索引列表：

node_indices = G.node_indices()
edge_indices = G.edge_indices()
print(node_indices)
print(edge_indices)

NodeIndices[0, 1, 2, 3, 4, 5, 6]
EdgeIndices[0]

由于索引是节点和边的唯一标识符，它们是您访问图中元素的句柄。这在多重图的情况下尤其重要，或者当多个节点之间具有相同数据负载时。您可以使用索引来访问数据负载。对于节点，PyGraph对象的行为类似于一个带有索引的映射：

first_index_data = G[node_indices[0]]
print(first_index_data)

1

对于边缘，您可以使用 get_edge_data_by_index() 方法来访问给定边缘的数据载荷，以及 get_edge_endpoints_by_index() 来根据索引获取 给定边缘的端点：

first_index_data = G.get_edge_data_by_index(edge_indices[0])
first_index_edgepoints = G.get_edge_endpoints_by_index(edge_indices[0])
print(first_index_edgepoints)
print(first_index_data)

(1, 2)
None

我们不实现边的映射协议，因此有一个辅助方法可用于获取边索引到边端点与数据载荷的映射关系，edge_index_map()：

print(G.edge_index_map())

EdgeIndexMap{0: (1, 2, None)}

此外，您可以直接使用nodes()和edges()访问节点和边数据载荷的列表

print("Node data payloads")
print(G.nodes())
print("Edge data payloads")
print(G.edges())

Node data payloads
[1, 0, 1, 2, 3, 4, {'color': 'green', 'size': 42}]
Edge data payloads
[None]

从图中删除元素

你可以以类似于向图中添加元素的方式从图中移除节点或边。有方法remove_node(), remove_nodes_from(), remove_edge(), remove_edge_from_index(), 和 remove_edges_from()来从图中移除节点和边。需要注意的是，移除操作可能会在图中节点和边的索引列表中引入空隙。例如：

graph = rx.PyGraph()
graph.add_nodes_from(list(range(5)))
graph.add_nodes_from(list(range(2)))
graph.remove_node(2)
print(graph.node_indices())

NodeIndices[0, 1, 3, 4, 5, 6]

你可以看到这里2现在已从graph的节点索引中消失。 此外，在移除之后，被移除节点或边的索引将在后续添加时被重新使用。例如，假设延续上一个示例，你运行了

graph.add_node("New Node")

2

该新节点再次被分配索引2。

修改图的元素

rustworkx中的图类还允许对图中元素的有效载荷进行就地修改。对于节点，您可以直接使用映射协议通过节点索引来更改有效载荷。例如:

last_index = graph.node_indices()[-1]
graph[last_index] = "New Payload"
print(graph[last_index])

New Payload

您可以通过此接口更新图中任意节点的负载。对于边，可利用update_edge或 update_edge_by_index方法来原地更新边的负载。 例如：

edge_index = graph.add_edge(0, 1, None)
graph.update_edge_by_index(edge_index, "New Edge Payload")
print(graph.get_edge_data_by_index(edge_index))

New Edge Payload

节点和边数据负载的用途

在上面的示例中，我们主要使用整数、字符串和None 作为图中节点和边的数据负载（主要是为了简化）。 然而，rustworkx允许使用任何Python对象作为 节点和边的数据负载。这种灵活性非常强大， 因为它允许你创建包含其他图的图、包含 文件的图、带有函数的图等。这意味着你只需保留 rustworkx为你用作数据负载的对象返回的 整数索引，即可在图中找到这些对象。例如，一种可以 采用的方法是将索引存储为你添加到图中的对象的属性：

class GraphNode:

    def __init__(self, value):
        self.value = value
        self.index = None

graph = rx.PyGraph()
index = graph.add_node(GraphNode("A"))
graph[index].index = index

此外，您可以随时找到数据有效载荷的索引映射，并构建映射或更新对其的引用。例如，在上述示例基础上，您可以在创建后一次性更新所有索引引用：

class GraphNode:
    def __init__(self, value):
        self.index = None
        self.value = value

    def __str__(self):
        return f"GraphNode: {self.value} @ index: {self.index}"

class GraphEdge:
    def __init__(self, value):
        self.index = None
        self.value = value

    def __str__(self):
        return f"EdgeNode: {self.value} @ index: {self.index}"

graph = rx.PyGraph()
graph.add_nodes_from([GraphNode(i) for i in range(5)])
graph.add_edges_from([(i, i + 1, GraphEdge(i)) for i in range(4)])
# Populate index attribute in GraphNode objects
for index in graph.node_indices():
    graph[index].index = index
# Populate index attribute in GraphEdge objects
for index, data in graph.edge_index_map().items():
    data[2].index = index
print("Nodes:")
for node in graph.nodes():
    print(node)
print("Edges:")
for edge in graph.edges():
    print(edge)

Nodes:
GraphNode: 0 @ index: 0
GraphNode: 1 @ index: 1
GraphNode: 2 @ index: 2
GraphNode: 3 @ index: 3
GraphNode: 4 @ index: 4
Edges:
EdgeNode: 0 @ index: 0
EdgeNode: 1 @ index: 1
EdgeNode: 2 @ index: 2
EdgeNode: 3 @ index: 3

访问边与邻居

您可以使用 incident_edges() 方法访问节点的边：

print(G.incident_edges(2))

EdgeIndices[0]

这将返回与节点 2 相关联的边缘索引。你也可以使用 neighbors() 方法找到相邻节点：

print(G.neighbors(2))

NodeIndices[1]

返回节点 2 的任意邻居的节点索引。

图属性

rustworkx中的图有一个属性，可用于向图对象分配元数据。该属性可在对象创建时分配，或在创建后通过attrs属性进行访问和修改。此属性可以是任何Python对象，如果在图对象创建时未指定，则默认为None。例如：

graph = rx.PyGraph(attrs=dict(day="Friday"))
graph.attrs['day'] = "Monday"

或者，你可以使用一个自定义类，例如：

class Day:

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

graph = rx.PyGraph(attrs=Day("Friday"))
graph.attrs = Day("Monday")

有向图

有向图是由一组节点通过有向边（通常称为弧）连接而成的图。边具有方向性，这与无向图不同，无向图的边没有方向的概念。在rustworkx中，PyDiGraph类用于创建有向图。例如：

from rustworkx.visualization import mpl_draw

path_graph = rx.generators.directed_path_graph(5)
mpl_draw(path_graph)

在此示例中，我们创建了一个包含5个节点的有向路径图。这通过箭头指向目标节点的方式展示了图中边的方向性。

多重图

默认情况下，rustworkx中的所有图皆为多重图。这意味着每个图对象都可以包含节点之间的平行边。但是，你可以在PyGraph和PyDiGraph构造函数上设置multigraph参数为False，从而在创建新图对象时阻止引入平行边。当multigraph设为False时，任何试图添加平行边的方法调用都会转而更新现有边的权重/数据载荷。例如：

graph = rx.PyGraph(multigraph=False)
graph.add_nodes_from(range(3))
graph.add_edges_from([(0, 1, 'A'), (0, 1, 'B'), (1, 2, 'C')])
mpl_draw(graph, with_labels=True, edge_labels=str)

在这个例子中，我们尝试在节点 0 和 1 之间添加一条平行边，但实际操作会导致现有边的数据负载从 'A' 更新为 'B'。

图生成器和操作

除了一次构建一个节点和边来构造图外，你还可以使用Generators、Random Graph Generator Functions和Graph Operations来快速生成图和/或对图应用不同的操作。例如：

lolipop_graph = rx.generators.lollipop_graph(4, 3)
mesh_graph = rx.generators.mesh_graph(4)
combined_graph = rx.cartesian_product(lolipop_graph, mesh_graph)[0]
mpl_draw(combined_graph)

此外还有替代构造函数如 read_edge_list() 或 from_adjacency_matrix() 用于从文件或其他输入构建图。例如：

import tempfile

with tempfile.NamedTemporaryFile('wt') as fd:
    path = fd.name
    fd.write('0 1\n')
    fd.write('0 2\n')
    fd.write('0 3\n')
    fd.write('1 2\n')
    fd.write('2 3\n')
    fd.flush()
    graph = rx.PyGraph.read_edge_list(path)
mpl_draw(graph)

图分析

图\(G\)的结构可以使用可用的图算法函数进行分析。例如：

G = rx.PyGraph()
G.extend_from_edge_list([(0, 1), (0, 2)])
new_node = G.add_node("spam")
print(rx.connected_components(G))
degrees = {}
for node in G.node_indices():
    degrees[node] = G.degree(node)
print(degrees)

[{0, 1, 2}, {3}]
{0: 2, 1: 1, 2: 1, 3: 0}

G.remove_node(new_node)
G.extend_from_edge_list([(0, 3), (0, 4), (1, 2)])
rx.transitivity(G)

0.375

查看Algorithm Functions API文档部分获取可用函数及相应使用信息的列表。

绘制图形

rustworkx 提供了两个用于可视化图的可视化函数。第一个是 mpl_draw()，它使用 matplotlib 库来渲染图的可视化效果。mpl_draw() 函数依赖于 rustworkx 提供的 布局函数 来为图生成布局（即绘制图节点的坐标）（默认使用 spring_layout()）。例如：

import matplotlib.pyplot as plt

G = rx.generators.generalized_petersen_graph(5, 2)
subax1 = plt.subplot(121)
mpl_draw(G, with_labels=True, ax=subax1)
subax2 = plt.subplot(122)
layout = rx.shell_layout(G, nlist=[[0, 1, 2, 3, 4], [6, 7, 8, 9, 5]])
mpl_draw(G, pos=layout, with_labels=True, ax=subax2)

第二个函数是graphviz_draw(), 它 使用Graphviz生成可视化图形。例如:

from rustworkx.visualization import graphviz_draw

G = rx.generators.heavy_hex_graph(7)
# set data payload to index
for node in G.node_indices():
    G[node] = node

def node_attr_fn(node):
    attr_dict = {
        "style": "filled",
        "shape": "circle",
        "label": str(node)
    }
    # Data nodes are yellow
    if node < 7 * 7:
        attr_dict["color"] = "yellow"
        attr_dict["fill_color"] = "yellow"
    # Syndrome nodes are black
    elif node >= 7 * 7 and node < (7 * 7) + ((7 - 1) * (7 + 1) / 2):
        attr_dict["color"] = "black"
        attr_dict["fill_color"] = "black"
        attr_dict["fontcolor"] = "white"
    # Flag quits are blue
    else:
        attr_dict["color"] = "blue"
        attr_dict["fill_color"] = "blue"
    return attr_dict

graphviz_draw(G, node_attr_fn=node_attr_fn, method="neato")

通常，在决定使用哪种可视化函数时，需要考虑几个因素。mpl_draw()是较小图或当你希望将图形绘制整合为大型可视化一部分时的更好选择。 graphviz_draw()通常是较大图的更佳选择，因为Graphviz是一个专用于绘制图形的工具。