mptevsion
mptevsion

Reputation: 947

Networkx Graph Type

I want to find a way of getting a "cluster" only if each component in the cluster is connected with every other component (directionally or non-)

This means that for a non-directional graph to get a cluster of A,B,C,D I need to specify 6 connections:

(A,C)(A,B)(A,D)(C,B)(C,D)(B,D)

enter image description here

However, if I specify

(A,C)(A,B)(A,D)(C,B)(C,D)

enter image description here

I want this to only give me a cluster of A,B,C and then D. Because A,B,C are all fully connected whereas D is not.

I can't really get this to work with networkx; my code is below:

from pylab import *
import networkx as nx        
data_edges = [
    ('A','C'), 
    ('A','B'),
    ('A','D'),
    ('C','B'),
    ('C','D')
]

# Add edges
G=nx.Graph()
G.add_edges_from(data_edges)

# Cluster    
connections_nx = nx.biconnected_components(G)
print("Bi-connected")
for con in connections_nx:
    print(con)

#Draw
pos=nx.spring_layout(G)
nx.draw_networkx_nodes(G,pos,node_color='r')
nx.draw_networkx_edges(G,pos)
nx.draw_networkx_labels(G,pos,font_size=16)
plt.axis('off')
show()
plt.clf()

Because this outputs:

{'D', 'A', 'B', 'C'}

Instead of:

{'A', 'B', 'C'} {'A', 'C', 'D'}

Upvotes: 0

Views: 1375

Answers (1)

mptevsion
mptevsion

Reputation: 947

Ah, silly me. The term I was looking for were 'cliques' in networkx:

from pylab import *
import networkx as nx        
data_edges = [
    ('A','C'),
    ('A','B'),
    ('A','D'),
    ('A','E'),
    ('B','C'),
    ('B','E'),
    ('D','E'),
    ('C','F'),
    ('C','G'),
    ('F','G'),
    ('Y','X')

]

# Add edges
G=nx.Graph()
G.add_edges_from(data_edges)

cliq = nx.find_cliques(G)
in_cliq = set()
for c in cliq:
    for x in c:
        in_cliq.add(x)

print(in_cliq)

Upvotes: 1

Related Questions