NXEP 3 — 图构建器

作者:

Dan Schult

作者:

Kelly Boothby

状态:

起草中

类型:

标准跟踪

创建时间:

2020-11-27

修订版本:

2023年春季

摘要

NetworkX中的图生成器从指定在 create_using 参数中的对象开始创建图。这些生成器中的许多只是创建要添加到图中的边。有时我们只需要图来生成这些边。允许图生成器函数返回 edgelist 或由 create_using 指定的图对象可能更好。本NXEP提出了一个图构建器框架，允许用户友好地使用此功能，并使用装饰器使开发人员能够轻松提供此功能，无论图构建算法是需要图还是仅需要边。

动机和范围

例如，考虑函数 nx.path_graph(nodes, create_using) 。它为指定的路径创建边，并将它们添加到使用类型 create_using 创建的图数据结构中。 path_graph 不使用图结构来创建正在生成的边，可以说只需生成边而不涉及数据结构即可。本NXEP提出了语法 nx.path_graph_generator(nodes) 来获取图的生成器。也就是说，结果会迭代图的边列表，而不构建图本身。请注意，我们为每个现有的图构建函数添加了一个新函数。API为 *_graph() 用于图构建器， *_graph_generator() 用于边的生成器。

边列表实际上不足以表示图，因为存在节点属性、图属性和孤立节点。为了处理这些更奇特的元素，我们引入了图序列作为指定图的所有节点、边和属性的一种方式。生成器会产生这个序列。

将边生成与图数据结构创建分离，可以在独立工具之间以创造性方式组合，从而实现更清晰的接口。在用户需要生成边而不是图的情况下，具有不存储图的边生成器是一种优势。目前尚不清楚对此功能有多少需求。但作为此方法灵活性的一个示例， nx.utils.pairwise(nbunch) 调用可以通过 nx.path_graph_generator(nbunch) 来替代。

create_using 参数是告诉构建函数要从哪种图数据结构类开始的机制。将边生成与图构建分离意味着当不需要图数据结构类型时，边生成器函数将不再需要图数据结构的类型。本NXEP提出了一种在需要时提供将边生成与图数据结构创建分离的接口的方法，同时保留。

图形序列

仅包含指示边的节点对的边缘列表是有限制的。 一些图形具有孤立节点，这些节点不会出现在任何节点对中。 一些图形具有与节点或边相关联的节点或边属性。 多重图具有与每个边相关的边键，通常表示为3元组 (u, v, ekey)。本提案建议我们采用以下图形序列协议来描述一个图形。

图形序列是一个序列的序列，通常是元组的列表。 每个元组的长度以及元组最后一个元素的可散列性确定了元组中包含的信息类型。 所有networkx图形信息都可以存储在这样的序列中。 逻辑如下，其中S表示内部序列：

	len(S)	hashable(S[-1])
图形属性：	1	False
没有属性的节点：	1	True
具有属性的节点：	2	False
没有属性的边：	2	True
具有属性的边：	3	False
没有属性的多边：	3	True
具有属性的多边：	4	False

以下是用于处理这样一个序列并从空图G开始构建图形的代码：

