{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "Technische Hochschule Ostwestfalen-Lippe, inIT\n",
    "Kurs Künstliche Intelligenz (KI), Wintersemester 2020\n",
    "Malte Schmidt, Arbeitsgruppe Diskrete Systeme\n",
    "```\n",
    "\n",
    "# Suchalgorithmen\n",
    "\n",
    "In diesem Notebook werden die Breiten-, und Tiefensuche implementiert. Literaturreferenzen finden Sie in den Lösungshinweisen.\n",
    "\n",
    "Führen Sie die folgende Codezelle aus. In der Codezelle wird der Graph aus Aufgabe 3.2 erstellt."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "\n",
    "    def __init__(self, name, neighbors=None):\n",
    "        if neighbors:\n",
    "            self.neighbors = neighbors\n",
    "        else:\n",
    "            self.neighbors = set()\n",
    "        self.name = name\n",
    "    \n",
    "    def connect(self, node):\n",
    "        if node not in self.neighbors:\n",
    "            self.neighbors.add(node)\n",
    "            node.connect(self)\n",
    "    \n",
    "    def __str__(self):\n",
    "         return self.name\n",
    "\n",
    "a, b, c, d, e, f, g, h = Node('A'), Node('B'), Node('C'), Node('D'), Node('E'), Node('F'), Node('G'), Node('H')\n",
    "\n",
    "a.connect(c)\n",
    "a.connect(d)\n",
    "\n",
    "b.connect(d)\n",
    "b.connect(e)\n",
    "\n",
    "c.connect(d)\n",
    "c.connect(f)\n",
    "\n",
    "d.connect(g)\n",
    "\n",
    "e.connect(h)\n",
    "\n",
    "g.connect(h)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Speicher\n",
    "Implementieren Sie die für die Tiefen- und Breitensuche benötigten FIFO- und LIFO-Speicher. Eine Übersicht über Methoden von Python-Listen finden sie in der [Pyhton-Dokumentation](https://docs.python.org/3/tutorial/datastructures.html). Implementieren Sie die `__str__`-Methode. Diese Methode gibt einen String zurück. Dieser String soll alle Elemente im Speicher in der richtigen Reihenfolge auflisten. Das Element, dass mit der Methode `pop()` als nächstes zurückgegeben wird, soll am Anfang des Strings stehen. Benutzen Sie für den Namen eines einzelnen Elements `str(item)`. \n",
    "\n",
    "Die untenstehenden Implementierungen speichern die Speicherinhalte in einer Python-Liste `items`. Auf diese kann mit `self.items` innehalb der Methoden eines Objekts zugegriffen werden.\n",
    "\n",
    "Die Implementationen unterstützen die von Pyhton-Listen bekannten Operatoren `in` und `not in` und die Python-Funktion `len()`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from abc import ABC, abstractmethod\n",
    "\n",
    "class Queue(ABC):\n",
    "    \"\"\"An abstract base class for a queue implementation.\"\"\"\n",
    "\n",
    "    def __init__(self, items=()):\n",
    "        self.items = []\n",
    "        for item in items:\n",
    "            self.add(item)\n",
    "\n",
    "    @abstractmethod\n",
    "    def add(self, item):\n",
    "        \"\"\"Add item to the queue.\"\"\"\n",
    "        pass\n",
    "\n",
    "    @abstractmethod\n",
    "    def pop(self):\n",
    "        \"\"\"Remove and return an item.\"\"\"\n",
    "        pass\n",
    "    \n",
    "    @abstractmethod\n",
    "    def __str__(self):\n",
    "         pass\n",
    "\n",
    "    # Support for built-in len() function\n",
    "    def __len__(self): return len(self.items)\n",
    "    \n",
    "    # Support for \"in\" and \"not in\" operations\n",
    "    def __contains__(self, key):\n",
    "        return key in self.items\n",
    "\n",
    "class FIFOQueue(Queue):\n",
    "    \"\"\"A FIFO queue.\"\"\"\n",
    "\n",
    "    def __init__(self, items=()):\n",
    "        super().__init__(items)\n",
    "    \n",
    "    def add(self, item):\n",
    "        \"\"\"Add item to the end of the queue.\"\"\"\n",
    "        ########################################\n",
    "        # Your code goes here.\n",
    "        ########################################\n",
    "    \n",
    "    def pop(self):\n",
    "        \"\"\"Remove item from the front of the queue.\"\"\"\n",
    "        ########################################\n",
    "        # Your code goes here.\n",
    "        ########################################\n",
    "    \n",
    "    def __str__(self):\n",
    "        ########################################\n",
    "        # Your code goes here.\n",
    "        ########################################\n",
    "\n",
    "class LIFOQueue(Queue):\n",
    "    \"\"\"A FIFO queue.\"\"\"\n",
    "\n",
    "    def __init__(self, items=()):\n",
    "        super().__init__(items)\n",
    "    \n",
    "    def add(self, item):\n",
    "        \"\"\"Add item to the front of the queue.\"\"\"\n",
    "        ########################################\n",
    "        # Your code goes here.\n",
    "        ########################################\n",
    "    \n",
    "    def pop(self):\n",
    "        \"\"\"Remove item from the front of the queue.\"\"\"\n",
    "        ########################################\n",
    "        # Your code goes here.\n",
    "        ########################################\n",
    "    \n",
    "    def __str__(self):\n",
    "        ########################################\n",
    "        # Your code goes here.\n",
    "        ########################################"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Führen Sie nun die folgende Codezelle aus um ihre Implementierung zu testen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import re\n",
    "items = ['a', 'b', 'c']\n",
    "\n",
    "# Test FIFO Queue\n",
    "fifo = FIFOQueue(items)\n",
    "if fifo.pop() != 'a':\n",
    "    raise ValueError('Check your FIFOQueue Implementation.')\n",
    "fifo.add('d')\n",
    "if 'b' not in fifo or 'c' not in fifo or 'd' not in fifo:\n",
    "    raise ValueError('Check your FIFOQueue Implementation.')\n",
    "pattern = re.compile(\"[\\s\\[']*[b][\\s,']*[c][\\s,']*[d][\\s\\]']*\", re.IGNORECASE)\n",
    "if not pattern.match(str(fifo)):\n",
    "    raise ValueError('Check your FIFOQueue Implementation.' +\n",
    "                     ' Your output of the content was ' + str(fifo) +\n",
    "                     ' but something like [B, C, D] is expected.')\n",
    "fifo.pop()\n",
    "fifo.pop()\n",
    "if fifo.pop() != 'd':\n",
    "    raise ValueError('Check your FIFOQueue Implementation.')\n",
    "\n",
    "# Test LIFO Queue\n",
    "lifo = LIFOQueue(items)\n",
    "if lifo.pop() != 'c':\n",
    "    raise ValueError('Check your LIFOQueue Implementation.')\n",
    "lifo.add('d')\n",
    "if 'a' not in lifo or 'b' not in lifo or 'd' not in lifo:\n",
    "    raise ValueError('Check your LIFOQueue Implementation.')\n",
    "pattern = re.compile(\"[\\s\\[']*[d][\\s,']*[b][\\s,']*[a]\", re.IGNORECASE)\n",
    "if not pattern.match(str(lifo)):\n",
    "    raise ValueError('Check your LIFOQueue Implementation.'+ \n",
    "                     ' Your output of the content was ' + str(lifo) +\n",
    "                     ' but something like [D, B, A] is expected.')\n",
    "lifo.pop()\n",
    "lifo.pop()\n",
    "if lifo.pop() != 'a':\n",
    "    raise ValueError('Check your LIFOQueue Implementation.')\n",
    "\n",
    "print('Your queue implementations seem to work.')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Breitensuche\n",
    "Implementieren Sie die Breitensuche und benutzen Sie als Speicher ihre `FIFOQueue`-Implementation. \n",
    "\n",
    "Die schon gesehenen Knoten werden in einem Python-Set gespeichert. Ein Python-Set Objekt stellt die Methode `add(element)` bereit um dem Set ein Element hinzuzufügen. Eine Überprüfung, ob ein Elemnt in einem Set ist kann wie bei Listen mit `in` geschehen.\n",
    "\n",
    "Eine alphabetisch sortierte Liste aller Nachfolgerknoten eines Knotens `node` kann mit `sorted([node for node in node.neighbors], key=lambda node: node.name)` erstellt werden.\n",
    "\n",
    "Fügen Sie an geeigneter Stelle die Textausgabe `print(node.name + ' ' + str(frontier))` hinzu, um eine Ausgabe wie in Aufgabe 3.2 zu erhalten."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def breadth_first_search(start_node):\n",
    "    \"\"\"\n",
    "    Search the shallowest nodes in the search tree first.\n",
    "    \"\"\"\n",
    "    # Setup:\n",
    "    node = start_node\n",
    "    frontier = FIFOQueue([node])\n",
    "    explored = set()  # Set of explored nodes\n",
    "    # Search:\n",
    "    while frontier:\n",
    "        ########################################\n",
    "        # Your code goes here.\n",
    "        ########################################\n",
    "\n",
    "breadth_first_search(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Implementieren Sie die Funktion `graph_search`, die den Typ des Speichers `frontier` als Parameter erhält. Ein Aufruf von `graph_search(a, FIFOQueue)` soll die gleiche Ausgabe wie ein Aufruf von `breadth_first_search(a)` liefern."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def graph_search(start_node, queue_class):\n",
    "    \"\"\"\n",
    "    Graph search according to Artificial Intelligence: A Modern Approach, 3ed., by Stuart Russel and Peter Norvig.\n",
    "    queue_class should be FIFOQueue for Breadth-First-Search and LIFOQueue for Depth-First-Search.\n",
    "    \"\"\"\n",
    "    ########################################\n",
    "    # Your code goes here.\n",
    "    ########################################\n",
    "    \n",
    "graph_search(a, FIFOQueue)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Tiefensuche\n",
    "Führen Sie nun eine Tiefensuche mit Hilfe der Funktion `graph_search` und `a` als Startknoten durch und vergleichen Sie die Ausgabe mit den Ergebnissen aus Aufgabe 3.2."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "########################################\n",
    "# Your code goes here.\n",
    "########################################"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}