advanced_Concepts.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Advanced Programming Concepts taught in Python #\n",
    "### A Workshop by Ryan Handley ###  \n",
    "Welcome back, everyone!  Today, we will go over more advanced concepts in Computer Programming.  We will investigate the object oriented programming paradigm (OOP), as well as some more advanced data structures and algorithms.  These two areas are extremely useful for Software Engineering and enforcing highly efficient data CRUD Operations.  Here is our agenda for this session:  \n",
    "- ### Object Oriented Programming ###\n",
    "    - Concept Introduction\n",
    "    - Classes, Attributes & Methods\n",
    "    - Instantiating Objects\n",
    "    - Inheritance\n",
    "    - Polymorphism\n",
    "    - Encapsulation\n",
    "    - Abstraction\n",
    "- ### Advanced Data Structures & Algorithms ###\n",
    "    - Linked Lists\n",
    "        - Singly Linked List\n",
    "        - Doubly Linked List\n",
    "    - Trees\n",
    "        - Binary\n",
    "        - AVL\n",
    "    - Graphs\n",
    "     - Directed\n",
    "     - Acycliic vs Cyclic\n",
    "     - Djikstra's Algorithm\n",
    "     - A* Algorithm\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Object Oriented Programming ##  \n",
    "This paradigm of programming is extremely useful when we consider representing the physical world as code.  We represent aspects of reality as ***objects***, which contain data and fuctions which control it.  OOP is used to organize the design of complex software and create more reusable, scalable, and maintainable code. Often, common language conventions represent the structure of code.\n",
    "\n",
    "- Nouns represent singuar ***classes*** and their propterties/attributes\n",
    "    - A class is the body of code used to define an object, which in itself is a kind of data structure\n",
    "    - The propereties/attributes of a class can be thought of as fields in a relational database schema, or even like columns in an excel document.  These may be described using nouns or adjectives.\n",
    "- Verbs are used to name functions we call ***methods***\n",
    "    - A method is a kind of function created within the scope of a class, allowing us to perform operations like CRUD, or class specific calculations.\n",
    "\n",
    "### Common Conventions ###\n",
    "- Pascal Case\n",
    "    - Use Pascal Casing to name classes.  Pascal casing is when each word begins with an upper case character and has no spaces.\n",
    "        - UserAccount, Car, Dog, HomeAddress, etc...\n",
    "- Camel Case\n",
    "    - Use Camel Casing to name methods.  Camel Casing is when the first word is all lower case with all other words having their first letter in upper case\n",
    "        - getAddress, setAddress, setName, getName, calcProfits, etc...\n",
    "- Snake Case\n",
    "    - Use snake case to name variables, attributes, and packages.  Snake casing uses underscores to separate each word.\n",
    "        - student_name, employee_address, my_variable, etc...\n",
    "    - Use Upper Snake casing for constants.\n",
    "        - MAX_CLASSES, MIN_GPA, ROOM_CAPACITY, etc...\n",
    "- Singles vs. Plurals\n",
    "    - Use the singular form when naming classes as they represent a single entity.\n",
    "    - Use the plural form when naming collections of objects such as lists\n",
    "\n",
    "### Defining Classes, Attributes & Methods ###\n",
    "- In this section, we'll create a basic Employee class with basic Methods which would traditionally be used to keep time and track pay."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import datetime\n",
    "\n",
    "# Create a class using the keyword class, indent, and add attributes/properties\n",
    "class Employee:\n",
    "    def __init__(self, name, age, role, wage)-> None: # -> None indicates the return type when called\n",
    "        self.name = name\n",
    "        self.age = age\n",
    "        self.role = role\n",
    "        self.wage = wage\n",
    "        self.clock_in_time = None\n",
    "        self.clock_out_time = None\n",
    "        self.hours_worked = []\n",
    "        self.current_period_pay = 0\n",
    "\n",
    "    # Lets add methods to clock in, clock out, log the times worked each clocking cycle, and to calculate pay\n",
    "\n",
    "    def clockIn(self):\n",
    "        self.clock_in_time = datetime.datetime.now()\n",
    "        return f\"Welcome, clock in successfully logged: {self.clock_in_time}\"\n",
    "    \n",
    "    def clockOut(self):\n",
    "        self.clock_out_time = datetime.datetime.now()\n",
    "        return f\"Enjoy your day, clock out successfully logged: {self.clock_out_time}\"\n",
    "    \n",
    "    def loggedInDuration(self):\n",
    "        if self.clock_in_time and self.clock_out_time:\n",
    "            duration = self.clock_out_time - self.clock_in_time\n",
    "            return duration.total_seconds() / 3600  # Return duration in hours\n",
    "        return None\n",
    "\n",
    "    def addDuration(self, duration):\n",
    "        if duration is not None:\n",
    "            if len(self.hours_worked) >= 28:\n",
    "                self.hours_worked.pop(0)  # Remove the oldest entry if we have 28 entries\n",
    "            self.hours_worked.append(duration)\n",
    "        \n",
    "        total_hours = sum(self.hours_worked)\n",
    "        if len(self.hours_worked) == 28:\n",
    "            if total_hours > 40:\n",
    "                return f\"End of Pay Period:\\nRegular Hours: 40\\nOvertime Hours: {total_hours - 40}\"\n",
    "            return f\"End of Pay Period:\\nRegular Hours: {total_hours}\"\n",
    "        return f\"Hours worked so far: {total_hours}\"\n",
    "    \n",
    "    def calculatePay(self):\n",
    "        total_hours = sum(self.hours_worked)\n",
    "        if total_hours > 40:\n",
    "            overtime_hours = total_hours - 40\n",
    "            self.current_period_pay = (40 * self.wage) + (overtime_hours * (self.wage * 1.5))\n",
    "        else:\n",
    "            self.current_period_pay = total_hours * self.wage\n",
    "        return self.current_period_pay\n",
    "    \n",
    "    def getHoursWorked(self):\n",
    "        return sum(self.hours_worked)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Instantiating Objects & Calling Methods ###\n",
    "Here, we will create an instance of the employee object, and execute its methods to demonstrate how objects work as a data structure to CRUD data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "\n",
    "# This is an instance.  We assign instances to variables to store data specific to one employee.  We may have a list of instances containing employees as opposed to \n",
    "# one singular instance\n",
    "employee_1 = Employee(\"Ryan Handley\", 21, \"Data Management/Operation Intern\", 25)\n",
    "for _ in range(29):\n",
    "    employee_1.clockIn()\n",
    "    time.sleep(1) # Sleep fucntion from time module allows us to pass in a time (seconds) to simulate the passage of time, or reflect the passage of time in reality.\n",
    "    employee_1.clockOut()\n",
    "    employee_1.addDuration(employee_1.loggedInDuration())\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.007782663333333334\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "0.19456658333333335"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print(employee_1.getHoursWorked())\n",
    "employee_1.calculatePay()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Inheritance, Abstraction, and Polymoprhism ###\n",
    "Think of how we classify things in the real world.  More specifically, lets look at animals as an example.  Depending on ones definition, animal may mean something more complex than it does to someone else, but generally speaking, the consensus is that animals are living things which are neither a human being or plant.  There are, of course, different types of animals in the animal kingdom.  If we picture this as a hierarchy, animals are the root of the tree, and as you traverse down said tree, there are different species of animals, and even different subspecies of those animals.  \n",
    "  \n",
    "In OOP, we can account for these natural hierarchies using ***Inheritance***.  Inheritance allows us to create a class with general attributes, which can be extended to apply to all of its children.  \n",
    "\n",
    "If we want to access the name of a kind of animal, we won't need to reference the original animal class or its methods, as each of it's children will have their own implementation.  For example, no two species of animals make the same noises, so using the Animal Classes speak method would be usless as it doesn't give us any information about what noises a specific animal makes.\n",
    "\n",
    "To make this feature inaccessible so we only access the essential data, we make animal an ***Abstract*** class.  Abstraction allows the internal details of a class to be hidden, only showing the essential features, which aids in reducing the complexity of code.  This allows a programmer to focus more on what the object does as opposed to how it does it.\n",
    "We import the *abc* module from python to implement abstraction.\n",
    "\n",
    "We can also reduce the amount of code we need to write by using the ***super()*** function.  This allows us to avoid hardcoding the name of a parent class, and allows us to do less maintenance work when code is changed or refactored.  It makes code more extensibile because it allows the derived classes to extend the functionality of the base class.\n",
    "\n",
    "We refer to the implementation of different variations of an abstract method ***polymorphism***.  Essentially, methods will do things differently based on the object they are acting upon, despite having the same name.  makeSound will function this way.  We also refer to this as method overriding."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Bufford goes woof!\n",
      "Pitbull\n",
      "\n",
      "Timmy goes gobble gobble!\n",
      "Wild Turkey\n",
      "Wild Turkeys fly: True\n"
     ]
    }
   ],
   "source": [
    "from abc import ABC, abstractmethod\n",
    "\n",
    "class Animal(ABC):\n",
    "    def __init__(self, name: str) -> None: # Notice that name has a colon and the str data type next to it.  This indicates that we require a string value to be passed in as a param\n",
    "        super().__init__()\n",
    "        self.name = name\n",
    "\n",
    "    @abstractmethod\n",
    "    def makeSound(self) -> None:\n",
    "        pass # Pass lets us define the method without an implementation, so it may be assigned to each derived class\n",
    "\n",
    "class Dog(Animal):\n",
    "    def __init__(self, name: str, breed: str) -> None:\n",
    "        super().__init__(name) # Indicates that this correlates to the name attribute of Animal.  Used for dynamic looping through a list of different derived animal classes\n",
    "        self.breed = breed\n",
    "    \n",
    "    def makeSound(self) -> None:\n",
    "        print(f\"{self.name} goes woof!\")\n",
    "    \n",
    "    def getBreed(self) -> str:\n",
    "        return self.breed\n",
    "\n",
    "class Bird(Animal):\n",
    "    def __init__(self, name:str, breed: str, flight: bool) -> None: # Flight accepts a boolean value, as a bird either can or cannot fly\n",
    "        super().__init__(name)\n",
    "        self.breed = breed\n",
    "        self.flight = flight\n",
    "\n",
    "    def makeSound(self) -> None:\n",
    "        print(f\"{self.name} goes gobble gobble!\")\n",
    "    \n",
    "    def doesItFly(self) -> bool:\n",
    "        return self.flight\n",
    "    \n",
    "    def getBreed(self) -> str:\n",
    "        return self.breed\n",
    "    \n",
    "    \n",
    "\n",
    "dog = Dog(\"Bufford\", \"Pitbull\")\n",
    "dog.makeSound()\n",
    "print(dog.getBreed())\n",
    "\n",
    "print()\n",
    "\n",
    "bird = Bird(\"Timmy\", \"Wild Turkey\", True)\n",
    "bird.makeSound()\n",
    "print(bird.getBreed())\n",
    "print(f\"{bird.breed}s fly: {bird.doesItFly()}\")\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Encapsulation ###\n",
    "Sometimes we need to limit direct access to some of an object's features to prevent accidental data modification.  We can do this through ***encapsulation***, a way of making attributes and methods private."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1300\n"
     ]
    }
   ],
   "source": [
    "class BankAccount:\n",
    "    def __init__(self, owner: str, balance: float) -> None:\n",
    "        self.owner = owner\n",
    "        self.__balance = balance # Private Attribute\n",
    "\n",
    "    def deposit(self, amount):\n",
    "        if self.__validateTransaction(amount):\n",
    "            self.__balance += amount\n",
    "\n",
    "    def withdraw(self, amount):\n",
    "        if self.__validateTransaction(amount) and amount <= self.__balance:\n",
    "            self.__balance -= amount\n",
    "\n",
    "    def getBalance(self):\n",
    "        return self.__balance\n",
    "\n",
    "    # This Private Method cannot be called outside of the class itself\n",
    "    def __validateTransaction(self, amount):\n",
    "        if amount > 0:\n",
    "            return True\n",
    "        else:\n",
    "            print(\"Invalid transaction amount\")\n",
    "            return False\n",
    "\n",
    "# Create an instance of BankAccount\n",
    "account = BankAccount(\"Alice\", 1000)\n",
    "account.deposit(500)\n",
    "account.withdraw(200)\n",
    "print(account.getBalance())  # Output: 1300\n",
    "#print(account.__validateTransaction(0)) # When called, will produce an AttributeError"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercises ###\n",
    "1. Create a `Book` class with the following properties and method, then create 2 instances and call the class' method  \n",
    "- Properties\n",
    "    - Title : String\n",
    "    - Author : String\n",
    "    - Pages : Int\n",
    "- Method\n",
    "    - `getDetails` should print the title, author, and page count of a Book.  Should have no return type"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Book:\n",
    "    #Start coding here\n",
    "    pass # Remove this line when complete"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. Define an abstract `Vehicle` class with `Car` and `Bike` subclasses inheriting from it.  `Vehicle` should have an Abstract Method called `vehicleInfo`, which is overriden by the subclasses with their own details.  *Hint: Use the super() function to call the methods.*\n",
    "- Properties\n",
    "    - `Vehicle` Class\n",
    "        - Make: String\n",
    "        - Model: String\n",
    "        - Year: Int\n",
    "- Method \n",
    "    - `vehicleInfo` should print the vehicle type (Car or Bike), followed by the information common to all vehicles. Should have no return type.   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Add import statements here\n",
    "\n",
    "class Vehicle():\n",
    "    pass # Remove this line when complete\n",
    "    \n",
    "\n",
    "class Car(Vehicle):\n",
    "    pass # Remove this line when complete\n",
    "\n",
    "class Bike(Vehicle):\n",
    "    pass # Remove this line when complete\n",
    "\n",
    "# Create instances and test functions\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3. Create an abstract `Shape` class with an abstract `area` method.  Make `Circle` and `Square` subclasses which implement the area method differently.\n",
    "- Properties\n",
    "    - `Shape`\n",
    "        - None\n",
    "    - `Circle`\n",
    "        - Radius\n",
    "    - `Square`\n",
    "        - Length\n",
    "- Method\n",
    "    - `area` should calculate the area of the shape in question. Returns a numeric value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Add import statements for doing the math and abstraction\n",
    "\n",
    "class Shape():\n",
    "    pass # Remove this line when complete\n",
    "\n",
    "class Circle(Shape):\n",
    "    pass # Remove this line when complete\n",
    "\n",
    "class Square(Shape):\n",
    "    pass # Remove this line when complete "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Advanced Data Structures & Algorithms ##\n",
    "Now that we've covered OOP, we're going to create some more advanced data structured from the ground up.  There are pre-existing libraries for some of these structures in Python, but learning to build them from the ground up allows you to understand them a bit more and create more efficient versions.  THis is especially important considering some of the concepts can become a tad complex.\n",
    "\n",
    "## Linked Lists ##\n",
    "- Linear data structure where elements (called *Nodes*) are stored in separate objects,  Each node contains two pieces:\n",
    "    - Data: The actual value stored\n",
    "    - Pointer: A reference to the next node in a sequence (or the previous node and next node in the case of a doubly linked list)\n",
    "- Three Types:\n",
    "    - Singly Linked List: Each node points to the next node in the sequence.  The last node points to None\n",
    "    - Doubly Linked List: Each node has two pointers, one to the previous node, and another to the next node\n",
    "    - Circular Linked List: Singly or Doubly Linked List where the last node points back to the first, or in the case of doubly, the first points to the last as well\n",
    "- Advantages of use:\n",
    "    - Dynamic Sizing allows easy scalability up or down by adding or removing nodes without needing to resize a list or array\n",
    "    - Efficient Insertion/Deletion compared to arrays/lists.  We only change the pointers, not individual elements\n",
    "    - No required contiguous memory allocation means better memory management, which is great for systems with limited RAM\n",
    "    - Linked lists are the basis for implementing other complex data structures like stacks, queues, dictionaries, and graphs from the ground up\n",
    "\n",
    "- Singly Linked List Pros & Cons\n",
    "    - Simple to implement and understand\n",
    "    - Suitable for general purposes\n",
    "    - Inefficient insterstion & deletion unless optimized (O(n) when the tail is not maintained)\n",
    "    - Requires special handling to detect the end of the list\n",
    "- Doubly Linked List Pros & Cons\n",
    "    - Effective Traversal bidirectionally\n",
    "    - Easier to delete nodes given a reference to those nodes\n",
    "    - Increased memory usage from maintaining the extra prev pointer\n",
    "    - More complex to implement\n",
    "- Circular Singly Linked List Pros & Cons\n",
    "    - Efficient Insertions and Deletions at both ends\n",
    "    - Simple looping and traversal\n",
    "    - Slightly more complex to implement and understand\n",
    "    - Traversal needs to be managed carefully to avoid infinite looping\n",
    "- Circular Doubly Linked List Pros & Cons\n",
    "    - Combines the benefits of circular and doubly linked lists\n",
    "    - Efficient bidirectional traversal\n",
    "    - Simplified and uniform node handling\n",
    "    - More complex and higher memory usage due to the extra pointers\n",
    "\n",
    "    \n",
    "- Circular Linked Lists in particular come with distinct benefits\n",
    "    - Constant Time Insertion and Deletion due to looped structure\n",
    "    - More memory efficient because they don't need to maintain separate head and tail structures (but can be made more time efficient with these structures, meaning there is a trade-off between space and time depending on implementation)\n",
    "    - Great for implementing circular buffers, which make them ideal in streaming, networking, and scheduling tasks\n",
    "    - Easier looping since the end of thie list connects back to the beginning\n",
    "    - Solves for problems which are inherently circular (token ring networks, round-robin scheduling, etc.)\n",
    "    - Uniform treatment of nodes due to no distinct end node.\n",
    "\n",
    "### Singly Linked List Implementation ###"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 -> 1 -> 2 -> None\n",
      "0 -> 2 -> None\n"
     ]
    }
   ],
   "source": [
    "class Node:\n",
    "    def __init__(self, data):\n",
    "        self.data = data  # The data value stored in the node\n",
    "        self.next = None  # Pointer to the next node\n",
    "\n",
    "class SinglyLinkedList:\n",
    "    def __init__(self):\n",
    "        self.head = None  # Pointer to the first node in the list\n",
    "        self.tail = None  # Pointer to the last node in the list\n",
    "\n",
    "    def append(self, data):\n",
    "        \"\"\"\n",
    "        Add a node with the given data to the end of the list.\n",
    "        \"\"\"\n",
    "        new_node = Node(data)\n",
    "        if not self.head:\n",
    "            # If the list is empty, initialize the list with the new node\n",
    "            self.head = self.tail = new_node\n",
    "        else:\n",
    "            # Link the new node to the end of the list\n",
    "            self.tail.next = new_node\n",
    "            self.tail = new_node  # Update the tail to be the new node\n",
    "\n",
    "    def prepend(self, data):\n",
    "        \"\"\"\n",
    "        Add a node with the given data to the beginning of the list.\n",
    "        \"\"\"\n",
    "        new_node = Node(data)\n",
    "        if not self.head:\n",
    "            # If the list is empty, initialize the list with the new node\n",
    "            self.head = self.tail = new_node\n",
    "        else:\n",
    "            # Link the new node to the beginning of the list\n",
    "            new_node.next = self.head\n",
    "            self.head = new_node  # Update the head to be the new node\n",
    "\n",
    "    def deleteWithValue(self, data):\n",
    "        \"\"\"\n",
    "        Delete the first node that contains the given data.\n",
    "        \"\"\"\n",
    "        if not self.head:\n",
    "            return  # If the list is empty, there's nothing to delete\n",
    "        if self.head.data == data:\n",
    "            # If the node to delete is the head\n",
    "            if self.head == self.tail:\n",
    "                # If the list has only one node\n",
    "                self.head = self.tail = None\n",
    "            else:\n",
    "                self.head = self.head.next\n",
    "            return\n",
    "        current_node = self.head\n",
    "        while current_node.next and current_node.next.data != data:\n",
    "            current_node = current_node.next\n",
    "        if current_node.next:\n",
    "            if current_node.next == self.tail:\n",
    "                self.tail = current_node\n",
    "            current_node.next = current_node.next.next\n",
    "\n",
    "    def printList(self):\n",
    "        \"\"\"\n",
    "        Print the list data from head to tail.\n",
    "        \"\"\"\n",
    "        current_node = self.head\n",
    "        while current_node:\n",
    "            print(current_node.data, end=\" -> \")\n",
    "            current_node = current_node.next\n",
    "        print(\"None\")\n",
    "\n",
    "# Usage\n",
    "sll = SinglyLinkedList()\n",
    "sll.append(1)\n",
    "sll.append(2)\n",
    "sll.prepend(0)\n",
    "sll.printList()  # Output: 0 -> 1 -> 2 -> None\n",
    "sll.deleteWithValue(1)\n",
    "sll.printList()  # Output: 0 -> 2 -> None\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Doubly Linked List Implementation ###"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 <-> 1 <-> 2 <-> None\n",
      "2 <-> 1 <-> 0 <-> None\n",
      "0 <-> 2 <-> None\n"
     ]
    }
   ],
   "source": [
    "class Node:\n",
    "    def __init__(self, data):\n",
    "        self.data = data  # The data value stored in the node\n",
    "        self.prev = None  # Pointer to the previous node\n",
    "        self.next = None  # Pointer to the next node\n",
    "\n",
    "class DoublyLinkedList:\n",
    "    def __init__(self):\n",
    "        self.head = None  # Pointer to the first node in the list\n",
    "        self.tail = None  # Pointer to the last node in the list\n",
    "\n",
    "    def append(self, data):\n",
    "        \"\"\"\n",
    "        Add a node with the given data to the end of the list.\n",
    "        \"\"\"\n",
    "        new_node = Node(data)\n",
    "        if not self.head:\n",
    "            # If the list is empty, initialize the list with the new node\n",
    "            self.head = self.tail = new_node\n",
    "            return\n",
    "        # Link the new node to the end of the list\n",
    "        new_node.prev = self.tail\n",
    "        self.tail.next = new_node\n",
    "        self.tail = new_node  # Update the tail to be the new node\n",
    "\n",
    "    def prepend(self, data):\n",
    "        \"\"\"\n",
    "        Add a node with the given data to the beginning of the list.\n",
    "        \"\"\"\n",
    "        new_node = Node(data)\n",
    "        if not self.head:\n",
    "            # If the list is empty, initialize the list with the new node\n",
    "            self.head = self.tail = new_node\n",
    "            return\n",
    "        # Link the new node to the beginning of the list\n",
    "        new_node.next = self.head\n",
    "        self.head.prev = new_node\n",
    "        self.head = new_node  # Update the head to be the new node\n",
    "\n",
    "    def deleteWithValue(self, data):\n",
    "        \"\"\"\n",
    "        Delete the first node that contains the given data.\n",
    "        \"\"\"\n",
    "        if not self.head:\n",
    "            return  # If the list is empty, there's nothing to delete\n",
    "        current_node = self.head\n",
    "        while current_node and current_node.data != data:\n",
    "            current_node = current_node.next\n",
    "        if not current_node:\n",
    "            return\n",
    "        if current_node.prev:\n",
    "            current_node.prev.next = current_node.next\n",
    "        if current_node.next:\n",
    "            current_node.next.prev = current_node.prev\n",
    "        if current_node == self.head:\n",
    "            self.head = current_node.next\n",
    "        if current_node == self.tail:\n",
    "            self.tail = current_node.prev\n",
    "\n",
    "    def printListForward(self):\n",
    "        \"\"\"\n",
    "        Print the list data from head to tail.\n",
    "        \"\"\"\n",
    "        current_node = self.head\n",
    "        while current_node:\n",
    "            print(current_node.data, end=\" <-> \")\n",
    "            current_node = current_node.next\n",
    "        print(\"None\")\n",
    "\n",
    "    def printListBackward(self):\n",
    "        \"\"\"\n",
    "        Print the list data from tail to head.\n",
    "        \"\"\"\n",
    "        current_node = self.tail\n",
    "        while current_node:\n",
    "            print(current_node.data, end=\" <-> \")\n",
    "            current_node = current_node.prev\n",
    "        print(\"None\")\n",
    "\n",
    "# Usage\n",
    "dll = DoublyLinkedList()\n",
    "dll.append(1)\n",
    "dll.append(2)\n",
    "dll.prepend(0)\n",
    "dll.printListForward()  # Output: 0 <-> 1 <-> 2 <-> None\n",
    "dll.printListBackward() # Output: 2 <-> 1 <-> 0 <-> None\n",
    "dll.deleteWithValue(1)\n",
    "dll.printListForward()  # Output: 0 <-> 2 <-> None\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### (Singly) Circular Linked List Implementation ###"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 -> 1 -> 2 -> None\n",
      "0 -> 2 -> None\n"
     ]
    }
   ],
   "source": [
    "class Node:\n",
    "    def __init__(self, data):\n",
    "        self.data = data  # The data value stored in the node\n",
    "        self.next = None  # Pointer to the next node\n",
    "\n",
    "class CircularLinkedList:\n",
    "    def __init__(self):\n",
    "        self.head = None  # Pointer to the first node in the list\n",
    "        self.tail = None  # Pointer to the last node in the list\n",
    "\n",
    "    def append(self, data):\n",
    "        \"\"\"\n",
    "        Add a node with the given data to the end of the list.\n",
    "        \"\"\"\n",
    "        new_node = Node(data)\n",
    "        if not self.head:\n",
    "            # If the list is empty, initialize the list with the new node\n",
    "            self.head = self.tail = new_node\n",
    "            new_node.next = self.head  # Circular link\n",
    "            return\n",
    "        # Link the new node to the end of the list\n",
    "        self.tail.next = new_node\n",
    "        self.tail = new_node  # Update the tail to be the new node\n",
    "        self.tail.next = self.head  # Maintain the circular link\n",
    "\n",
    "    def prepend(self, data):\n",
    "        \"\"\"\n",
    "        Add a node with the given data to the beginning of the list.\n",
    "        \"\"\"\n",
    "        new_node = Node(data)\n",
    "        if not self.head:\n",
    "            # If the list is empty, initialize the list with the new node\n",
    "            self.head = self.tail = new_node\n",
    "            new_node.next = self.head  # Circular link\n",
    "            return\n",
    "        # Link the new node to the beginning of the list\n",
    "        new_node.next = self.head\n",
    "        self.head = new_node  # Update the head to be the new node\n",
    "        self.tail.next = self.head  # Maintain the circular link\n",
    "\n",
    "    def deleteWithValue(self, data):\n",
    "        \"\"\"\n",
    "        Delete the first node that contains the given data.\n",
    "        \"\"\"\n",
    "        if not self.head:\n",
    "            return  # If the list is empty, there's nothing to delete\n",
    "        current_node = self.head\n",
    "        prev_node = None\n",
    "        while True:\n",
    "            if current_node.data == data:\n",
    "                if current_node == self.head:\n",
    "                    if self.head == self.tail:\n",
    "                        # If the list has only one node\n",
    "                        self.head = self.tail = None\n",
    "                    else:\n",
    "                        self.head = self.head.next\n",
    "                        self.tail.next = self.head\n",
    "                else:\n",
    "                    prev_node.next = current_node.next\n",
    "                    if current_node == self.tail:\n",
    "                        self.tail = prev_node\n",
    "                return\n",
    "            prev_node = current_node\n",
    "            current_node = current_node.next\n",
    "            if current_node == self.head:\n",
    "                break  # Exit if we have traversed the entire list\n",
    "\n",
    "    def printList(self):\n",
    "        \"\"\"\n",
    "        Print the list data starting from the head.\n",
    "        \"\"\"\n",
    "        if not self.head:\n",
    "            print(\"List is empty\")\n",
    "            return\n",
    "        current_node = self.head\n",
    "        while True:\n",
    "            print(current_node.data, end=\" -> \")\n",
    "            current_node = current_node.next\n",
    "            if current_node == self.head:\n",
    "                break  # Exit if we have returned to the head\n",
    "        print(\"None\")\n",
    "\n",
    "# Usage\n",
    "cll = CircularLinkedList()\n",
    "cll.append(1)\n",
    "cll.append(2)\n",
    "cll.prepend(0)\n",
    "cll.printList()  # Output: 0 -> 1 -> 2 -> None\n",
    "cll.deleteWithValue(1)\n",
    "cll.printList()  # Output: 0 -> 2 -> None\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### (Doubly) Circular Linked List Implementation ###"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 <-> 1 <-> 2 <-> None\n",
      "2 <-> 1 <-> 0 <-> None\n",
      "0 <-> 2 <-> None\n"
     ]
    }
   ],
   "source": [
    "class Node:\n",
    "    def __init__(self, data):\n",
    "        self.data = data  # The data value stored in the node\n",
    "        self.prev = None  # Pointer to the previous node\n",
    "        self.next = None  # Pointer to the next node\n",
    "\n",
    "class DoublyCircularLinkedList:\n",
    "    def __init__(self):\n",
    "        self.head = None  # Pointer to the first node in the list\n",
    "        self.tail = None  # Pointer to the last node in the list\n",
    "\n",
    "    def append(self, data):\n",
    "        \"\"\"\n",
    "        Add a node with the given data to the end of the list.\n",
    "        \"\"\"\n",
    "        new_node = Node(data)\n",
    "        if not self.head:\n",
    "            # If the list is empty, initialize the list with the new node\n",
    "            self.head = self.tail = new_node\n",
    "            self.head.next = self.head.prev = self.head  # Circular link\n",
    "        else:\n",
    "            # Link the new node to the end of the list\n",
    "            new_node.prev = self.tail\n",
    "            new_node.next = self.head\n",
    "            self.tail.next = new_node\n",
    "            self.head.prev = new_node\n",
    "            self.tail = new_node  # Update the tail to be the new node\n",
    "\n",
    "    def prepend(self, data):\n",
    "        \"\"\"\n",
    "        Add a node with the given data to the beginning of the list.\n",
    "        \"\"\"\n",
    "        new_node = Node(data)\n",
    "        if not self.head:\n",
    "            # If the list is empty, initialize the list with the new node\n",
    "            self.head = self.tail = new_node\n",
    "            self.head.next = self.head.prev = self.head  # Circular link\n",
    "        else:\n",
    "            # Link the new node to the beginning of the list\n",
    "            new_node.next = self.head\n",
    "            new_node.prev = self.tail\n",
    "            self.head.prev = new_node\n",
    "            self.tail.next = new_node\n",
    "            self.head = new_node  # Update the head to be the new node\n",
    "\n",
    "    def deleteWithValue(self, data):\n",
    "        \"\"\"\n",
    "        Delete the first node that contains the given data.\n",
    "        \"\"\"\n",
    "        if not self.head:\n",
    "            return  # If the list is empty, there's nothing to delete\n",
    "        current_node = self.head\n",
    "        while True:\n",
    "            if current_node.data == data:\n",
    "                if current_node == self.head:\n",
    "                    if self.head == self.tail:\n",
    "                        # If the list has only one node\n",
    "                        self.head = self.tail = None\n",
    "                    else:\n",
    "                        self.tail.next = self.head.next\n",
    "                        self.head.next.prev = self.tail\n",
    "                        self.head = self.head.next\n",
    "                elif current_node == self.tail:\n",
    "                    # If the node to delete is the tail\n",
    "                    self.tail = self.tail.prev\n",
    "                    self.tail.next = self.head\n",
    "                    self.head.prev = self.tail\n",
    "                else:\n",
    "                    # If the node to delete is in the middle\n",
    "                    current_node.prev.next = current_node.next\n",
    "                    current_node.next.prev = current_node.prev\n",
    "                return\n",
    "            current_node = current_node.next\n",
    "            if current_node == self.head:\n",
    "                break  # Exit if we have traversed the entire list\n",
    "\n",
    "    def printListForward(self):\n",
    "        \"\"\"\n",
    "        Print the list data from head to tail.\n",
    "        \"\"\"\n",
    "        if not self.head:\n",
    "            print(\"List is empty\")\n",
    "            return\n",
    "        current_node = self.head\n",
    "        while True:\n",
    "            print(current_node.data, end=\" <-> \")\n",
    "            current_node = current_node.next\n",
    "            if current_node == self.head:\n",
    "                break  # Exit if we have returned to the head\n",
    "        print(\"None\")\n",
    "\n",
    "    def printListBackward(self):\n",
    "        \"\"\"\n",
    "        Print the list data from tail to head.\n",
    "        \"\"\"\n",
    "        if not self.tail:\n",
    "            print(\"List is empty\")\n",
    "            return\n",
    "        current_node = self.tail\n",
    "        while True:\n",
    "            print(current_node.data, end=\" <-> \")\n",
    "            current_node = current_node.prev\n",
    "            if current_node == self.tail:\n",
    "                break  # Exit if we have returned to the tail\n",
    "        print(\"None\")\n",
    "\n",
    "# Usage\n",
    "dccll = DoublyCircularLinkedList()\n",
    "dccll.append(1)\n",
    "dccll.append(2)\n",
    "dccll.prepend(0)\n",
    "dccll.printListForward()  # Output: 0 <-> 1 <-> 2 <-> None\n",
    "dccll.printListBackward() # Output: 2 <-> 1 <-> 0 <-> None\n",
    "dccll.deleteWithValue(1)\n",
    "dccll.printListForward()  # Output: 0 <-> 2 <-> None\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Trees ##\n",
    "Trees are a fundamental data structure used to represent hierarchial relationsips.  Trees are used mostly to: represent hierarchies; provide efficient searching and sorting operations; routing and navigation through networks, websites, and file structures; database indexing; and AI decision making\n",
    "  \n",
    "Trees have the following structure:\n",
    "- Node: An element of a tree\n",
    "- Root: The top node of a tree\n",
    "- Parent: A node with one or more child nodes\n",
    "- Child: A node that is a descendant of another node\n",
    "- Leaf: A node with no children\n",
    "- Subtree: A tree formed by a node and its descendants\n",
    "- Depth: The length of the path from the root to a node\n",
    "- Height: The length of the path from a node to the deepest leaf\n",
    "- Binary Tree: A tree where each node has at most two children\n",
    "- Balanced Tree: A tree is balanced if all leaves are on the same level or within one level of each other\n",
    "  \n",
    "There are a lot of different kinds of trees but we'll focus on the following:\n",
    "- Binary Trees: Basic tree structure for representing hierarchial data \n",
    "- Binary Search Trees: Provides efficiecnt read, update, and deletion operations\n",
    "- AVL Trees: Self-balancing BST with O(log n) operations\n",
    "- B-Trees: Self-balancing tree for efficient data storage & retrieval, ideal for databases\n",
    "- Tries: Good at string matching and prefix queries\n",
    "\n",
    "Trees are used a lot in decision making in ML & AI Libraries.  While they are all implemented by these libraries, it is important to understand how they operate under the hood to some extent.\n",
    "\n",
    "### Binary Tree Implementation ###"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "In-order Traversal: [4, 2, 5, 1, 3]\n"
     ]
    }
   ],
   "source": [
    "class BinaryTreeNode:\n",
    "    def __init__(self, data):\n",
    "        self.data = data  # The value stored in the node\n",
    "        self.left = None  # Pointer to the left child node\n",
    "        self.right = None  # Pointer to the right child node\n",
    "\n",
    "class BinaryTree:\n",
    "    def __init__(self):\n",
    "        self.root = None  # Pointer to the root of the tree\n",
    "\n",
    "    def insert(self, data):\n",
    "        \"\"\"\n",
    "        Insert data into the binary tree. Nodes are inserted at the first available position.\n",
    "        \"\"\"\n",
    "        newNode = BinaryTreeNode(data)  # Create a new node\n",
    "        if not self.root:\n",
    "            # If the tree is empty, set the new node as the root\n",
    "            self.root = newNode\n",
    "            return\n",
    "        queue = [self.root]  # Initialize a queue with the root node for level-order insertion\n",
    "        while queue:\n",
    "            current = queue.pop(0)  # Get the first node in the queue\n",
    "            if not current.left:\n",
    "                # If the current node has no left child, insert the new node as the left child\n",
    "                current.left = newNode\n",
    "                return\n",
    "            else:\n",
    "                queue.append(current.left)  # Add the left child to the queue\n",
    "            if not current.right:\n",
    "                # If the current node has no right child, insert the new node as the right child\n",
    "                current.right = newNode\n",
    "                return\n",
    "            else:\n",
    "                queue.append(current.right)  # Add the right child to the queue\n",
    "\n",
    "    def inorderTraversal(self, node, result=None):\n",
    "        \"\"\"\n",
    "        In-order traversal of the binary tree. Left -> Root -> Right\n",
    "        \"\"\"\n",
    "        if result is None:\n",
    "            result = []  # Initialize the result list if not provided\n",
    "        if node:\n",
    "            self.inorderTraversal(node.left, result)  # Traverse the left subtree\n",
    "            result.append(node.data)  # Visit the root node\n",
    "            self.inorderTraversal(node.right, result)  # Traverse the right subtree\n",
    "        return result\n",
    "\n",
    "# Example usage:\n",
    "bt = BinaryTree()\n",
    "bt.insert(1)\n",
    "bt.insert(2)\n",
    "bt.insert(3)\n",
    "bt.insert(4)\n",
    "bt.insert(5)\n",
    "print(\"In-order Traversal:\", bt.inorderTraversal(bt.root))  # Output: [4, 2, 5, 1, 3]\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Binary Search Tree Implementation ###"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "In-order Traversal: [4, 2, 5, 1, 3]\n"
     ]
    }
   ],
   "source": [
    "class BSTNode:\n",
    "    def __init__(self, data):\n",
    "        self.data = data  # The value stored in the node\n",
    "        self.left = None  # Pointer to the left child node\n",
    "        self.right = None  # Pointer to the right child node\n",
    "\n",
    "class BinarySearchTree:\n",
    "    def __init__(self):\n",
    "        self.root = None  # Pointer to the root of the tree\n",
    "\n",
    "    def insert(self, data):\n",
    "        \"\"\"\n",
    "        Insert data into the BST. Nodes are inserted in a way that maintains the BST property.\n",
    "        \"\"\"\n",
    "        if not self.root:\n",
    "            # If the tree is empty, set the new node as the root\n",
    "            self.root = BSTNode(data)\n",
    "            return\n",
    "        self._insertRecursive(self.root, data)  # Call the recursive insert function\n",
    "\n",
    "    def _insertRecursive(self, node, data):\n",
    "        if data < node.data:\n",
    "            # If the data is less than the current node's data, go to the left subtree\n",
    "            if node.left:\n",
    "                self._insertRecursive(node.left, data)  # Recursively insert in the left subtree\n",
    "            else:\n",
    "                node.left = BSTNode(data)  # Create a new left child node\n",
    "        else:\n",
    "            # If the data is greater than or equal to the current node's data, go to the right subtree\n",
    "            if node.right:\n",
    "                self._insertRecursive(node.right, data)  # Recursively insert in the right subtree\n",
    "            else:\n",
    "                node.right = BSTNode(data)  # Create a new right child node\n",
    "\n",
    "    def inorderTraversal(self, node, result=None):\n",
    "        \"\"\"\n",
    "        In-order traversal of the BST. Left -> Root -> Right\n",
    "        \"\"\"\n",
    "        if result is None:\n",
    "            result = []  # Initialize the result list if not provided\n",
    "        if node:\n",
    "            self.inorderTraversal(node.left, result)  # Traverse the left subtree\n",
    "            result.append(node.data)  # Visit the root node\n",
    "            self.inorderTraversal(node.right, result)  # Traverse the right subtree\n",
    "        return result\n",
    "\n",
    "# Example usage:\n",
    "bst = BinarySearchTree()\n",
    "bst.insert(10)\n",
    "bst.insert(5)\n",
    "bst.insert(15)\n",
    "bst.insert(2)\n",
    "bst.insert(7)\n",
    "print(\"In-order Traversal:\", bst.inorderTraversal(bst.root))  # Output: [2, 5, 7, 10, 15]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### AVL Tree Implementation ###"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "In-order Traversal: [10, 20, 30, 40, 50]\n"
     ]
    }
   ],
   "source": [
    "class AVLNode:\n",
    "    def __init__(self, data):\n",
    "        self.data = data  # The value stored in the node\n",
    "        self.left = None  # Pointer to the left child node\n",
    "        self.right = None  # Pointer to the right child node\n",
    "        self.height = 1  # Height of the node (1 for a new node)\n",
    "\n",
    "class AVLTree:\n",
    "    def __init__(self):\n",
    "        self.root = None  # Pointer to the root of the tree\n",
    "\n",
    "    def insert(self, data):\n",
    "        \"\"\"\n",
    "        Insert data into the AVL tree. The tree is balanced after each insertion.\n",
    "        \"\"\"\n",
    "        if not self.root:\n",
    "            self.root = AVLNode(data)  # If the tree is empty, set the new node as the root\n",
    "        else:\n",
    "            self.root = self._insertRecursive(self.root, data)  # Call the recursive insert function\n",
    "\n",
    "    def _insertRecursive(self, node, data):\n",
    "        if not node:\n",
    "            return AVLNode(data)  # Create a new node if the current position is empty\n",
    "\n",
    "        if data < node.data:\n",
    "            node.left = self._insertRecursive(node.left, data)  # Recursively insert in the left subtree\n",
    "        else:\n",
    "            node.right = self._insertRecursive(node.right, data)  # Recursively insert in the right subtree\n",
    "\n",
    "        node.height = 1 + max(self._getHeight(node.left), self._getHeight(node.right))  # Update the node's height\n",
    "\n",
    "        balance = self._getBalance(node)  # Get the balance factor\n",
    "\n",
    "        # Perform rotations to maintain balance\n",
    "        if balance > 1 and data < node.left.data:\n",
    "            return self._rightRotate(node)\n",
    "        if balance < -1 and data > node.right.data:\n",
    "            return self._leftRotate(node)\n",
    "        if balance > 1 and data > node.left.data:\n",
    "            node.left = self._leftRotate(node.left)\n",
    "            return self._rightRotate(node)\n",
    "        if balance < -1 and data < node.right.data:\n",
    "            node.right = self._rightRotate(node.right)\n",
    "            return self._leftRotate(node)\n",
    "\n",
    "        return node\n",
    "\n",
    "    def _leftRotate(self, z):\n",
    "        y = z.right\n",
    "        T2 = y.left\n",
    "        y.left = z\n",
    "        z.right = T2\n",
    "        z.height = 1 + max(self._getHeight(z.left), self._getHeight(z.right))\n",
    "        y.height = 1 + max(self._getHeight(y.left), self._getHeight(y.right))\n",
    "        return y\n",
    "\n",
    "    def _rightRotate(self, z):\n",
    "        y = z.left\n",
    "        T3 = y.right\n",
    "        y.right = z\n",
    "        z.left = T3\n",
    "        z.height = 1 + max(self._getHeight(z.left), self._getHeight(z.right))\n",
    "        y.height = 1 + max(self._getHeight(y.left), self._getHeight(y.right))\n",
    "        return y\n",
    "\n",
    "    def _getHeight(self, node):\n",
    "        if not node:\n",
    "            return 0\n",
    "        return node.height\n",
    "\n",
    "    def _getBalance(self, node):\n",
    "        if not node:\n",
    "            return 0\n",
    "        return self._getHeight(node.left) - self._getHeight(node.right)\n",
    "\n",
    "    def inorderTraversal(self, node, result=None):\n",
    "        \"\"\"\n",
    "        In-order traversal of the AVL tree. Left -> Root -> Right\n",
    "        \"\"\"\n",
    "        if result is None:\n",
    "            result = []  # Initialize the result list if not provided\n",
    "        if node:\n",
    "            self.inorderTraversal(node.left, result)  # Traverse the left subtree\n",
    "            result.append(node.data)  # Visit the root node\n",
    "            self.inorderTraversal(node.right, result)  # Traverse the right subtree\n",
    "        return result\n",
    "\n",
    "# Example usage:\n",
    "avl = AVLTree()\n",
    "avl.insert(10)\n",
    "avl.insert(20)\n",
    "avl.insert(30)\n",
    "avl.insert(40)\n",
    "avl.insert(50)\n",
    "print(\"In-order Traversal:\", avl.inorderTraversal(avl.root))  # Output: [10, 20, 30, 40, 50]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### B-Tree Implementation ###"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "In-order Traversal: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n"
     ]
    }
   ],
   "source": [
    "class BTreeNode:\n",
    "    def __init__(self, t, leaf=False):\n",
    "        self.t = t  # Minimum degree (defines the range for the number of keys)\n",
    "        self.leaf = leaf  # True if this node is a leaf node, otherwise False\n",
    "        self.keys = []  # List of keys in the node\n",
    "        self.children = []  # List of child pointers\n",
    "\n",
    "class BTree:\n",
    "    def __init__(self, t):\n",
    "        self.t = t  # Minimum degree\n",
    "        self.root = BTreeNode(t, leaf=True)  # Create the root node\n",
    "\n",
    "    def insert(self, k):\n",
    "        \"\"\"\n",
    "        Insert a new key into the B-tree.\n",
    "        \"\"\"\n",
    "        root = self.root\n",
    "        # If the root is full, the tree grows in height\n",
    "        if len(root.keys) == 2 * self.t - 1:\n",
    "            newRoot = BTreeNode(self.t)\n",
    "            newRoot.children.append(self.root)  # Old root becomes child of new root\n",
    "            self._splitChild(newRoot, 0)  # Split the old root and move a key to the new root\n",
    "            self.root = newRoot  # New root is now the root\n",
    "            self._insertNonFull(newRoot, k)  # Insert the new key into the non-full new root\n",
    "        else:\n",
    "            self._insertNonFull(root, k)  # Insert the new key into the non-full root\n",
    "\n",
    "    def _insertNonFull(self, node, k):\n",
    "        \"\"\"\n",
    "        Insert a key into a non-full node.\n",
    "        \"\"\"\n",
    "        i = len(node.keys) - 1  # Start from the end of the keys list\n",
    "        if node.leaf:\n",
    "            # If node is a leaf, find the location to insert the new key\n",
    "            node.keys.append((None, None))  # Add a dummy key to extend the list\n",
    "            while i >= 0 and k < node.keys[i]:\n",
    "                node.keys[i + 1] = node.keys[i]  # Shift keys to the right to make space\n",
    "                i -= 1\n",
    "            node.keys[i + 1] = k  # Insert the new key at the correct position\n",
    "        else:\n",
    "            # If node is not a leaf, find the child to recurse into\n",
    "            while i >= 0 and k < node.keys[i]:\n",
    "                i -= 1\n",
    "            i += 1\n",
    "            # If the child is full, split it\n",
    "            if len(node.children[i].keys) == 2 * self.t - 1:\n",
    "                self._splitChild(node, i)\n",
    "                if k > node.keys[i]:\n",
    "                    i += 1\n",
    "            self._insertNonFull(node.children[i], k)  # Recur for the appropriate child\n",
    "\n",
    "    def _splitChild(self, parent, i):\n",
    "        \"\"\"\n",
    "        Split the child of a node.\n",
    "        \"\"\"\n",
    "        t = self.t\n",
    "        y = parent.children[i]  # y is the node to be split\n",
    "        z = BTreeNode(t, y.leaf)  # z is the new node to store (t-1) keys of y\n",
    "        parent.children.insert(i + 1, z)  # Insert new node z as a child of parent\n",
    "        parent.keys.insert(i, y.keys[t - 1])  # Move the middle key of y to the parent\n",
    "        z.keys = y.keys[t: (2 * t) - 1]  # Copy the last (t-1) keys of y to z\n",
    "        y.keys = y.keys[0: t - 1]  # Reduce the number of keys in y\n",
    "        if not y.leaf:\n",
    "            z.children = y.children[t: 2 * t]  # Copy the last t children of y to z\n",
    "            y.children = y.children[0: t - 1]  # Reduce the number of children in y\n",
    "\n",
    "    def inorderTraversal(self, node, result=None):\n",
    "        \"\"\"\n",
    "        In-order traversal of the B-tree. Left -> Root -> Right\n",
    "        \"\"\"\n",
    "        if result is None:\n",
    "            result = []  # Initialize the result list if not provided\n",
    "        i = 0\n",
    "        while i < len(node.keys):\n",
    "            if not node.leaf:\n",
    "                self.inorderTraversal(node.children[i], result)  # Traverse the left subtree\n",
    "            result.append(node.keys[i])  # Visit the root node\n",
    "            i += 1\n",
    "        if not node.leaf:\n",
    "            self.inorderTraversal(node.children[i], result)  # Traverse the rightmost subtree\n",
    "        return result\n",
    "\n",
    "# Example usage:\n",
    "btree = BTree(3)  # Create a B-tree with minimum degree 3\n",
    "for i in range(10):\n",
    "    btree.insert(i)  # Insert keys 0 to 9 into the B-tree\n",
    "print(\"In-order Traversal:\", btree.inorderTraversal(btree.root))  # Output [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Trie Implementation ###"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "True\n",
      "False\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.children = {}  # Dictionary to store children nodes\n",
    "        self.endOfWord = False  # Boolean to mark the end of a word\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = TrieNode()  # Root node of the Trie\n",
    "\n",
    "    def insert(self, word):\n",
    "        \"\"\"\n",
    "        Insert a word into the Trie.\n",
    "        Args:\n",
    "            word (str): The word to be inserted into the Trie.\n",
    "        \"\"\"\n",
    "        node = self.root\n",
    "        for char in word:\n",
    "            if char not in node.children:\n",
    "                node.children[char] = TrieNode()  # Create a new TrieNode if character not present\n",
    "            node = node.children[char]\n",
    "        node.endOfWord = True  # Mark the end of the word\n",
    "\n",
    "    def search(self, word):\n",
    "        \"\"\"\n",
    "        Search for a word in the Trie. \n",
    "        Args:\n",
    "            word (str): The word to search for in the Trie.\n",
    "        Returns:\n",
    "            bool: True if the word exists, else False.\n",
    "        \"\"\"\n",
    "        node = self.root\n",
    "        for char in word:\n",
    "            if char not in node.children:\n",
    "                return False  # Return False if character not found\n",
    "            node = node.children[char]\n",
    "        return node.endOfWord  # Check if the current node marks the end of the word\n",
    "\n",
    "    def startsWith(self, prefix):\n",
    "        \"\"\"\n",
    "        Check if there is any word in the Trie that starts with the given prefix.\n",
    "        Args:\n",
    "            prefix (str): The prefix to check in the Trie.\n",
    "        Returns:\n",
    "            bool: True if any word starts with the prefix, else False.\n",
    "        \"\"\"\n",
    "        node = self.root\n",
    "        for char in prefix:\n",
    "            if char not in node.children:\n",
    "                return False  # Return False if character not found\n",
    "            node = node.children[char]\n",
    "        return True  # If all characters in the prefix are found, return True\n",
    "\n",
    "# Example usage:\n",
    "trie = Trie()\n",
    "trie.insert(\"hello\")\n",
    "trie.insert(\"hell\")\n",
    "trie.insert(\"heaven\")\n",
    "print(trie.search(\"hell\"))  # Output: True\n",
    "print(trie.search(\"hello\"))  # Output: True\n",
    "print(trie.search(\"he\"))  # Output: False\n",
    "print(trie.startsWith(\"he\"))  # Output: True\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Graphs ##\n",
    "- Graphs are collections of nodes (vertices) and edges which connect them.  Graphs are extremely vversatile data structures which help to solve a lot of real-world problems, as well as more abstract issues.  Generally, we don't need to implement these data structures ourselves for most machine learning and analytics tasks, but understanding the concepts and code behind them is helpful.  \n",
    "### Use Cases ###\n",
    "- Used for modeling relationships between entities\n",
    "    - Useful in social networks (imagine degrees of connection on LinkedIn)\n",
    "    - Modeling Road netowrks\n",
    "    - Representing the relationships between a website and the hyperlinks they have\n",
    "- Used in path finding and routing\n",
    "    - GPS & Navigation Software\n",
    "    - Network Routing \n",
    "- ML & AI\n",
    "    - Graph Neural Networks \n",
    "    - Recommendation systems to model user-item interactions\n",
    "- Network Analytics\n",
    "    - Protein interactions, genetic networks\n",
    "    - Finding communities or influencers in social networks\n",
    "- Data Organization\n",
    "    - File Systems \n",
    "    - Knowledge Graphs\n",
    "- Sceduling & Optimization\n",
    "    - Project Management with Directed Acyclic Graphs help to represent task dependencies  \n",
    "\n",
    "### Types of Graphs and Representations of Graphs ###\n",
    "- Graphs can be represented as adjacency lists or adjacency matrices\n",
    "    - An adjacency list is a collection of lists representing a graph.  \n",
    "        - Each node has a list containing the nodes it is connected to\n",
    "        - More space efficient at O(V + E) where V is the number of nodes and E is the number of edges\n",
    "        - More time complex to check the existence of an edge at O(degree of the vertex)\n",
    "    - An adjacency matrix represents a graph as a 2D matrix\n",
    "        - Rows and columns corespond to nodes, and the matrix inicates adjacency\n",
    "        - More space complex at O($V^2$)\n",
    "        - Time efficient when checking for the existence of an edge at O(1)\n",
    "        - Iterating over all neighoring vertices of a node at O(V)\n",
    "- There are a few different kinds of graphs\n",
    "    - Directed Graphs have edges with a direction, meaning nodes have one way relationships\n",
    "    - Undirected Graphs indicate a two way relationship between interconnected nodes\n",
    "    - Weighted graphs have edges with \"weights\", a measure of cost or distance between nodes\n",
    "    - Unweighted graphs are therefore self-explanatory\n",
    "    - Cyclic Graphs contain paths which start and end at the same node\n",
    "    - Acyclic graphs are therefore self-explanatory\n",
    "    - Graphs can be a combination of directed or undirected, weighted or unweighted, and cyclic or acyclic  \n",
    "### Graph Algorithms ###\n",
    "- Depth First Search (DPS) will explore as far as possible across a branch of nodes & edges before backtracking\n",
    "- Breadth First Search (BFS) explores all the neighboring nodes at the present depth before moving to nodes on the next level of depth.\n",
    "- Dijkstra's Algorithm finds the shortest path from a starting node to all other nodes in a weighted graph\n",
    "- Kruskal's & Prim's Algorithms find the minimum spannig tree of a graph\n",
    "    - The Minimum Spanning Tree (MST) of a graph is a subset of the edges connecting all vertices, without cycles, and the minimum possible total edge weight.\n",
    "        - Used in network design and hierarchical clustering method\n",
    "- A* Algorithm builds on Dijkstra's work, using heuristics to improve the efficiency of path finding (Used in most mapping softwares)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Undirected Graph Implementation ###\n",
    "This graph is Undirected & Unweighted"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Adjacency List:\n",
      "A: ['B', 'C']\n",
      "B: ['A', 'D']\n",
      "C: ['A']\n",
      "D: ['B']\n",
      "\n",
      "Adjacency Matrix:\n",
      "[0, 1, 1, 0]\n",
      "[1, 0, 0, 1]\n",
      "[1, 0, 0, 0]\n",
      "[0, 1, 0, 0]\n"
     ]
    }
   ],
   "source": [
    "class UndirectedGraph:\n",
    "    def __init__(self):\n",
    "        self.adjacencyList = {}  # Dictionary to store adjacency list representation\n",
    "        self.adjacencyMatrix = []  # List to store adjacency matrix representation\n",
    "        self.nodes = []  # List to store all nodes\n",
    "\n",
    "    def addNode(self, node):\n",
    "        \"\"\"Add a node to the graph.\"\"\"\n",
    "        if node not in self.adjacencyList:\n",
    "            self.adjacencyList[node] = []  # Initialize with an empty list\n",
    "            self.nodes.append(node)  # Add node to the list of nodes\n",
    "            self._updateMatrix()  # Update adjacency matrix\n",
    "\n",
    "    def addEdge(self, node1, node2):\n",
    "        \"\"\"Add an undirected edge between node1 and node2.\"\"\"\n",
    "        if node1 not in self.adjacencyList:\n",
    "            self.addNode(node1)\n",
    "        if node2 not in self.adjacencyList:\n",
    "            self.addNode(node2)\n",
    "        self.adjacencyList[node1].append(node2)  # Add node2 to the adjacency list of node1\n",
    "        self.adjacencyList[node2].append(node1)  # Add node1 to the adjacency list of node2\n",
    "        self._updateMatrix()  # Update adjacency matrix\n",
    "\n",
    "    def _updateMatrix(self):\n",
    "        \"\"\"Update the adjacency matrix to reflect the current graph structure.\"\"\"\n",
    "        size = len(self.nodes)\n",
    "        self.adjacencyMatrix = [[0] * size for _ in range(size)]  # Initialize matrix with zeros\n",
    "        nodeIndex = {node: i for i, node in enumerate(self.nodes)}  # Map nodes to indices\n",
    "        for node, neighbors in self.adjacencyList.items():\n",
    "            for neighbor in neighbors:\n",
    "                self.adjacencyMatrix[nodeIndex[node]][nodeIndex[neighbor]] = 1  # Set matrix entry to 1\n",
    "                self.adjacencyMatrix[nodeIndex[neighbor]][nodeIndex[node]] = 1  # Ensure symmetry for undirected graph\n",
    "\n",
    "    def display(self):\n",
    "        \"\"\"Display the adjacency list and adjacency matrix.\"\"\"\n",
    "        print(\"Adjacency List:\")\n",
    "        for node in self.adjacencyList:\n",
    "            print(f\"{node}: {self.adjacencyList[node]}\")\n",
    "        print(\"\\nAdjacency Matrix:\")\n",
    "        for row in self.adjacencyMatrix:\n",
    "            print(row)\n",
    "\n",
    "# Example usage\n",
    "ug = UndirectedGraph()\n",
    "ug.addEdge(\"A\", \"B\")\n",
    "ug.addEdge(\"A\", \"C\")\n",
    "ug.addEdge(\"B\", \"D\")\n",
    "ug.display()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Directed Graph Implementation ###\n",
    "This graph is Directed & Unweighted"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Adjacency List:\n",
      "A: ['B', 'C']\n",
      "B: ['D']\n",
      "C: []\n",
      "D: []\n",
      "\n",
      "Adjacency Matrix:\n",
      "[0, 1, 1, 0]\n",
      "[0, 0, 0, 1]\n",
      "[0, 0, 0, 0]\n",
      "[0, 0, 0, 0]\n"
     ]
    }
   ],
   "source": [
    "class DirectedGraph:\n",
    "    def __init__(self):\n",
    "        self.adjacencyList = {}  # Dictionary to store adjacency list representation\n",
    "        self.adjacencyMatrix = []  # List to store adjacency matrix representation\n",
    "        self.nodes = []  # List to store all nodes\n",
    "\n",
    "    def addNode(self, node):\n",
    "        \"\"\"Add a node to the graph.\"\"\"\n",
    "        if node not in self.adjacencyList:\n",
    "            self.adjacencyList[node] = []  # Initialize with an empty list\n",
    "            self.nodes.append(node)  # Add node to the list of nodes\n",
    "            self._updateMatrix()  # Update adjacency matrix\n",
    "\n",
    "    def addEdge(self, node1, node2):\n",
    "        \"\"\"Add a directed edge from node1 to node2.\"\"\"\n",
    "        if node1 not in self.adjacencyList:\n",
    "            self.addNode(node1)\n",
    "        if node2 not in self.adjacencyList:\n",
    "            self.addNode(node2)\n",
    "        self.adjacencyList[node1].append(node2)  # Add node2 to the adjacency list of node1\n",
    "        self._updateMatrix()  # Update adjacency matrix\n",
    "\n",
    "    def _updateMatrix(self):\n",
    "        \"\"\"Update the adjacency matrix to reflect the current graph structure.\"\"\"\n",
    "        size = len(self.nodes)\n",
    "        self.adjacencyMatrix = [[0] * size for _ in range(size)]  # Initialize matrix with zeros\n",
    "        nodeIndex = {node: i for i, node in enumerate(self.nodes)}  # Map nodes to indices\n",
    "        for node, neighbors in self.adjacencyList.items():\n",
    "            for neighbor in neighbors:\n",
    "                self.adjacencyMatrix[nodeIndex[node]][nodeIndex[neighbor]] = 1  # Set matrix entry to 1\n",
    "\n",
    "    def display(self):\n",
    "        \"\"\"Display the adjacency list and adjacency matrix.\"\"\"\n",
    "        print(\"Adjacency List:\")\n",
    "        for node in self.adjacencyList:\n",
    "            print(f\"{node}: {self.adjacencyList[node]}\")\n",
    "        print(\"\\nAdjacency Matrix:\")\n",
    "        for row in self.adjacencyMatrix:\n",
    "            print(row)\n",
    "\n",
    "# Example usage\n",
    "dg = DirectedGraph()\n",
    "dg.addEdge(\"A\", \"B\")\n",
    "dg.addEdge(\"A\", \"C\")\n",
    "dg.addEdge(\"B\", \"D\")\n",
    "dg.display()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Weighted Graph Implementation ###\n",
    "This is a weighted, undirected graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Adjacency List:\n",
      "A: [('B', 1), ('C', 2)]\n",
      "B: [('A', 1), ('D', 3)]\n",
      "C: [('A', 2)]\n",
      "D: [('B', 3)]\n",
      "\n",
      "Adjacency Matrix:\n",
      "[0, 1, 2, 0]\n",
      "[1, 0, 0, 3]\n",
      "[2, 0, 0, 0]\n",
      "[0, 3, 0, 0]\n"
     ]
    }
   ],
   "source": [
    "class WeightedGraph:\n",
    "    def __init__(self):\n",
    "        self.adjacencyList = {}  # Dictionary to store adjacency list representation\n",
    "        self.adjacencyMatrix = []  # List to store adjacency matrix representation\n",
    "        self.nodes = []  # List to store all nodes\n",
    "\n",
    "    def addNode(self, node):\n",
    "        \"\"\"Add a node to the graph.\"\"\"\n",
    "        if node not in self.adjacencyList:\n",
    "            self.adjacencyList[node] = []  # Initialize with an empty list\n",
    "            self.nodes.append(node)  # Add node to the list of nodes\n",
    "            self._updateMatrix()  # Update adjacency matrix\n",
    "\n",
    "    def addEdge(self, node1, node2, weight):\n",
    "        \"\"\"Add a weighted edge between node1 and node2.\"\"\"\n",
    "        if node1 not in self.adjacencyList:\n",
    "            self.addNode(node1)\n",
    "        if node2 not in self.adjacencyList:\n",
    "            self.addNode(node2)\n",
    "        self.adjacencyList[node1].append((node2, weight))  # Add node2 with weight to the adjacency list of node1\n",
    "        self.adjacencyList[node2].append((node1, weight))  # Add node1 with weight to the adjacency list of node2\n",
    "        self._updateMatrix()  # Update adjacency matrix\n",
    "\n",
    "    def _updateMatrix(self):\n",
    "        \"\"\"Update the adjacency matrix to reflect the current graph structure.\"\"\"\n",
    "        size = len(self.nodes)\n",
    "        self.adjacencyMatrix = [[0] * size for _ in range(size)]  # Initialize matrix with zeros\n",
    "        nodeIndex = {node: i for i, node in enumerate(self.nodes)}  # Map nodes to indices\n",
    "        for node, neighbors in self.adjacencyList.items():\n",
    "            for neighbor, weight in neighbors:\n",
    "                self.adjacencyMatrix[nodeIndex[node]][nodeIndex[neighbor]] = weight  # Set matrix entry to weight\n",
    "                self.adjacencyMatrix[nodeIndex[neighbor]][nodeIndex[node]] = weight  # Ensure symmetry for undirected graph\n",
    "\n",
    "    def display(self):\n",
    "        \"\"\"Display the adjacency list and adjacency matrix.\"\"\"\n",
    "        print(\"Adjacency List:\")\n",
    "        for node in self.adjacencyList:\n",
    "            print(f\"{node}: {self.adjacencyList[node]}\")\n",
    "        print(\"\\nAdjacency Matrix:\")\n",
    "        for row in self.adjacencyMatrix:\n",
    "            print(row)\n",
    "\n",
    "# Example usage\n",
    "wg = WeightedGraph()\n",
    "wg.addEdge(\"A\", \"B\", 1)\n",
    "wg.addEdge(\"A\", \"C\", 2)\n",
    "wg.addEdge(\"B\", \"D\", 3)\n",
    "wg.display()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Directed Weighted Graph ###\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Adjacency List:\n",
      "A: [('B', 1), ('C', 2)]\n",
      "B: [('D', 3)]\n",
      "C: []\n",
      "D: []\n",
      "\n",
      "Adjacency Matrix:\n",
      "[0, 1, 2, 0]\n",
      "[0, 0, 0, 3]\n",
      "[0, 0, 0, 0]\n",
      "[0, 0, 0, 0]\n"
     ]
    }
   ],
   "source": [
    "class DirectedWeightedGraph:\n",
    "    def __init__(self):\n",
    "        self.adjacencyList = {}  # Dictionary to store adjacency list representation\n",
    "        self.adjacencyMatrix = []  # List to store adjacency matrix representation\n",
    "        self.nodes = []  # List to store all nodes\n",
    "\n",
    "    def addNode(self, node):\n",
    "        \"\"\"Add a node to the graph.\"\"\"\n",
    "        if node not in self.adjacencyList:\n",
    "            self.adjacencyList[node] = []  # Initialize with an empty list\n",
    "            self.nodes.append(node)  # Add node to the list of nodes\n",
    "            self._updateMatrix()  # Update adjacency matrix\n",
    "\n",
    "    def addEdge(self, node1, node2, weight):\n",
    "        \"\"\"Add a directed weighted edge from node1 to node2.\"\"\"\n",
    "        if node1 not in self.adjacencyList:\n",
    "            self.addNode(node1)\n",
    "        if node2 not in self.adjacencyList:\n",
    "            self.addNode(node2)\n",
    "        self.adjacencyList[node1].append((node2, weight))  # Add node2 with weight to the adjacency list of node1\n",
    "        self._updateMatrix()  # Update adjacency matrix\n",
    "\n",
    "    def _updateMatrix(self):\n",
    "        \"\"\"Update the adjacency matrix to reflect the current graph structure.\"\"\"\n",
    "        size = len(self.nodes)\n",
    "        self.adjacencyMatrix = [[0] * size for _ in range(size)]  # Initialize matrix with zeros\n",
    "        nodeIndex = {node: i for i, node in enumerate(self.nodes)}  # Map nodes to indices\n",
    "        for node, neighbors in self.adjacencyList.items():\n",
    "            for neighbor, weight in neighbors:\n",
    "                self.adjacencyMatrix[nodeIndex[node]][nodeIndex[neighbor]] = weight  # Set matrix entry to weight\n",
    "\n",
    "    def display(self):\n",
    "        \"\"\"Display the adjacency list and adjacency matrix.\"\"\"\n",
    "        print(\"Adjacency List:\")\n",
    "        for node in self.adjacencyList:\n",
    "            print(f\"{node}: {self.adjacencyList[node]}\")\n",
    "        print(\"\\nAdjacency Matrix:\")\n",
    "        for row in self.adjacencyMatrix:\n",
    "            print(row)\n",
    "\n",
    "# Example usage\n",
    "dwg = DirectedWeightedGraph()\n",
    "dwg.addEdge(\"A\", \"B\", 1)\n",
    "dwg.addEdge(\"A\", \"C\", 2)\n",
    "dwg.addEdge(\"B\", \"D\", 3)\n",
    "dwg.display()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Cyclic Graphs ###\n",
    "Adding a node that creates a loop or cycle is all that defines a cyclic graph.  However, if we want to strictly enforce a graph to be acyclic, we may do so.\n",
    "### Acyclic Graphs ###\n",
    "We may use a DFS algorithm to detect cycles and prevent those edges from being added to a graph, directed or undirected."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Adding edge D - A creates a cycle. Edge not added.\n",
      "Adjacency List:\n",
      "A: ['B', 'C']\n",
      "B: ['A', 'D']\n",
      "C: ['A']\n",
      "D: ['B']\n",
      "\n",
      "Adjacency Matrix:\n",
      "[0, 1, 1, 0]\n",
      "[1, 0, 0, 1]\n",
      "[1, 0, 0, 0]\n",
      "[0, 1, 0, 0]\n"
     ]
    }
   ],
   "source": [
    "class UndirectedAcyclicGraph(UndirectedGraph):\n",
    "    def __init__(self):\n",
    "        super().__init__()  # Initialize the base class\n",
    "\n",
    "    def addEdge(self, node1, node2):\n",
    "        \"\"\"Add an undirected edge between node1 and node2, ensuring no cycles are created.\"\"\"\n",
    "        if node1 not in self.adjacencyList:\n",
    "            self.addNode(node1)\n",
    "        if node2 not in self.adjacencyList:\n",
    "            self.addNode(node2)\n",
    "        if self._createsCycle(node1, node2):\n",
    "            print(f\"Adding edge {node1} - {node2} creates a cycle. Edge not added.\")\n",
    "        else:\n",
    "            self.adjacencyList[node1].append(node2)  # Add node2 to the adjacency list of node1\n",
    "            self.adjacencyList[node2].append(node1)  # Add node1 to the adjacency list of node2\n",
    "            self._updateMatrix()  # Update adjacency matrix\n",
    "\n",
    "    def _createsCycle(self, node1, node2):\n",
    "        \"\"\"Check if adding an edge creates a cycle using DFS.\"\"\"\n",
    "        visited = set()\n",
    "        return self._dfs(node1, node2, visited, None)\n",
    "\n",
    "    def _dfs(self, current, target, visited, parent):\n",
    "        \"\"\"Depth-first search to detect cycles.\"\"\"\n",
    "        visited.add(current)\n",
    "        for neighbor in self.adjacencyList[current]:\n",
    "            if neighbor == parent:  # Skip the edge we came from\n",
    "                continue\n",
    "            if neighbor == target:\n",
    "                return True\n",
    "            if neighbor not in visited and self._dfs(neighbor, target, visited, current):\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "# Example usage\n",
    "uag = UndirectedAcyclicGraph()\n",
    "uag.addEdge(\"A\", \"B\")\n",
    "uag.addEdge(\"A\", \"C\")\n",
    "uag.addEdge(\"B\", \"D\")\n",
    "uag.addEdge(\"D\", \"A\")  # This will not be added as it creates a cycle\n",
    "uag.display()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Adding edge D -> A creates a cycle. Edge not added.\n",
      "Adjacency List:\n",
      "A: ['B', 'C']\n",
      "B: ['D']\n",
      "C: []\n",
      "D: []\n",
      "\n",
      "Adjacency Matrix:\n",
      "[0, 1, 1, 0]\n",
      "[0, 0, 0, 1]\n",
      "[0, 0, 0, 0]\n",
      "[0, 0, 0, 0]\n"
     ]
    }
   ],
   "source": [
    "class DirectedAcyclicGraph(DirectedGraph):\n",
    "    def __init__(self):\n",
    "        super().__init__()\n",
    "\n",
    "    def addEdge(self, node1, node2):\n",
    "        \"\"\"Add a directed edge from node1 to node2, ensuring no cycles are created.\"\"\"\n",
    "        if self._createsCycle(node1, node2):\n",
    "            print(f\"Adding edge {node1} -> {node2} creates a cycle. Edge not added.\")\n",
    "        else:\n",
    "            super().addEdge(node1, node2)\n",
    "            self._updateMatrix()  # Update adjacency matrix\n",
    "\n",
    "    def _createsCycle(self, node1, node2):\n",
    "        \"\"\"Check if adding an edge creates a cycle.\"\"\"\n",
    "        visited = set()\n",
    "        return self._dfs(node2, node1, visited)\n",
    "\n",
    "    def _dfs(self, current, target, visited):\n",
    "        \"\"\"Depth-first search to detect cycles.\"\"\"\n",
    "        if current in visited:\n",
    "            return False\n",
    "        if current == target:\n",
    "            return True\n",
    "        visited.add(current)\n",
    "        for neighbor in self.adjacencyList.get(current, []):\n",
    "            if self._dfs(neighbor, target, visited):\n",
    "                return True\n",
    "        visited.remove(current)\n",
    "        return False\n",
    "\n",
    "    def _updateMatrix(self):\n",
    "        \"\"\"Update the adjacency matrix to reflect the current graph structure.\"\"\"\n",
    "        size = len(self.nodes)\n",
    "        self.adjacencyMatrix = [[0] * size for _ in range(size)]  # Initialize matrix with zeros\n",
    "        nodeIndex = {node: i for i, node in enumerate(self.nodes)}  # Map nodes to indices\n",
    "        for node, neighbors in self.adjacencyList.items():\n",
    "            for neighbor in neighbors:\n",
    "                self.adjacencyMatrix[nodeIndex[node]][nodeIndex[neighbor]] = 1  # Set matrix entry to 1\n",
    "\n",
    "# Example usage\n",
    "dag = DirectedAcyclicGraph()\n",
    "dag.addEdge(\"A\", \"B\")\n",
    "dag.addEdge(\"A\", \"C\")\n",
    "dag.addEdge(\"B\", \"D\")\n",
    "dag.addEdge(\"D\", \"A\")  # This will not be added as it creates a cycle\n",
    "dag.display()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Thank you #\n",
    "I'm glad you've decided to take this journey to learn Python.  We covered some pretty advanced stuff today, and while you may not really need to implement most of this in your code, it is extremely useful to understand these concepts as they are the building blocks of data science & machine learning.  I hope you enjoyed this workshop, but above all, I hope you learned a lot."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "MST-Analytics",
   "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.12.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}