Notebooks/1_general_discussion_graphs.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h1 align=\"center\">Graph for tech Interviews</h1>\n",
    "\n",
    "Graph is a collection of nodes (circles) and edges (connections between nodes).\n",
    "\n",
    "Directed and Undirected graph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Adjancency List. Hash map data structure.\n",
    "\n",
    "G = {\n",
    "    'a': ['b','c'],\n",
    "    'b': ['d'],\n",
    "    'c': ['e'],\n",
    "    'd': [],\n",
    "    'e': ['b'],\n",
    "    'f': ['d']\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Depth First Traversal Algorithm - Stack - Last In First Out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a\n",
      "b\n",
      "d\n",
      "f\n",
      "c\n",
      "e\n",
      "=================================\n",
      "a\n",
      "c\n",
      "e\n",
      "b\n",
      "d\n",
      "f\n"
     ]
    }
   ],
   "source": [
    "# Iterative\n",
    "\n",
    "def depthFirstTraversal_It(graph,starting=''):\n",
    "    \n",
    "    # A list is a nice choice to be used as a stack. \n",
    "    \n",
    "    stack = [starting]\n",
    "    \n",
    "    while stack:\n",
    "        current = stack.pop()\n",
    "        \n",
    "        print(current)\n",
    "        \n",
    "        for neighbor in graph[current]:\n",
    "            stack.append(neighbor)\n",
    "\n",
    "# Recursive\n",
    "\n",
    "def depthFirstTraversal_Re(graph,starting=''):\n",
    "    \n",
    "    print(starting)\n",
    "    for neighbor in graph[starting]:\n",
    "        depthFirstTraversal_Re(graph,neighbor)\n",
    "\n",
    "\n",
    "G = {\n",
    "    'a': ['c','b'],\n",
    "    'b': ['d'],\n",
    "    'c': ['e'],\n",
    "    'd': ['f'],\n",
    "    'e': [],\n",
    "    'f': []\n",
    "}\n",
    "\n",
    "\n",
    "depthFirstTraversal_It(graph=G, starting='a')\n",
    "print('=================================')\n",
    "depthFirstTraversal_Re(graph=G, starting='a')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Breadth First Traverasl Algorithm - Queue - First In First Out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a\n",
      "c\n",
      "b\n",
      "e\n",
      "d\n",
      "f\n"
     ]
    }
   ],
   "source": [
    "# Iterative\n",
    "\n",
    "def breadthFirstTraversal(graph,starting=''):\n",
    "    \n",
    "    # A list can be used as a queue. Where queue.pop(0) removes the first element and append insert to the end.\n",
    "    \n",
    "    queue = [starting]\n",
    "    \n",
    "    while queue: \n",
    "        current = queue.pop(0)\n",
    "        print(current)\n",
    "        for neighbor in graph[current]:\n",
    "            queue.append(neighbor)\n",
    "        \n",
    "    \n",
    "\n",
    "G = {\n",
    "    'a': ['c','b'],\n",
    "    'b': ['d'],\n",
    "    'c': ['e'],\n",
    "    'd': ['f'],\n",
    "    'e': [],\n",
    "    'f': []\n",
    "}\n",
    "\n",
    "\n",
    "breadthFirstTraversal(graph=G, starting='a')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# The has path problem.\n",
    "\n",
    "Is there a path from the source node to the destination node?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test Case 1: A to F\n",
      "The answer is: True The real answer is True\n",
      "\n",
      "Test Case 2: B to D\n",
      "The answer is: True The real answer is True\n",
      "\n",
      "Test Case 3: A to E\n",
      "The answer is: True The real answer is True\n",
      "\n",
      "Test Case 4: A to A\n",
      "The answer is: True The real answer is True\n",
      "\n",
      "Test Case 5: C to A\n",
      "The answer is: False The real answer is False\n",
      "\n",
      "Test Case 6: D to F\n",
      "The answer is: False The real answer is False\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# Depth First traversal approach.\n",
    "\n",
    "def hasPath(graph,source,destination):\n",
    "    \n",
    "    if source == destination:\n",
    "        return True\n",
    "    \n",
    "    for neighbor in graph[source]:\n",
    "        if hasPath(graph,neighbor,destination):\n",
    "            return True\n",
    "    \n",
    "    return False\n",
    "\n",
    "# Breadth First Solution.\n",
    "\n",
    "def hasPathBFT(graph,source,destination):\n",
    "    \n",
    "    queue = [source]\n",
    "    \n",
    "    while queue:\n",
    "        current = queue.pop(0)\n",
    "        \n",
    "        if current == destination: \n",
    "            return True\n",
    "        \n",
    "        for neighbor in graph[current]:\n",
    "            queue.append(neighbor)\n",
    "            \n",
    "    return False\n",
    "\n",
    "\n",
    "graph = {\n",
    "    'A': ['B', 'C'],\n",
    "    'B': ['D', 'E'],\n",
    "    'C': ['F'],\n",
    "    'D': [],\n",
    "    'E': ['F'],\n",
    "    'F': []\n",
    "}\n",
    "\n",
    "# Test cases created with ChatGPT.\n",
    "print(\"Test Case 1: A to F\")\n",
    "print(\"The answer is:\", hasPath(graph, 'A', 'F'), \"The real answer is True\\n\")\n",
    "\n",
    "print(\"Test Case 2: B to D\")\n",
    "print(\"The answer is:\", hasPath(graph, 'B', 'D'), \"The real answer is True\\n\")\n",
    "\n",
    "print(\"Test Case 3: A to E\")\n",
    "print(\"The answer is:\", hasPath(graph, 'A', 'E'), \"The real answer is True\\n\")\n",
    "\n",
    "print(\"Test Case 4: A to A\")\n",
    "print(\"The answer is:\", hasPathBFT(graph, 'A', 'A'), \"The real answer is True\\n\")\n",
    "\n",
    "print(\"Test Case 5: C to A\")\n",
    "print(\"The answer is:\", hasPathBFT(graph, 'C', 'A'), \"The real answer is False\\n\")\n",
    "\n",
    "print(\"Test Case 6: D to F\")\n",
    "print(\"The answer is:\", hasPath(graph, 'D', 'F'), \"The real answer is False\\n\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "FFMachine",
   "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.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}