{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Graphentheorie – Notebook\n",
    "\n",
    "**Informatik 12 · Graphentheorie**\n",
    "\n",
    "Dieses Kapitel gehört zum Leistungskurs. Im Notebook bauen Sie die vier\n",
    "Algorithmen selbst — auf demselben Saarland-Netz, das im Heft gezeichnet ist.\n",
    "\n",
    "Am Ende sehen Sie an einer Tabelle, warum das Problem des Handlungsreisenden\n",
    "anders ist als die drei davor.\n",
    "\n",
    "Führen Sie zuerst die nächste Zelle aus."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Das Netz aus Kapitel 9, Entfernungen in Kilometern\n",
    "NETZ = {\n",
    "    \"SB\":  {\"NK\": 24, \"WND\": 40, \"HOM\": 31, \"MZG\": 45},\n",
    "    \"NK\":  {\"SB\": 24, \"OTW\": 8, \"HOM\": 15},\n",
    "    \"OTW\": {\"NK\": 8, \"WND\": 10},\n",
    "    \"WND\": {\"SB\": 40, \"OTW\": 10, \"HOM\": 28, \"MZG\": 48},\n",
    "    \"HOM\": {\"SB\": 31, \"NK\": 15, \"WND\": 28},\n",
    "    \"MZG\": {\"SB\": 45, \"WND\": 48},\n",
    "}\n",
    "\n",
    "ORTE = list(NETZ)\n",
    "\n",
    "\n",
    "def zeile(*teile):\n",
    "    print(\"  \".join(str(t).ljust(12) for t in teile))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Aufgabe 1 · Adjazenzmatrix und Adjazenzliste\n",
    "\n",
    "Erzeugen Sie aus `NETZ` die Adjazenzmatrix als Liste von Listen (0, wo keine\n",
    "Kante ist) und geben Sie sie mit Zeilen- und Spaltenbeschriftung aus.\n",
    "\n",
    "Zählen Sie außerdem die Kanten und prüfen Sie die Gradsumme aus Abschnitt 9.2.2.\n",
    "\n",
    "**Frage:** Die Matrix hat 36 Felder, der Graph 9 Kanten. Ab welcher Dichte lohnt sich die Matrix gegenüber der Liste? Rechnen Sie den Speicherbedarf beider Darstellungen für 1000 Orte mit je 4 Nachbarn aus."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def matrix(netz, orte):\n",
    "    # TODO\n",
    "    return []\n",
    "\n",
    "\n",
    "def kantenzahl(netz):\n",
    "    # TODO: jede Kante steht zweimal im dict\n",
    "    return 0\n",
    "\n",
    "\n",
    "# m = matrix(NETZ, ORTE)\n",
    "# zeile(\"\", *ORTE)\n",
    "# for ort, zeileninhalt in zip(ORTE, m):\n",
    "#     zeile(ort, *zeileninhalt)\n",
    "# print(kantenzahl(NETZ), \"Kanten, Gradsumme\",\n",
    "#       sum(len(NETZ[o]) for o in ORTE))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Aufgabe 2 · Breitensuche und Tiefensuche\n",
    "\n",
    "Schreiben Sie beide Suchen und geben Sie die Besuchsreihenfolge ab Saarbrücken aus.\n",
    "\n",
    "Die Breitensuche nimmt den nächsten Knoten **vorne** aus einer Warteschlange, die\n",
    "Tiefensuche arbeitet rekursiv.\n",
    "\n",
    "**Frage:** Beide besuchen dieselben sechs Orte. Vergleichen Sie Ihre Reihenfolgen mit denen im Heft. Was passiert, wenn Sie die Nachbarn in `NETZ` anders sortieren — und was sagt das über „die“ Reihenfolge einer Suche aus?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def breitensuche(netz, start):\n",
    "    besucht, schlange = [start], [start]\n",
    "    # TODO\n",
    "    return besucht\n",
    "\n",
    "\n",
    "def tiefensuche(netz, knoten, besucht=None):\n",
    "    if besucht is None:\n",
    "        besucht = []\n",
    "    # TODO\n",
    "    return besucht\n",
    "\n",
    "\n",
    "# print(\"Breite:\", breitensuche(NETZ, \"SB\"))\n",
    "# print(\"Tiefe: \", tiefensuche(NETZ, \"SB\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Aufgabe 3 · Dijkstra\n",
    "\n",
    "Berechnen Sie die kürzesten Entfernungen ab Merzig. Geben Sie zu jedem Ort auch\n",
    "den Vorgänger aus, damit Sie den Weg zurückverfolgen können.\n",
    "\n",
    "Schreiben Sie dazu `weg(vorher, ziel)`, das aus den Vorgängern den Weg baut.\n",
    "\n",
    "**Frage:** Im Heft steht, dass die Entfernung nach Neunkirchen unterwegs von 69 auf 66 km verbessert wird. Lassen Sie sich jede Verbesserung ausgeben und finden Sie die Stelle. Warum passiert so etwas in einem Straßennetz selten?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def dijkstra(netz, start):\n",
    "    \"\"\"Gibt (entfernungen, vorher) zurueck.\"\"\"\n",
    "    unendlich = float(\"inf\")\n",
    "    entfernung = {ort: unendlich for ort in netz}\n",
    "    entfernung[start] = 0\n",
    "    vorher, fest = {}, set()\n",
    "    # TODO: immer den naechsten unfesten Ort mit kleinster Entfernung nehmen\n",
    "    return entfernung, vorher\n",
    "\n",
    "\n",
    "def weg(vorher, ziel):\n",
    "    # TODO: vom Ziel rueckwaerts\n",
    "    return []\n",
    "\n",
    "\n",
    "# e, v = dijkstra(NETZ, \"MZG\")\n",
    "# for ort in sorted(e, key=e.get):\n",
    "#     zeile(ort, e[ort], \" \".join(weg(v, ort)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Aufgabe 4 · Kruskal\n",
    "\n",
    "Bauen Sie den minimalen Spannbaum: alle Kanten nach Gewicht sortieren und jede\n",
    "nehmen, die keinen Kreis schließt.\n",
    "\n",
    "Für „schließt einen Kreis“ genügt hier: Beide Enden liegen schon in derselben\n",
    "Gruppe. Verwalten Sie die Gruppen als `dict` von Ort auf Gruppennummer.\n",
    "\n",
    "**Frage:** Ihr Spannbaum hat fünf Kanten. Warum sind es bei sechs Orten immer genau fünf — unabhängig davon, wie das Netz aussieht?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def kanten(netz):\n",
    "    \"\"\"Jede Kante genau einmal, als (gewicht, a, b).\"\"\"\n",
    "    raus = set()\n",
    "    # TODO\n",
    "    return sorted(raus)\n",
    "\n",
    "\n",
    "def kruskal(netz):\n",
    "    \"\"\"Gibt (Kantenliste, Summe) zurueck.\"\"\"\n",
    "    gruppe = {ort: i for i, ort in enumerate(netz)}\n",
    "    baum, summe = [], 0\n",
    "    # TODO\n",
    "    return baum, summe\n",
    "\n",
    "\n",
    "# baum, summe = kruskal(NETZ)\n",
    "# for g, a, b in baum:\n",
    "#     zeile(a + \" - \" + b, g)\n",
    "# print(\"Summe:\", summe, \"km\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Aufgabe 5 · Handlungsreisender: alle Touren durchprobieren\n",
    "\n",
    "Suchen Sie die kürzeste Rundreise durch alle sechs Orte. Probieren Sie dazu alle\n",
    "Reihenfolgen durch (`itertools.permutations`) und verwerfen Sie Touren, für die\n",
    "eine Straße fehlt.\n",
    "\n",
    "Messen Sie dabei die Zeit.\n",
    "\n",
    "**Frage:** Wie viele Touren mussten Sie prüfen? Rechnen Sie aus, wie lange es bei gleichem Tempo für 12 und für 15 Orte dauern würde. Vergleichen Sie mit Dijkstra, der auf demselben Netz in Millisekunden fertig ist — worin genau liegt der Unterschied?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import permutations\n",
    "from time import perf_counter\n",
    "\n",
    "\n",
    "def touren(netz, start=\"SB\"):\n",
    "    \"\"\"Gibt (beste Tour, Laenge, geprueft) zurueck.\"\"\"\n",
    "    uebrige = [o for o in netz if o != start]\n",
    "    beste, kuerzeste, geprueft = None, float(\"inf\"), 0\n",
    "    # TODO: alle Reihenfolgen durchgehen, Laenge aufsummieren,\n",
    "    #       bei fehlender Strasse abbrechen\n",
    "    return beste, kuerzeste, geprueft\n",
    "\n",
    "\n",
    "# start = perf_counter()\n",
    "# tour, laenge, n = touren(NETZ)\n",
    "# print(tour, laenge, \"km,\", n, \"Touren geprueft in\",\n",
    "#       round(perf_counter() - start, 4), \"s\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "### Abgabe\n",
    "\n",
    "Fertig ist das Notebook, wenn die Breitensuche ab Saarbrücken alle sechs Orte\n",
    "findet, Dijkstra ab Merzig genau eine Verbesserung meldet, Kruskal auf 102 km\n",
    "kommt und die kürzeste Rundreise 157 km lang ist.\n",
    "\n",
    "Schreiben Sie zum Schluss in eine Markdown-Zelle: Welche der vier Aufgaben ließe\n",
    "sich auch für 10 000 Orte noch lösen — und welche nicht?"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
