SMAstar/SMAstar.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "75b34af0",
   "metadata": {},
   "source": [
    "Code credits - **Mukesh Prasanna**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "bc07fcf2",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Enter the number of nodes : 10\n",
      "Enter the node and heuristic value : a 8\n",
      "Enter the node and heuristic value : b 10\n",
      "Enter the node and heuristic value : c 4\n",
      "Enter the node and heuristic value : d 15\n",
      "Enter the node and heuristic value : e 14\n",
      "Enter the node and heuristic value : f 12\n",
      "Enter the node and heuristic value : g 11\n",
      "Enter the node and heuristic value : h 2\n",
      "Enter the node and heuristic value : i 0\n",
      "Enter the node and heuristic value : j 2\n",
      "\n",
      "Enter the number of edges : 11\n",
      "Enter the source and destination of edge : a b 1\n",
      "Enter the source and destination of edge : a c 2\n",
      "Enter the source and destination of edge : b d 7\n",
      "Enter the source and destination of edge : b e 4\n",
      "Enter the source and destination of edge : b f 5\n",
      "Enter the source and destination of edge : c g 4\n",
      "Enter the source and destination of edge : c h 3\n",
      "Enter the source and destination of edge : c i 6\n",
      "Enter the source and destination of edge : c j 8\n",
      "Enter the source and destination of edge : g h 1\n",
      "Enter the source and destination of edge : h i 3\n",
      "Enter the source and goal nodes : a i\n",
      "Enter memory bound : 4\n",
      "Path : ('a', 'c', 'h', 'i')\n",
      "Cost : 8\n"
     ]
    }
   ],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "class Graph :\n",
    "    def __init__(self) -> None:\n",
    "        self.edges = defaultdict(dict)\n",
    "        self.nodes = defaultdict(int)\n",
    "\n",
    "    def addNode(self, x, hval) :\n",
    "        self.nodes[x] = hval \n",
    "    \n",
    "    def addEdge(self, u, v, w) :\n",
    "        self.edges[u][v] = w\n",
    "\n",
    "    def calcCost(self, cost, path) :\n",
    "        return cost-self.nodes[path[-2]] + self.edges[path[-2]][path[-1]] + self.nodes[path[-1]]\n",
    "    \n",
    "    def smastar(self, source, goal, bound) :\n",
    "\n",
    "        if source==goal :\n",
    "            print(source)\n",
    "            return\n",
    "        \n",
    "        if bound==1 :\n",
    "            print('Goal not found')\n",
    "            return\n",
    "        \n",
    "        bound+=1\n",
    "        \n",
    "        frontier = []\n",
    "        frontier.append((self.nodes[source], (source,)))\n",
    "\n",
    "        visited = defaultdict(list)\n",
    "        mem = 1\n",
    "\n",
    "        while frontier :\n",
    "            \n",
    "            if mem==bound :\n",
    "                frontier.pop(-1)\n",
    "                mem-=1\n",
    "            \n",
    "            if not frontier :\n",
    "                print('Failure')\n",
    "                return\n",
    "            \n",
    "            cost, path = frontier.pop(0)\n",
    "            added = False\n",
    "            for i in self.edges[path[-1]] :\n",
    "                if i not in visited[path[-1]] :\n",
    "                    npath = path+(i,)\n",
    "                    ncost = self.calcCost(cost, npath)\n",
    "                    frontier.append((ncost, npath))\n",
    "                    visited[path[-1]].append(i)\n",
    "                    mem+=1\n",
    "                    added = True\n",
    "                    if mem==bound :\n",
    "                        break \n",
    "                \n",
    "            \n",
    "            if not added :\n",
    "                print('Failure')\n",
    "                return\n",
    "            \n",
    "            frontier.sort()\n",
    "            if frontier[0][1][-1]==goal :\n",
    "                print('Path :', frontier[0][1])\n",
    "                print('Cost :', frontier[0][0])\n",
    "                return \n",
    "            \n",
    "\n",
    "\n",
    "g = Graph()\n",
    "\n",
    "for _ in range(int(input('Enter the number of nodes : '))) :\n",
    "    x, hval = input('Enter the node and heuristic value : ').split()\n",
    "    g.addNode(x, int(hval))\n",
    "    \n",
    "for _ in range(int(input('\\nEnter the number of edges : '))) :\n",
    "    u,v,w = input('Enter the source and destination of edge : ').split()\n",
    "    g.addEdge(u,v,int(w))\n",
    "    \n",
    "source, goal = input('Enter the source and goal nodes : ').split()\n",
    "bound = int(input('Enter memory bound : '))\n",
    "g.smastar(source, goal, bound)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "884e5c0e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Enter the number of nodes : 10\n",
      "Enter the node and heuristic value : s 180\n",
      "Enter the node and heuristic value : a 70\n",
      "Enter the node and heuristic value : b 95\n",
      "Enter the node and heuristic value : c 110\n",
      "Enter the node and heuristic value : d 50\n",
      "Enter the node and heuristic value : e 40\n",
      "Enter the node and heuristic value : f 80\n",
      "Enter the node and heuristic value : h 20\n",
      "Enter the node and heuristic value : g 0\n",
      "Enter the node and heuristic value : i 90\n",
      "\n",
      "Enter the number of edges : 15\n",
      "Enter the source and destination of edge : s a 2\n",
      "Enter the source and destination of edge : s b 5\n",
      "Enter the source and destination of edge : s c 10\n",
      "Enter the source and destination of edge : a d 1\n",
      "Enter the source and destination of edge : b d 10\n",
      "Enter the source and destination of edge : b c 15\n",
      "Enter the source and destination of edge : d e 3\n",
      "Enter the source and destination of edge : c f 20\n",
      "Enter the source and destination of edge : e f 15\n",
      "Enter the source and destination of edge : e h 4\n",
      "Enter the source and destination of edge : f i 15\n",
      "Enter the source and destination of edge : f g 12\n",
      "Enter the source and destination of edge : f h 13\n",
      "Enter the source and destination of edge : h g 2\n",
      "Enter the source and destination of edge : i g 20\n",
      "Enter the source and goal nodes : s g\n",
      "Enter memory bound : 5\n",
      "Failure\n"
     ]
    }
   ],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "class Graph :\n",
    "    def __init__(self) -> None:\n",
    "        self.edges = defaultdict(dict)\n",
    "        self.nodes = defaultdict(int)\n",
    "\n",
    "    def addNode(self, x, hval) :\n",
    "        self.nodes[x] = hval \n",
    "    \n",
    "    def addEdge(self, u, v, w) :\n",
    "        self.edges[u][v] = w\n",
    "\n",
    "    def calcCost(self, cost, path) :\n",
    "        return cost-self.nodes[path[-2]] + self.edges[path[-2]][path[-1]] + self.nodes[path[-1]]\n",
    "    \n",
    "    def smastar(self, source, goal, bound) :\n",
    "\n",
    "        if source==goal :\n",
    "            print(source)\n",
    "            return\n",
    "        \n",
    "        if bound==1 :\n",
    "            print('Goal not found')\n",
    "            return\n",
    "        \n",
    "        bound+=1\n",
    "        \n",
    "        frontier = []\n",
    "        frontier.append((self.nodes[source], (source,)))\n",
    "\n",
    "        visited = defaultdict(list)\n",
    "        mem = 1\n",
    "\n",
    "        while frontier :\n",
    "            \n",
    "            if mem==bound :\n",
    "                frontier.pop(-1)\n",
    "                mem-=1\n",
    "            \n",
    "            if not frontier :\n",
    "                print('Failure')\n",
    "                return\n",
    "            \n",
    "            cost, path = frontier.pop(0)\n",
    "            added = False\n",
    "            for i in self.edges[path[-1]] :\n",
    "                if i not in visited[path[-1]] :\n",
    "                    npath = path+(i,)\n",
    "                    ncost = self.calcCost(cost, npath)\n",
    "                    frontier.append((ncost, npath))\n",
    "                    visited[path[-1]].append(i)\n",
    "                    mem+=1\n",
    "                    added = True\n",
    "                    if mem==bound :\n",
    "                        break \n",
    "                \n",
    "            \n",
    "            if not added :\n",
    "                print('Failure')\n",
    "                return\n",
    "            \n",
    "            frontier.sort()\n",
    "            if frontier[0][1][-1]==goal :\n",
    "                print('Path :', frontier[0][1])\n",
    "                print('Cost :', frontier[0][0])\n",
    "                return \n",
    "            \n",
    "\n",
    "\n",
    "g = Graph()\n",
    "\n",
    "for _ in range(int(input('Enter the number of nodes : '))) :\n",
    "    x, hval = input('Enter the node and heuristic value : ').split()\n",
    "    g.addNode(x, int(hval))\n",
    "    \n",
    "for _ in range(int(input('\\nEnter the number of edges : '))) :\n",
    "    u,v,w = input('Enter the source and destination of edge : ').split()\n",
    "    g.addEdge(u,v,int(w))\n",
    "    \n",
    "source, goal = input('Enter the source and goal nodes : ').split()\n",
    "bound = int(input('Enter memory bound : '))\n",
    "g.smastar(source, goal, bound)"
   ]
  }
 ],
 "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.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}