NXEP 3-图形生成器#

作者: 丹·舒特
作者: 凯利·布斯比
状态: 草稿
类型: 标准轨道
创建: 2020-11-27

摘要#

NetworkX中的图形生成器从 create_using 争论。这些生成器中的许多只是创建边来添加到图中。有时候，我们想要的图形就是生成那些边。更好的做法可能是允许生成器报告 edgelist 或任何标准图形类或自定义类。NXEP为图形生成器提出了一个框架，它允许用户友好地使用这些功能和修饰器，从而使开发人员能够轻松地提供这些功能，无论图形生成器算法需要图形还是只需要边。

动机和范围#

例如，请考虑以下函数 nx.path_graph(nodes, create_using) 。它为所指示的路径创建边，并将它们添加到使用类型创建的空图数据结构中 create_using 。 path_graph 不使用图结构来创建要生成的边，并且可以证明只生成边而根本不涉及数据结构。该参数 create_using 用于指示要使用的图形数据结构的类型。这可以通过将边缘生成器传递给类型构造函数来指示。 nx.MultiDiGraph(nx.path_edges(n)) 而不是 nx.path_graph(n, create_using=nx.MultiDiGraph) 。如果需要，前一种样式允许在不创建任何图形数据结构的情况下使用边。后者在风格上是首选的，因为代码短语的主要思想是创建路径图，这是第一位的。诸如要使用哪种图形类型等细节将在本短语的后面部分指定。

将边生成与图形数据结构创建分离可以使界面更清晰，其中独立的工具可以以创造性的方式组合在一起。就用户需要生成边而不是图的程度而言，拥有不存储图的边生成器是一个优势。目前还不清楚这一功能的需求到底有多大。但是，例如 nx.utils.pairwise 如果我们有了 nx.path_edges(node_iterable) 。

这个 create_using 参数是一种告诉函数从哪类图形数据结构开始的机制。将边生成与图构造分开将意味着边生成函数不再需要用于图数据结构的类型，因为没有类型。NXEP提出了一种方法，可以提供一个界面，在需要时将边生成与图形数据结构创建分开，同时保留一个用户友好的机制，以便在需要时选择图形类型。

建议的更改涉及创建图形或边列表的任何NX函数。建议让这些函数根据用户指示的选择返回任何类型的图形或边缘列表。开发人员选择是生成边还是返回图形更有效。装饰符用于构造周围的代码，以启用其他输出样式。

建议的解决方案是为用户提供返回图形或边列表的图形构建器，同时最大限度地减少开发人员支持两者所需的代码。底层代码可以选择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)

仅包含指示边的节点对的EDGLIST是受限的。有些图有孤立的节点，这些节点不会出现在任何节点对中。某些图具有与节点或边相关联的节点或边属性。多重图具有与每条边相关联的边关键字，通常作为3元组(u，v，ekey)。这个建议建议我们采用下面的边列表协议来描述图(也许有一个比边列表更好的名称)。

边缘列表是一系列容器。容器的长度以及其最后一个元素的Hasable性质决定了容器中包含的信息类型。所有当前使用的图形信息都可以存储在这样的序列中。逻辑如下，其中C表示容器：

	镜头(C)	可哈希(C [-1] )
图表属性：	1	错误
不带属性的节点：	1	真的
具有属性的节点：	2	错误
不带属性的边：	2	真的
具有属性的边：	3	错误
不带属性的多边：	3	真的
具有属性的多边：	4	错误

以下是处理此类边列表并从空图G开始构建图的一些代码：

for C in edgelist:
    if len(C) == 1:
        if not hashable(C[-1]):
            G.graph.update(C[-1])  # C[-1] is a dict of graph attributes
        else:
            G.add_node(C[-1])  # C[-1] is a node
    elif len(C) == 2:
        if not hashable(C[-1]):
            G.add_node(C[0], **C[-1])  # C[-1] is a dict of node attributes
        else:
            G.add_edge(*C)  # C is a node-pair indicating an edge
    elif len(C) == 3:
        if not hashable(C[-1]):
            G.add_edge(*C[:2], **C[-1])  # C -> (u, v, attrdict)
        else:
            G.add_edge(*C)  # C -> (u, v, edge_key)
    elif len(C) == 4:
        assert not hashable(C[-1])
        G.add_edge(*C)  # C -> (u, v, edge_key, attr_dict)
    else:
        raise NetworkXInvalidEdgelist(
            "no container in an edgelist should be larger than 4 objects."
        )

使用和影响#

