{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# igraph\n",
    "\n",
    "This Jupyter notebook provides an example of using the Python packages [gravis](https://pypi.org/project/gravis) and [igraph](https://igraph.org). The .ipynb file can be found [here](https://github.com/robert-haas/gravis/tree/master/examples).\n",
    "\n",
    "## References\n",
    "\n",
    "- [igraph website](https://igraph.org)\n",
    "  - [Documentation](https://igraph.org/python/#docs) for the Python interface\n",
    "    - [Tutorial](https://igraph.org/python/doc/tutorial/tutorial.html)\n",
    "    - [API reference](https://igraph.org/python/api/latest/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Installation\n",
    "\n",
    "- With [pip](https://pypi.org/project/igraph): `pip install igraph`\n",
    "- With [conda](https://anaconda.org/search?q=igraph): `conda install -c conda-forge igraph`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Import"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import os\n",
    "\n",
    "import igraph as ig\n",
    "\n",
    "import gravis as gv"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Quick start"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def assign_properties(g):\n",
    "    # Centrality calculation\n",
    "    node_centralities = g.betweenness()\n",
    "    edge_centralities = g.edge_betweenness()\n",
    "    \n",
    "    # Community detection\n",
    "    communities = g.community_fastgreedy().as_clustering().membership\n",
    "    \n",
    "    # Graph properties\n",
    "    g['node_border_size'] = 1.5\n",
    "    g['node_border_color'] = 'black'\n",
    "    g['edge_opacity'] = 0.75\n",
    "\n",
    "    # Node properties: Size by centrality, color by community\n",
    "    colors = ['red', 'blue', 'green', 'orange', 'pink', 'brown', 'yellow', 'cyan', 'magenta', 'violet']\n",
    "    g.vs['size'] = [10.0 + val / 50.0 for val in node_centralities]\n",
    "    g.vs['color'] = [colors[community_index % len(colors)] for community_index in communities]\n",
    "    \n",
    "    # Edge properties: Size by centrality, color by community (within=community color, between=black)\n",
    "    g.es['size'] = [0.5 + val / 100.0 for val in edge_centralities]\n",
    "    g.es['color'] = [colors[communities[i] % len(colors)] if communities[i] == communities[j] else 'black'\n",
    "                     for i, j in g.get_edgelist()]\n",
    "\n",
    "\n",
    "# Create a graph with a generator function\n",
    "g = ig.Graph.GRG(200, 0.14)\n",
    "\n",
    "# Scale the coordinates provided by this particular graph generator (alternative: delete them)\n",
    "g.vs['x'] = [val * 2000 - 1000 for val in g.vs['x']]  # del g.vs['x']\n",
    "g.vs['y'] = [val * 2000 - 1000 for val in g.vs['y']]  # del g.vs['y']\n",
    "\n",
    "# Assign properties\n",
    "assign_properties(g)\n",
    "\n",
    "# Plot it\n",
    "gv.d3(g, zoom_factor=0.2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Graph construction\n",
    "\n",
    "### 1) Manual graph construction\n",
    "\n",
    "- Tutorial\n",
    "    - [Creating a graph from scratch](https://igraph.org/python/doc/tutorial/tutorial.html#creating-a-graph-from-scratch)\n",
    "- API reference\n",
    "    - [Graph](https://igraph.org/python/api/latest/igraph.Graph.html#__init__)\n",
    "        - [add_vertex](https://igraph.org/python/api/latest/igraph.Graph.html#add_vertex)\n",
    "        - [add_vertices](https://igraph.org/python/api/latest/igraph.Graph.html#add_vertices)\n",
    "        - [add_edge](https://igraph.org/python/api/latest/igraph.Graph.html#add_edge)\n",
    "        - [add_edges](https://igraph.org/python/api/latest/igraph.Graph.html#add_edges)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 1a) Graph (with directed=False)\n",
    "\n",
    "undirected, with self-loops, with parallel edges, with attributes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ug = ig.Graph(directed=False)\n",
    "\n",
    "\n",
    "# Node with automatic id (starts from 0)\n",
    "ug.add_vertex()\n",
    "\n",
    "# Node with user-defined id (=only a synonym, also gets an automatic id!)\n",
    "ug.add_vertex(name='b')\n",
    "\n",
    "# Node + attribute\n",
    "ug.add_vertex(name='c', size=20)\n",
    "\n",
    "# Node + attributes\n",
    "ug.add_vertex(name='d', size=30, color='orange')\n",
    "\n",
    "\n",
    "# Nodes\n",
    "ug.add_vertices(2)           # argument: number of nodes with automatic ids\n",
    "ug.add_vertices('g')         # argument: user-defined id (also gets an automatic id)\n",
    "ug.add_vertices(['h', 'i'])  # argument: iterable of user-defined ids (also get automatic ids)\n",
    "\n",
    "\n",
    "# Edge (nodes need to already exist)\n",
    "ug.add_edge(0, 1)\n",
    "ug.add_edge('b', 'c')\n",
    "\n",
    "# Edge + attribute\n",
    "ug.add_edge('c', 'd', size=3)\n",
    "\n",
    "# Edge + attributes\n",
    "ug.add_edge('d', 4, size=4, color='orange')\n",
    "\n",
    "\n",
    "# Edges\n",
    "ug.add_edges([\n",
    "    (4, 5),\n",
    "    (5, 'g'),\n",
    "    ('g', 'h'),\n",
    "    ('h', 'i'),\n",
    "    (8, 0),\n",
    "    (0, 0),\n",
    "    (0, 0),\n",
    "    (0, 1),\n",
    "    (0, 1),\n",
    "])\n",
    "\n",
    "\n",
    "gv.d3(ug, graph_height=200)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 1b) Graph (with directed=True)\n",
    "\n",
    "undirected, with self-loops, with parallel edges, with attributes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dg = ig.Graph(directed=True, edges=[(e.source, e.target) for e in ug.es])\n",
    "\n",
    "gv.d3(dg, graph_height=200)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Assign attributes to a created graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "g = ig.Graph(directed=False, edges=[(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 0)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Graph attributes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "g['background_color'] = 'gray'\n",
    "g['node_shape'] = 'rectangle'\n",
    "g['node_label_color'] = 'white'\n",
    "g['edge_opacity'] = 0.3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Node attributes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Nodes\n",
    "num_nodes = len(g.vs)\n",
    "g.vs['size'] = [5 + i*5 for i in range(num_nodes)]\n",
    "g.vs['color'] = ['lightblue'] * num_nodes\n",
    "\n",
    "# Node\n",
    "g.vs[3]['color'] = 'darkred'\n",
    "g.vs[3]['shape'] = 'hexagon'\n",
    "g.vs[3]['size'] = 40\n",
    "g.vs[3]['opacity'] = 0.3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Edge attributes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Edges\n",
    "num_edges = len(g.es)\n",
    "g.es['size'] = [1 + i for i in range(num_edges)]\n",
    "g.es['color'] = ['lightgreen'] * num_edges\n",
    "\n",
    "# Edge\n",
    "g.es[3]['size'] = 1\n",
    "g.es[3]['color'] = 'darkred'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "gv.d3(g, graph_height=200, use_centering_force=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2) Algorithmic graph construction\n",
    "\n",
    "- Tutorial\n",
    "    - [Generating graphs](https://igraph.org/python/doc/tutorial/tutorial.html#generating-graphs)\n",
    "- API reference\n",
    "  - [Barabasi](https://igraph.org/python/api/latest/igraph._igraph.GraphBase.html#Barabasi)\n",
    "  - [De Bruijn](https://igraph.org/python/api/latest/igraph._igraph.GraphBase.html#De_Bruijn)\n",
    "  - [Degree Sequence](https://igraph.org/python/api/latest/igraph._igraph.GraphBase.html#Degree_Sequence)\n",
    "  - [Erdos-Renyi](https://igraph.org/python/api/latest/igraph._igraph.GraphBase.html#Erdos_Renyi)\n",
    "  - [Establishment](https://igraph.org/python/api/latest/igraph._igraph.GraphBase.html#Establishment)\n",
    "  - [Forest Fire](https://igraph.org/python/api/latest/igraph._igraph.GraphBase.html#Forest_Fire)\n",
    "  - [Full](https://igraph.org/python/api/latest/igraph._igraph.GraphBase.html#Full)\n",
    "  - [Full Bipartite](https://igraph.org/python/api/latest/igraph.Graph.html#Full_Bipartite)\n",
    "  - [Full Citation](https://igraph.org/python/api/latest/igraph._igraph.GraphBase.html#Full_Citation)\n",
    "  - [Growing Random](https://igraph.org/python/api/latest/igraph._igraph.GraphBase.html#Growing_Random)\n",
    "  - [GRG](https://igraph.org/python/api/latest/igraph.Graph.html#GRG)\n",
    "  - [Isoclass](https://igraph.org/python/api/latest/igraph._igraph.GraphBase.html#Isoclass)\n",
    "  - [Kautz](https://igraph.org/python/api/latest/igraph._igraph.GraphBase.html#Kautz)\n",
    "  - [K_Regular](https://igraph.org/python/api/latest/igraph._igraph.GraphBase.html#K_Regular)\n",
    "  - [Lattice](https://igraph.org/python/api/latest/igraph._igraph.GraphBase.html#Lattice)\n",
    "  - [Lederberg-Coxeter-Frucht (LCF)](https://igraph.org/python/api/latest/igraph._igraph.GraphBase.html#LCF)\n",
    "  - [Preference](https://igraph.org/python/api/latest/igraph._igraph.GraphBase.html#Preference)\n",
    "  - [Random Bipartite](https://igraph.org/python/api/latest/igraph.Graph.html#Random_Bipartite)\n",
    "  - [Realize Degree Sequence](https://igraph.org/python/api/latest/igraph._igraph.GraphBase.html#Realize_Degree_Sequence)\n",
    "  - [Recent_Degree](https://igraph.org/python/api/latest/igraph._igraph.GraphBase.html#Recent_Degree)\n",
    "  - [Ring](https://igraph.org/python/api/latest/igraph._igraph.GraphBase.html#Ring)\n",
    "  - [Star](https://igraph.org/python/api/latest/igraph._igraph.GraphBase.html#Star)\n",
    "  - [Static Fitness](https://igraph.org/python/api/latest/igraph._igraph.GraphBase.html#Static_Fitness)\n",
    "  - [Static Power Law](https://igraph.org/python/api/latest/igraph._igraph.GraphBase.html#Static_Power_Law)\n",
    "  - [Stochastic Block Model (SBM)](https://igraph.org/python/api/latest/igraph._igraph.GraphBase.html#SBM)\n",
    "  - [Tree](https://igraph.org/python/api/latest/igraph._igraph.GraphBase.html#Tree)\n",
    "  - [Tree Game](https://igraph.org/python/api/latest/igraph._igraph.GraphBase.html#Tree_Game)\n",
    "  - [Watts-Strogatz](https://igraph.org/python/api/latest/igraph._igraph.GraphBase.html#Watts_Strogatz)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 10\n",
    "\n",
    "g = ig.Graph.Barabasi(10)\n",
    "g = ig.Graph.Erdos_Renyi(50, 0.1)\n",
    "g = ig.Graph.Watts_Strogatz(2, 3, 3, 0.1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3) Graph loading from an internal collection\n",
    "\n",
    "- API reference\n",
    "  - [Atlas](https://igraph.org/python/api/latest/igraph._igraph.GraphBase.html#Atlas)\n",
    "  - [Famous](https://igraph.org/python/api/latest/igraph._igraph.GraphBase.html#Famous)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "g = ig.Graph.Atlas(22)\n",
    "g = ig.Graph.Famous('Chvatal')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4) Graph import and export\n",
    "\n",
    "- Tutorial\n",
    "    - [igraph and the outside world](https://igraph.org/python/doc/tutorial/tutorial.html#igraph-and-the-outside-world)\n",
    "\n",
    "#### Import"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# TODO"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Export"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# TODO"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Basic graph inspection\n",
    "\n",
    "### 1) Graph and its properties"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print('Type:', type(g))\n",
    "print('Directed:', g.is_directed())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2) Nodes and their properties"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for node in g.vs:\n",
    "    node_id = node.index\n",
    "    attributes = node.attributes()\n",
    "    degree = node.degree()\n",
    "    print('Type:', type(node), type(attributes))\n",
    "    print('Id:', node_id)\n",
    "    print('Attributes:', attributes)\n",
    "    print('Degree:', degree)\n",
    "    break"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3) Edges and their properties"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for edge in g.es:\n",
    "    source = edge.source\n",
    "    target = edge.target\n",
    "    attributes = edge.attributes()\n",
    "    print('Type:', type(source), type(target), type(attributes))\n",
    "    print('Source:', source)\n",
    "    print('Target:', target)\n",
    "    print('Attributes:', )\n",
    "    break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "edge_list = g.get_edgelist()\n",
    "edge_list[0:3]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Calculating graph measures and metrics\n",
    "\n",
    "### 1) Quantitative measures"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "g.degree()\n",
    "g.betweenness()\n",
    "g.edge_betweenness()\n",
    "g.pagerank()\n",
    "\n",
    "# TODO: more measures are available"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2) Structure inference\n",
    "\n",
    "#### Community detection and graph partitioning\n",
    "\n",
    "- API reference\n",
    "    - [community_edge_betweenness](https://igraph.org/python/api/latest/igraph.Graph.html#community_edge_betweenness)\n",
    "    - [community_fastgreedy](https://igraph.org/python/api/latest/igraph.Graph.html#community_fastgreedy)\n",
    "    - [community_infomap](https://igraph.org/python/api/latest/igraph.Graph.html#community_infomap)\n",
    "    - [community_label_propagation](https://igraph.org/python/api/latest/igraph.Graph.html#community_label_propagation)\n",
    "    - [community_leading_eigenvector](https://igraph.org/python/api/latest/igraph.Graph.html#community_leading_eigenvector)\n",
    "    - [community_leading_eigenvector_naive](https://igraph.org/python/api/latest/igraph.Graph.html#community_leading_eigenvector_naive)\n",
    "    - [community_multilevel](https://igraph.org/python/api/latest/igraph.Graph.html#community_multilevel)\n",
    "    - [community_optimal_modularity](https://igraph.org/python/api/latest/igraph.Graph.html#community_optimal_modularity)\n",
    "    - [community_spinglass](https://igraph.org/python/api/latest/igraph.Graph.html#community_spinglass)\n",
    "    - [community_walktrap](https://igraph.org/python/api/latest/igraph.Graph.html#community_walktrap)\n",
    "    - [modularity](https://igraph.org/python/api/latest/igraph.Graph.html#modularity)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "g = ig.Graph.GRG(40, 0.4)\n",
    "\n",
    "# based on the betweenness of the edges in the network\n",
    "g.community_edge_betweenness()\n",
    "\n",
    "# Greedily maximize the modularity score of the graph - Clauset, Newman, Moore\n",
    "g.community_fastgreedy()\n",
    "\n",
    "# Infomap method of Rosvall and Bergstrom\n",
    "g.community_infomap()\n",
    "\n",
    "# Label propagation method of Raghavan, Albert, Kumara\n",
    "g.community_label_propagation()\n",
    "\n",
    "# Newman's leading eigenvector method\n",
    "g.community_leading_eigenvector()\n",
    "\n",
    "# g.community_leading_eigenvector_naive()\n",
    "\n",
    "# Multilevel algorithm of Blondel et al.\n",
    "g.community_multilevel()\n",
    "\n",
    "# Calculates the optimal modularity score with GNU Linear Programming Kit\n",
    "g.community_optimal_modularity()\n",
    "\n",
    "# Spinglass community detection method of Reichardt and Bornholdt\n",
    "g.community_spinglass()\n",
    "\n",
    "# Community detection algorithm of Latapy and Pons, based on random walks\n",
    "g.community_walktrap()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Graph visualization\n",
    "\n",
    "### Layout calculation\n",
    "\n",
    "- Tutorial\n",
    "    - [Layouts and plotting](https://igraph.org/python/doc/tutorial/tutorial.html#layouts-and-plotting)\n",
    "- API reference\n",
    "    - [Layout class](https://igraph.org/python/api/latest/igraph.layout.Layout.html)\n",
    "    - [layout](https://igraph.org/python/api/latest/igraph.Graph.html#layout)\n",
    "    - [drawing package](https://igraph.org/python/api/latest/igraph.drawing.html)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# TODO"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Plot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# TODO"
   ]
  }
 ],
 "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.7.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}