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

作者:

Mridul Seth

状态:

已接受

类型:

标准跟踪

创建时间:

2020-07-23

摘要#

在网络分析中，迭代图中的节点或边的子集是一种非常常见的操作。 NetworkX中的图类（例如:class:Graph 、DiGraph 、MultiGraph 等）通过:meth:nodes 和:meth: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进行交互时，例如在终端中，通常会使用:meth:nodes 和:meth:edges 。 如果一个图有很多组件（即边或节点），那么 View 对象的 repr 可能会非常长：

>>> G = nx.complete_graph(100)   # 一个具有4950条边的图
>>> G.edges                      # 输出被抑制

在这种情况下，用户的第一反应通常是仅检查前几条边，比如前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] 将返回第一条边。我们需要找到一种方式来解决这种潜在的混淆。提出的另一种新切片方法是一种可能的解决方案。

在历史背景下，在2.0版本之前的NetworkX中，G.nodes() 和 G.edges() 返回的是列表。因此，像 G.nodes()[:10] 这样的切片是本地行为。一个注意事项是，如果在调用之间邻接结构发生变化，那么列表的顺序可能会从一次调用到下一次调用发生变化。

更详细地说，在2.0版本之前的NetworkX中，有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中没有提供切片功能，主要是因为存储在字典-字典-字典数据结构中的节点或边没有固有的顺序。然而，在Python 3.6中，字典根据插入顺序变得有序。因此，节点的顺序是基于它们添加到图中的时间顺序，边的顺序是基于邻接字典-字典结构的。因此，现在有了“第一条边”的概念。

通过这个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是所需的切片对象。

向后兼容性#

N/A

详细描述#

新的实现将允许用户对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:]

相关工作#

N/A

实现#

在 #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__”以添加序列语义。

选项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)   # 显示前三个节点
NodeView((0, 1, 2))

这种方法的一个缺点是引入了新的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”对象添加序列语义）可以说是最方便的，因为它不涉及引发任何错误消息。 然而，覆盖“*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 中找到。

On this page