NXEP 2 — 视图切片的 API 设计#

作者:

Mridul Seth

状态:

已接受

类型:

标准跟踪

创建时间:

2020-07-23

摘要#

在 networkx 分析中，遍历图的节点或边的子集是一种非常常见的操作。NetworkX 中的图类（例如 Graph、DiGraph、MultiGraph 等）通过 nodes() 和 edges() 暴露图的节点和边数据，它们分别返回字典视图对象 NodeView（或 NodeDataView）和 EdgeView（或 EdgeDataView）。节点和边 View 类具有类似字典的项访问语义，返回与给定节点或边对应的属性字典。本 NXEP 建议为相关的节点和边 View 类添加切片支持。

动机与范围#

在使用 G.nodes 和 G.edges 访问图数据时，切片数据的唯一方法是手动将视图转换为列表，然后在其上调用切片。切片本身意味着元素的排序。我们打算使用迭代顺序（由于邻接数据结构）强加给节点和边的顺序。

G.nodes(data=True) 返回所有节点的 NodeDataView，G.nodes(data=True)[x] 返回节点 x 的属性字典。目前从底层字典视图获取切片的方法是将其转换为列表，然后进行切片，例如 list(G.nodes(data=True))[0:10]。这段代码是用户经常编写的。对于节点和边非常多的图，G.nodes 和 G.edges 将占用大量屏幕空间，当用户尝试对结果视图进行切片（第一反应）时，会出错。用户肯定需要查阅一些文档链接才能意识到他们需要先将 NodeDataView 转换为列表，然后才能创建切片。更新文档使其更清晰会有所帮助。但简化这种常见用法的复杂性似乎也是个好主意。

在此 NXEP 中，我们建议将转换为列表的操作移动到 Node(Data)View 方法内部。因此，list(G.nodes(data=True))[0:10] 要么变成 G.nodes(data=True)[0:10]，要么由一个新的切片方法提供，例如 G.nodes(data=True).slice(10)，或者使用一个新的切片对象以允许像 G.nodes(data=True).slice[0:10:2] 这样的下标访问。这样用户可以通过创建切片来获取节点的少量子集。

驱动用例#

在使用 NetworkX 进行交互时（例如在终端中），经常使用 nodes() 和 edges()。如果图有非常多的组件（即边或节点），那么 repr 的 View 对象可能会非常长

>>> G = nx.complete_graph(100)   # A graph with 4950 edges
>>> G.edges                      # Output suppressed

在这种情况下，用户的第一个直觉通常是通过切片来检查前几条边，例如 10 条边

>>> G.edges[0:10]
Traceback (most recent call last)
   ...
TypeError: cannot unpack non-iterable slice object

由此产生的 TypeError 在用户最初意图的背景下是晦涩难懂的。

用法与影响#

本 NXEP 的主要影响和需要做出的决定与用户界面 API 有关。通过通过下标访问 NodeViews 来实现本 NXEP，我们可能会给用户带来一些歧义。例如，G.nodes[x] 将返回一个属性字典，但 G.nodes[0:5] 将返回前五个节点的列表。这对于 EdgeView 将更加模糊，因为 G.edges[0, 1] 将返回节点 0 和 1 之间边的属性字典，而 G.edges[0:1] 将返回第一条边。我们需要找到一种方法来解决这种潜在的混淆。提出一个新的切片方法是其中一个可能的解决方案。

从历史背景来看，在 NetworkX 2.0 版本之前，G.nodes() 和 G.edges() 返回的是列表。因此，切片是原生行为，例如 G.nodes()[:10]。一个注意事项是，如果两次调用之间邻接结构发生变化，该列表的顺序可能会改变。

更详细地说，在 NetworkX 2.0 版本之前，有 3 种方式访问节点信息

  • G.node 是一个字典，以节点为键，以该节点的属性字典为值。

  • G.nodes() 返回一个列表。

  • G.nodes_iter() 返回一个节点迭代器。

