1

我希望通过由 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)
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)。此外，您还有一个缩进问题，因为您的大部分代码都在“继续”语句之后，所以它不会被执行。

代码示例

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 回答