Connected components

This notebook illustrates the search for connected components in graphs.

[1]:
from IPython.display import SVG
[2]:
import numpy as np
[3]:
from sknetwork.data import karate_club, painters, movie_actor
from sknetwork.topology import get_connected_components, get_largest_connected_component
from sknetwork.visualization import svg_graph, svg_bigraph
from sknetwork.utils.format import bipartite2undirected

Graphs

[4]:
graph = karate_club(metadata=True)
adjacency = graph.adjacency
position = graph.position
[5]:
# subgraph
k = 15
adjacency = adjacency[:k][:,:k]
position = position[:k]
[6]:
# connected components
labels = get_connected_components(adjacency)
[7]:
image = svg_graph(adjacency, position, labels=labels)
SVG(image)
[7]:
../../_images/tutorials_topology_connected_components_9_0.svg
[8]:
# largest connected component
new_adjacency, index = get_largest_connected_component(adjacency, return_index=True)
[9]:
len(index)
[9]:
14

Directed graphs

[10]:
graph = painters(metadata=True)
adjacency = graph.adjacency
names = graph.names
position = graph.position
[11]:
# weak connected components
labels = get_connected_components(adjacency)
[12]:
image = svg_graph(adjacency, position=position, names=names, labels=labels)
SVG(image)
[12]:
../../_images/tutorials_topology_connected_components_15_0.svg
[13]:
# strong connected components
labels = get_connected_components(adjacency, connection='strong')
[14]:
image = svg_graph(adjacency, position, names, labels)
SVG(image)
[14]:
../../_images/tutorials_topology_connected_components_17_0.svg
[15]:
# largest connected component
new_adjacency, index = get_largest_connected_component(adjacency, connection='strong', return_index=True)
[16]:
image = svg_graph(new_adjacency, position[index], names[index])
SVG(image)
[16]:
../../_images/tutorials_topology_connected_components_19_0.svg

Bipartite graphs

[17]:
graph = movie_actor(metadata=True)
biadjacency = graph.biadjacency
names_row = graph.names_row
names_col = graph.names_col
[18]:
# subgraph
k = 5
biadjacency = biadjacency[k:]
names_row = names_row[k:]
[19]:
labels = get_connected_components(biadjacency, force_bipartite=True)
[20]:
n_row, _ = biadjacency.shape
labels_row = labels[:n_row]
labels_col = labels[n_row:]
[21]:
image = svg_bigraph(biadjacency, names_row, names_col, labels_row, labels_col)
SVG(image)
[21]:
../../_images/tutorials_topology_connected_components_25_0.svg
[22]:
# largest connected component
new_biadjacency, index = get_largest_connected_component(biadjacency, force_bipartite=True, return_index=True)
[23]:
n_row, n_col = new_biadjacency.shape
index_row = index[:n_row]
index_col = index[n_row:]
[24]:
image = svg_bigraph(new_biadjacency, names_row[index_row], names_col[index_col])
SVG(image)
[24]:
../../_images/tutorials_topology_connected_components_28_0.svg