C1M3_Assignment.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Assignment - Implementing graph algorithms with LLMs\n",
    "\n",
    "Welcome to the first assignment of Course 1 in the Generative AI for Software Development Specialization!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1 - Introduction\n",
    "\n",
    "In this assignment, you'll start by working with a basic `Graph` class that comes with simple methods. Then, you'll move on to another class named `Graph_Advanced`. Here, you'll be tasked with implementing four methods to tackle four different problems.\n",
    "\n",
    "It's important to note that the Graph class cannot be modified in any way. However, you're free to add as many methods as you need to the `Graph_Advanced` class to address the challenges you'll encounter.\n",
    "\n",
    "We expect you to leverage an LLM (Large Language Model) to aid in developing the algorithms. These algorithms should not only aim for solutions that are close to optimal but also adhere to a specific time execution limit. We provide an LLM with GPT-3.5 for you, the link is [here](https://www.coursera.org/learn/introduction-to-generative-ai-for-software-development/ungradedLab/Vuqvf/gpt-3-5-environment), but feel free to use the LLM you want!\n",
    "\n",
    "[**LINK FOR GPT-3.5**](https://www.coursera.org/learn/introduction-to-generative-ai-for-software-development/ungradedLab/Vuqvf/gpt-3-5-environment)\n",
    "\n",
    "Don't worry if things seem a bit unclear at the moment! You'll receive guidance throughout the assignment.\n",
    "\n",
    "We expect you to use LLMs in the following manner:\n",
    "\n",
    "- Begin by clearly defining the problem you are trying to solve or the concept you wish to understand better. Present this to the LLM in a concise manner.\n",
    "- Engage with the LLM as if it were a knowledgeable peer. Ask questions, seek clarifications, and propose hypotheses for the LLM to comment on.\n",
    "- Provide the LLM the Graph class given to you and ask it to explain how it works.\n",
    "- After receiving input from the LLM, critically evaluate the information and decide how best to apply it to your work. Not all suggestions from the LLM may be directly applicable or correct; part of your task is to discern the most valuable advice.\n",
    "\n",
    "\n",
    "#### TIPS FOR SUCCESSFUL GRADING OF YOUR ASSIGNMENT:\n",
    "\n",
    "- All cells are frozen except for the ones where you need to submit your solutions.\n",
    "\n",
    "- You can add new cells to experiment but these will be omitted by the grader, so don't rely on newly created cells to host your solution code, use the provided places for this.\n",
    "\n",
    "- To submit your notebook, save it and then click on the blue submit button at the beginning of the page."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.1 Importing necessary libraries\n",
    "\n",
    "Let's begin by importing the necessary libraries. **It's crucial to remember that you should not use any libraries beyond those imported for this assignment. Please communicate this constraint clearly to the LLM. Importing additional libraries could disrupt the autograder, preventing you from receiving a grade.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "deletable": false,
    "editable": false,
    "tags": [
     "graded"
    ]
   },
   "outputs": [],
   "source": [
    "import random\n",
    "import heapq\n",
    "import os\n",
    "import numpy as np\n",
    "import itertools"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.2 Importing unittests library\n",
    "\n",
    "This library includes basic unittests to evaluate your solution. If you don't pass some of these unittests, it's probable that your solution will also fail upon submission. However, passing all the unittests doesn't guarantee success in this assignment, as the autograder will subject your solutions to more extensive testing. To successfully pass this assignment, your solution needs to meet the requirements in more than 85% of the test cases. If your solution fails, you will receive up to three examples highlighting where your algorithm fell short, along with instructions on how to replicate the graphs for debugging purposes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [],
   "source": [
    "import unittests"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here is the Graph class you'll be working with. Please take a moment to familiarize yourself with it and its methods. Feel free to ask an LLM to help explain how the class functions!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "deletable": false,
    "editable": false,
    "tags": [
     "graded"
    ]
   },
   "outputs": [],
   "source": [
    "class Graph:\n",
    "    def __init__(self, directed=False):\n",
    "        \"\"\"\n",
    "        Initialize the Graph.\n",
    "\n",
    "        Parameters:\n",
    "        - directed (bool): Specifies whether the graph is directed. Default is False (undirected).\n",
    "\n",
    "        Attributes:\n",
    "        - graph (dict): A dictionary to store vertices and their adjacent vertices (with weights).\n",
    "        - directed (bool): Indicates whether the graph is directed.\n",
    "        \"\"\"\n",
    "        self.graph = {}\n",
    "        self.directed = directed\n",
    "    \n",
    "    def add_vertex(self, vertex):\n",
    "        \"\"\"\n",
    "        Add a vertex to the graph.\n",
    "\n",
    "        Parameters:\n",
    "        - vertex: The vertex to add. It must be hashable.\n",
    "\n",
    "        Ensures that each vertex is represented in the graph dictionary as a key with an empty dictionary as its value.\n",
    "        \"\"\"\n",
    "        if not isinstance(vertex, (int, str, tuple)):\n",
    "            raise ValueError(\"Vertex must be a hashable type.\")\n",
    "        if vertex not in self.graph:\n",
    "            self.graph[vertex] = {}\n",
    "    \n",
    "    def add_edge(self, src, dest, weight):\n",
    "        \"\"\"\n",
    "        Add a weighted edge from src to dest. If the graph is undirected, also add from dest to src.\n",
    "\n",
    "        Parameters:\n",
    "        - src: The source vertex.\n",
    "        - dest: The destination vertex.\n",
    "        - weight: The weight of the edge.\n",
    "        \n",
    "        Prevents adding duplicate edges and ensures both vertices exist.\n",
    "        \"\"\"\n",
    "        if src not in self.graph or dest not in self.graph:\n",
    "            raise KeyError(\"Both vertices must exist in the graph.\")\n",
    "        if dest not in self.graph[src]:  # Check to prevent duplicate edges\n",
    "            self.graph[src][dest] = weight\n",
    "        if not self.directed and src not in self.graph[dest]:\n",
    "            self.graph[dest][src] = weight\n",
    "    \n",
    "    def remove_edge(self, src, dest):\n",
    "        \"\"\"\n",
    "        Remove an edge from src to dest. If the graph is undirected, also remove from dest to src.\n",
    "\n",
    "        Parameters:\n",
    "        - src: The source vertex.\n",
    "        - dest: The destination vertex.\n",
    "        \"\"\"\n",
    "        if src in self.graph and dest in self.graph[src]:\n",
    "            del self.graph[src][dest]\n",
    "        if not self.directed:\n",
    "            if dest in self.graph and src in self.graph[dest]:\n",
    "                del self.graph[dest][src]\n",
    "    \n",
    "    def remove_vertex(self, vertex):\n",
    "        \"\"\"\n",
    "        Remove a vertex and all edges connected to it.\n",
    "\n",
    "        Parameters:\n",
    "        - vertex: The vertex to be removed.\n",
    "        \"\"\"\n",
    "        if vertex in self.graph:\n",
    "            # Remove any edges from other vertices to this one\n",
    "            for adj in list(self.graph):\n",
    "                if vertex in self.graph[adj]:\n",
    "                    del self.graph[adj][vertex]\n",
    "            # Remove the vertex entry itself\n",
    "            del self.graph[vertex]\n",
    "    \n",
    "    def get_adjacent_vertices(self, vertex):\n",
    "        \"\"\"\n",
    "        Get a list of vertices adjacent to the specified vertex.\n",
    "\n",
    "        Parameters:\n",
    "        - vertex: The vertex whose neighbors are to be retrieved.\n",
    "\n",
    "        Returns:\n",
    "        - List of adjacent vertices. Returns an empty list if vertex is not found.\n",
    "        \"\"\"\n",
    "        return list(self.graph.get(vertex, {}).keys())\n",
    "\n",
    "    def _get_edge_weight(self, src, dest):\n",
    "        \"\"\"\n",
    "        Get the weight of the edge from src to dest.\n",
    "\n",
    "        Parameters:\n",
    "        - src: The source vertex.\n",
    "        - dest: The destination vertex.\n",
    "\n",
    "        Returns:\n",
    "        - The weight of the edge. If the edge does not exist, returns infinity.\n",
    "        \"\"\"\n",
    "        return self.graph[src].get(dest, float('inf'))\n",
    "    \n",
    "    def __str__(self):\n",
    "        \"\"\"\n",
    "        Provide a string representation of the graph's adjacency list for easy printing and debugging.\n",
    "\n",
    "        Returns:\n",
    "        - A string representation of the graph dictionary.\n",
    "        \"\"\"\n",
    "        return str(self.graph)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You are required to modify a new class, which inherits from the Graph class, by filling in the blank methods listed below. It's entirely acceptable, and often necessary, to add auxiliary (helper) methods to address each problem effectively. \n",
    "\n",
    "**However, the primary function tasked with solving each problem must retain the names provided below and return the output in the specified order: first the distance, followed by the path. Variable names in the return call are just examples. You can change them, as long as the first argument is the distance and the second is the path, given by a list of node numbers.**\n",
    "\n",
    "## Example of an expected function output\n",
    "\n",
    "```Python\n",
    "graph = Graph_Advanced() # Assume the graph is already built with nodes and edges\n",
    "\n",
    "print(graph.shortest_path(5, 260)) # Find the shortest path between node 5 and 260.\n",
    "\n",
    "310, [5,17, 80, 71, 190, 260]\n",
    "\n",
    "```\n",
    "\n",
    "## 2 - The Graph_Advanced Class\n",
    "\n",
    "Below is the Graph_Advanced class, which is a subclass of the Graph class. You are tasked with implementing 4 methods, each corresponding to an exercise in this assignment. It's crucial to remember that you **must not** alter the names of these functions, and the output format must be (distance, path) as specified. You **can** introduce auxiliary methods **within the Graph_Advanced class** to aid in solving any of the exercises, but the final solution **must** be delivered through the functions listed below.\n",
    "\n",
    "### 2.1 How to Complete The Exercises with LLM Assistance\n",
    "\n",
    "1. **Problem Understanding with LLM**: Discuss graph theory problems like the Travelling Salesman Problem (TSP) and shortest path finding with the LLM. Use it to clarify concepts and get examples, enhancing your foundational knowledge.\n",
    "\n",
    "2. **Graph Class Analysis with LLM**: Analyze the provided Graph class functions and structure by consulting the LLM. Its explanations will help you understand how to effectively utilize and extend the class.\n",
    "\n",
    "3. **Method Implementation Guidance**: For coding tasks (`shortest_path`, `tsp_small_graph`, `tsp_large_graph`, `tsp_medium_graph`), brainstorm with the LLM. Share your logic and seek optimization tips to refine your solutions. You can even ask the LLM to build the code for you, with any specification you want.\n",
    "\n",
    "4. **Developing Helper Methods**: Before adding helper methods to the `Graph_Advanced` class, discuss your ideas with the LLM for feedback on implementation strategies, ensuring they align with the class's integrity.\n",
    "\n",
    "5. **Testing Solutions with LLM**: Use the LLM to strategize and review your testing approach, especially for tests that yield unexpected results. It can offer debugging and optimization advice to improve your solutions.\n",
    "\n",
    "Keep the interaction with the LLM continuous, treating it as a mentor for advice, debugging, and review throughout the exercise process. This approach will not only aid in task completion but also in skill enhancement."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "deletable": false,
    "tags": [
     "graded"
    ]
   },
   "outputs": [],
   "source": [
    "class Graph_Advanced(Graph):\n",
    "    \n",
    "    def shortest_path(self, start, end): \n",
    "        \"\"\"\n",
    "        Calculate the shortest path from a starting node to an ending node in a sparse graph\n",
    "        with potentially 10000s of nodes. Must run under 0.5 second and find the shortest distance between two nodes.\n",
    "        \n",
    "        Parameters:\n",
    "        start: The starting node.\n",
    "        end: The ending node.\n",
    "        \n",
    "        Returns:\n",
    "        A tuple containing the total distance of the shortest path and a list of nodes representing that path.\n",
    "        \"\"\"\n",
    "        # Your code here\n",
    "        # Min-heap to store (distance, vertex) tuples\n",
    "        queue = [(0, start)]\n",
    "        # Dictionary to store the shortest distances from the start node\n",
    "        distances = {start: 0}\n",
    "        # Dictionary to store the shortest path\n",
    "        previous_nodes = {start: None}\n",
    "        \n",
    "        while queue:\n",
    "            current_distance, current_node = heapq.heappop(queue)\n",
    "            \n",
    "            # Early exit if we reached the destination node\n",
    "            if current_node == end:\n",
    "                break\n",
    "            \n",
    "            for neighbor, weight in self.graph[current_node].items():\n",
    "                distance = current_distance + weight\n",
    "                \n",
    "                # Only consider this path if it's shorter than any previously found\n",
    "                if neighbor not in distances or distance < distances[neighbor]:\n",
    "                    distances[neighbor] = distance\n",
    "                    previous_nodes[neighbor] = current_node\n",
    "                    heapq.heappush(queue, (distance, neighbor))\n",
    "        \n",
    "        # If the end node is unreachable, return infinity and an empty path\n",
    "        if end not in distances:\n",
    "            return float('inf'), []\n",
    "        \n",
    "        # Reconstruct the shortest path from start to end\n",
    "        path = []\n",
    "        current = end\n",
    "        while current is not None:\n",
    "            path.append(current)\n",
    "            current = previous_nodes[current]\n",
    "        \n",
    "        path.reverse()\n",
    "        return distances[end], path\n",
    "    \n",
    "    def tsp_small_graph(self, start_vertex): \n",
    "        \"\"\"\n",
    "        Solve the Travelling Salesman Problem for a small (~10 node) complete graph starting from a specified node.\n",
    "        Required to find the optimal tour. Expect graphs with at most 10 nodes. Must run under 0.5 seconds.\n",
    "        \n",
    "        Parameters:\n",
    "        start: The starting node.\n",
    "        \n",
    "        Returns:\n",
    "        A tuple containing the total distance of the tour and a list of nodes representing the tour path.\n",
    "        \"\"\"\n",
    "        # Your code here\n",
    "        vertices = list(self.graph.keys())\n",
    "        vertices.remove(start_vertex)\n",
    "        min_path = float('inf')\n",
    "        best_route = []\n",
    "\n",
    "        for perm in itertools.permutations(vertices):\n",
    "            current_path = 0\n",
    "            current_vertex = start_vertex\n",
    "            for next_vertex in perm:\n",
    "                current_path += self.graph[current_vertex][next_vertex]\n",
    "                current_vertex = next_vertex\n",
    "            current_path += self.graph[current_vertex][start_vertex]  # Complete the cycle\n",
    "\n",
    "            if current_path < min_path:\n",
    "                min_path = current_path\n",
    "                best_route = [start_vertex] + list(perm) + [start_vertex]\n",
    "\n",
    "        return min_path, best_route\n",
    "    \n",
    "    \n",
    "    def tsp_large_graph(self, start): \n",
    "        \"\"\"\n",
    "        Solve the Travelling Salesman Problem for a large (~1000 node) complete graph starting from a specified node.\n",
    "        No requirement to find the optimal tour. Must run under 0.5 second and its solution must no\n",
    "        \n",
    "        Parameters:\n",
    "        start: The starting node.\n",
    "        \n",
    "        Returns:\n",
    "        A tuple containing the total distance of the tour and a list of nodes representing the tour path.\n",
    "        \"\"\"\n",
    "        # Your code here\n",
    "        vertices = set(self.graph.keys())\n",
    "        current_vertex = start\n",
    "        tour = [start]\n",
    "        total_cost = 0\n",
    "        vertices.remove(start)\n",
    "\n",
    "        while vertices:\n",
    "            next_vertex = min(vertices, key=lambda v: self.graph[current_vertex][v])\n",
    "            total_cost += self.graph[current_vertex][next_vertex]\n",
    "            tour.append(next_vertex)\n",
    "            vertices.remove(next_vertex)\n",
    "            current_vertex = next_vertex\n",
    "\n",
    "        total_cost += self.graph[current_vertex][start]  # Complete the cycle\n",
    "        tour.append(start)\n",
    "        return total_cost, tour\n",
    "    \n",
    "    def tsp_medium_graph(self, start): \n",
    "        \"\"\"\n",
    "        Solve the Travelling Salesman Problem for a medium (~100 node) complete graph starting from a specified node.\n",
    "        Expected to perform better than tsp_large_graph. Must run under 1 second.\n",
    "        \n",
    "        Parameters:\n",
    "        start: The starting node.\n",
    "        \n",
    "        Returns:\n",
    "        A tuple containing the total distance of the tour and a list of nodes representing the tour path.\n",
    "        \"\"\"\n",
    "        # Your code here\n",
    "        # Step 1: Generate an initial tour using Nearest Neighbor heuristic\n",
    "        initial_path = self.nearest_neighbor(start)\n",
    "        \n",
    "        # Step 2: Refine the initial path using Simulated Annealing with 2-opt or 3-opt\n",
    "        best_cost, best_path = self.simulated_annealing(initial_path, opt_type='3-opt')\n",
    "        \n",
    "        # Complete the tour by returning to the starting node\n",
    "        return best_cost, best_path + [start]\n",
    "\n",
    "    def nearest_neighbor(self, start):\n",
    "        unvisited = set(self.graph.keys())\n",
    "        unvisited.remove(start)\n",
    "        path = [start]\n",
    "        current = start\n",
    "\n",
    "        while unvisited:\n",
    "            next_vertex = min(unvisited, key=lambda vertex: self.graph[current][vertex])\n",
    "            path.append(next_vertex)\n",
    "            unvisited.remove(next_vertex)\n",
    "            current = next_vertex\n",
    "\n",
    "        return path\n",
    "\n",
    "    def cost(self, path):\n",
    "        total = 0\n",
    "        for i in range(len(path) - 1):\n",
    "            total += self.graph[path[i]][path[i + 1]]\n",
    "        total += self.graph[path[-1]][path[0]]  # Complete the cycle\n",
    "        return total\n",
    "\n",
    "    def two_opt_swap(self, path, i, j):\n",
    "        return path[:i] + path[i:j + 1][::-1] + path[j + 1:]\n",
    "\n",
    "    def simulated_annealing(self, initial_path, initial_temp=1000, cooling_rate=0.99, opt_type='2-opt'):\n",
    "        current_path = initial_path[:]\n",
    "        current_cost = self.cost(current_path)\n",
    "        \n",
    "        best_path = current_path[:]\n",
    "        best_cost = current_cost\n",
    "        \n",
    "        T = initial_temp\n",
    "        \n",
    "        while T > 1:\n",
    "            # Generate a new path using either 2-opt or 3-opt\n",
    "            if opt_type == '2-opt':\n",
    "                i, j = sorted(random.sample(range(1, len(current_path)), 2))  # Avoid the starting node\n",
    "                new_path = self.two_opt_swap(current_path, i, j)\n",
    "            else:\n",
    "                i, j, k = sorted(random.sample(range(1, len(current_path)), 3))\n",
    "                new_path = self.three_opt_swap(current_path, i, j, k)\n",
    "\n",
    "            new_cost = self.cost(new_path)\n",
    "\n",
    "            # Accept the new solution if it's better or with some probability\n",
    "            if new_cost < current_cost or random.random() < np.exp((current_cost - new_cost) / T):\n",
    "                current_path = new_path\n",
    "                current_cost = new_cost\n",
    "\n",
    "                # Update the best solution found\n",
    "                if current_cost < best_cost:\n",
    "                    best_path = current_path[:]\n",
    "                    best_cost = current_cost\n",
    "\n",
    "            # Cool down\n",
    "            T *= cooling_rate\n",
    "\n",
    "        return best_cost, best_path\n",
    "\n",
    "    def three_opt_swap(self, path, i, j, k):\n",
    "        return path[:i] + path[i:j + 1][::-1] + path[j + 1:k + 1][::-1] + path[k + 1:]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3 - Exercises\n",
    "\n",
    "### 3.1 Exercises description\n",
    "\n",
    "### Exercise 1: The Shortest Path Challenge\n",
    "\n",
    "Develop an algorithm to find the quickest route between two points in a sparse graph containing 10,000 nodes, ensuring it executes in less than `0.5` seconds. If you're unsure about your approach or need optimization advice, the LLM is there to provide insights and strategies.\n",
    "\n",
    "### Exercise 2: Solving the TSP for Small Graphs\n",
    "\n",
    "Your task is to create a function that solves the Traveling Salesman Problem for small graphs of about 10 nodes, starting at node 0. The solution must be efficient, completing the task in under `1` second. The LLM can serve as a valuable resource for exploring algorithmic solutions and improving your code's efficiency.\n",
    "\n",
    "### Exercise 3: Tackling the TSP for Large Graphs\n",
    "\n",
    "Address the Traveling Salesman Problem for large graphs with 1,000 nodes. The goal isn't to find the perfect solution but to approach it closely within `0.5` seconds. When faced with the complexity of this challenge, the LLM can offer guidance on heuristic approaches and performance optimization.\n",
    "\n",
    "### Exercise 4: The TSP Medium Graphs Challenge\n",
    "\n",
    "Focus on medium-sized graphs with 300 nodes and develop an algorithm that performs better than your solution for larger graphs, with a completion time of less than `1.3` seconds. The LLM is ready to assist by sharing insights on algorithmic efficiency and helping you surpass your previous solutions.\n",
    "\n",
    "### 3.2 Unit Testing\n",
    "\n",
    "Unit testing functions are provided to validate your algorithms. Run these without modifications after completing each exercise. They offer immediate feedback, including failure reasons and guidance for improving your solutions. You can test solutions individually, ensuring focused and efficient debugging."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.3 Generate Graph Function\n",
    "\n",
    "The function outlined below can assist you in experimenting, debugging, and testing your code while you work on the algorithms. If your algorithm fails a test case, you will be given the call to this function with the appropriate arguments needed to replicate the graph that caused your algorithm to fail. Additionally, the reason for the failure will be provided, whether it was due to exceeding the time limit or not achieving an optimal or near-optimal distance. Feel free to ask the LLM to explain how this function works."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [],
   "source": [
    "def generate_graph(nodes, edges=None, complete=False, weight_bounds=(1,600), seed=None):\n",
    "    \"\"\"\n",
    "    Generates a graph with specified parameters, allowing for both complete and incomplete graphs.\n",
    "    \n",
    "    This function creates a graph with a specified number of nodes and edges, with options for creating a complete graph, and for specifying the weight bounds of the edges. It uses the Graph_Advanced class to create and manipulate the graph.\n",
    "\n",
    "    Parameters:\n",
    "    - nodes (int): The number of nodes in the graph. Must be a positive integer.\n",
    "    - edges (int, optional): The number of edges to add for each node in the graph. This parameter is ignored if `complete` is set to True. Defaults to None.\n",
    "    - complete (bool, optional): If set to True, generates a complete graph where every pair of distinct vertices is connected by a unique edge. Defaults to False.\n",
    "    - weight_bounds (tuple, optional): A tuple specifying the lower and upper bounds (inclusive) for the random weights of the edges. Defaults to (1, 600).\n",
    "    - seed (int, optional): A seed for the random number generator to ensure reproducibility. Defaults to None.\n",
    "\n",
    "    Raises:\n",
    "    - ValueError: If `edges` is not None and `complete` is set to True, since a complete graph does not require specifying the number of edges.\n",
    "\n",
    "    Returns:\n",
    "    - Graph_Advanced: An instance of the Graph_Advanced class representing the generated graph, with vertices labeled as integers starting from 0.\n",
    "\n",
    "    Examples:\n",
    "    - Generating a complete graph with 5 nodes:\n",
    "        generate_graph(5, complete=True)\n",
    "    \n",
    "    - Generating an incomplete graph with 5 nodes and 2 edges per node:\n",
    "        generate_graph(5, edges=2)\n",
    "    \n",
    "    Note:\n",
    "    - The function assumes the existence of a Graph_Advanced class with methods for adding vertices (`add_vertex`) and edges (`add_edge`), as well as a method for getting adjacent vertices (`get_adjacent_vertices`).\n",
    "    \"\"\"\n",
    "    random.seed(seed)\n",
    "    graph = Graph_Advanced()\n",
    "    if edges is not None and complete:\n",
    "        raise ValueError(\"edges must be None if complete is set to True\")\n",
    "    \n",
    "\n",
    "    for i in range(nodes):\n",
    "        graph.add_vertex(i)\n",
    "    if complete:\n",
    "        for i in range(nodes):\n",
    "            for j in range(i+1,nodes):\n",
    "                weight = random.randint(weight_bounds[0], weight_bounds[1])\n",
    "                graph.add_edge(i,j,weight)\n",
    "    else:\n",
    "        for i in range(nodes):\n",
    "            for _ in range(edges):\n",
    "                j = random.randint(0, nodes - 1)\n",
    "                while j == i or j in graph.get_adjacent_vertices(i):  # Ensure the edge is not a loop or a duplicate\n",
    "                    j = random.randint(0, nodes - 1)\n",
    "                weight = random.randint(weight_bounds[0], weight_bounds[1])\n",
    "                graph.add_edge(i, j, weight)\n",
    "    return graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4 - Playground\n",
    "\n",
    "This section is your space to experiment with and test your methods. To measure the execution time of your code, you can use the `%%timeit` magic method. Remember, `%%timeit` should be placed at the **beginning** of a code block, even before any comments marked by `#`. It's important to note that this magic method doesn't save the output of the function it measures. You're encouraged to create as many new cells as needed for testing, but keep in mind that only the code within the `Graph_Advanced` class will be considered during grading. Here's an example of how to use `%%timeit` to assess the execution time of functions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "deletable": false
   },
   "outputs": [],
   "source": [
    "## Example function\n",
    "def foo(n):\n",
    "    i = 0\n",
    "    for i in range(10000):\n",
    "        for j in range(n):\n",
    "            i += j\n",
    "    return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10044\n"
     ]
    }
   ],
   "source": [
    "print(foo(10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4.58 ms ± 113 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "foo(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Feel free to add as many cells as you want! You can do so by clicking in the `+` button in the left upper corner of this notebook."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5 - Test Your Solutions\n",
    "\n",
    "After implementing your methods in the previous class, you can run the code blocks below to test each of your developed methods! If you see the message \"All tests passed!\" for every unittest, your assignment is likely ready for submission. If not, you'll be able to see which cases your code didn't pass and understand why. **Remember, the unittests here cover only a few example cases due to the constraints of this environment. The grading process will include more extensive testing. It's possible to pass all the tests here but still fail some during the autograding.** However, if that happens, don't worry—you will receive feedback on why you failed, which will allow you to adjust your functions and resubmit the assignment. You're welcome to submit your assignment multiple times as needed.\n",
    "\n",
    "**IMPORTANT NOTE: Please ensure you shut down any other live kernels (if you have another notebook open within this environment), as they may affect the execution time of your functions.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "source": [
    "### 5.1 Test Exercise 1 (method Graph_Advanced.shortest_path)\n",
    "\n",
    "Run the code below to test the `shortest_path` method on sparsely connected graphs with 10,000 nodes. The requirements for passing this exercise are:\n",
    "\n",
    "- The algorithm must complete its run in under `0.5` second for each graph.\n",
    "- It must accurately find the shortest path."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[92m All tests passed!\n"
     ]
    }
   ],
   "source": [
    "unittests.test_shortest_path(Graph_Advanced)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "source": [
    "### 5.2 Test Exercise 2 (method Graph_Advanced.tsp_small_graph)\n",
    "\n",
    "Run the code below to test the `tsp_small_graph` on complete (fully connected) graphs with 10 nodes. The requirements for passing this exercise are:\n",
    "\n",
    "- The algorithm must complete its run in under `1` second for each graph.\n",
    "- It must fund the optimal solution, starting at node 0."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[92m All tests passed!\n"
     ]
    }
   ],
   "source": [
    "unittests.test_tsp_small_graph(Graph_Advanced)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "source": [
    "### 5.3 Test Exercise 3 (method Graph_Advanced.tsp_large_graph)\n",
    "\n",
    "Run the code below to test the `tsp_large_graph` on complete (fully connected) graphs with 1000 nodes. The requirements for passing this exercise are:\n",
    "\n",
    "- The algorithm must complete its run in under `0.5` second for each graph.\n",
    "- It must find the good solution (less than a specified value, depending on the graph). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[92m All tests passed!\n"
     ]
    }
   ],
   "source": [
    "unittests.test_tsp_large_graph(Graph_Advanced)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "source": [
    "### 5.4 Test Exercise 4 (method Graph_Advanced.tsp_medium_graph)\n",
    "\n",
    "Run the code below to test the `tsp_medium_graph` on complete (fully connected) graphs with 300 nodes. The requirements for passing this exercise are:\n",
    "\n",
    "- The algorithm must complete its run in under `1.3` seconds for each graph.\n",
    "- It must find the good solution (less than a specified value, depending on the graph). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[91mFailed test case: Failed to find a solution a solution closest to the optimal solution. To replicate the graph, you may run generate_graph(nodes = 300, complete = True, seed = 42).\n",
      "Expected: Solution no greater than 76% of Nearest Neighbor.\n",
      "Got: For the graph starting at node 0, the target path distance to beat is 3855. Your algorithm returned a distance of 3855, greater than 76%.\n",
      "\n",
      "\u001b[91mFailed test case: Failed to find a solution a solution closest to the optimal solution. To replicate the graph, you may run generate_graph(nodes = 300, complete = True, seed = 43).\n",
      "Expected: Solution no greater than 76% of Nearest Neighbor.\n",
      "Got: For the graph starting at node 0, the target path distance to beat is 3554. Your algorithm returned a distance of 3554, greater than 76%.\n",
      "\n",
      "\u001b[91mFailed test case: Failed to find a solution a solution closest to the optimal solution. To replicate the graph, you may run generate_graph(nodes = 300, complete = True, seed = 44).\n",
      "Expected: Solution no greater than 76% of Nearest Neighbor.\n",
      "Got: For the graph starting at node 0, the target path distance to beat is 3665. Your algorithm returned a distance of 3665, greater than 76%.\n",
      "\n",
      "\u001b[91mFailed test case: Failed to find a solution a solution closest to the optimal solution. To replicate the graph, you may run generate_graph(nodes = 300, complete = True, seed = 45).\n",
      "Expected: Solution no greater than 76% of Nearest Neighbor.\n",
      "Got: For the graph starting at node 0, the target path distance to beat is 3192. Your algorithm returned a distance of 3192, greater than 76%.\n",
      "\n",
      "\u001b[91mFailed test case: Failed to find a solution a solution closest to the optimal solution. To replicate the graph, you may run generate_graph(nodes = 300, complete = True, seed = 46).\n",
      "Expected: Solution no greater than 76% of Nearest Neighbor.\n",
      "Got: For the graph starting at node 0, the target path distance to beat is 3760. Your algorithm returned a distance of 3760, greater than 76%.\n",
      "\n",
      "\u001b[91mFailed test case: Failed to find a solution a solution closest to the optimal solution. To replicate the graph, you may run generate_graph(nodes = 300, complete = True, seed = 47).\n",
      "Expected: Solution no greater than 76% of Nearest Neighbor.\n",
      "Got: For the graph starting at node 0, the target path distance to beat is 3786. Your algorithm returned a distance of 3786, greater than 76%.\n",
      "\n",
      "\u001b[91mFailed test case: Failed to find a solution a solution closest to the optimal solution. To replicate the graph, you may run generate_graph(nodes = 300, complete = True, seed = 48).\n",
      "Expected: Solution no greater than 76% of Nearest Neighbor.\n",
      "Got: For the graph starting at node 0, the target path distance to beat is 3669. Your algorithm returned a distance of 3669, greater than 76%.\n",
      "\n",
      "\u001b[91mFailed test case: Failed to find a solution a solution closest to the optimal solution. To replicate the graph, you may run generate_graph(nodes = 300, complete = True, seed = 49).\n",
      "Expected: Solution no greater than 76% of Nearest Neighbor.\n",
      "Got: For the graph starting at node 0, the target path distance to beat is 3668. Your algorithm returned a distance of 3668, greater than 76%.\n",
      "\n",
      "\u001b[91mFailed test case: Failed to find a solution a solution closest to the optimal solution. To replicate the graph, you may run generate_graph(nodes = 300, complete = True, seed = 50).\n",
      "Expected: Solution no greater than 76% of Nearest Neighbor.\n",
      "Got: For the graph starting at node 0, the target path distance to beat is 4362. Your algorithm returned a distance of 4362, greater than 76%.\n",
      "\n",
      "\u001b[91mFailed test case: Failed to find a solution a solution closest to the optimal solution. To replicate the graph, you may run generate_graph(nodes = 300, complete = True, seed = 51).\n",
      "Expected: Solution no greater than 76% of Nearest Neighbor.\n",
      "Got: For the graph starting at node 0, the target path distance to beat is 4148. Your algorithm returned a distance of 4148, greater than 76%.\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "unittests.test_tsp_medium_graph(Graph_Advanced)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Congratulations! You completed the first assignment of the Specialization!**"
   ]
  }
 ],
 "metadata": {
  "grader_version": "1",
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.11.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}