topological_sorting.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Topological sorting \n",
    "A strategy to perform a search in the graph.\n",
    "Sorts the nodes of the Directed Acyclic Graph such that for every directed edge $uv$, vertex $u$ comes before vertex $v$ in ordering. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Given graph\n",
      " {0: [(1, 1), (2, 2), (3, 3)], 1: [(4, 2), (5, 1)], 2: [(4, 2), (5, 1), (6, 2)], 3: [(5, 1), (6, 2)], 4: [(7, 0)], 5: [(7, 0)], 6: [(7, 0)], 7: []}\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "## declaring the directed graph with weights\n",
    "## g[i] = [(j,k)] - a graph has an edge from node i to node j with weight k\n",
    "g = dict()\n",
    "g[0] = [(1,1), (2,2), (3,3)]\n",
    "g[1] = [(4,2), (5,1)]\n",
    "g[2] = [(4,2), (5,1), (6,2)]\n",
    "g[3] = [(5,1), (6,2)]\n",
    "g[4] = [(7,0)]\n",
    "g[5] = [(7,0)]\n",
    "g[6] = [(7,0)]\n",
    "g[7] = []\n",
    "print(\"Given graph\\n\", g)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def constructIncomingGraph(og):\n",
    "    ## og - graph with ougoing edges\n",
    "    ## returns the same graph structure but with incoming edges\n",
    "    ## no weights preserved\n",
    "    # ig[i] = j,  there is an edge from node j to node i\n",
    "    ig = dict()\n",
    "    for node_from, nodes_to in og.items():\n",
    "        for node_to in nodes_to:\n",
    "            if node_to[0] in ig:\n",
    "                ig[node_to[0]].append(node_from)\n",
    "            else:\n",
    "                ig[node_to[0]] = [node_from]\n",
    "    return ig"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Graph of incoming edges\n",
      " {1: [0], 2: [0], 3: [0], 4: [1, 2], 5: [1, 2, 3], 6: [2, 3], 7: [4, 5, 6]}\n"
     ]
    }
   ],
   "source": [
    "## Checking that graph of incoming edges is properly constructed\n",
    "ig = constructIncomingGraph(g)\n",
    "print(\"Graph of incoming edges\\n\", ig)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import deque\n",
    "\n",
    "def topologicalSorting(g, start_node):\n",
    "    ig = constructIncomingGraph(g)\n",
    "    # queue of sorted nodes (result)\n",
    "    sorted_nodes = deque([])\n",
    "    ## queue of nodes with no incoming edges\n",
    "    I = deque([start_node])\n",
    "    while(I):   ## I is not empty\n",
    "        n = I.popleft()\n",
    "        # if out of I than no incoming\n",
    "        sorted_nodes.append(n)\n",
    "        if n not in g:\n",
    "            print(\"Your graph is missing node\", n)\n",
    "        children = g[n] ## children of type [(j,k)]\n",
    "        for child in children:\n",
    "            ## remove an incoming edge (release the node from a parent :))\n",
    "            child_id = child[0]\n",
    "            ig[ child_id ].remove(n)\n",
    "            if not ig[ child_id ]:\n",
    "                ## no incoming edges -> add to I\n",
    "                I.append(child_id)\n",
    "    print(\"sorting done\") \n",
    "    return sorted_nodes\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "sorting done\n",
      "deque([0, 1, 2, 3, 4, 5, 6, 7])\n"
     ]
    }
   ],
   "source": [
    "## testing sorting\n",
    "S = topologicalSorting(g, 0)\n",
    "print(S)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Well-well it seems like working, the only problem to implement this is normal cofing language is line 19. To make it efficient the list of children should be implemented as list :) Otherwise of vector will need to remove from the beginning or from the middle of the vector, which involves copying the whole vector. BAD :(\n",
    "\n",
    "### Searching for the shortest path\n",
    "Let's now try to find the shortest path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "def shortestPath(g, S):\n",
    "    # Incoming: g - graph with outgoing edges\n",
    "    # S - queue of sorted nodes\n",
    "    N = len(S) ## total number of nodes in S\n",
    "    dist = N * [math.inf]\n",
    "    p = N * [None]\n",
    "    dist[S[0]] = 0\n",
    "#     print(\"Graph\\n\", g)\n",
    "#     print(\"sorted\\n\", S)\n",
    "    for el in S:\n",
    "        u = el\n",
    "        children = g[u]\n",
    "        for child in children:\n",
    "            v = child[0] ## node to \n",
    "            w = child[1] ## weight between u and v\n",
    "#             print(\"Edge\", u,\"->\", v, \":\", w)\n",
    "            if (dist[v] > dist[u] + w):\n",
    "                dist[v] = dist[u] + w\n",
    "                p[v] = u\n",
    "#     print(\"Distance: \", dist)\n",
    "#     print(\"Parent: \",p)\n",
    "    \n",
    "    ## reverting path \n",
    "    path = []\n",
    "    par_id = len(p)-1\n",
    "    path.append(par_id)\n",
    "    while par_id:\n",
    "        par_id = p[par_id]\n",
    "        path.append(par_id)\n",
    "        \n",
    "    return path\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "shortestPath(g, S_test)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Making a proper example"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "sorting done\n",
      "Sorted nodes:  deque([0, 1, 2, 3, 4, 5, 6, 7])\n",
      "given graph\n",
      " {0: [(1, 1), (2, 2), (3, 3)], 1: [(4, 2), (5, 1)], 2: [(4, 2), (5, 1), (6, 2)], 3: [(5, 1), (6, 2)], 4: [(7, 0)], 5: [(7, 0)], 6: [(7, 0)], 7: []}\n",
      "Shortest path\n",
      " [7, 5, 1, 0]\n"
     ]
    }
   ],
   "source": [
    "## Assuming the graph is given \n",
    "S = topologicalSorting(g, 0)\n",
    "print(\"Sorted nodes: \", S)\n",
    "path = shortestPath(g,S)\n",
    "print(\"given graph\\n\", g)\n",
    "print(\"Shortest path\\n\", path)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "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.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}