CODEWITHSUNDEEP
pythonroutesnetworkxdijkstra
wfgeo
wfgeo

Reputation: 3098

Verify if all target nodes are reachable from at least one source node in Python NetworkX

I'm wondering what the most efficient method would be to verify that all target nodes from a set T are reachable from at least one source node S in Python's NetworkX library.

To me, it should be a simple many-to-many Dijkstra function call, where S is the source node list input and T is the target node list input. I could then verify that the returned value indicates that at least one of the routings was a success. This is how I would approach the problem using PostgreSQL's pgRouting extension, for those that may be familiar with that:

pgr_dijkstra(edges_sql, start_vids, end_vids)

However, it seems from the documentation that a function where both the sources and targets are lists does not exist. The closest I could find is multi_source_dijkstra or all_pairs_dijkstra.

I feel that multi_source_dijkstra is insufficient because I cannot specify a list of multiple target nodes as input, and that all_pairs_dijkstra is too much because I don't want to waste time testing connectivity between source nodes or between target nodes. Furthermore, I am fully expecting my graph to have gaps within itself, and I just want to test the original condition - that all target nodes are just reachable from at least one source node.

I'm sure that something can be cobbled together the multi_source_dijkstra function, but I want to this be as efficient as possible so I am hoping that I am just missing an obvious implementation that would do what I want most efficiently.

EDIT: Image for @abc. The red/yellow, red/pink lines and green lines represent a subgraph which I am using in the DFS or BFS algorithm. This configuration is returning True, claiming that all the red dots (targets) are reachable from the green dot (source).

enter image description here

Upvotes: 1

Views: 809

Answers (1)

abc
abc

Reputation: 11929

Why using a shortest path algorithm such as Dijkstra's one?
If your goal is to check whether all target nodes are reachable from at least one source node you only need a graph traversal algorithm (e.g., bfs and dfs).

S = {1,2}
T = {3,4}
g = nx.fast_gnp_random_graph(6, 0.3, directed=True)

# True if all the nodes of T are reachable from at least a node in S
any(T < set(nx.bfs_tree(g,s).nodes()) for s in S)

Upvotes: 2

Related Questions