幅優先範囲検索エラーのリスト範囲外エラーのエラー

Question

私は、指定されたノードからネットワーク内のすべてのノードに最短距離の配列を返し、次にこれらの最短距離の行列を作成する幅優先探索関数を作成しています。すべてのノード。小規模なネットワークではうまく動作しますが、大規模なネットワークに拡張しようとすると、リストインデックスが範囲外であるというエラーが発生します。エラーが

def bfs_short(G,node): 
    queue=[] 
    visit=[] 
    parent=[] 
    for n in range(len(G)): 
     visit.append(False) 
     parent.append(None) 
    queue.append(node) 
    visit[node]=True 
    while len(queue)!=0: 
     current=queue.pop(0) 
     for a in G[current]: 
      if visit[a]==False: 
       visit[a]=True 
       parent[a]=current 
       queue.append(a) 
    distances=[] 
    for n in range(len(G)): 
     distances.append(0) 
    for n in range(len(G)): 
     dist=0 
     current=n 
     while parent[current]!=None: 
      dist=dist+1 
      current=parent[current] 
     distances[n]=dist 
    return distances 

    V=len(G.keys()) 
    dist_matrix=np.empty([V, V]) 
    keys = G.keys() 
    for k in keys: 
     dist_matrix[k,:]=bfs_short(G,k) 
    return dist_matrix 

ある

My機能がされています

<ipython-input-296-b89665c85020> in bfs_short(G, node) 
    11   current=queue.pop(0) 
    12   for a in G[current]: 
---> 13    if visit[a]==False: 
    14     visit[a]=True 
    15     parent[a]=current 

IndexError: list index out of range 

はるかに大きい使うときは、この小さなadjaceny行列

G_dict2 = {0:[1,3], 1:[0,2,5], 2:[1,3], 3:[0,2], 4:[1,2,3], 5:[0,4], 6:[3,4]} 

で正常に動作します。しかし、それはエラーになりますネットワーク。ネットワークは大きすぎて（〜2,000ノード）実際にここに貼り付けることはできますが、小さな抜粋が何かを照らすのに役立つかどうかはわかりません。

network= {0: [1, 2], 
1: [6, 0, 7], 
2: [8, 9, 10], 
3: [4, 1, 5], 
4: [11, 12, 13], 
5: [14, 15, 16], 
6: [17, 1, 18], 
7: [19, 20, 1], 
8: [21, 2, 3], 
9: [2, 22, 23], 
10: [24, 2, 25], 
11: [4], 
12: [4, 13, 26], 
13: [12, 4, 27], 
14: [28, 29, 30], 
15: [31, 5, 32], 
16: [33, 5], 
17: [6, 34, 35], 
18: [36, 37, 38], 
19: [7, 39, 40], 
20: [41, 7, 42],} 

大規模なネットワークでこのエラーを引き起こす原因に気づいている人はいますか？

ありがとうございます！

Answer 1

このエラーは、len（G_dict2）以上の値を持つ隣接行列にノードがある場合にのみ発生する可能性があります。

これは、G_dict2の最大のキーよりも大きい隣接リストにノードがある場合（例：ネットワーク内の最大ノードが2017であるが、リスト21: [2018]が存在する場合、または隣接行列に欠損ノードがある場合、つまり、あるノードiのエントリがない場合、i < len（G_dict2）です。この場合、訪問した時間も長くなります可能な最大ノード値の略です。次でこれをテストすることができます。

from itertools import chain 
assert max(chain(*G_dict2.values())) < len(G_dict2), "You got an out of range because G_dict2 has a node with id {} which is larger than the range of visit (0, {})".format(max(chain(*G_dict2.values())), len(G_dict2) - 1) 
assert max(G_dict2.keys()) < len(G_dict2), "You got an out of range because visit is constructed by iterating over the *number* of keys in the dict, but the node {} is not in the range (0, len(G_dict2)-1) = (0, {})".format(max(G_dict2.keys()), len(G_dict2)-1) 

あなたは、すべての隣接リスト内の最大値に基づいて訪問した初期化することによって、問題を解決することができ、例えば：

from itertools import chain 
visit = [False]*(max(chain.from_iterable(G.values()))+1) 
parent = [None]*(max(chain.from_iterable(G.values()))+1)