{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# NetworKit Graph Tutorial"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this notebook we will cover the main functionalities of `networkit.Graph`, the central class in NetworKit. 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": [
    "We start by creating the core object, a `networkit.Graph`. The [networkit.Graph](https://networkit.github.io/dev-docs/python_api/networkit.html?highlight=graph#networkit.Graph) constructor expects the `number of nodes` as an integer, a boolean value stating if the graph is weighted or not followed by another boolean value stating whether the graph is directed or not. The latter two are set to false by default. If the graph is unweighted, all edge weights are set to `1.0`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G = nk.Graph(5)\n",
    "print(G.numberOfNodes(), G.numberOfEdges())\n",
    "print(G.isWeighted(), G.isDirected())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`G` has 5 nodes, but no edges yet. Using the [addEdge(node u, node v)](https://networkit.github.io/dev-docs/python_api/graph.html?highlight=addedge#networkit.graph.Graph.addEdge) method, we can add edges between the nodes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G.addEdge(1, 3)\n",
    "G.addEdge(2, 4)\n",
    "G.addEdge(1, 2)\n",
    "G.addEdge(3, 4)\n",
    "G.addEdge(2, 3)\n",
    "G.addEdge(4, 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Node IDs in NetworKit are integer indices that start at 0 through to `G.upperNodeIdBound() - 1`. Hence, for this graph `G.addEdge(1,5)` would an illegal operation as node `5` does not exist. The same goes for edge IDs. If we need to add an edge between node 0 and node 5, we first need to add a sixth node to the graph using `G.addNode()`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G.addNode()\n",
    "print(G.numberOfNodes())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can add the new edge."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G.addEdge(0,5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using the method [overview(G)](https://networkit.github.io/dev-docs/python_api/networkit.html?highlight=overview#networkit.overview), we can take a look at the main properties of the graph we have created."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nk.overview(G)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that we have created a graph we can start to play around with it. Say we want to remove the node with the node ID 2, so the third node. We can easily do so using [Graph.removeNode(node u)](https://networkit.github.io/dev-docs/python_api/graph.html?highlight=remove%20node#networkit.graph.Graph.removeNode). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G.removeNode(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 2 has been deleted\n",
    "print(G.hasNode(2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The node has been remove from the graph, however, the node IDs are not adjusted to the match the new number of nodes. Hence, if we want to restore the node we previously removed from G, we can do so using [Graph.restoreNode(node u)](https://networkit.github.io/dev-docs/python_api/graph.html?highlight=restore#networkit.graph.Graph.restoreNode) using the original node ID."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Restore node with ID 2\n",
    "G.restoreNode(2)\n",
    "\n",
    "# Check if it is back in G\n",
    "print(G.hasNode(2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that in default mode NetworKit allows you to add an edge multiple times, most algorithms (and also io-functions) do not support it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G.addNode()\n",
    "G.addEdge(0, 6)\n",
    "print(G.numberOfEdges())\n",
    "# NetworKit does not complain when inserting the same edge a second time \n",
    "G.addEdge(0, 6)\n",
    "print(G.numberOfEdges())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If wanted, this behavior can be changed. This increases the running time of adding an edge by the degree of the involved nodes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Remove one of the multiple edges\n",
    "G.removeEdge(0, 6)\n",
    "print(G.numberOfEdges())\n",
    "# The multi-edge is not added to the graph. \n",
    "G.addEdge(0, 6, checkMultiEdge = True)\n",
    "print(G.numberOfEdges())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "NetworKit provides iterators that enable iterating over all nodes or edges in a simple manner. There are two kinds of iterators: one is based on ranges, the other one accepts callback a function.\n",
    "The easiest to use are the range-based iterators, they can be used in a simple for loop:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Iterate over the nodes of G\n",
    "for u in G.iterNodes():\n",
    "    print(u)\n",
    "    if u > 4:\n",
    "        print('...')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Iterate over the edges of G\n",
    "for u, v in G.iterEdges():\n",
    "    print(u, v)\n",
    "    if u > 2:\n",
    "        print('...')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Iterate over the edges of G1 and include weights\n",
    "G1 = nk.graphtools.toWeighted(G)\n",
    "G1.setWeight(0, 4, 2)\n",
    "G1.setWeight(1, 3, 3)\n",
    "for u, v, w in G1.iterEdgesWeights():\n",
    "    print(u, v, w)\n",
    "    if u > 2:\n",
    "        print('...')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Callback-based iterators accept a callback function passed to the iterators as input parameter.\n",
    "Those functions can also be lambda functions.\n",
    "More information can be found in the NetworKit documentation [here](https://networkit.github.io/dev-docs/python_api/graph.html). Let's start by using the [forNodes](https://networkit.github.io/dev-docs/python_api/graph.html?highlight=fornodes#networkit.graph.Graph.forNodes) iterator. It expects a callback function which accepts one parameter, i.e., a node. First, we define such a function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def nodeFunc(u):\n",
    "    print(\"Node \", u, \" passed to nodeFunc()\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We then pass `nodeFunc` to the iterator. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G.forNodes(nodeFunc)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G.forNodes(lambda u: print(\"Node \", u, \" passed to lambda\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Similarly, we can iterate over the edges of `G`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# First define callback function\n",
    "# that accepts exactly 4 parameters:\n",
    "def edgeFunc(u, v, weight, edgeId):\n",
    "    print(\"Edge from {} to {} has weight {} and id {}\".format(u, v, weight, edgeId))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can now call the [forEdges](https://networkit.github.io/dev-docs/python_api/graph.html?highlight=foredges#networkit.graph.Graph.forEdges) iterator, and pass `edgeFunc` to it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Using iterator with callback function.\n",
    "G.forEdges(edgeFunc)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Although we did not add any indexes to our edges, our edges all have indexes of 0. This is because NetworKit by default indexes all edges with 0. However, sometimes it makes sense to have indexed edges. If you decide to index the edges of your graph after creating it, you can use the [Graph.indexEdges(bool force = False)](https://networkit.github.io/dev-docs/python_api/graph.html?highlight=indexedges#networkit.graph.Graph.indexEdges) method. The `force` parameter forces re-indexing of edges if they had already been indexed."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Since we did not index the edges of our graph initially, we can use the default value. Indexing the edges of `G` can then be done as simply as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G.indexEdges()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sometimes you also need to iterate over specific edges, for example the ones connecting a node `u` to its neighbors. Using the [forNodes](https://networkit.github.io/dev-docs/python_api/graph.html?highlight=foredges#networkit.graph.Graph.forNodes) iterator and the [forEdgesOf](https://networkit.github.io/dev-docs/python_api/graph.html?highlight=foredges#networkit.graph.Graph.forEdges) iterator we can do so."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G.forNodes(lambda u: G.forEdgesOf(u, edgeFunc))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note, in an undirected graph, like we have here, the [forEdgesOf](https://networkit.github.io/dev-docs/python_api/networkit.html?highlight=foredgesof#networkit.Graph.forEdgesOf) iterator returns all edges of a node. When dealing with a directed graph only the out edges are returned. The rest of the edges can be accessed using the [forInEdgesOf](https://networkit.github.io/dev-docs/python_api/networkit.html?highlight=forinedges#networkit.Graph.forInEdgesOf) iterator."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Node Attributes\n",
    "\n",
    "It is possible to attach attributes to the nodes of a NetworKit graph with `attachNodeAttribute`. Attributes can be of type `str`, `float`, or `int`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Create a new attribute named 'myAtt' of type 'str'\n",
    "att = G.attachNodeAttribute(\"myAtt\", str)\n",
    "\n",
    "# Set attribute values\n",
    "att[0] = \"foo\" # Attribute of node 0\n",
    "att[1] = \"bar\" # Attribute of node 1\n",
    "\n",
    "# Get attribute value\n",
    "for u in G.iterNodes():\n",
    "    try:\n",
    "        print(f\"Attribute of node {u} is {att[u]}\")\n",
    "    except ValueError:\n",
    "        print(f\"Node {u} has no attribute\")\n",
    "        break    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## GraphTools"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`networkit.graphtools` implements some useful functions to get information or modify graphs. The following section shows some of the GraphTools functionalities."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`toWeighted(G)` takes an unweighted graph `G` as input, and returns a weighted copy of `G`. All the edge weights are set to a default value of 1.0."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "weightedG = nk.graphtools.toWeighted(G)\n",
    "assert(weightedG.numberOfNodes() == G.numberOfNodes())\n",
    "assert(weightedG.numberOfEdges() == G.numberOfEdges())\n",
    "assert(weightedG.isWeighted())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`toUnweighted(G)` does the inverse of the one above: it takes a weighted graph `G` as input, and returns an unweighted copy of `G` as output."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`randomNode(G)` returns a node of `G` selected uniformly at random."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nk.graphtools.randomNode(G)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`randomNeighbor(G, u)` returns a random (out) neighbor of node `u` in the graph `G`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nk.graphtools.randomNeighbor(G, 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`randomEdge(G, uniformDistribution=False)` returns a random edge of graph `G`. If `uniformDistribution` is set to `True`, the edge is selected uniformly at random."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nk.graphtools.randomEdge(G, True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sometimes it makes sense to compact the graph, e.g., after deleting nodes. The method `getCompactedGraph(G, nodeIdMap)` does just that by designating continuous node ids. `nodeIdMap` maps each node id of graph `G` to their new ids.\n",
    "\n",
    "First, we delete a node from `G`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G.removeNode(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then, we use `getContinuousNodeIds(G)` to get a map from the original nodes ids of G, to their new ids."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nodeIdMap = nk.graphtools.getContinuousNodeIds(G)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, we get a new graph with compacted node ids."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "compGraph = nk.graphtools.getCompactedGraph(G, nodeIdMap)\n",
    "assert(compGraph.numberOfNodes() == G.numberOfNodes())\n",
    "assert(compGraph.numberOfEdges() == G.numberOfEdges())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`maxDegree(G)` returns the highest (out) degree of `G`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nk.graphtools.maxDegree(G)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`maxInDegree(G)` returns the highest in-degree of a directed graph `G`. `maxWeightedDegree(G)` returns the highest sum of the (out) edge weights of `G`, while `maxWeightedInDegree(G)` returns the highest sum of the in-edge weights of a directed graph `G`."
   ]
  }
 ],
 "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}