Efficiently identifying ancestors/descendants within a given distance, in networkx
<p>Is there a function/method in networkx to identify all ancestors/descendants that are within a given (optionally weighted) distance?</p>

<p>For example, something that would efficiently produce the same result as the function below?</p>

<pre class="lang-py prettyprint-override"><code>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) &lt; constraint:
            result.add(node)
    return result

print(descendants_within(g))

#set([2, 4])
</code></pre>

<p>There is a "cutoff" parameter for some of the NetworkX shortest path algorithms.  For example, in your case you can run a "single source shortest path" calculation from your source node to all other nodes and limit the search to paths shorter than a specified cutoff length.  In the example below Dijkstra's algorithm is used to compute the shortest paths for a weighed network.  </p>

<pre><code>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]
</code></pre>

python networkx directed-graph