为了与 Python 3 返回字典视图和迭代器而非列表的趋势保持一致，NetworkX 2.0 引入了节点信息的统一接口。G.nodes 是一个类似字典的对象，以节点为键，以该节点的属性字典为值。它还提供了对节点的类似集合的操作。并且它提供了一个方法 G.nodes.data，该方法提供了类似于 dict.items 的接口，但从内部属性字典中提取特定属性而不是整个字典。函数同义词 G.nodes(data="cost", default=1) 和 G.nodes.data("cost", 1) 允许提供一个接口，看起来像一个以节点为键，以特定节点属性为值的字典。

NetworkX 2.0 中没有提供切片功能，主要是因为存储在 dict-of-dict-of-dict 数据结构中的节点或边没有固有顺序。然而，在 Python 3.6 中，字典根据插入顺序变得有序。因此，节点根据添加到图中的时间排序，边根据邻接 dict-of-dict 结构排序。所以，现在有了“第一条边”的概念。

通过本 NXEP，我们希望利用节点添加顺序和基于邻接存储的边顺序，将切片行为的直观性重新带回 G.edges 和 G.nodes。

在计算方面，如果创建列表以允许切片，我们将使用内存来存储列表。这是用户无论如何都会用 list(G.nodes(data=True))[0:10] 这样的代码做的事情。但是我们的切片机制可以做得更好。我们应该能够通过内部使用类似以下代码来避免仅仅为了获取切片而构建整个列表：indx=[n for i, n in enumerate(G.nodes(data=True)) if i in range(x.start, x.stop, s.step)]，其中 x 是期望的切片对象。

向后兼容性#

不适用

详细描述#

新的实现将允许用户切片 Node(Data)View 和 Edge(Data)View。

以下代码将有效

>>> G.nodes(data=True)[0:10]
>>> G.nodes[3:10]
>>> G.edges[1:10]
>>> G.edges(data=True)[4:6]

初步的实现工作可在 networkx/networkx#4086 查看

或者，为了消除切片 API 相对于字典视图的歧义，我们可以实现一个新的 slice 方法，从而使 API 更清晰。

>>> G.nodes(data=True).slice[:10]
>>> G.nodes.slice[10:30]
>>> G.edges.slice[10:40]
>>> G.edges(data=True).slice[5:]

实现#

在 #4086 中提出了一个参考实现。

本 NXEP 的核心是为 Node(Data)View 和 Edge(Data)View 实现 slicing，以允许用户访问节点和边的子集，而无需先将它们转换为列表。我们将通过在 Node(Data)View 和 Edge(Data)View 的 getitem dunder 方法中添加对 slice 的检查，并返回切片值的列表来实现。例如，NodeView 的 __getitem__ 方法可能看起来像这样

def __getitem__(self, n):
    if isinstance(n, slice):
        return list(self._nodes).__getitem__(n)
    return self._nodes[n]

我们可以将对 slice 的检查移动到独立的针对节点和边的 slice 方法中来实现本 NXEP。

备选方案#

以下列表总结了修改各种 View 类的 __getitem__ 方法的一些备选方案。列出的备选方案并非互斥。

  • 改进文档 - 添加更清晰的文档，说明必须将 Node(Data)View 和 Edge(Data)View 对象转换为列表才能使用切片。

  • 改进异常 - 目前，用户在尝试对 View 进行切片时会看到以下异常

    >>> G.nodes[0:10]
Traceback (most recent call last)
   ...
TypeError: unhashable type: 'slice'

    该异常消息在访问图的节点或边的子集的上下文中用处不大。更具体的异常消息可以是类似以下内容

    >>> G.nodes[0:10]
Traceback (most recent call last)
   ...
NetworkXError: NodeView does not support slicing. Try list(G.nodes)[0:10].

  • 与其改变 __getitem__ 的行为，我们可以实现一个新方法，例如 G.nodes.head(x)（受 pandas 启发），它返回前 x 个节点。这种方法可以扩展到直接使用 slice 对象，但将其与 G.nodes 和 G.edges 的独立 slice 方法对接，而不是在 getitem dunder 方法中实现。

    • 切片的漂亮冒号语法只能与下标符号一起使用。为了让 G.nodes.slice 使用漂亮的冒号语法，我们可以将其设置为一个属性，该属性创建一个可下标访问的对象。语法将是 G.nodes.slice[4:9:2]。

