Эффективно идентифицировать предков/потомков на заданном расстоянии в сетиx

Question

Существует ли функция/метод в сетиx для идентификации всех предков/потомков, находящихся в заданном (необязательно взвешенном) расстоянии?

Например, что-то, что эффективно привело бы к тому же результату, что и функция ниже?

import networkx 
g = networkx.DiGraph() 
edges_with_atts = [(1, 2, {'length':5}), 
       (1, 3, {'length':11}), 
       (2, 4, {'length':4}), 
       (2, 5,{'length':7})] 
g.add_edges_from(edges_with_atts) 

def descendants_within(graph, start_node=1, constraint=10, weight='length'): 
    result = set() 
    for node in networkx.descendants(graph, start_node): 
     if networkx.shortest_path_length(graph, start_node, node, weight) < constraint: 
      result.add(node) 
    return result 

print(descendants_within(g)) 

#set([2, 4]) 

Answer 1

Для некоторых алгоритмов кратчайшего пути NetworkX существует параметр «обрезание». Например, в вашем случае вы можете выполнить вычисление «один источник кратчайшего пути» из вашего исходного узла ко всем другим узлам и ограничить поиск на пути короче, чем заданная длина отсечки. В приведенном ниже примере алгоритм Дейкстры используется для вычисления кратчайших путей для взвешенной сети.

import networkx as nx 
g = nx.DiGraph() 
edges_with_atts = [(1, 2, {'length':5}), 
       (1, 3, {'length':11}), 
       (2, 4, {'length':4}), 
       (2, 5,{'length':7})] 
g.add_edges_from(edges_with_atts) 

lengths = nx.single_source_dijkstra_path_length(g, source=1, weight='length', cutoff=10) 
print(dict(lengths).keys()) 
# [1, 2, 4]