{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Components"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In this notebook we present some algorithms to analyze the connectivity properties of a graph.\n",
"NetworKit's components classes are grouped in the [networkit.components](https://networkit.github.io/dev-docs/python_api/components.html) module. They all have a `run` method that must be called after the chosen algorithm has been initialised. The first step is to import Networkit."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"import networkit as nk"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Connected Components"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The [ConnectedComponents(G)](https://networkit.github.io/dev-docs/python_api/components.html?highlight=connected#networkit.components.ConnectedComponents) of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph. The constructor expects a [networkit.Graph](https://networkit.github.io/dev-docs/python_api/networkit.html?highlight=graph#networkit.Graph). \n",
"\n",
"The following function determines the connected components of a disconnected graph:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Read graph\n",
"G = nk.readGraph(\"../input/hep-th.graph\", nk.Format.METIS)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Initialse algorithm\n",
"cc = nk.components.ConnectedComponents(G)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Run algorithm\n",
"cc.run()\n",
"print(\"number of components \", cc.numberOfComponents())"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Get components as unordered sets of nodes\n",
"v = 0\n",
"print(\"component of node \", v , \": \" , cc.componentOfNode(v))\n",
"\n",
"# Get all nodes in in v's component\n",
"print(cc.getComponents()[0])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Additionally, the connected components class has a function [extractLargestConnectedComponent(G, compactGraph=False)](https://networkit.github.io/dev-docs/python_api/components.html?highlight=extract#networkit.components.ConnectedComponents.extractLargestConnectedComponent) which constructs a new graph that contains only the nodes inside the largest connected component. It expects an undirected graph as well. If `compactGraph` is set to true the node ids of the output graph will be renumbered; otherwise they will not be changed."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"newGraph = cc.extractLargestConnectedComponent(G, True)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The new graph containing only the nodes inside the largest the connected component can then be manipulated like any other graph."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Biconnected Components"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"A [BiconnectedComponent(G)](https://networkit.github.io/dev-docs/python_api/components.html?highlight=biconnected#networkit.components.BiconnectedComponents) is a maximal biconnected subgraph of an undirected graph G. A biconnected graph is a connected and nonseparable graph, meaning that if any one vertex were to be removed, the graph will remain connected. The constructor expects an undirected [networkit.Graph](https://networkit.github.io/dev-docs/python_api/networkit.html?highlight=graph#networkit.Graph)."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Read graph\n",
"G = nk.readGraph(\"../input/karate.graph\", nk.Format.METIS)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Initialse algorithm\n",
"bicc = nk.components.BiconnectedComponents(G)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Run algorithm\n",
"bicc.run()\n",
"print(\"number of components: \", bicc.numberOfComponents())"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Get components as unordered sets of nodes\n",
"print(bicc.getComponents())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Weakly Connected Components"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"A [WeaklyConnectedComponent(G)](https://networkit.github.io/dev-docs/python_api/components.html?highlight=weakly#networkit.components.WeaklyConnectedComponents) is a maximal subgraph of a directed graph such that for every pair of vertices u, v in the subgraph, there is an undirected path from u to v and a directed path from v to u. The constructor expects a directed [networkit.Graph](https://networkit.github.io/dev-docs/python_api/networkit.html?highlight=graph#networkit.Graph)."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Read graph\n",
"G = nk.readGraph(\"../input/jazz2_directed.gml\", nk.Format.GML)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"wcc = nk.components.WeaklyConnectedComponents(G)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"wcc.run()\n",
"print(\"number of components: \", wcc.numberOfComponents())"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Get components as unordered sets of nodes\n",
"print(wcc.getComponents())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Strongly Connected Components"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"A [StronglyConnectedComponent(G)](https://networkit.github.io/dev-docs/python_api/components.html?highlight=strongly#networkit.components.StronglyConnectedComponents) of a directed graph G is a maximal strongly connected subgraph. A directed graph is strongly connected if there is a path between all pairs of vertices in the graph. The constructor expects a directed [networkit.Graph](https://networkit.github.io/dev-docs/python_api/networkit.html?highlight=graph#networkit.Graph) as a mandatory parameter."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Read graph\n",
"G = nk.readGraph(\"../input/foodweb-baydry.konect\", nk.Format.KONECT)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"scc = nk.components.StronglyConnectedComponents(G)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"#Run recursively\n",
"scc.run()\n",
"print(\"number of components: \", scc.numberOfComponents())"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Get sorted list of components\n",
"partition = scc.getPartition()\n",
"indexes = sorted(set(partition.getVector()))\n",
"\n",
"# Print every member of each component\n",
"for cmp in indexes:\n",
" print(\"Members of component {} : {}\".format(cmp, partition.getMembers(cmp)))"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"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.7.5"
}
},
"nbformat": 4,
"nbformat_minor": 2
}