nxep2-视图切片的API设计#

作者

塞思

状态

已接受

类型

标准轨道

创建

2020-07-23

摘要#

迭代遍历图中的节点或边的子集是网络分析中非常常见的操作。NetworkX中的图形类(如: GraphDiGraphMultiGraph (等)通过以下方式公开图的节点和边数据 nodes()edges() ,返回Dict视图对象, NodeView (或 NodeDataView )和 EdgeView (或 EdgeDataView )。节点和边 View 类对于项访问具有类似于字典的语义,返回与给定节点或边相对应的数据字典。该NXEP建议向相关节点和边添加切片支持 View 上课。

动机和范围#

使用访问图形数据时 G.nodesG.edges ,对数据进行切片的唯一方法是手动将视图强制转换为列表,然后对其调用切片。切片本质上意味着元素的顺序。我们打算使用迭代顺序对节点和边施加的顺序(由于邻接数据结构)。

G.nodes(data=True) 返回所有节点的NodeDataView, G.nodes(data=True)[x] 返回节点x的属性字典。当前从底层dict视图获取切片的方法是将其强制转换为list,然后对其进行切片 list(G.nodes(data=True))[0:10] . 这段代码是由用户多次编写的。对于有很多节点和边的图, G.nodesG.edges 将占用大量的屏幕空间,当用户尝试分割结果视图时(第一直觉),它将出错。用户在意识到首先需要将这个NodeDataView转换为一个列表,然后创建一个slice之前,肯定需要浏览几个文档链接。更新文档以使这一点更清楚将是有帮助的。但这似乎也有助于缓解这一常见习语的复杂性。

在这个NXEP中,我们建议将casting as list移到Node(data)视图方法中。因此 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] . 然后用户可以通过创建一个切片来获得一小部分节点。

激励性用例#

这是很常见的 nodes()edges() 以交互方式使用NetworkX时,例如在终端中。如果一个图有很多组件(即边或节点),那么 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] 将返回属性dict但是 G.nodes[0:5] 将返回前五个节点的列表。对于EdgeView as来说,这会更加矛盾 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 是否由节点将dict键控到该节点的属性dict作为值。

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

  • G.nodes_iter() 返回节点上的迭代器。

随着Python3朝着返回dict视图和迭代器而不是列表的方向发展,networkx2.0为节点信息引入了一个单一的接口。 G.nodes 是一个类似dict的对象,由节点键控到该节点的属性dict。它还提供对节点的set-like操作。它提供了一种方法 G.nodes.data 它提供了一个类似于 dict.items 但是从内部属性dict而不是整个dict中提取特定属性。功能同义词 G.nodes(data="cost", default=1)G.nodes.data("cost", 1) 允许一个看起来像dict的接口,该接口由节点键控到特定的节点属性。

NetworkX 2.0中没有提供切片,主要是因为在dict的dict数据结构中存储的节点或边没有固有的顺序。然而,在Python3.6中,dict是根据插入顺序进行排序的。因此,节点的排序是根据节点添加到图中的时间来进行的,而边的排序则是基于dict结构的邻接dict。所以,现在有了“第一边缘”的概念。

有了这个NXEP,我们希望将切片行为的直观性带回 G.edgesG.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是所需的切片对象。

向后兼容性#

不适用

详细描述#

新的实现将允许用户切片节点(数据)视图和边缘(数据)视图。

以下代码将有效:

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

初步实施工作可在https://github.com/networkx/networkx/pull/4086

或者,为了消除切片API中关于dict视图的模糊性,我们可以实现一个新的 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的核心是实现 slicing 到节点(数据)视图和边(数据)视图,以允许用户访问节点和边的子集,而无需首先将它们转换为列表。我们将通过添加一个 slice 在节点(数据)视图和边(数据)视图的getitem dunder方法中,返回切片值的列表。例如 __getitem__ 方法 NodeView 可能看起来像:

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

我们可以把支票换成 slice 一个独立的 slice 方法来实现此NXEP。

选择#

下表总结了修改 __getitem__ 各种各样的 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 对象直接但与独立的 slice G.nodes和G.edges的方法,而不是在getitem dunder方法中实现它。

    • 切片的nice冒号语法仅适用于下标表示法。允许G。节点.slice我们可以使用冒号来创建一个很好的对象。语法应该是 G.nodes.slice[4:9:2] .

讨论#

NXEP的一个激励人心的例子是这样一个用例:用户想要反省节点和/或边的子集(通常是前几个)。如果我们看看这个NXEP提出的变更和列出的替代方案,有几种方法可以改进这个用例。

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

  2. 向slice对象添加专门的方法(例如。 head()tail()slice() 为内省提供了有用的功能。

  3. NXEP提出的方法是修改 View.__getitem__ 添加序列语义。

选项1(更好的错误消息)既不改变API,也不改变行为,有助于引导用户为内省用例找到正确的解决方案。缺点是它不能提供与切片支持相同的便利级别。

方案2 (headtail 和/或 slice 方法/a)将新方法添加到视图的子集中。例如::

>>> 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,它必须是可发现的和直观的,以便更方便地查看节点/边缘。例如,是 G.nodes().head(3)G.nodes().slice(0, 10, 2)list(G.nodes())[:3]list(G.nodes())[0:10:2] 分别是?另一个复杂的问题是选择新方法的名称。 headtail 对于来自 *nix 背景和已被其他流行类库采用,如 pandas . 然而, headtail 在网络科学的背景下也有意义,例如图形边缘。例如,用户可以合理地假设 G.edges().tail() 将给出有向图中的源节点集,而不是最后一个 n 边缘。

选项3添加语义 View 对象)可以说是最方便的,因为它不涉及引发任何错误消息。但是,重写 *View.__getitem__ 混合映射和序列语义是一个相对普遍的变化,可能会对一些用例产生不可预见的后果。此外,Python本身也有从一些映射返回不可切片视图对象的先例,一个值得注意的例子是 dict_keysdict_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 在上面的讨论中。用户现在将看到 NetworkXError 当他们试图切开一片 *View 对象。::

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

该实施可在https://github.com/networkx/networkx/pull/4300和https://github.com/networkx/networkx/pull/4304.上获得