4. Advanced Graph Algorithms.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"width: 100%; overflow: hidden;\">\n",
    "    <div style=\"width: 150px; float: left;\"> <img src=\"https://raw.githubusercontent.com/DataForScience/Networks/master/data/D4Sci_logo_ball.png\" alt=\"Data For Science, Inc\" align=\"left\" border=\"0\" width=160px> </div>\n",
    "    <div style=\"float: left; margin-left: 10px;\"> <h1>Graphs and Networks</h1>\n",
    "<h1>Lesson IV - Advanced Graph Algorithms</h1>\n",
    "        <p>Bruno Gonçalves<br/>\n",
    "        <a href=\"http://www.data4sci.com/\">www.data4sci.com</a><br/>\n",
    "            @bgoncalves, @data4sci</p></div>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "from pprint import pprint\n",
    "import heapq\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "import matplotlib\n",
    "import matplotlib.pyplot as plt \n",
    "\n",
    "import watermark\n",
    "\n",
    "%load_ext watermark\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Watermark the notebook with current versions of all loaded libraries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Python implementation: CPython\n",
      "Python version       : 3.8.5\n",
      "IPython version      : 7.19.0\n",
      "\n",
      "Compiler    : Clang 10.0.0 \n",
      "OS          : Darwin\n",
      "Release     : 21.6.0\n",
      "Machine     : x86_64\n",
      "Processor   : i386\n",
      "CPU cores   : 16\n",
      "Architecture: 64bit\n",
      "\n",
      "Git hash: e2a121886d5fb3c11344fccd2cf35c76180f7246\n",
      "\n",
      "matplotlib: 3.3.2\n",
      "numpy     : 1.19.2\n",
      "json      : 2.0.9\n",
      "watermark : 2.1.0\n",
      "\n"
     ]
    }
   ],
   "source": [
    "%watermark -n -v -m -g -iv"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Load default figure style"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.style.use('./d4sci.mplstyle')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We import the previous Graph Class definition"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "from Graph import *"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And add a convenience method to easily add weighted edges"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "@add_method(Graph)\n",
    "def add_weighted_edges_from(self, edges):\n",
    "    # Each edge can have simply a weight of a feature dictionary \n",
    "    for edge in edges:\n",
    "        if isinstance(edge[2], dict):\n",
    "            self.add_edge(edge[0], edge[1], **edge[2])\n",
    "        else:\n",
    "            self.add_edge(edge[0], edge[1], weight=edge[2])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We manually define our undirected graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "G = Graph(directed=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "G.add_weighted_edges_from(\n",
    "[\n",
    "    [0, 1, {\"weight\": 5}],\n",
    "    [0, 2, 10],\n",
    "    [0, 4, 2],\n",
    "    [1, 2, 2],\n",
    "    [1, 3, 4],\n",
    "    [2, 3, 7],\n",
    "    [2, 5, 10],\n",
    "    [3, 4, 3]\n",
    "])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Since the graph is undirected, we have double the edges:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[0, 1, {'weight': 5}],\n",
       " [0, 2, {'weight': 10}],\n",
       " [0, 4, {'weight': 2}],\n",
       " [1, 0, {'weight': 5}],\n",
       " [1, 2, {'weight': 2}],\n",
       " [1, 3, {'weight': 4}],\n",
       " [2, 0, {'weight': 10}],\n",
       " [2, 1, {'weight': 2}],\n",
       " [2, 3, {'weight': 7}],\n",
       " [2, 5, {'weight': 10}],\n",
       " [4, 0, {'weight': 2}],\n",
       " [4, 3, {'weight': 3}],\n",
       " [3, 1, {'weight': 4}],\n",
       " [3, 2, {'weight': 7}],\n",
       " [3, 4, {'weight': 3}],\n",
       " [5, 2, {'weight': 10}]]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "G.edges()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Priority Queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Our implementation of Dijkstra's algorithm relies on a priority queue. We can easily build one by wrapping around the functionality of the **heapq** standard library module as a priority queue is just a min-heap"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "code_folding": []
   },
   "outputs": [],
   "source": [
    "class PriorityQueue:\n",
    "    def __init__(self):\n",
    "        self.heap = []\n",
    "\n",
    "    def push(self, node, priority):\n",
    "        heapq.heappush(self.heap, [priority, node])\n",
    "\n",
    "    def pop(self, data=True):\n",
    "        if data:\n",
    "            return heapq.heappop(self.heap)\n",
    "        else:\n",
    "            return heapq.heappop(self.heap)[1]\n",
    "\n",
    "    def update(self, node, new_priority):\n",
    "        pos = -1 \n",
    "\n",
    "        for i, value in enumerate(self.heap):\n",
    "            priority, node_i = value\n",
    "\n",
    "            if node_i == node:\n",
    "                self.heap[i][0] = new_priority\n",
    "                pos = i\n",
    "                break\n",
    "\n",
    "        if pos == -1:\n",
    "            self.heap.append([new_priority, node])\n",
    "\n",
    "        heapq.heapify(self.heap)\n",
    "\n",
    "    def empty(self):\n",
    "        return len(self.heap) == 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We test our implementation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "queue = PriorityQueue()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "queue.push(\"a\", 10)\n",
    "queue.push(\"b\", 7)\n",
    "queue.push(\"c\", 6)\n",
    "queue.push(\"d\", 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The contens of the heap are then"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[3, 'd'], [6, 'c'], [7, 'b'], [10, 'a']]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "queue.heap"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And if we update the priority of one of the elements"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "queue.update(\"c\", 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It becomes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 'c'], [3, 'd'], [7, 'b'], [10, 'a']]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "queue.heap"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, we note that we recover a sorted list of items by simply popping them all out of the queue. This is known as Heapsort https://en.wikipedia.org/wiki/Heapsort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 'c']\n",
      "[3, 'd']\n",
      "[7, 'b']\n",
      "[10, 'a']\n"
     ]
    }
   ],
   "source": [
    "print(queue.pop(True))\n",
    "print(queue.pop(True))\n",
    "print(queue.pop(True))\n",
    "print(queue.pop(True))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Dijkstra's algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "def dijkstra(G, source):\n",
    "    N = G.number_of_nodes()\n",
    "    queue = PriorityQueue()\n",
    "\n",
    "    dist = {}\n",
    "\n",
    "    for node in G._nodes.keys():\n",
    "        dist[node] = [np.inf, []]\n",
    "    \n",
    "    dist[source][0] = 0\n",
    "    dist[source][1].append(source)\n",
    "\n",
    "    queue.push(source, 0)\n",
    "\n",
    "    while not queue.empty():\n",
    "        node_i = queue.pop(False)\n",
    "\n",
    "        NN = G.neighbours(node_i)\n",
    "\n",
    "        for node_j in NN:\n",
    "            weight = G._edges[node_i][node_j][\"weight\"]\n",
    "            new_dist = dist[node_i][0] + weight\n",
    "\n",
    "            if new_dist < dist[node_j][0]:\n",
    "                dist[node_j][0] = new_dist\n",
    "                dist[node_j][1] = list(dist[node_i][1])\n",
    "                dist[node_j][1].append(node_j)\n",
    "\n",
    "                queue.update(node_j, new_dist)\n",
    "\n",
    "    return dist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{0: [0, [0]],\n",
      " 1: [5, [0, 1]],\n",
      " 2: [7, [0, 1, 2]],\n",
      " 3: [5, [0, 4, 3]],\n",
      " 4: [2, [0, 4]],\n",
      " 5: [17, [0, 1, 2, 5]]}\n"
     ]
    }
   ],
   "source": [
    "dist = dijkstra(G, 0)\n",
    "pprint(dist)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Path representation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "N = G.number_of_nodes()\n",
    "target = -1*np.ones((N, N), dtype='int')\n",
    "\n",
    "for node in dist:\n",
    "    path = dist[node][1]\n",
    "    target[node, node] = node\n",
    "    \n",
    "    for i in range(len(path)-1):\n",
    "        target[path[i], path[-1]] = path[i+1] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 0,  1,  1,  4,  4,  1],\n",
       "       [-1,  1,  2, -1, -1,  2],\n",
       "       [-1, -1,  2, -1, -1,  5],\n",
       "       [-1, -1, -1,  3, -1, -1],\n",
       "       [-1, -1, -1,  3,  4, -1],\n",
       "       [-1, -1, -1, -1, -1,  5]])"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "target"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### All shortest paths"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(1, 6):\n",
    "    dist = dijkstra(G, i)\n",
    "    \n",
    "    for node in dist:\n",
    "        path = dist[node][1]\n",
    "\n",
    "        for i in range(len(path)-1):\n",
    "            target[path[i], path[-1]] = path[i+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0, 1, 1, 4, 4, 1],\n",
       "       [0, 1, 2, 3, 3, 2],\n",
       "       [1, 1, 2, 1, 1, 5],\n",
       "       [4, 1, 1, 3, 4, 1],\n",
       "       [0, 0, 0, 3, 4, 0],\n",
       "       [2, 2, 2, 2, 2, 5]])"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "target"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Floyd-Warshall Algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "def FloydWarshall(G):\n",
    "    N = G.number_of_nodes()\n",
    "    dist = np.ones((N, N), dtype='float')*np.inf\n",
    "    target = -np.ones((N, N), dtype='int')\n",
    "\n",
    "    for node_i, node_j, w in G.edges():\n",
    "        weight = w[\"weight\"]\n",
    "        dist[node_i, node_j] = weight\n",
    "        target[node_i, node_j] = node_j\n",
    "\n",
    "    for node_i in G.nodes():\n",
    "        dist[node_i, node_i] = 0\n",
    "        target[node_i, node_i] = node_i\n",
    "\n",
    "    for node_k in range(N):\n",
    "        for node_i in range(N):\n",
    "            for node_j in range(N):\n",
    "                if dist[node_i, node_j] > dist[node_i, node_k] + dist[node_k, node_j]:\n",
    "                    dist[node_i, node_j] = dist[node_i, node_k] + dist[node_k, node_j]\n",
    "                    target[node_i, node_j] = target[node_i, node_k]\n",
    "\n",
    "    return dist, target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "G2 = Graph(directed=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "G2.add_weighted_edges_from(\n",
    "[\n",
    "    [1, 0, 4],\n",
    "    [0, 2, -2],\n",
    "    [1, 2, 3],\n",
    "    [2, 3, 2],\n",
    "    [3, 1, -1],\n",
    "])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "dist, target = FloydWarshall(G2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "array([[ 0., -1., -2.,  0.],\n",
      "       [ 4.,  0.,  2.,  4.],\n",
      "       [ 5.,  1.,  0.,  2.],\n",
      "       [ 3., -1.,  1.,  0.]])\n"
     ]
    }
   ],
   "source": [
    "pprint(dist)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "array([[0, 2, 2, 2],\n",
      "       [0, 1, 0, 0],\n",
      "       [3, 3, 2, 3],\n",
      "       [1, 1, 1, 3]])\n"
     ]
    }
   ],
   "source": [
    "pprint(target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "def path(target, node_i, node_j):\n",
    "    if target[node_i, node_j] == -1:\n",
    "        return []\n",
    "\n",
    "    path = [node_i]\n",
    "\n",
    "    while node_i != node_j:\n",
    "        node_i = target[node_i, node_j]\n",
    "        path.append(node_i)\n",
    "\n",
    "    return path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 3, 1]\n",
      "[2, 3, 1, 0]\n"
     ]
    }
   ],
   "source": [
    "print(path(target, 2, 1))\n",
    "print(path(target, 2, 0))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"width: 100%; overflow: hidden;\">\n",
    "     <img src=\"data/D4Sci_logo_full.png\" alt=\"Data For Science, Inc\" align=\"center\" border=\"0\" width=300px> \n",
    "</div>"
   ]
  }
 ],
 "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.8.5"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": true,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}