Эффективная идентификация предков / потомков на заданном расстоянии в сети 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]