{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Connected components"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This notebook illustrates the search for [connected components](https://en.wikipedia.org/wiki/Component_(graph_theory)) in graphs."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"from IPython.display import SVG"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"ExecuteTime": {
"end_time": "2019-07-15T12:29:50.554431Z",
"start_time": "2019-07-15T12:29:50.414075Z"
}
},
"outputs": [],
"source": [
"import numpy as np"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [],
"source": [
"from sknetwork.data import karate_club, painters, movie_actor\n",
"from sknetwork.topology import get_connected_components, get_largest_connected_component\n",
"from sknetwork.visualization import visualize_graph, visualize_bigraph\n",
"from sknetwork.utils.format import bipartite2undirected"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Graphs"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"ExecuteTime": {
"end_time": "2019-07-15T12:29:51.261957Z",
"start_time": "2019-07-15T12:29:51.249107Z"
}
},
"outputs": [],
"source": [
"graph = karate_club(metadata=True)\n",
"adjacency = graph.adjacency\n",
"position = graph.position"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [],
"source": [
"# subgraph\n",
"k = 15\n",
"adjacency = adjacency[:k][:,:k]\n",
"position = position[:k]"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [],
"source": [
"# connected components\n",
"labels = get_connected_components(adjacency)"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"ExecuteTime": {
"end_time": "2019-07-15T12:29:55.341520Z",
"start_time": "2019-07-15T12:29:55.026465Z"
},
"scrolled": true
},
"outputs": [
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"image = visualize_graph(adjacency, position, labels=labels)\n",
"SVG(image)"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [],
"source": [
"# largest connected component\n",
"new_adjacency, index = get_largest_connected_component(adjacency, return_index=True)"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"14"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"len(index)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Directed graphs"
]
},
{
"cell_type": "code",
"execution_count": 34,
"metadata": {
"ExecuteTime": {
"end_time": "2019-07-15T12:29:58.542147Z",
"start_time": "2019-07-15T12:29:58.529699Z"
}
},
"outputs": [],
"source": [
"graph = painters(metadata=True)\n",
"adjacency = graph.adjacency\n",
"names = graph.names\n",
"position = graph.position"
]
},
{
"cell_type": "code",
"execution_count": 35,
"metadata": {},
"outputs": [],
"source": [
"# weak connected components\n",
"labels = get_connected_components(adjacency)"
]
},
{
"cell_type": "code",
"execution_count": 36,
"metadata": {
"scrolled": true
},
"outputs": [
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"execution_count": 36,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"image = visualize_graph(adjacency, position=position, names=names, labels=labels)\n",
"SVG(image)"
]
},
{
"cell_type": "code",
"execution_count": 37,
"metadata": {},
"outputs": [],
"source": [
"# strong connected components\n",
"labels = get_connected_components(adjacency, connection='strong')"
]
},
{
"cell_type": "code",
"execution_count": 38,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"execution_count": 38,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"image = visualize_graph(adjacency, position, names, labels)\n",
"SVG(image)"
]
},
{
"cell_type": "code",
"execution_count": 39,
"metadata": {},
"outputs": [],
"source": [
"# largest connected component\n",
"new_adjacency, index = get_largest_connected_component(adjacency, connection='strong', return_index=True)"
]
},
{
"cell_type": "code",
"execution_count": 40,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"execution_count": 40,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"image = visualize_graph(new_adjacency, position[index], names[index])\n",
"SVG(image)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Bipartite graphs"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {},
"outputs": [],
"source": [
"graph = movie_actor(metadata=True)\n",
"biadjacency = graph.biadjacency\n",
"names_row = graph.names_row\n",
"names_col = graph.names_col"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {},
"outputs": [],
"source": [
"# subgraph\n",
"k = 5\n",
"biadjacency = biadjacency[k:]\n",
"names_row = names_row[k:]"
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {},
"outputs": [],
"source": [
"labels = get_connected_components(biadjacency, force_bipartite=True)"
]
},
{
"cell_type": "code",
"execution_count": 27,
"metadata": {},
"outputs": [],
"source": [
"n_row, _ = biadjacency.shape\n",
"labels_row = labels[:n_row]\n",
"labels_col = labels[n_row:]"
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"execution_count": 28,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"image = visualize_bigraph(biadjacency, names_row, names_col, labels_row, labels_col)\n",
"SVG(image)"
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {},
"outputs": [],
"source": [
"# largest connected component\n",
"new_biadjacency, index = get_largest_connected_component(biadjacency, force_bipartite=True, return_index=True)"
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {},
"outputs": [],
"source": [
"n_row, n_col = new_biadjacency.shape\n",
"index_row = index[:n_row]\n",
"index_col = index[n_row:]"
]
},
{
"cell_type": "code",
"execution_count": 32,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"execution_count": 32,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"image = visualize_bigraph(new_biadjacency, names_row[index_row], names_col[index_col])\n",
"SVG(image)"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.9.13"
},
"toc": {
"base_numbering": 1,
"nav_menu": {},
"number_sections": true,
"sideBar": true,
"skip_h1_title": false,
"title_cell": "Table of Contents",
"title_sidebar": "Contents",
"toc_cell": false,
"toc_position": {},
"toc_section_display": true,
"toc_window_display": false
}
},
"nbformat": 4,
"nbformat_minor": 2
}