{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# NetworKit Reachability Tutorial"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import networkit as nk"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Read a graph\n",
    "G = nk.readGraph(\"../input/foodweb-baydry.konect\", nk.Format.KONECT)\n",
    "GDir = G\n",
    "source = 0\n",
    "target = 27"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## All Simple Paths"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This algorithm computes all existing simple paths from a source node to a target node.\n",
    "\n",
    "The [AllSimplePaths(G, source, target, cutoff=none)](https://networkit.github.io/dev-docs/python_api/distance.html?highlight=all#networkit.distance.AllSimplePaths) constructor expects an unweighted graph, the source node and the target node as mandatory parameters. The maximum length of the paths can be fixed through `cutoff` parameter. This algorithm could take a lot of time on large networks (many edges), especially if the cutoff value is high or not specified.\n",
    "\n",
    "The algorithm is implemented only for unweighted graphs, so we shall convert G to an unweighted graph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "GUnweighted = nk.graphtools.toUnweighted(GDir)\n",
    "# Initialize algorithm\n",
    "asp = nk.reachability.AllSimplePaths(GUnweighted, source, target, 5).run()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# The number of simple paths in the graph\n",
    "print(asp.numberOfSimplePaths())\n",
    "# The list of all paths\n",
    "paths = asp.getAllSimplePaths()\n",
    "# Print first simple path node 0 \n",
    "print(paths[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Reachable Nodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This algorithm computes/estimates the number of reachable nodes from each node in the graph\n",
    "\n",
    "It takes as input a graph and a boolean value `exact` to determine (in directed graphs) whether to compute the exact number of reachable nodes (set to `True`), or an estimation (set to `False`). The estimation is only done in directed graphs where to compute the number of reachable nodes is expensive. In undirected graphs the number of reachable nodes is always computed exactly in linear time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exact computation\n",
    "rn = nk.reachability.ReachableNodes(G).run()\n",
    "u = 27\n",
    "print(\"Number of nodes reachable from {:d}: {:d}\".format(u, rn.numberOfReachableNodes(u)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Estimate\n",
    "rn = nk.reachability.ReachableNodes(G, False).run()\n",
    "u = 55\n",
    "print(\"Number of nodes reachable from {:d} is at least {:d} and at most {:d}\".format(u, rn.numberOfReachableNodesLB(u), rn.numberOfReachableNodesUB(u)))"
   ]
  }
 ],
 "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.6.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}