Datashader (Graph Layout)

graph_layout.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import itertools\n",
    "\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "import datashader as ds\n",
    "import datashader.transfer_functions as tf\n",
    "\n",
    "from colorcet import fire\n",
    "from datashader.bundling import directly_connect_edges, hammer_bundle\n",
    "from datashader.layout import forceatlas2_layout\n",
    "from datashader.utils import export_image\n",
    "\n",
    "from dask.distributed import Client\n",
    "\n",
    "client = Client()\n",
    "width, height = 2000, 2000\n",
    "x_range = (-0.01, 1.01)\n",
    "y_range = (-0.01, 1.01)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Generate a 100-node complete graph without positions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For datasets representing a relationship (e.g. social networks, computer networks, etc), the given nodes may not have an assigned point. In this case, we must assign a position based on some algorithm."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will generate a dataset in which all nodes are connected to every other node."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nodes = list(range(100))\n",
    "edges = list(itertools.combinations(nodes, 2))\n",
    "len(nodes), len(edges)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we convert these lists of nodes and edges into respective dataframes. For nodes, the resulting dataframe has an `id` column. For edges, the resulting dataframe needs two required columns: `source` and `target`. Both columns use the node id assigned in the first dataframe."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "nodes_df = pd.DataFrame(nodes, columns=['id'])\n",
    "edges_df = pd.DataFrame(edges, columns=['source', 'target'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Edges can also have weights, which can be assigned to the dataframe's `weight` column. The force-directed graph layout algorithm used below will factor in the edge weights when computing the layout."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nodes_df.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "edges_df.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Layout graph on a circle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With our graph dataframes, we will layout the nodes evenly on a unit circle."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def unit_circle_layout(df):\n",
    "    df = df.copy()\n",
    "    circumference = 2 * np.pi\n",
    "    x0, y0, r = 0.5, 0.5, 0.5\n",
    "    thetas = np.arange(circumference, step=circumference/len(df))\n",
    "    df['x'] = x0 + r * np.cos(thetas)\n",
    "    df['y'] = y0 + r * np.sin(thetas)\n",
    "    return df"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "circular_df = unit_circle_layout(nodes_df)\n",
    "direct_circular_df = directly_connect_edges(circular_df, edges_df)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "cvs = ds.Canvas(width, height, x_range, y_range)\n",
    "agg = cvs.points(direct_circular_df, 'x', 'y')\n",
    "nodes_img = tf.spread(tf.shade(agg, cmap='red'), px=5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "edges_img = tf.shade(cvs.line(direct_circular_df, 'x', 'y'), cmap='blue')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "edges_img + nodes_img"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Edge bundling"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "bundled_df = hammer_bundle(circular_df, edges_df)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "cvs = ds.Canvas(width, height, x_range, y_range)\n",
    "img = tf.shade(cvs.points(bundled_df, 'x', 'y'), cmap=fire)\n",
    "tf.set_background(img, color='black') + nodes_img"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Layout graph using force-directed algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we will layout the nodes using a force-directed graph layout algorithm provided by Datashader."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "force_directed_df = forceatlas2_layout(nodes_df, edges_df)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "force_directed_df.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "direct_df = directly_connect_edges(force_directed_df, edges_df)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "cvs = ds.Canvas(width, height, x_range, y_range)\n",
    "agg = cvs.points(direct_df, 'x', 'y')\n",
    "nodes_img = tf.spread(tf.shade(agg, cmap='red'), px=5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "edges_img = tf.shade(cvs.line(direct_df, 'x', 'y'), cmap='blue')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "edges_img + nodes_img"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Edge bundling"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "bundled_df = hammer_bundle(force_directed_df, edges_df)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "cvs = ds.Canvas(width, height, x_range, y_range)\n",
    "img = tf.shade(cvs.points(bundled_df, 'x', 'y'), cmap=fire)\n",
    "tf.set_background(img, color='black') + nodes_img"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}