{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Ayudantía 09 : \n",
    "\n",
    "## Estructuras Nodales - Grafos 🗺️\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ayudantes  👾\n",
    "\n",
    "- [Clemente Campos](https://github.com/mskdancers)\n",
    "- [Patricio Hinostroza](https://github.com/Dvckhv)\n",
    "- [Julio Huerta](https://github.com/julius)\n",
    "- [Carlos Olguin](https://github.com/CarlangaUC)\n",
    "- [Catalina Miranda](https://github.com/catalinamirandah)\n",
    "- [Felipe Vidal](https://github.com/fvidalf)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Problema:"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Luego de un largo dia de ~~procastinación~~ programación, el querido `DCCabro` debe llegar a su casa. Sin embargo, el no sabe como llegar.\n",
    "Es pos esto, `DCCabro` te pide que, en base al mapa que posee de los paraderos de micro, le indiques alguna ruta con la que el pueda llegar sano y salvo a su casa. Ademas, te agradecieria demasiado si tambien le muestras la ruta mas corta."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    " <center><div style=\"background-color: #f8dcb4\"><img src=\"Images/AY-1.png\" alt=\"image2\" width=\"90%\" weight=\"90%\"></div></center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Busqueda"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Breadth First Search (BFS)\n",
    "\n",
    "\"Busqueda amplitud primero\". Este algoritmo recorre el arbol por niveles de profundidad. Es decir,\n",
    "prioriza hermanos sobre hijos"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Depth First Search(DFS)\n",
    "\n",
    "\"Busqueda profundidad primero\". Este algoritmo recorre el arbol por ramas. Es decir, prioriza hijos sobre hermanos."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![BFS](Images\\Algorithms.gif)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Codigo"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Librerias"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import deque"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Clase Nodo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "class Nodo:\n",
    "    def __init__(self, codigo):\n",
    "        self.codigo = codigo\n",
    "        self.conexiones = []\n",
    "    \n",
    "    def agregar_nodo(self, nodo):\n",
    "        self.conexiones.append(nodo)\n",
    "    \n",
    "    def quitar_nodo(self, nodo):\n",
    "        if nodo in self.conexiones:\n",
    "            self.conexiones.remove(nodo)\n",
    "    \n",
    "    def __str__(self):\n",
    "        return f\"{self.__class__.__name__}({self.codigo})\"\n",
    "\n",
    "nodo = Nodo(123)\n",
    "print(nodo)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Clase Grafo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "class Grafo:\n",
    "    def __init__(self):\n",
    "        self.nodos = dict()\n",
    "    \n",
    "    def agregar_nodo(self, nodo):\n",
    "        self.nodos[nodo.codigo] = nodo\n",
    "    \n",
    "    def conectar(self, nodo_A, nodo_B):\n",
    "        # grafo no simple a->b pero b -\\> a\n",
    "        nodo_a = self.nodos[nodo_A]\n",
    "        nodo_b = self.nodos[nodo_B]\n",
    "        \n",
    "        nodo_a.agregar_nodo(nodo_b)\n",
    "\n",
    "        #print(f\"{nodo_b} se ha conectado a {nodo_a}\")\n",
    "    \n",
    "    def remover_conexion(self, nodo_A, nodo_B):\n",
    "        nodo_a = self.nodos[nodo_A.codigo]\n",
    "        nodo_b = self.nodos[nodo_B.codigo]\n",
    "        \n",
    "        nodo_a.quitar_nodo(nodo_b)\n",
    "        \n",
    "        #print(f\"{nodo_b} se ha desconectado de {nodo_a}\")\n",
    "    \n",
    "    def hay_ruta(self, nodo_A, nodo_B):\n",
    "        #Completar\n",
    "        pass\n",
    "\n",
    "    \n",
    "    def ruta_DFS(self, nodo_A, nodo_B):\n",
    "        #Completar\n",
    "        pass\n",
    "       \n",
    "    #Si nuetra ruta es de largo 1, significa que solo es el nodo actual \n",
    "    #y por lo tanto, los hijos tampoco pudieron llegar al destino.\n",
    "    # Se retorna una lista vacía indicando que no hay ruta.\n",
    "    \n",
    "    def ruta_DFS_2(self,nodo_A, nodo_B, visitados = set(), ruta = []):\n",
    "        #Completar\n",
    "        pass\n",
    "\n",
    "    def ruta_BFS(self, nodo_A, nodo_B):\n",
    "        #Completar\n",
    "        pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Archivos"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def leer_archivos(archivo_nodos, archivo_conexiones, echo=False):\n",
    "    grafo = Grafo()\n",
    "    \n",
    "    with open(archivo_nodos, \"r\") as nodos:\n",
    "        for linea in nodos:\n",
    "            nodo = Nodo(linea.strip())\n",
    "            grafo.agregar_nodo(nodo)\n",
    "\n",
    "    with open(archivo_conexiones, \"r\") as conexiones:\n",
    "        for linea in conexiones:\n",
    "            nodo_a, nodo_b = linea.strip().split(\",\")\n",
    "            grafo.conectar(nodo_a, nodo_b)\n",
    "            if echo:\n",
    "                print(f'{nodo_a} -> {nodo_b}')\n",
    "        \n",
    "    return grafo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "grafo = leer_archivos(\"nodos.txt\", \"conexiones.txt\", echo=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Ver Nodo con sus Conexiones\n",
    "nodo_elegido = grafo.nodos['P001']\n",
    "print(f'El Nodo: {nodo_elegido}')\n",
    "[char.codigo for char in nodo_elegido.conexiones]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## A jugar!!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "grafo = leer_archivos(\"nodos.txt\", \"conexiones.txt\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "scrolled": false,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grafo.hay_ruta(\"P001\",\"P502\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grafo.hay_ruta(\"P001\",\"P505\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "ruta = grafo.ruta_DFS(\"P001\",\"P502\")\n",
    "print(\" -> \".join(str(n) for n in ruta))\n",
    "ruta = grafo.ruta_DFS_2(\"P001\",\"P502\")\n",
    "print(\" -> \".join(str(n) for n in ruta))\n",
    "ruta = grafo.ruta_BFS(\"P001\",\"P502\")\n",
    "print(\" -> \".join(str(n) for n in ruta))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grafo.hay_ruta(\"P001\",\"P502\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Nodo(P001) -> Nodo(P002)\n"
     ]
    }
   ],
   "source": [
    "ruta = grafo.ruta_DFS_2(\"P001\",\"P002\")\n",
    "print(\" -> \".join(str(n) for n in ruta))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Propuesto 😏: Ruta más corta"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Es necesario hacer mas codigo?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def ruta_corta(grafo, nodo_A, nodo_B):\n",
    "    #Completar\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ruta = ruta_corta(grafo, \"P001\", \"P502\")\n",
    "print(\" -> \".join(str(n) for n in ruta))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Listo!  ahora debrías poder llegar a casa sin problemas"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "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.10.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}