连通分量

此笔记本演示了在图中搜索连通分量。

[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 visualize_graph, visualize_bigraph
from sknetwork.utils.format import bipartite2undirected

图

[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 = visualize_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]:

有向图

[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 = visualize_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 = visualize_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 = visualize_graph(new_adjacency, position[index], names[index])
SVG(image)

[16]:

../../_images/tutorials_topology_connected_components_19_0.svg

二分图

[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 = visualize_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 = visualize_bigraph(new_biadjacency, names_row[index_row], names_col[index_col])
SVG(image)

[24]:

../../_images/tutorials_topology_connected_components_28_0.svg