for S in graphsequence:
    N = len(S)
    last_entry = S[-1]
    attrs = not hashable(last_entry)
    if N == 1:
        if attrs:
            G.graph.update(last_entry)  # 图形属性
        else:
            G.add_node(last_entry)  # 没有属性的节点
    elif N == 2:
        if attrs:
            G.add_node(S[0], **last_entry)  # (节点, 属性字典)
        else:
            G.add_edge(*S)  # (u, v)
    elif N == 3:
        if attrs:
            G.add_edge(*S[:2], **last_entry)  # (u, v, 属性字典)
        else:
            G.add_edge(*S)  # (u, v, 边键)
    elif N == 4:
        if attrs:
            G.add_edge(*S)  # (u, v, 边键, 属性字典)
        else:
            raise NetworkXInvalidEdgelist(
                "序列元素有4个项目，且最后一个不可散列：{S}"
            )
    else:
        raise NetworkXInvalidEdgelist(

```rst

“Graph Sequence元素的项数超过4个：{S}”

)

请注意，顺序不会影响网络结构，但如果在添加边之前按照期望的顺序添加节点，则可以保留节点的报告顺序。

用法和影响

每个图构建函数（以前称为图生成器）将允许以与以前相同的语法返回图结构。例如， 创建一个具有9个辐条的轮形图（10个节点）：

>>> G = nx.wheel_graph(9)  # 与当前代码相同

在不创建图的情况下遍历Graph Sequence：

>>> for u, v in nx.binomial_graph.edges(9):
>>>     process(u, v)

向现有图G添加10个新节点和随机边（可能包括孤立节点）：

>>> G.update(nx.binomial_graph_generator(range(9, 19))

使用MultiDiGraph数据结构构建路径图（两种方法）：

>>> MDG = nx.path_graph([3, 4, 2, 5, 7, 6], create_using=MultiDiGraph)
>>> MDG = nx.MultiDiGraph(nx.path_graph_generator([3, 4, 2, 5, 7, 6])

在实例化时读取edgelist的代码，或通过 update 方法读取，将更改以允许Graph Sequences而不仅仅是edgelists。另外， 一个基类方法 G.as_sequence() 将为图产生Graph Sequence。

开发人员将使用装饰器指示他们的图构建器是否具有从edgelist产生的基础代码，或者返回一个图。

   @graph_builder
   @py_random_state(4)
   def extended_barabasi_albert_graph(n, m, p, q, seed=None):
       # 一些需要我们构建G来使用图属性的花哨代码
       # 在决定下一步添加哪些边时。
       return G

`@graph_builder` 装饰器添加了代码以启用

例如 nx.extended_barabasi_albert_graph_generator 。

另一个装饰器为那些编写简单从edgelist产生的代码的开发人员提供处理 create_using 参数的代码。

   @node_and_edge_builder
   def ladder_graph_generator(n):
       yield from pairwise(range(n))
       yield from pairwise(range(n, 2 * n))
       yield from ((v, v + n) for v in range(n))

`@node_and_edge_builder` 装饰器添加了代码以启用

例如 nx.ladder_graph(6, create_using=MultiGraph) 。请注意， nx.ladder_graph(6) 仍将返回一个nx.Graph，就像当前一样。要利用edgelist功能，语法将是 nx.ladder_graph.edges(6) 。

最好将doc_strings显示在单个网页上，同时包括函数和生成器。我们正在探索这种可能性。

向后兼容性

为了减少向后不兼容性，基本调用结构 nx.path_graph(9) 的工作方式与当前相同。 create_using 参数的行为与通常情况下相同。 因此，不应该破坏任何现有代码。

为了减少对开发人员的影响，在初始阶段，我们可以通过附加 @graph_builder 装饰器将所有当前的图生成器重新用作图构建器。 ``` 据推测，为了提高效率，许多生成器应该被重写，以产生边缘列表而不是返回图形。但这可以逐渐进行，并且与切换装饰器为 @node_and_edge_builder 一起进行。两组代码都应该返回等效的图构建器对象。

详细描述

这可以通过一些装饰器来实现，可以逐渐采用 – 最初使用 @graph_builder 装饰所有现有生成器的一个大补丁，将立即支持符号 nx.complete_graph_generator(...) ，而不影响现有代码。后续生成器可以使用 @node_and_edge_builder 。

** 需要更新 **

def node_and_edge_builder(f):
    @wraps(f)
    def graph(*args, create_using=None, **kwargs):
        G = nx.empty_graph(0, create_using=create_using)
        G.update(f(*args, **kwargs))
        return G

    graph.edges = f
    graph.edges_plus = f
    return graph


def graph_builder(f):
    @wraps(f)
    def edgelist(*args, **kwargs):
        G = f(*args, **kwargs)
        return itertools.ichain(map(tuple, G.nodes.data()), map(tuple, G.edges.data()))

    def edges(*args, **kwargs):
        G = f(*args, **kwargs)
        return map(tuple, G.edges.data())

    f.edges_plus = edgelist
    f.edges = edges

    return f

注意：基础代码中的 graph_builder 应接受一个 create_using 参数，以使此实现生效。我们需要考虑这是否适用于所有四个主要的 NetworkX 图类，以及如何处理不应与所有四个主要 NetworkX 图类一起使用的构建器。

Graph.update 需要处理图序列输入。它目前处理多重图的节点对和带有边键的节点对。应该使用类似上述“图序列”描述中显示的代码。

开发者使用示例：

@node_and_edge_builder
def path_graph(n):
    """一个过于简化的路径图实现"""
    return pairwise(range(n))


@graph_builder
def complete_graph(n, create_using=None):
    """一个过于简化的完全图实现"""
    if create_using is None:
        create_using = nx.Graph
    g = empty_graph(0, create_using)
    g.update(itertools.combinations(range(n), 2))
    return g

相关工作

该提案基于 #3036 和 #1393 的想法和讨论。

该提案不涉及使用 _dispatchable 功能的后端，以及我们是否应该提供或允许对后端库的构建器函数进行控制。这是一个潜在有益的讨论，但超出了此 NXEP 的范围。

实现

第一个重要步骤是实现这两个构建器装饰器。接下来，我们需要更改图的更新方法，转换函数等。 处理包含孤立节点和数据属性的图序列。 第三步应该识别构建图或边缘列表的任何函数，并对其进行装饰，使其成为图构建器。我们应该注意处理处理边缘列表且无法处理图序列的代码时要适当保护它们。

特别注意确保只有所需的图类型被接受，并在不符合条件时引发适当的错误。

后续步骤包括检查现有的生成器代码，并将该代码更改为生成边缘列表而不是返回图（在适当的情况下）。

替代方案

1. 我们可以保持生成器不变，并处理仅在需要边缘列表时创建图的成本。大多数情况下这不是一个巨大的成本。

2. 我们可以在图构建器函数上创建一个属性函数，提供生成器功能。例如： nx.path_graph.edges_plus() 以及 nx.path_graph.edges() 。

3. 我们可以提供 nx.path_graph.edges_plus 而不提供 edges 属性。通过一个属性函数的简单接口（一个属性函数），我们可以确保提供了创建、消费和处理图序列的简便工具。

4. 我们可以提供装饰器，使用属性语法来表示图类型，而不是参数 create_using 。因此， nx.path_graph.MultiGraph(9) 将与 nx.path_graph(9, create_using=nx.MultiGraph) 相同。对于 Graph 、 DiGraph 、 MultiDiGraph 以及可能的 CustomGraph ，都可以使用一个关键字参数 create_using 。

此提案的早期版本包括将此属性样式替代方案作为 create_using 参数的替代方案。开发人员仍将编写代码来 1) 生成边缘，或 2) 从输入图参数构建图。然后，两个装饰器将添加所需的额外代码，以构建单个对象，使用户可以使用相同的接口，无论使用哪种底层代码风格。用户界面将允许用户按类型指定图数据结构，或请求一个边缘列表。一个语法提案如下:

