Finden der n-Grad-Nachbarschaft eines Knotens

Question

Ich bin neu bei networkx und eigentlich ein bisschen verwirrt, wie man die n-Grad-Nachbarschaft eines Knotens effizient findet. Die n-Grad-Nachbarschaft eines Knotens v_i ist die Menge von Knoten, die genau n hop von v_i entfernt ist. Bei einem gegebenen n muss ich die n-Grad-Nachbarschaft für jeden Knoten im Graphen/Netzwerk finden.

Angenommen, ich habe die folgende Grafik und ich möchte die n = 1 Umgebung von Knoten v1 finden. Das wäre v2 und v3. Als nächstes nehme ich an, ich möchte die n = 2 Umgebung von Knoten v1 finden, dann wäre das 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

Der effizienteste Weg, um die n-Nachbarn eines bestimmten Knotens zu finden ist Tiefensuche zu verwenden: http://en.wikipedia.org/wiki/Depth-first_search. Die folgende Funktion gibt die Nachbarn von Start für alle Entfernungen zurück. Wenn Sie jedoch die n-Nachbarn für alle Knoten finden müssen, wäre die Verwendung dieser Funktion für alle Knoten nicht die effizienteste Lösung. Stattdessen könnte man diese Funktion nur für einen Startknoten in jeder verbundenen Komponente verwenden und die n-Nachbarn für die anderen Knoten relativ zu den Starts berechnen, aber das wäre ziemlich komplizierter.

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

Wenn Sie eine Breitensuche in einem Diagramm durchführen, an einem Wurzelknoten R ausgehend - die Knoten werden in zunehmendem Abstand von r betrachtet.

Daher müssen Sie nur die Ebene der Knoten bei der Durchführung einer BFS verfolgen, siehe http://en.wikipedia.org/wiki/Level_structure für eine gründlichere Diskussion.