AI_Assignment1.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "code",
      "source": [
        "# 21K-4934 | Hannan Irfan | CS-6E\n",
        "\n",
        "# For Importing Default Dictionary\n",
        "from collections import defaultdict\n",
        "# For Importing Heap and Queue Data Structures\n",
        "import heapq\n",
        "\n",
        "class Graph:\n",
        "    def __init__(self):\n",
        "        # Keeping graph in a dictionary for access later\n",
        "        self.graph = defaultdict(list)\n",
        "\n",
        "    def add_edge(self, u, v, weight):\n",
        "        self.graph[u].append((v, weight))\n",
        "\n",
        "    def breadth_first_search(self, start):\n",
        "        # Keeping the visited nodes in a set\n",
        "        visited = set()\n",
        "        queue = [(start, [start], 0)]\n",
        "        while queue:\n",
        "          # current, path, total weight are being appended together during file reading so they also have to be popped together\n",
        "            current, path, total_weight = queue.pop(0)\n",
        "            if current not in visited:\n",
        "                visited.add(current)\n",
        "                if len(visited) == len(self.graph):\n",
        "                    return path, total_weight\n",
        "                for neighbor, edge_weight in self.graph[current]:\n",
        "                    if neighbor not in visited:\n",
        "                        queue.append((neighbor, path + [neighbor], total_weight + edge_weight))\n",
        "        return [], float('inf')\n",
        "\n",
        "    def depth_first_search(self, start):\n",
        "        visited = set()\n",
        "        stack = [(start, [start], 0)]\n",
        "        while stack:\n",
        "            current, path, total_weight = stack.pop()\n",
        "            if current not in visited:\n",
        "                visited.add(current)\n",
        "                if len(visited) == len(self.graph):\n",
        "                    return path, total_weight\n",
        "                for neighbor, edge_weight in self.graph[current]:\n",
        "                    if neighbor not in visited:\n",
        "                        stack.append((neighbor, path + [neighbor], total_weight + edge_weight))\n",
        "        return [], float('inf')\n",
        "\n",
        "    def uniform_cost_search(self, start):\n",
        "        visited = set()\n",
        "        heap = [(0, [start], start)]\n",
        "        while heap:\n",
        "            total_weight, path, current = heapq.heappop(heap)\n",
        "            if current not in visited:\n",
        "                visited.add(current)\n",
        "                if len(visited) == len(self.graph):\n",
        "                    return path, total_weight\n",
        "                for neighbor, edge_weight in self.graph[current]:\n",
        "                    if neighbor not in visited:\n",
        "                        heapq.heappush(heap, (total_weight + edge_weight, path + [neighbor], neighbor))\n",
        "        return [], float('inf')\n",
        "\n",
        "def load_data(filename):\n",
        "    data = []\n",
        "    with open(filename, 'r') as file:\n",
        "        for line in file:\n",
        "            parts = line.strip().split(',')\n",
        "            node = int(parts[0])\n",
        "            dependencies = tuple(map(int, parts[1].strip('{}').split(','))) if parts[1] and parts[1] != '{}' else tuple()\n",
        "            weight = float(parts[2])\n",
        "            data.append((node, dependencies, weight))\n",
        "    return data\n",
        "\n",
        "def main():\n",
        "    data = load_data('data3.txt')\n",
        "\n",
        "    graph = Graph()\n",
        "\n",
        "    # Add edges to the graph\n",
        "    for node, dependencies, weight in data:\n",
        "        for dependency in dependencies:\n",
        "            graph.add_edge(dependency, node, weight)  # Bidirectional edges\n",
        "\n",
        "    # Execute algos\n",
        "    def run_algorithms(graph):\n",
        "      start_node = 1\n",
        "\n",
        "      print(\"BFS:\")\n",
        "      order_bfs, weight_bfs = graph.breadth_first_search(start_node)\n",
        "      print(\"Optimal Order:\", order_bfs)\n",
        "      print(\"Total Weight:\", weight_bfs)\n",
        "\n",
        "      print(\"\\nDFS:\")\n",
        "      order_dfs, weight_dfs = graph.depth_first_search(start_node)\n",
        "      print(\"Optimal Order:\", order_dfs)\n",
        "      print(\"Total Weight:\", weight_dfs)\n",
        "\n",
        "      print(\"\\nUCS:\")\n",
        "      order_ucs, weight_ucs = graph.uniform_cost_search(start_node)\n",
        "      print(\"Optimal Order:\", order_ucs)\n",
        "      print(\"Total Weight:\", weight_ucs)\n",
        "\n",
        "    run_algorithms(graph)\n",
        "\n",
        "if __name__ == \"__main__\":\n",
        "    main()\n"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "F3CQk7cbmOtm",
        "outputId": "afce8088-a1b0-4258-ad76-0a999ccad2e7"
      },
      "execution_count": 83,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "BFS:\n",
            "Optimal Order: [1, 4, 6]\n",
            "Total Weight: 502.303\n",
            "\n",
            "DFS:\n",
            "Optimal Order: [1, 19, 16, 18, 15, 17, 14, 13, 12, 11, 10, 9, 8, 7, 4, 3, 2]\n",
            "Total Weight: 7885.271\n",
            "\n",
            "UCS:\n",
            "Optimal Order: [1, 19]\n",
            "Total Weight: 788.89\n"
          ]
        }
      ]
    }
  ]
}