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.

What is the language you use? Python? You should add the tag. — DrakaSAN, Aug 01 '15 at 17:54
Thanks for editing it, I am using Python. The graph is acyclic. — Gabriella Lapesa, Aug 01 '15 at 18:30

Joel · Accepted Answer · 2015-08-02T06:00:27.550

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

Alternatively, you can use `nx.descendants` to find reachable nodes. See https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.dag.descendants.html — JanLikar, Oct 12 '21 at 23:12

score 1 · Answer 2 · answered Aug 01 '15 at 18:15

1

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).

answered Aug 01 '15 at 18:15

Roy Shahaf

494
5
10

So you mean, not using the predefined functions in networkx? – Gabriella Lapesa Aug 01 '15 at 18:38
I'm not familiar with the predefined functions in networkx, it's possible that using a combination of existing functions (or, if it exists, a dedicated function fitting your needs) you could reach the necessary improvement. But clearly your current approach is quite straight forward which means that a. it works (you don't have to work hard to prove that) but b. it's slow. – Roy Shahaf Aug 01 '15 at 19:16
Thanks a lot for your suggestion. I'll try to implement it myself and compare the speed, but I guess the built in functions from the package do a better job than my code – Gabriella Lapesa Aug 03 '15 at 15:25

score 1 · Answer 3 · edited May 23 '17 at 12:06

As Roy Shahaf says, you might be able to build a constructive algorithm that doesn't lose work you already did. Also, since the graph is directed, if you do a topological sort on the graph first, you have an immediate optimization of an improvement of 50%, because the only nodes that you can possibly reach are the ones that come after the starting node. I posted an earlier answer (not using nx) that does a topo-sort and then finds all the distances from a node to every other node here

Note that for clarity, that answer wasn't optimized at all (except for the initial toposort). It does the equivalent of for n1 in G for n2 in G, but as I said, you could cut it down if you put your nodes in a list and then index through the entire list for your first node, and index through all the nodes in the list after the first one for the second one, e.g. (nlist[i], nlist[j]) for i in range(len(nlist)) for j in range(i+1, len(nlist))

Find all nodes connected to n

3 Answers3