6

1111 個のノードを持ち、ノード 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])のですが、他のレベルではどうすればよいですか?

4

3 に答える 3

6

1行で「箱から出して」目的の結果を得ることができます。

import networkx as nx

G = nx.balanced_tree(10,10)
于 2012-12-29T11:07:05.160 に答える
4

グラフの作成を、各内部ノードの任意の深さと任意の数の子に一般化できます。

レベルの番号付けを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レベル-1）*nです。
その場合、（nレベル-1）は、そのレベルの先行ノードの数です。
一般に、オフセットは[そのレベルの先行ノードの数]*nとして計算されます。

この概念は、コードでとしてカバーされていますoffset = ulim + i * n + 1。fromの代わりにfromでループできるように
追加しました。10 - (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 
---------
于 2012-10-08T17:28:43.147 に答える
1

答えを導き出した

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'
于 2012-10-08T09:26:59.237 に答える