生成具有最多n个节点的所有未标记树

Question

我想用\$n\或更少的节点来可视化所有未标记的树，而不仅仅是数一数。

第一个想法/尝试:获取所有n-1\$节点树的列表，然后以各种方式向每个树追加一个新的叶，以获得n个节点树的新列表。显然，这个新列表将包含同构重复的a批量。为了解决这个问题，我们开始将n\$树添加到一个新列表中，并且只有当它们与新列表中的任何树不同构时才会这样做。由于不知道图同构问题在多项式时间内是可解的，这使得整个过程的性能变得更加糟糕，因为这个过程将对此类检查执行a批量。

我的问题是，这是否可以更有效地进行，还是以更好的方式进行？

使用networkX和pyplot实现这种思想/尝试的python代码：

""" trees of order N or less will be generated """
N = 9

import networkx as nx

""" return copy of graph with newNode node appended to toNode node """
def leaf_copy(graph, newNode, toNode):
    g = nx.Graph.copy(graph)
    g.add_node(newNode)
    g.add_edge(newNode,toNode)
    return g


from networkx.algorithms import isomorphism

""" get all n+1 node cases out of all n node cases in prevTreeList """
def genNextTreeList(prevTreeList):
    """ one node case """
    if prevTreeList == None or prevTreeList == []:
        g = nx.Graph()
        g.add_node(1)
        return [g]

    """ new loads of n+1 graphs by all possible list appendations """
    """ this will include loads of isomprhic duplicates... """
    nextTreeList = []
    for g in prevTreeList:
        v = len(g.nodes())+1
        for node in g.nodes():
            nextTreeList.append(leaf_copy(g,v,node))

    """ remove isomorphic duplicates """
    """ it will check every graph to be added with all added graphs for isomorphism... """
    nextTreeListClean = []
    for g in nextTreeList:    
        isomorphic = False
        for clean_g in nextTreeListClean:
            i = isomorphism.GraphMatcher(g,clean_g)
            if i.is_isomorphic():
                isomorphic = True
                break
        if not isomorphic:
            nextTreeListClean.append(g)
    return nextTreeListClean


import matplotlib.pyplot as plt

if __name__ == "__main__":

    print(0, "\t", 1)

    G = []
    figure = 0
    for n in range(N):
        G = genNextTreeList(G)

        """ print the number of examples to check if the code is working properly """
        print(n+1, "\t", len(G))

        """ draw and save the plots """
        for g in G:
            figure += 1
            fig = plt.figure(figure)
            plt.title(str(n+1)+'.'+str(G.index(g)+1))
            nx.draw(g, with_labels=False) 
            plt.figure(figure).savefig('plot'+str(figure)+'.png',bbox_inches='tight',dpi=100)
            plt.close(fig)

Answer 1

1.回顾

1. 在Python中，docstring位于函数或类介绍之后。所以，不是：“”返回newNode节点附加到toNode节点的图形副本“def leaf_copy(图，newNode，toNode)：编写类似于: def leaf_copy(图，newNode，toNode)：”“返回附加到toNode的带有newNode的图形副本”。这样做有几个好处。通过交互式解释器中的help函数可以获得文档字符串：>>>帮助( leaf_copy )在__main__：leaf_copy(图形、newNode、toNode)模块中的函数leaf_copy上的帮助，返回附加到toNode的带有newNode的图形副本。此外，一些集成开发环境(例如，PyCharm)可以读取和解释文档字符串，以提供上下文敏感的帮助或生成参考文档。内置的doctest模块可以在文档字符串中自动运行示例。
2. 生成具有一个节点且没有边的平凡图，如:G= nx.Graph() g.add_node(1)，但networkx具有函数trivial_graph，其功能类似。
3. genNextTreeList的规范是：“”从prevTreeList中的所有n个节点案例中获取所有n+1节点案例“，但是只有当prevTreeList是以空列表开始的genNextTreeList迭代结果时，才会出现这种情况。更准确的规范应该是这样的: def genNextTreeList( prevTreeList )：“返回可以通过将一个新节点附加到prevTreeList中任何一个图中的任何节点来构造的图的列表，但如果prevTreeList为空列表或空列表，则返回包含该平凡图的列表。”
4. 它说，在Python的禅宗中，特例不足以打破规则。所以我会放弃这个特例。如果需要的话，调用方可以很容易地传递包含琐碎图的列表。而且，现在应该清楚的是，genNextTreeList不仅对树进行操作。因此，更好的名称和规范应该是这样的: def augmented_graphs(图)：“返回可以通过将一个新节点附加到参数中任何图中的任何节点来构造的图的列表。”
5. 使用isomorphic的for ... else: ...语句，或者使用any或all函数，而不是使用标志C23来确定新的图是否是重复的。
6. 没有必要使用networkx.algorithms.isomorphism.GraphMatcher：您可以直接调用networkx.algorithms.isomorphism.is_isomorphic。
7. genNextTreeList对结果进行了两步构造:第一，构造增广图的列表nextTreeList，第二，消除重复。这些可以通过测试每个新图的同构来组合成一个步骤，就像这样:从networkx.algorithms.isomorphism import is_isomorphic def augmented_graphs(图)：“”返回可以通过将一个新节点附加到参数中任何图中的任何节点来构造的图的列表。“图中的old_graph = []：new_node = max(old_graph.nodes()) +1表示old_graph.nodes()中的节点: new_graph = leaf_copy(old_graph，new_node，node)，如果没有(is_isomorphic(new_graph，g)，对于g)：result.append(new_graph)返回结果
8. 顶层代码做两件事:它生成具有最多N节点的空闲树，并绘制它们。这将更好地分为两个函数，每个函数只做一件事情，例如:从networkx.generators.classic import trivial_graph def free_trees(n)：“返回具有最多n个顶点的空闲树的列表”。结果=tree= for i in range(n - 1)：tree=augmented_graphs(Tree)result.extend(Tree)返回结果

2.替代方法

查看NetworkX手册查找networkx.generators.nonisomorphic_trees.nonisomorphic_trees，它实现了

• Robert Alan Wright，Bruce Richmond，Andrew Odlyzko和Brendan D. Mckay (1986)。“自由树的恒时间生成”。SIAM J. Comput。15:2，第540至548页。

这将在一秒钟内生成16个节点(请参见A000055)上的19,320棵免费树：

>>> from networkx.generators.nonisomorphic_trees import nonisomorphic_trees
>>> from timeit import timeit
>>> timeit(lambda:list(nonisomorphic_trees(16)), number=1)
1.0307372510433197

这里有100棵这样的树：