您可以将图的创建概括为任意深度和任意数量的每个内部节点的子节点。
如果您从 0 开始对级别进行编号(即根节点代表级别 0),则每个级别包含 n 个级别节点。
n 是每个内部节点上的子节点数。
因此,您可以识别每个级别上第一个和最后一个节点的索引。
例如,在 n = 10 的情况下,级别 0、1、2、3 的最后一个节点是
10 0 =
1、10 0 + 10 1 = 11、10
0 + 10 1 + 10 2 = 111、10 0 +
10 1 + 10 2 + 10 3 = 1111。
要查找给定节点的子节点索引,您需要获取该级别上最后一个节点的索引并添加偏移量。
如果给定节点是该级别上的第一个(最左侧)节点,则偏移量为 0。
如果它是该级别上的最后一个节点,则偏移量为 (n level - 1) * n。
然后 (n level - 1) 是该级别上的前驱节点的数量。
通常,偏移量计算为 [该级别上的前驱节点数] * n。
这个概念在代码中被覆盖为offset = ulim + i * n + 1
.
我添加1
了能够在以下循环0 - (n-1)
而不是 from中循环1 - n
。
import networkx as nx
n = 10 # the number of children for each node
depth = 3 # number of levels, starting from 0
G = nx.Graph()
G.add_node(1) # initialize root
ulim = 0
for level in range(depth): # loop over each level
nl = n**level # number of nodes on a given level
llim = ulim + 1 # index of first node on a given level
ulim = ulim + nl # index of last node on a given level
for i in range(nl): # loop over nodes (parents) on a given level
parent = llim + i
offset = ulim + i * n + 1 # index pointing to node just before first child
for j in range(n): # loop over children for a given node (parent)
child = offset + j
G.add_node(child)
G.add_edge(parent, child)
# show the results
print '{:d}-{:d}'.format(parent, child),
print ''
print '---------'
这是输出depth = 3
:n = 3
1-2 1-3 1-4
---------
2-5 2-6 2-7
3-8 3-9 3-10
4-11 4-12 4-13
---------
5-14 5-15 5-16
6-17 6-18 6-19
7-20 7-21 7-22
8-23 8-24 8-25
9-26 9-27 9-28
10-29 10-30 10-31
11-32 11-33 11-34
12-35 12-36 12-37
13-38 13-39 13-40
---------