NXEP 3 — 图构建器

作者:

Dan Schult

作者:

Kelly Boothby

状态:

草稿

类型:

标准跟踪

创建日期:

2020-11-27

修订日期:

2023年春季

摘要

NetworkX中的图生成器从`create_using`参数中指定的对象开始创建图。其中许多生成器除了创建要添加到图中的边之外，没有做更多事情。有时我们想要图只是为了生成这些边。或许允许图生成器函数根据`create_using`指定返回`edgelist`或图对象会更好。本NXEP提出了一个图构建器框架，为这一功能提供了友好的用户界面，并提供了装饰器，使开发者能够轻松提供此功能，无论图构建算法需要图还是仅需要边。

动机与范围

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

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

将边生成与图数据结构创建分离，可以说创建了一个更清晰的接口，独立工具可以创造性地组合在一起。在用户需要生成边而不是图的情况下，拥有一个不存储图的边生成器是一个优势。目前还不完全清楚对这项功能的需求有多大。但作为这种方法灵活性的一个例子，`nx.utils.pairwise(nbunch)`调用可以通过`nx.path_graph_generator(nbunch)`来替代。

`create_using`参数是一种机制，用于告诉构建器函数应从哪种图数据结构类开始。将边生成与图构建分离意味着在没有图数据结构类型时，边生成器函数将不再需要它。本NXEP提出了一种方法来提供一个接口，可以在需要时将边生成与图数据结构创建分离，同时在需要时保留熟悉的`create_using`语法用于图类型选择。

图序列

仅包含表示边的节点对的边列表是受限制的。有些图有孤立节点，它们不会出现在任何节点对中。有些图有与节点或边相关的节点或边属性。多重图的每条边都关联有边键，通常是一个三元组 (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)  # graph attributes
        else:
            G.add_node(last_entry)  # node without attributes
    elif N == 2:
        if attrs:
            G.add_node(S[0], **last_entry)  # (node, attrdict)
        else:
            G.add_edge(*S)  # (u, v)
    elif N == 3:
        if attrs:
            G.add_edge(*S[:2], **last_entry)  # (u, v, attrdict)
        else:
            G.add_edge(*S)  # (u, v, edge_key)
    elif N == 4:
        if attrs:
            G.add_edge(*S)  # (u, v, edge_key, attrdict)
        else:
            raise NetworkXInvalidEdgelist(
                "Sequence element has 4 items and last is not hashable: {S}"
            )
    else:
        raise NetworkXInvalidEdgelist(
            "Graph Sequence element has more than 4 items: {S}"
        )

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

用法与影响

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

>>> G = nx.wheel_graph(9)  # same as current code

在不创建图的情况下迭代图序列

>>> 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])

在实例化时或通过`update`方法读取边列表的代码将更改，以允许除了边列表之外还支持图序列。一个额外的基类方法`G.as_sequence()`将为图生成图序列。

开发者将使用装饰器来指示他们的图构建器底层代码是生成边列表还是返回图。

@graph_builder
@py_random_state(4)
def extended_barabasi_albert_graph(n, m, p, q, seed=None):
    # some fancy code that requires we construct G to use graph properties
    # while we decide what edges to add next.
    return G

`@graph_builder`装饰器添加代码以启用例如`nx.extended_barabasi_albert_graph_generator`。

另一个装饰器为编写仅生成边列表的开发者提供处理`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。要使用边列表功能，语法将是`nx.ladder_graph.edges(6)`。

理想情况下，函数和生成器的文档字符串将显示在单个网页上。我们正在探索这种可能性。

向后兼容性

为了减少向后不兼容性，基本的调用结构`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

注意：图构建器底层代码应该接受`create_using`参数才能使此实现工作。我们需要考虑这是否普遍适用，以及如何处理不应与所有四种主要的NetworkX图类一起使用的构建器。

Graph.update将需要处理图序列输入。它目前处理节点对以及多重图的带边键的三元组。应使用类似于上述图序列描述中所示的代码。

开发者使用示例

@node_and_edge_builder
def path_graph(n):
    """an overly simplified path graph implementation"""
    return pairwise(range(n))


@graph_builder
def complete_graph(n, create_using=None):
    """an overly simplified complete graph implementation"""
    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的范围。

实现

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

应特别注意确保只接受所需的图类型，并在不接受时引发适当的错误。

后续步骤包括遍历现有的生成器代码，并将这些代码切换为生成边列表而不是返回图（在适当的情况下）。

备选方案

#) 我们可以让生成器保持原样，并在只需要边列表时承担创建图的成本。大多数时候这不是一个巨大的成本。

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

#) 我们可以提供`nx.path_graph.edges_plus`而不提供`edges`属性。更简单的接口（少一个属性函数）的代价是我们必须确保创建、使用和处理图序列的便捷工具可用。

#) 我们可以提供装饰器，使用属性语法来指定图类型，而不是使用参数`create_using`。因此，`nx.path_graph.MultiGraph(9)`将与`nx.path_graph(9, create_using=nx.MultiGraph)`相同。对于`Graph`、`DiGraph`、`MultiDiGraph`以及可能带有`create_using`关键字参数的`CustomGraph`，情况类似。

本提案的早期版本包含此属性风格的备选方案，作为`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)`用于生成器。这获得了足够的支持被纳入。不需要属性支持。

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