CODEWITHSUNDEEP
pythongraphnetworkx
Ahmed Al-haddad
Ahmed Al-haddad

Reputation: 833

Easy method to find minimum number of nodes that connect to each node in a graph

I have an undirected network of nodes connected to each other in a mesh fashion (i.e degree of each node is >= 2). I am trying to find a way to find the minimum number of nodes that connect to the other nodes in the network.

For example, if I have 10 nodes in my graph, and one of the nodes is connected to all of the other nodes, then I can directly say that node is the one connects all my graph and the minimum number of nodes to cover the connectivity of graph is 1.

But usually that's not the case as I need to find the other nodes manually. I am thinking that I can use the highest degree node (x for example) as the source to find the shortest paths to the other nodes using nx.shortest_path(G, x). Then I can iterate over the shortest paths to find the other nodes. But this method is tedious and I am wondering if anyone got any other suggestion using the tools available in networkx to solve this optimally.

Upvotes: 1

Views: 1231

Answers (1)

Ahmed Al-haddad
Ahmed Al-haddad

Reputation: 833

As it is mentioned here: https://networkx.github.io/documentation/stable/reference/algorithms/dominating.html

A dominating set for a graph with node set V is a subset D of V such that every node not in D is adjacent to at least one member of D 

 D= nx.dominating_set(G, x) # the node source here is optional
 print(D)

Upvotes: 1

Related Questions