用Python的networkx库创建一棵树形数据。

Question

我试图创建一棵拥有1111个节点的树，每个节点都有10个子节点，节点1拥有10个子节点（2到11），节点2拥有10个子节点（12到21）以此类推... 即每个节点都有10个子节点，根层级节点有1个节点，它有10个子节点，每个子节点又有10个子节点，每个100个子节点也有10个子节点，因此有1000个叶子节点。该树共有1111个节点。

import networkx as nx
G = nx.Graph()
L1 = [1]
L2 = [x for x in range(2,12)]
L3 = [x for x in range(12,112)]
L4 = [x for x in range(112,1112)]

G.add_node(1)
G.add_nodes_from(L1)
G.add_nodes_from(L2)
G.add_nodes_from(L3)
G.add_nodes_from(L4)

现在我想要使用 G.add_edges_from([(x,y) for x in L1 for y in L2]) 添加边，这对于第一层是可以的，但是对于其他层该怎么做呢？

- Deepak B

Answer 1

你可以通过一行代码轻松实现所需的结果：“开箱即用”。

import networkx as nx

G = nx.balanced_tree(10,10)

- tzelleke

Answer 2

你可以将图的创建推广到任意深度和每个内部节点的任意数量的子节点。

如果从0开始给层级编号，即根节点表示第0层，则每个层级包含n^level个节点。 其中n是每个内部节点的子节点数。

因此，您可以确定每个层级上第一个和最后一个节点的索引。 例如，在n = 10的情况下，第0、1、2、3层的最后一个节点分别为： 10⁰ = 1， 10⁰ + 10¹ = 11， 10⁰ + 10¹ + 10² = 111， 10⁰ + 10¹ + 10² + 10³ = 1111。

要查找给定节点的子节点的索引，您需要获取该层级上最后一个节点的索引并添加一个偏移量。 如果给定节点是该层级上的第一个（最左边）节点，则偏移量为0。 如果它是该层级上的最后一个节点，则偏移量为(n^level - 1) * n。 然后，(n^level - 1)是该层级上的前任节点数。 通常，偏移量的计算方法为[该层级上的前任节点数] * n。

这个概念在代码中表示为offset = ulim + i * n + 1。 我添加了1以便能够从0-(n-1)循环，而不是从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 
---------

- tzelleke

Answer 3

找到了答案

import networkx as nx
G = nx.Graph()
L1 = [1]
L2 = [x for x in range(2,12)]
L3 = [x for x in range(12,112)]
L4 = [x for x in range(112,1112)]


G.add_node(1)
G.add_nodes_from(L1)
G.add_nodes_from(L2)
G.add_nodes_from(L3)
G.add_nodes_from(L4)
G.add_edges_from([(x,y) for x in L1 for y in L2])
temp2 = []
temp = []
temp2.extend(L4)
temp.extend(L3)
for i in range(1,11,1):
    G.add_edges_from([x,temp.pop()] for x in L2)
    G.add_edges_from([y,temp2.pop()] for y in L3)

print G.nodes()
print G.edges()
print G.number_of_nodes()
print G.number_of_edges()
print G.neighbors(1)

try:
    diameter_of_myGraph =nx.shortest_path_length(G)
    #print diameter_of_myGraph
except nx.NetworkXNoPath:
    print 'No path'

try:
    avg_distance_of_myGraph =nx.average_shortest_path_length(G)
    print avg_distance_of_myGraph
except nx.NetworkXNoPath:
    print 'No path'

- Deepak B