Critical-Path-Method.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Task 2: Simulation of Critical Path Method"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Importing the Libraries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Class for storing activity information"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Activity:\n",
    "    def __init__(self, name, duration) -> None:\n",
    "        self.name = name #Activity name\n",
    "        self.duration = duration #Completion time\n",
    "        self.predecessors = [] #Precedence activities\n",
    "        self.successors = [] #Dependent activities\n",
    "        self.es = 0 #Earliest start\n",
    "        self.ef = 0 #Earliest finish\n",
    "        self.ls = 0 #Latest start\n",
    "        self.lf = 0 #Latest finish\n",
    "        self.st = 0 #Slack time"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Taking input from the file"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "file_name = \"precedence-relationship.txt\"\n",
    "\n",
    "activities = {} #Stores name -> activity information\n",
    "names = [] #stores name\n",
    "\n",
    "for lines in open(file_name):\n",
    "    words = lines.rstrip('\\n').split(' ')\n",
    "    name = words[0]\n",
    "    duration = int(words[1])\n",
    "    predecessors = words[2]\n",
    "\n",
    "    names.append(name)\n",
    "    activities[name] = Activity(name, duration)\n",
    "\n",
    "    if (predecessors != \"\"):\n",
    "        predecessors = predecessors.split(',')\n",
    "        for predecessor in predecessors:\n",
    "            activities[name].predecessors.append(predecessor)\n",
    "            activities[predecessor].successors.append(name)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Forward Pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "max_earliest_finish = 0\n",
    "\n",
    "for name in names:\n",
    "    if (len(activities[name].predecessors) == 0):\n",
    "        activities[name].ef = activities[name].duration\n",
    "    else:\n",
    "        max_earliest_start = 0\n",
    "        for predecessor in activities[name].predecessors:\n",
    "            max_earliest_start = max(max_earliest_start, activities[predecessor].ef)\n",
    "\n",
    "        activities[name].es = max_earliest_start\n",
    "        activities[name].ef = max_earliest_start + activities[name].duration\n",
    "\n",
    "    max_earliest_finish = max(max_earliest_finish, activities[name].ef)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Backward Pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "for name in reversed(names):\n",
    "    if (len(activities[name].successors) == 0):\n",
    "        activities[name].lf = max_earliest_finish\n",
    "        activities[name].ls = max_earliest_finish - activities[name].duration\n",
    "    else:\n",
    "        min_latest_start = 10 ** 9\n",
    "        for successor in activities[name].successors:\n",
    "            min_latest_start = min(min_latest_start, activities[successor].ls)\n",
    "\n",
    "        activities[name].lf = min_latest_start\n",
    "        activities[name].ls = min_latest_start - activities[name].duration\n",
    "        \n",
    "    activities[name].st = activities[name].ls - activities[name].es"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Finding Critical Path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A -> ES: 0 EF: 3 LS: 0 LF: 3 ST: 0\n",
      "B -> ES: 3 EF: 8 LS: 3 LF: 8 ST: 0\n",
      "C -> ES: 3 EF: 7 LS: 4 LF: 8 ST: 1\n",
      "D -> ES: 8 EF: 14 LS: 8 LF: 14 ST: 0\n",
      "E -> ES: 7 EF: 9 LS: 17 LF: 19 ST: 10\n",
      "F -> ES: 14 EF: 19 LS: 14 LF: 19 ST: 0\n",
      "\n",
      "Critical Path: A -> B -> D -> F\n"
     ]
    }
   ],
   "source": [
    "critical_path = \"\"\n",
    "\n",
    "for name in names:\n",
    "    print(f\"{name} -> ES: {activities[name].es} EF: {activities[name].ef} LS: {activities[name].ls} LF: {activities[name].lf} ST: {activities[name].st}\")\n",
    "    if (activities[name].st == 0):\n",
    "        critical_path += name + \" -> \"\n",
    "\n",
    "print(f\"\\nCritical Path: {critical_path[:-4]}\")"
   ]
  }
 ],
 "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.17"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}