python - 使用 Networkx Python 构建树形图的更快方法？

Question

有没有更快、更好的方法来构建 Networkx 树。目前，我的代码是

for numb in range(0,len(previous)):
    nodos = list(chunks(current,3))
        for i in range(0,3):
            G.add_edge(previous[numb],nodos[numb][i])

其工作原理如下: 1. 树有 3 个分支(或边)。我有两个数组:

previous = [x,y,z] #These nodes have already been added to the graph
current = [xx,xy,xz, xy,yy,yz, xz,yz,zz] #This nodes need to be added.

理想情况下，我应该执行以下操作:

1. Start with x in previous:
1.1 Pick the first 3 nodes in current (i.e. xx,xy,xz)
1.1.1 Add the nodes-edges: x->xx, x->xy, x->xz

到目前为止我的代码是这样的:

1. Start with x in previous
2. Partition current into chunks of 3 items: [[xx,xy,xz], [xy,yy,yz], [xz,yz,zz]]
3. Loop through all the nodes in these chunks:
4. Add x->xx, loop again, add x->xy... etc.

我的实现效率极低。您将如何有效地做到这一点？谢谢

Answer 1

您可以使用 https://github.com/networkx/networkx/blob/master/networkx/generators/classic.py#L50 中的辅助函数

def _tree_edges(n,r):
    # helper function for trees
    # yields edges in rooted tree at 0 with n nodes and branching ratio r
    nodes=iter(range(n))
    parents=[next(nodes)] # stack of max length r
    while parents:
        source=parents.pop(0)
        for i in range(r):
            try:
                target=next(nodes)
                parents.append(target)
                yield source,target
            except StopIteration:
                break

print list(_tree_edges(13,3))
#[(0, 1), (0, 2), (0, 3), (1, 4), (1, 5), (1, 6), (2, 7), (2, 8), (2, 9), (3, 10), (3, 11), (3, 12)]
import networkx as nx
G = nx.Graph(_tree_edges(13,3))

如果您想要整数以外的节点，您可以重新标记或在输入中指定它们，如下所示

def _tree_edges(nodes,r):
    # helper function for trees
    # yields edges in rooted tree with given nodes and branching ratio r
    nodes=iter(nodes)
    parents=[next(nodes)] # stack of max length r
    while parents:
        source=parents.pop(0)
        for i in range(r):
            try:
                target=next(nodes)
                parents.append(target)
                yield source,target
            except StopIteration:
                break

nodes = list('abcdefghijklm')
print list(_tree_edges(nodes,3))