返回节点邻域中的最大节点

我希望能够通过由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)

来源

2012-04-09 user1320502

我实在不明白的问题，你会做一个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

来源

2012-04-09 23:48:50 luke14free

如果您维护按数字属性排序的列表中的邻居，则问题将变为O（n）。尽管添加节点的时间是O（nlogn）。 – 2012-04-10 00:07:43

谢谢卢克，即时通讯新的Python，所以即时通讯代码尝试。现在它给我的输出并不像我预期的那样，即对于G中的20个节点，它给我的比列表长20个元素多得多。我需要对此进行研究...... – user1320502 2012-04-10 00:19:38

我想解决这样的问题，用正确的数据结构：

#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-10 00:03:56

返回节点邻域中的最大节点

回答

相关问题