ノードの近隣から最大のノードを返します

Question

私はn個のノードで構成されたグラフGを使いたいと考えていました。そして、各n番目のノードについて、その隣人の辞書を開きます。どのネイバーが最大の数値属性を持っているかを調べる。少なくとも100人の隣人が存在し得る。そしてすなわち

[node,biggestneighbor] 
[node,biggestneighbor] 
[node,biggestneighbor] 

このようなノードの外観の属性データ、各ノードのリストとその最大の隣人を返す：

G.node[0] 

{'type': 'a', 'pos': [0.76, 0.11]} 

と私が興味を持って属性がある

G.node[0]['pos'][0] 

0.76 

これは誰でも知っていますか？そうでない場合、開始ロジックは良い出発点のように見えますか？またはよりスマートな人ははるかに良いアイデアを持っていますか？

def thebiggestneighbor(G,attribute,nodes=None): 

    if nodes is None: 
     node_set = G 
    else: 
     node_set = G.subgraph(nodes) 
    node=G.node 
    for u,nbrsdict in G.adjacency_iter(): 
     if u not in node_set: 
      continue 
      for v,eattr in nbrsdict.items(): 
       vattr=node[v].get(attribute,None) 
      # then something like this but for many nodes. probably better subtraction 
      # of all nodes from each other and which one yeilds the biggest numner 
      # 
      # if x.[vattra] > x.[vattrb] then 
      #  a 
      # elif x.[vattra] < x.[vattrb] then 
      #  b 

      yield (u,b) 

Answer 1

私は本当にあなたがO（n個の* m）を行うだろう、問題が表示されていない[N =ノード、M =平均（ネイバー）]以上の反復すべてのノードとのforeachノードを反復処理による操作その隣人。最悪の場合、それはO（n^2）です。また、コードの大部分が「continue」ステートメントの後にあるので、インデントの問題があるため、実行されることはありません。

コード例

node=G.node 
output=[] 
for u,nbrsdict in G.adjacency_iter(): 
    if u not in node_set: 
     continue 
    max={'value':0,'node':None} 
    for v,eattr in nbrsdict.items(): 
     vattr=node[v].get(attribute,None) 
     if vattr>max['value']: 
      max={'value':vattr,'node':node} 
    output.append((node,max['node'])) 
return output 

Answer 2

私は右のデータ構造と、このような問題を解決するように：その後、また

#nodes = [ (att_n, [(att_n, n_idx).. ]), ... ] where each node is known by its index 
#in the outer list. Each node is represented with a tuple: att_n the numeric attribute, 
#and a list of neighbors. Neighbors have their numeric attribute repeated 
#eg. node 1 has neighbors 2, and 3. node 2 has neighbor 1 and 4, etc..: 
nodes = [ (192, [ (102, 2), (555, 3)]), 
      (102, [ (192, 1), (333, 4) ]), 
      (555, [ (192, 1),]), ... 
    ] 
#then to augment nodes so the big neighbor is visible: 
nodesandbigneighbor=[ (att_n, neighbors, max(neighbors)) for att_n, neighbors in nodes] 

あなたが高いと低い数値属性から隣接リストのソート順序を維持する場合は、次に行うことができます：

nodesandbigneighbor=[ (att_n, neighbors, neighbors[-1]) for att_n, neighbors in nodes] 

これは、ノード挿入時）、挿入時に問題を効果的に解決しています。