用户将使用与以前类似的语法构建图形，并增加了灵活性。

创建具有9个轮辐(10个节点)的轮廓图：

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

使用多重DiGraph数据结构构建路径图：

>>> MDG = nx.path_graph.MultiDiGraph([3, 4, 2, 5, 7, 6])
>>> # current code:
>>> MDG = nx.path_graph([3, 4, 2, 5, 7, 6], create_using=MultiDiGraph)

使用NetworkX图类的CustomGraph子类构建星图。

>>> G = nx.star_graph.CustomGraph(9, MyCustomGraph)
>>> # current code:
>>> G = nx.star_graph(9, create_using=MyCustomGraph)

将完整图添加到现有图G：

>>> G.update(nx.complete_graph.edgelist(range(len(G) - 10, 20))

遍历随机生成的图的边，而不存储它。

>>> for u, v in nx.configuration_model_graph.edgelist(deg_sequence):
>>>     process(u, v)

开发人员将使用修饰符来指示他们的图形构建器是否具有从边列表生成的底层代码，或者返回图形。

@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.edgelist 。

对于大多数图表创建者来说，我们只是从一个边缘人那里屈服。

@node_and_edge_builder
def ladder_graph(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.MultiGraph(6) 。请注意， nx.ladder_graph(6) 仍然会像现在一样返回nx.Graph。要利用边列表功能在不构建图的情况下生成边，语法应为 nx.ladder_graph.edgelist(6) 。

向后兼容性#

为了减少向后不兼容，基调用结构 nx.path_graph(9) 其工作方式与当前相同。这个 create_using 参数被移除并替换为调用函数的属性。所以 nx.path_graph(9, nx.DiGraph) 变成了 nx.path_graph.DiGraph(9) 。这个 create_using 参数也可以保留，从而提供更多的向后兼容性，但可能需要提供至少两种方法来创建相同的图形： nx.path_graph(9, create_using=nx.DiGraph) 和 nx.path_graph.DiGraph(9) 。请参见备选方案部分。

由于将图形生成器重命名为图形生成器(以避免与Python的生成器函数混淆)，任何使用全路径调用语法的人例如， nx.generators.path_graph(9) 将需要更改为 nx.path_graph(9) 或 nx.builders.path_graph(9) 尽管后者令人气馁。这一名称的更改与这项提案的主旨无关。但现在似乎是做出这种改变的合理时机。

为了减少开发人员的影响，在开始时，我们可以使用所有当前的图形生成器作为图形生成器，方法是将 @graph_builder 装饰师。大概是为了提高效率，它们中的许多应该被重写以生成边列表，而不是返回图形。但这可以逐步完成，完成后将装饰者切换到 @node_and_edge_builder 。两者都应该返回等价的图形生成器对象。

详细描述#

这可以通过几个装饰物来完成，这可以逐渐被采用--最初用一大块装饰所有现有的发电机 @graph_builder 会立即支持这种记号 nx.complete_graph.edgelist(...) 而不会影响现有代码。后来的发电机可以使用 @node_and_edge_builder 。

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

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

UPDATE需要处理边列表输入。它目前处理多图的节点对和带有边关键字三元组的节点对。应该使用上面Edglist描述中所示的代码。

开发人员用法示例：

@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

实施#

第一个主要步骤是实现两个构建器装饰器。接下来，我们需要更改Graph更新方法、转换函数等，以处理包含隔离节点和数据属性的边列表。第三，我们应该识别任何构建图形或边列表的函数，并对它们进行修饰以使它们成为图形构建器。

应特别注意，确保只接受所需的图形类型，否则会引发相应的错误。

我们应该将生成器目录重命名为Builders，并在需要的地方适当调整文档(包括获得正确规范URL的旧文档)。

后面的步骤包括检查现有的生成器代码，并切换该代码以生成边缘列表，而不是返回图形(在适当的情况下)。

选择#

我们可以让生成器保持原样，并在只需要边缘列表的情况下处理创建图形的成本。在大多数情况下，这并不是一笔巨大的成本。

我们可以使用以下命令将边生成与图形创建分开 nx.DiGraph(nx.path_edgelist(9)) 和不允许 create_using 。

我们可以实施该建议，保留 create_using 参数以实现向后兼容。

讨论#

这里的大部分想法都来自- [#3036] 它的基础是来自于- [#1393]

NXEP 3-图形生成器#

摘要#

动机和范围#

使用和影响#

向后兼容性#

详细描述#

相关工作#

实施#

选择#

讨论#