G = nx.path_graph(9)
DG = nx.path_graph.DiGraph(9)
MG = nx.path_graph.MultiGraph(9)
MDG = nx.path_graph.MultiDiGraph(9)
CG = nx.path_graph.CustomGraph(9, create_using)
elist = nx.path_graph.edgelist(9)

可以通过上述命名的装饰器来实现这一点，并编写类似于以下示例的代码。

def node_and_edge_builder(f):
    @wraps(f)
    def graph(*args, **kwargs):
        return nx.Graph(f(*args, **kwargs))

    def digraph(*args, **kwargs):
        return nx.DiGraph(f(*args, **kwargs))

    def multigraph(*args, **kwargs):
        return nx.MultiGraph(f(*args, **kwargs))

    def multidigraph(*args, **kwargs):
        return nx.MultiDiGraph(f(*args, **kwargs))

    def custom_graph(*args, create_using=None, **kwargs):
        g = create_using()
        g.update(f(*args, **kwargs))
        return g

    graph.Graph = graph
    graph.DiGraph = digraph
    graph.MultiGraph = multigraph
    graph.MultiDiGraph = multidigraph
    graph.CustomGraph = custom_graph
    graph.edgelist = f
    return graph


def graph_builder(f):
    @wraps(f)
    def edgelist(*args, **kwargs):
        g = f(*args, **kwargs)
        return itertools.ichain(map(tuple, G.nodes.data()), map(tuple, G.edges.data()))

    f.edgelist = edgelist
    f.CustomGraph = f

    # 定义不同类型的图形函数
    def graph(*args, **kwargs):
        return f(*args, create_using=nx.Graph, **kwargs)

    def digraph(*args, **kwargs):
        return f(*args, create_using=nx.DiGraph, **kwargs)

    def multigraph(*args, **kwargs):
        return f(*args, create_using=nx.MultiGraph, **kwargs)

    def multidigraph(*args, **kwargs):
        return f(*args, create_using=nx.MultiDiGraph, **kwargs)

    f.Graph = graph
    f.DiGraph = digraph
    f.MultiGraph = multigraph
    f.MultiDiGraph = multidigraph
    return f

#) 如果我们可以构建一个图形序列生成器对象（类EdgesPlus？），可以作为 create_using 参数提供，可能可以避免使用函数属性语法。 图形构建器代码将其视为图形类，但对象将神奇地处理所有 add_node 和 add_edge 调用，以迭代器的方式产生图形信息，随着构建的进行。 如果结构显示出不实用的早期迹象，用户可以停止构建。 然后可以使用 nx.path_graph, create_using=EdgesPlus) 生成图形序列。 这可能可以通过一些创造性的协程魔法来构建。

讨论

大部分想法来自于 - [ #3036 ] 这是基于以下讨论构建的 - [ #1393 ]

经过一年多偶尔的思考和更少的偶尔提及，大多数核心开发人员认为应保留 create_using 参数。 该提议被重写以保留该功能，并且不开发属性语法，如备选方案部分所示。 属性语法继续用于 edges 和 edges_plus 生成器， edges 用于边缘列表， edges_plus 用于完整的图形序列。

更多讨论导致提议为每种图形类型制作两个函数。 也就是说， nx.path_graph(9) 用于图形， nx.path_graph_generator(9) 用于生成器。 这获得了足够的支持以被包含。不需要属性支持。

剩下的问题： - 如何处理文档 - 如何让装饰器向命名空间添加两个函数。