Notebooks/2_undirected_path.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Undirected Graph edge list which can be converted into an adjacency list.\n",
    "\n",
    "Graph_edges = [['i','j'],['k','i'],['m','k'],['k','l'],['o','n']] # edge list. \n",
    "\n",
    "# Here we have a cycle between i,j,k that can trap us in an infinite traversal.\n",
    "# Also, O and n create a cycle. \n",
    "\n",
    "Graph = {\n",
    "    'i': ['j','k'],\n",
    "    'j': ['i','k'],\n",
    "    'k': ['i','m','l','j'],\n",
    "    'm': ['k'],\n",
    "    'l': ['k'],\n",
    "    'o': ['n'],\n",
    "    'n': ['o']\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "# We need to code the same has path function. \n",
    "# Now, in order to skip the cycle we need to mark the visited nodes as visited.\n",
    "# For this reason we will use a set.\n",
    "\n",
    "# Complexity of that n = # nodes and e = # edges -> O(e) for time complexity and O(n) for space complexity. \n",
    "\n",
    "def hasPathRe(graph,start,destination,visited):\n",
    "    \n",
    "    \n",
    "    if start in visited:\n",
    "        return False\n",
    "    \n",
    "    visited.add(start)\n",
    "    \n",
    "    if start == destination:\n",
    "        return True\n",
    "\n",
    "    for neighbor in graph[start]:\n",
    "        if hasPathRe(graph,neighbor,destination,visited):\n",
    "            return True\n",
    "    \n",
    "    return False\n",
    "\n",
    "def hasPathIt(graph, start, target):\n",
    "\n",
    "    stack = [start]\n",
    "    visited = set()\n",
    "\n",
    "    while stack:\n",
    "        current_node = stack.pop()\n",
    "\n",
    "        if current_node == target:\n",
    "            return True\n",
    "\n",
    "        if current_node not in visited:\n",
    "            visited.add(current_node)\n",
    "            stack.extend(Graph[current_node])\n",
    "\n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The recursively approach :  True\n",
      "The iteratively approach :  True\n"
     ]
    }
   ],
   "source": [
    "# Recursively approach\n",
    "\n",
    "def undirectedPathRe(edges,start,destination): \n",
    "    graph = createGraph(edges)\n",
    "    \n",
    "    return hasPathRe(graph,start,destination,set())\n",
    "\n",
    "# Iteratively approach.\n",
    "\n",
    "def undirectedPathIt(edges,start,destination): \n",
    "    graph = createGraph(edges)\n",
    "    \n",
    "    return hasPathIt(graph,start,destination)\n",
    "\n",
    "\n",
    "# Depth First Search Method. \n",
    "\n",
    "print('The recursively approach : ',undirectedPathRe(Graph_edges,start='i',destination='k'))\n",
    "print('The iteratively approach : ',undirectedPathIt(Graph_edges,start='i',destination='k'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Change the format of the edges list that we got into adjacency list.\n",
    "\n",
    "def createGraph(edges):\n",
    "\n",
    "    Graph = {} \n",
    "    \n",
    "    for nodeA,nodeB in edges: # Because each edge is [nodeA,nodeB] and I can unpack them immediatelly.\n",
    "        \n",
    "        if nodeA not in Graph:\n",
    "            Graph[nodeA] = []\n",
    "        \n",
    "        if nodeB not in Graph:\n",
    "            Graph[nodeB] = []\n",
    "        \n",
    "        Graph[nodeA].append(nodeB)\n",
    "        Graph[nodeB].append(nodeA)\n",
    "        \n",
    "    return Graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test Case 1:  True\n",
      "Test Case 2:  True\n",
      "Test Case 3:  False\n",
      "Test Case 4:  True\n"
     ]
    }
   ],
   "source": [
    "# Breadth First Search \n",
    "\n",
    "def hasPathBFS(graph, start, target):\n",
    "\n",
    "    queue = [start]\n",
    "    visited = set()\n",
    "\n",
    "    while queue:\n",
    "        current_node = queue.pop(0)\n",
    "        \n",
    "        if current_node == target:\n",
    "            return True\n",
    "\n",
    "        if current_node not in visited:\n",
    "            visited.add(current_node)\n",
    "            queue.extend(graph[current_node])\n",
    "\n",
    "    return False\n",
    "\n",
    "\n",
    "def undirectedPathBFS(edges,start,destination): \n",
    "    graph = createGraph(edges)\n",
    "    \n",
    "    return hasPathBFS(graph,start,destination)\n",
    "\n",
    "\n",
    "# Test cases created with ChatGPT.\n",
    "print('Test Case 1: ', undirectedPathBFS(Graph_edges, start='i', destination='k'))\n",
    "print('Test Case 2: ', undirectedPathBFS(Graph_edges, start='j', destination='m'))\n",
    "print('Test Case 3: ', undirectedPathBFS(Graph_edges, start='o', destination='i'))\n",
    "print('Test Case 4: ', undirectedPathBFS(Graph_edges, start='k', destination='i'))"
   ]
  },
  {
   "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
}