exercise1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Heap-based Version of Dijkstra's Algorithm\n",
    "The following code implement the heap-based version of the Dijkstra's Algorithm."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Dependencies\n",
    "From module `math` it is used `inf`, o represent the infinity distance between nodes. Moreover, it is used the code wrote by Alberto Casagrande to implement the binary heaps. The function `decrease_key()` was renamed in `_decrease_key()` and `decrease_key()`, `get_minimum()` were added."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "from heap import binheap\n",
    "from math import inf"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Graph Initialization\n",
    "The first step of the Dijkstra alghoritm is to set all the nodes to their default values. This is implemented by ```initialize_graph()``` function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def initialize_graph(graph, source):\n",
    "    for node in graph.keys():\n",
    "        graph.get(node).update({'distance': inf})\n",
    "        graph.get(node).update({'predecessor': None})\n",
    "        graph.get(node).update({'visited': False})\n",
    "    graph.get(source).update({'distance': 0})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Heap Total Order\n",
    "Every heap node is a pair (*node_name*, *actural_distance_from_source*). Hence, to establish the minim between two nodes, we have to compare their second value. This action is performed by the function `min_distance()`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def min_distance(pair_1, pair_2):\n",
    "    return pair_1[1] < pair_2[1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Relax\n",
    "The function `relax()` performs the relax operation between a node and its adjacents. This is a generalization of the one reported in the book 'Introduction to Algorithms'."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def relax(graph, current_node, queue):\n",
    "    for adjacent, edge in graph.get(current_node)['adjacency_list'].items():\n",
    "        if graph.get(adjacent).get('distance') > graph.get(current_node).get('distance') + edge:\n",
    "            graph.get(adjacent)['predecessor'] = current_node\n",
    "            graph.get(adjacent)['distance'] = graph.get(current_node).get('distance') + edge\n",
    "            queue.decrease_key(adjacent, graph.get(current_node).get('distance') + edge)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Dijkstra's Algorithm\n",
    "The function ```dijkstra()``` implements the dijkstra's algorithm. It takes the pair (*graph*, *source*) and it returns the graph itself, in which every node has its predecessor and its distance."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "def dijkstra(graph, source):\n",
    "    \n",
    "    initialize_graph(graph, source)\n",
    "    \n",
    "    queue = binheap([[node, attributes.get('distance')] for node, attributes in graph.items()], total_order = min_distance)\n",
    "\n",
    "    while not queue.is_empty():\n",
    "        \n",
    "        current_node, _ = queue.remove_minimum()\n",
    "        print('[dijkstra]: processed node', current_node)\n",
    "        \n",
    "        relax(graph, current_node, queue)\n",
    "        \n",
    "        graph.get(current_node)['visited'] = True    \n",
    "    \n",
    "    return graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Example Graph\n",
    "The following graph is used as an example to show how the code works.\n",
    "\n",
    "<div>\n",
    "<img style=\"display: block;margin: 0 auto;\" src=\"graph.png\" width=\"700\"/>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[dijkstra]: processed node A\n",
      "[dijkstra]: processed node B\n",
      "[dijkstra]: processed node D\n",
      "[dijkstra]: processed node E\n",
      "[dijkstra]: processed node C\n",
      "[dijkstra]: processed node H\n",
      "[dijkstra]: processed node F\n",
      "[dijkstra]: processed node G\n",
      "[dijkstra]: processed node I\n",
      "\n",
      "\n",
      "Node Distance\n",
      "A    0\n",
      "B    4\n",
      "C    15\n",
      "D    13\n",
      "E    15\n",
      "F    19\n",
      "G    22\n",
      "H    19\n",
      "I    29\n"
     ]
    }
   ],
   "source": [
    "if __name__ == '__main__':\n",
    "    graph = dict()\n",
    "    graph.setdefault('A', {'adjacency_list': {'B': 4}})\n",
    "    graph.setdefault('B', {'adjacency_list': {'C': 11, 'D': 9}})\n",
    "    graph.setdefault('C', {'adjacency_list': {'A': 8}})\n",
    "    graph.setdefault('D', {'adjacency_list': {'E': 2, 'F': 6, 'C': 7}})\n",
    "    graph.setdefault('E', {'adjacency_list': {'B': 8, 'G': 7, 'H': 4}})\n",
    "    graph.setdefault('F', {'adjacency_list': {'C': 1, 'E': 5}})\n",
    "    graph.setdefault('G', {'adjacency_list': {'H': 14, 'I': 9}})\n",
    "    graph.setdefault('H', {'adjacency_list': {'F': 2, 'I': 10}})\n",
    "    graph.setdefault('I', {'adjacency_list': {}})\n",
    "    dijkstra(graph, 'A')\n",
    "    print('\\n')\n",
    "    print('Node Distance')\n",
    "    for node, attributes in graph.items():\n",
    "        print(node, '  ', attributes.get('distance'))"
   ]
  }
 ],
 "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.9.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}