1

n 個のノードで構成されるグラフ G を通過したいと考えていました。そして、n 番目のノードごとに、その隣接ノードの dict を開きます。最大の数値属性を持つ近傍を見つけます。少なくとも 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)
4

2 に答える 2

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]

これは（ノードの挿入時間を犠牲にして）高速になりますが、挿入時に問題を効果的に解決しています。

于 2012-04-10T00:03:56.387 に答える
0

私は実際に問題を見ていません。すべてのノードを反復処理し、foreach ノードをその隣接ノードを反復処理することで、O(n*m) [n=nodes, m=avg(neighbors)] 操作を実行します。最悪の場合は 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
于 2012-04-09T23:48:50.200 に答える