尋找一個節點的n度鄰域

Question

我是networkx的新手，實際上對如何高效地找到節點的n度鄰域感到困惑。節點v_i的n度鄰居是距離v_i正好n跳的節點集合。給定一個指定的n，我需要找到圖/網絡中每個節點的n度鄰域。

假設我有下面的圖，我想找到節點v1的n = 1鄰域。那將是v2和v3。接下來假設我想要找到節點v1的n = 2鄰域，那麼這將是v4。

Answer 1

import networkx as nx 
G = nx.Graph() 
G.add_edges_from([('v1','v2'),('v2','v4'),('v1','v3')]) 

def neighborhood(G, node, n): 
    path_lengths = nx.single_source_dijkstra_path_length(G, node) 
    return [node for node, length in path_lengths.iteritems() 
        if length == n] 

print(neighborhood(G, 'v1', 1)) 
# ['v2', 'v3'] 
print(neighborhood(G, 'v1', 2)) 
# ['v4'] 

Answer 2

最有效的方法來找到一個給定節點的正鄰居是使用深度優先搜索： http://en.wikipedia.org/wiki/Depth-first_search。下面的函數返回所有距離的start的鄰居。但是，如果您需要爲所有節點查找n鄰居，則對所有節點使用此函數將不是最有效的解決方案。相反，可以將此函數僅用於每個連接組件中的起始節點，並計算相對於起始的其他節點的n鄰居，但這會非常複雜。

import networkx as nx 

def n_neighbor(G, start): 

    # {distance : [list of nodes at that distance]} 
    distance_nodes = {} 

    # nodes at distance 1 from the currently visited ones 
    next_shell = G.neighbors(start) 

    # set of all visited nodes 
    visited=set() 
    visited.add(start) 

    # how fare we are from start 
    distance = 0 

    # until we run out of nodes 
    while len(next_shell) > 0: 

     # this will be the next shell 
     shell_after_this = [] 

     # update distance 
     distance += 1 
     distance_nodes[distance] = [] 

     # update visited and distance_nodes 
     for node in next_shell: 
      visited.add(node) 
      distance_nodes[distance].append(node) 


     # compute shell_after_this 
     for node in next_shell: 
      # add neighbors to shell_after_this 
      # if they have not been visited already 
      for neighbor in G.neighbors(node): 
       if neighbor not in visited: 
        shell_after_this.append(neighbor) 

     # we repeat with the new_shell 
     next_shell = set(shell_after_this) 

    return distance_nodes 


# example 
G=nx.Graph() 

G.add_edge(1,2) 
G.add_edge(1,3) 
G.add_edge(2,3) 
G.add_edge(2,4) 
G.add_edge(3,5) 
G.add_edge(5,17) 
G.add_edge(2,6) 

print n_neighbor(G, 1)  

Answer 3

當在圖上進行廣度優先搜索，起始於根節點r - 被節點在從r的距離的增加考慮。

因此，您只需要在執行BFS時跟蹤節點的級別，請參閱http://en.wikipedia.org/wiki/Level_structure以獲得更全面的討論。