Find all nodes connected to n

Question

I need to find all the shortest paths between every pair of node in my directed graph. What I am doing is:

for i in A.nodes()
    for y in A.nodes()
        paths = nx.all_shortest_paths(G,i,y)

But this is very slow, I guess, because in the graph there are a lot of nodes that have no connection to i anyway. Is there a way to optimize that process? I am already taking care that nodes with no possibility to be connected to others do not end up in A.

Answer 1

There's a command built in: single_source_shortest_path_length(G, source) gives you the shortest paths between the source and each reachable node.

import networkx as nx
G=nx.DiGraph()
G.add_edges_from([(1,2), (2,3), (3,4), (1,5), (2,5), (6,7)]) #6,7 not reachable from 1
nx.single_source_shortest_path(G,1)
>{1: [1], 2: [1, 2], 3: [1, 2, 3], 4: [1, 2, 3, 4], 5: [1, 5]}

The question title suggests you just want to know the reachable nodes rather than the path. In that case, use a depth first or breadth first search. The documentation is here. For example: dfs_postorder_nodes(G, source=None) gives an iterator for the nodes reachable from source. The specific order they appear is a depth first search postorder.

for reachable_node in nx.dfs_postorder_nodes(G,source=1):
   print reachable_node
>4
>3
>5
>2
>1

Answer 2

You could try a constructuive algorithm for finding all the shortest paths between all pairs of nodes, instead of iterating over all the pairs and getting the shortest paths for each pair (which will not use past knowledge each time).