CODEWITHSUNDEEP
pythongraphnetworkxgraph-theory
peachnuts
peachnuts

Reputation: 103

Get networkx subgraph containing a certain number of nodes

I have a networkx DiGraph and I want to extract the subgraph that contains a certain number of nodes. For example, the Digraph is 0-1-2-3-4-5. I want to obtain all the subgraphs that contains 3 nodes. The result should be: 0-1-2, 1-2-3, 2-3-4, 3-4-5. How can I do that?

Upvotes: 0

Views: 2994

Answers (1)

Timus
Timus

Reputation: 11321

I'm not completely sure if I understand correctly: Your example implies that you only want connected subgraphs? In a directed graph there's more than one kind of connectivity (weak and strong). So you have to decide which one you're looking for.

This might work:

import networkx as nx
from itertools import combinations

# The graph in your example (as I understand it)
G = nx.DiGraph((i, i+1) for i in range(5))

num_of_nodes = 3 # Number of nodes in the subgraphs (here 3, as in your example)
subgraphs = [] # List for collecting the required subgraphs
for nodes in combinations(G.nodes, num_of_nodes):
    G_sub = G.subgraph(nodes) # Create subgraph induced by nodes
    # Check for weak connectivity
    if nx.is_weakly_connected(G_sub):
        subgraphs.append(G_sub)

combinations(G.nodes, num_of_nodes) iterates over all unique combinations of num_of_nodes many nodes from G.

The selected subgraphs are exactly the ones you mentioned:

print([H.nodes for H in subgraphs])
print([H.edges for H in subgraphs])

shows

[NodeView((0, 1, 2)), NodeView((1, 2, 3)), NodeView((2, 3, 4)), NodeView((3, 4, 5))]
[OutEdgeView([(0, 1), (1, 2)]), OutEdgeView([(1, 2), (2, 3)]), OutEdgeView([(2, 3), (3, 4)]), OutEdgeView([(3, 4), (4, 5)])]

If your graph is

G = nx.DiGraph([(i, i+1) for i in range(5)] + [(i+1, i) for i in range(5)])

and you're looking for strong connectivity then you have to use

...
    # Check for strong connectivity
    if nx.is_strongly_connected(G_sub):
        ...

(The usual warning: G.subgraph() only gives you a view.)

Upvotes: 3

Related Questions