Optimization Algorithm of Task Dependency Graph for Scheduling.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#  Optimization Algorithm of Task Dependency Graph for Scheduling\n",
    "A simple algorithm which optimize dependency graph by removing unnecessary and duplicated dependencies. In this notebook we provide two [isomorphic?] solution. First, when dependency graph is defended downstream, meaning every node knows all nodes which depends on it (children and descendants). Second, (I think more common) when each node knows its dependencies (parents and ancestors). The original idea of children and descendants comes from Cheng’s paper [1]."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](https://user-images.githubusercontent.com/45606539/98996311-8b3fcb00-252a-11eb-98f6-63d240e72132.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_Figures 👆 shows how we can simplify dependecy graph by removing common dependecies._\n",
    "\n",
    "**Definition:** Dependency graph is a _Directed Acyclic Graph_ (or _DAG_) where a dependecy is pointing to node."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import Dict\n",
    "from copy import deepcopy\n",
    "from itertools import product"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "dependency_graph_1 = {\n",
    "    'a': {'b', 'c', 'd', 'e'}, \n",
    "    'b': {'e'}, \n",
    "    'c': {'d'}, \n",
    "    'd': {'e'}, \n",
    "    'e': {}\n",
    "}\n",
    "\n",
    "dependency_graph_2 = {\n",
    "    'a': {}, \n",
    "    'b': {'a'}, \n",
    "    'c': {'a'}, \n",
    "    'd': {'a', 'c'}, \n",
    "    'e': {'a', 'd', 'b'}\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Algorithm 1 (children and descendants)\n",
    "**Input**: Task dependency graph $G=(N, E)$  \n",
    "**Input**: Task dependency graph $G'=(N, E')$ without redundant edges\n",
    "```\n",
    "  E := E'\n",
    "  for all node i ∈ N do\n",
    "    compute D(i), the set of descendants nodes of task i\n",
    "    compute C(i), the set of child nodes of task i\n",
    "  end for\n",
    "  \n",
    "  for all node i ∈ N do\n",
    "  for all j ∈ C(i), k ∈ D(i), and j ∈ D(k) do\n",
    "    remove the edge (i, j )\n",
    "    update C(i)\n",
    "    E := E \\ (i, j)\n",
    "    C(i) := C(i) \\ j\n",
    "   end for\n",
    "   end for\n",
    "   return the optimized graph G = (N, E')\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'a': {'b', 'c'}, 'b': {'e'}, 'c': {'d'}, 'd': {'e'}, 'e': {}}"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def optimize_dependency_graph_1(dependency_graph: Dict[str, set]) -> Dict[str, set]:\n",
    "    descendants = deepcopy(dependency_graph)\n",
    "    child = deepcopy(dependency_graph)\n",
    "\n",
    "    for i in dependency_graph:\n",
    "        parents_ancestors_combination = product(child[i], descendants[i])\n",
    "        for (j, k) in parents_ancestors_combination:\n",
    "            if len({i, j, k}) < 3:\n",
    "                continue\n",
    "            if j in descendants[k]:\n",
    "                child[i] = child[i].difference({j})\n",
    "\n",
    "    return child\n",
    "\n",
    "optimize_dependency_graph_1(dependency_graph_1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Algorithm 2 (parents and ancestors)\n",
    "**Input**: Task dependency graph $G=(N, E)$  \n",
    "**Input**: Task dependency graph $G'=(N, E')$ without redundant edges\n",
    "```\n",
    "  E := E'\n",
    "  for all node i ∈ N do\n",
    "    compute A(i), the set of ancestors nodes of task i\n",
    "    compute P(i), the set of parents nodes of task i\n",
    "  end for\n",
    "  \n",
    "  for all node i ∈ N do\n",
    "  for all j ∈ P(i), k ∈ A(i), and j ∈ A(k) do\n",
    "    remove the edge (i, j )\n",
    "    update P(i)\n",
    "    E := E \\ (i, j)\n",
    "    P(i) := P(i) \\ j\n",
    "   end for\n",
    "   end for\n",
    "   return the optimized graph G = (N, E')\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'a': {}, 'b': {'a'}, 'c': {'a'}, 'd': {'c'}, 'e': {'b', 'd'}}"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def optimize_dependency_graph_2(dependency_graph: Dict[str, set]) -> Dict[str, set]:\n",
    "    ancestors = deepcopy(dependency_graph)\n",
    "    parents = deepcopy(dependency_graph)\n",
    "\n",
    "    for i in dependency_graph:\n",
    "        parents_ancestors_combination = product(parents[i], ancestors[i])\n",
    "        for (j, k) in parents_ancestors_combination:\n",
    "            if len({i, j, k}) < 3:\n",
    "                continue\n",
    "            if j in ancestors[k]:\n",
    "                parents[i] = parents[i].difference({j})\n",
    "\n",
    "    return parents\n",
    "\n",
    "optimize_dependency_graph_2(dependency_graph_2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## References \n",
    "[1] Zhuo CHENG Yasuo TAN Yuto LIM (2016), *rERA: An Optimization Algorithm of Task Dependency\n",
    "Graph for Scheduling*, https://dspace.jaist.ac.jp/dspace/bitstream/10119/14090/1/22878.pdf"
   ]
  }
 ],
 "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.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}