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 connected_components
from sknetwork.visualization import svg_graph, svg_digraph, 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]:
labels = connected_components(adjacency)
[7]:
image = svg_graph(adjacency, position, labels=labels)
SVG(image)
[7]:
../../_images/tutorials_topology_connected_components_9_0.svg

Digraphs

[8]:
graph = painters(metadata=True)
adjacency = graph.adjacency
names = graph.names
position = graph.position
[9]:
labels = connected_components(adjacency)
[10]:
image = svg_digraph(adjacency, position, names, labels)
SVG(image)
[10]:
../../_images/tutorials_topology_connected_components_13_0.svg
[11]:
labels = connected_components(adjacency, connection='strong')
[12]:
image = svg_digraph(adjacency, position, names, labels)
SVG(image)
[12]:
../../_images/tutorials_topology_connected_components_15_0.svg

Bigraphs

[13]:
graph = movie_actor(metadata=True)
biadjacency = graph.biadjacency
names_row = graph.names_row
names_col = graph.names_col
[14]:
# subgraph
k = 5
biadjacency = biadjacency[k:]
names_row = names_row[k:]
[15]:
adjacency = bipartite2undirected(biadjacency)
[16]:
labels = connected_components(adjacency)
[17]:
n_row, _ = biadjacency.shape
labels_row = labels[:n_row]
labels_col = labels[n_row:]
[18]:
image = svg_bigraph(biadjacency, names_row, names_col, labels_row, labels_col)
[19]:
SVG(image)
[19]:
../../_images/tutorials_topology_connected_components_23_0.svg