1.py

class Node:
  def __init__(self, root, action, state):
    self.state = state
    self.root = root
    self.action = action


class DFS:
  def __init__(self):
    self.stack = []

  def is_empty(self):
    """
    check if the stack is empty
    """
    return len(self.stack) == 0

  def add(self, node):
    """
    Add a new item to to end of a stack
    """
    self.stack.append(node)

  def remove(self):
    """
    Remove from the end of a stack, using the
    Last in first out(LIFO)
    """
    node = self.stack[-1]  # remove the last node from the stack
    self.stack = self.stack[:-1]  # update the stack

    return node

  def contains(self, state, iterable):
    """
    Check if an item exists in a listjg
    """
    for item in iterable:
        if item.state == state:
            return True
    return False

  def algorithm(self, start, goal, callback):
    """
    This algorithm go through all the possible nodes
    that can be explored in a graph and returns the optimum
    path used to reach the goal
    """
    explored = list()  # maintain all the nodes that have been visitted
    count = 0
    begin = start

    start_node = Node(root=None, action=None, state=begin)
    self.add(start_node)  # add start node to the our stack

    while not self.is_empty():
        node = self.remove()
        count += 1  # keep a count of the number of visited nodes

        if node and node.state == goal:  # go here if the current node is our goal
            explored = []

            # backtracking to find the path used to get to the goal
            # an optimum path
            while node.root:
                explored.append(node.state)
                node = node.root
            break

        n = callback(node.state)

        # use the current that's being exployed and expand it to get
        # it's neighbouring nodes for exploring
        for a, new_state in n:
            if not self.contains(new_state,
                                 self.stack) and not self.contains(
                                     new_state, explored):
                child_node = Node(root=node, action=a, state=new_state)
                self.add(child_node)
        explored.append(node)
    return count, list(reversed(explored))


class BFS(DFS): # Inherits from DFS since it has similar functionalities
    def remove(self):
        node = self.stack[
            0]  # Removing an item from the list at the zero index (FIRST IN FIRST OUT(FIFO) or queue)
        self.stack = self.stack[1:]

        return node