networkx内の特定の距離内の祖先/子孫を効率的に特定する

Question

networkxには、与えられた（任意選択で重み付けされた）距離内にあるすべての祖先/子孫を特定する関数/メソッドがありますか？

たとえば、以下の関数と同じ結果を効率的に生成するものはありますか？

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の最短パスアルゴリズムには、「cutoff」パラメータがあります。たとえば、ソースノードから他のすべてのノードに「単一ソース最短パス」計算を実行し、指定されたカットオフ長よりも短いパスに検索を限定することができます。以下の例では、ダイクストラのアルゴリズムを使用して、重み付けされたネットワークの最短経路を計算しています。

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]