讨论#

本 NXEP 的驱动示例是用户想要检查节点和/或边的子集（通常是前几个）的用例。如果我们查看本 NXEP 提出的更改和列出的备选方案，有几种方法可以改进这个用例。

  1. 当用户尝试使用切片对象访问 View 对象时，添加描述性错误消息。

  2. 为切片对象添加专门的方法（例如 head() 和 tail() 或 slice()），这些方法提供了用于内省的功能。

  3. 本 NXEP 提出的方法 - 修改 View.__getitem__ 以添加 Sequence 语义。

方案 1（更好的错误消息）既不改变 API 也不改变行为，将有助于引导用户找到内省用例的正确解决方案。缺点是它不像支持切片那样方便。

方案 2（head、tail 和/或 slice 方法）将添加新方法来查看节点/边的子集。例如

>>> G = nx.path_graph(10)
>>> G.nodes()
NodeView((0, 1, 2, 3, 4, 5, 6, 7, 8, 9))
>>> G.nodes().head(3)   # Display the first three nodes
NodeView((0, 1, 2))

这种方法的一个缺点是引入了新的 API，为了使节点/边查看更方便，该 API 必须易于发现且直观。例如，G.nodes().head(3) 或 G.nodes().slice(0, 10, 2) 是否比 list(G.nodes())[:3] 或 list(G.nodes())[0:10:2] 更方便？另一个复杂之处在于为新方法选择名称。head 和 tail 对于来自 *nix 背景的用户来说很直观，并且已被 pandas 等其他流行库采用。然而，head 和 tail 在网络科学中关于图边等方面也有特定含义。例如，用户可能会合理地认为 G.edges().tail() 将返回有向图中的源节点集，而不是最后的 n 条边。

方案 3（为 View 对象添加 Sequence 语义）可以说是最方便的，因为它不会引发任何错误消息。然而，重写 *View.__getitem__ 的行为以混合 Mapping 和 Sequence 语义是一个相对普遍的改变，可能对某些用例产生不可预见的后果。此外，Python 本身就存在从某些映射返回不可切片的视图对象的先例，一个显著的例子是访问字典组件时返回的 dict_keys 和 dict_values 对象

>>> d = {k:v for k, v in zip(range(10), range(10))}
>>> d.values()[3:6]
Traceback (most recent call last)
   ...
TypeError: 'dict_values' object is not subscriptable
>>> list(d.values())[3:6]
[3, 4, 5]

由于 Python 字典现在默认有序（从 CPython 3.6 开始），这种行为将来可能会改变。

考虑到列出的选项相关的考量，建议采取以下行动方案

  • 采用方案 1 - 为驱动用例（例如 G.edges()[0:10]）提供更具信息性的错误消息，减轻了用户查阅文档来寻找/记住如何获得期望行为的需求。由于没有引入新的 API，也没有向后兼容性问题，此更改无需进一步的设计讨论。此更改可能足以令人满意地解决驱动用例 - 监测用户反馈。

  • 方案 2 无需在设计文档（即 NXEP）中进一步讨论。可以通​​过 PR 提出上面讨论的类似的新方法。

  • 暂时推迟实施方案 3，但如果出现以下情况则重新考虑

    • 改进的错误消息本身不足以成为解决方案

    • 确定了将切片功能添加到 *View 对象会是一个不错的改进的其他用例（例如，性能提升）。

决议#

为了让新用户更容易直观地理解切片，我们按照上面讨论的方案 1 进行了实施。现在，当用户尝试对 *View 对象进行切片时，将看到 NetworkXError。

>>> G.edges()[0:10]
Traceback (most recent call last)
   ...
NetworkXError: EdgeView does not support slicing, try list(G.edges)[0:10:None]

实现可在 networkx/networkx#4300 和 networkx/networkx#4304 查看。

本页内容