CODEWITHSUNDEEP
pythonnetworkx
kspr
kspr

Reputation: 1040

Fastest way to get all edges connected to a set of nodes in a Multi Directed Graph in NetworkX?

Given a large graph G of type nx.MultiDiGraph(), how do I in the most efficient way find all connected nodes?

I have a list with N nodes which I want to find all nodes connected to it.

list_of_nodes = [Node1,Node2,Node3,Node4,...]

I know one way of doing it, which is using a bfs_tree

all_nodes = list(G.nodes())
find_all_connected_edges= []
[find_all_connected_edges.extend(nx.bfs_tree(G, x, reverse=False).edges()) for x in all_nodes]

This works, but is quite slow for large number of N, is there a better way of finding all edges connected to a set of N nodes in a network?

Upvotes: 0

Views: 468

Answers (1)

Sparky05
Sparky05

Reputation: 4892

It depends on which kind of "connected nodes" you want. If you want all nodes which have a path in both ways (u->v and v->u) you can use the concept of strongly connected components. If you don't care about the direction of the edges you can use weakly connected components.

If those concepts match your use case, you can use either strongly_connected_components or weakly_connected_components to retrieve the respective components of all nodes. Then you can build the union of all the components, where at least one node is in, to retrieve the desired set of nodes.

Upvotes: 1

Related Questions