{
 "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
}