{
 "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": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import deque"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Clase Nodo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Nodo(123)\n"
     ]
    }
   ],
   "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": 3,
   "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",
    "        # Realiza DFS\n",
    "        nodo = self.nodos[nodo_A]\n",
    "        \n",
    "        visitados = set()\n",
    "        faltantes = [nodo]\n",
    "        \n",
    "        while len(faltantes) > 0:\n",
    "            nodo_actual = faltantes.pop() # BFS -> pop(0) DFS-> pop(-1)\n",
    "            if nodo_actual.codigo == nodo_B:\n",
    "                return True\n",
    "            if nodo_actual not in visitados:\n",
    "                visitados.add(nodo)\n",
    "                for hijo in nodo_actual.conexiones:\n",
    "                    faltantes.append(hijo)\n",
    "        return False\n",
    "\n",
    "    \n",
    "    def ruta_DFS(self, nodo_A, nodo_B):\n",
    "        #DFS ITERATIVO\n",
    "        nodo = self.nodos[nodo_A]\n",
    "     \n",
    "        por_visitar = list() #Se crea una cola\n",
    "        visitados = set() #Se crea un set para almacenar los nodos visitados\n",
    "        por_visitar.append((nodo,[nodo]))         #Como la ruta debe contener al nodo de inicio, se define inicialmente así\n",
    "        while len(por_visitar) > 0:\n",
    "            nodo_actual,ruta_actual = por_visitar.pop()\n",
    "            if nodo_actual.codigo == nodo_B:\n",
    "                return ruta_actual\n",
    "            for hijo in nodo_actual.conexiones:\n",
    "                if hijo not in visitados:\n",
    "                    por_visitar.append((hijo, ruta_actual + [hijo]))\n",
    "                    visitados.add(nodo_actual) \n",
    "        return []\n",
    "    \n",
    "    def ruta_DFS_2(self,nodo_A, nodo_B, visitados = list(), ruta = list()):\n",
    "        nodo = self.nodos[nodo_A]\n",
    "        #DFS RECURSIVO\n",
    "        ruta.append(nodo)\n",
    "        if nodo.codigo == nodo_B:\n",
    "            return ruta\n",
    "        visitados.append(nodo)\n",
    "        for hijo in nodo.conexiones:\n",
    "            if hijo not in visitados:\n",
    "                result =self.ruta_DFS_2(hijo.codigo, nodo_B, visitados, ruta.copy())\n",
    "                if result:\n",
    "                    return result\n",
    "        return\n",
    "            \n",
    "    def ruta_BFS(self, nodo_A, nodo_B):\n",
    "        # BFS\n",
    "        nodo = self.nodos[nodo_A]\n",
    "        visitados = set()\n",
    "        ruta_inicial = [nodo]\n",
    "        por_visitar = list()\n",
    "        por_visitar.append([nodo,ruta_inicial])\n",
    "            \n",
    "        while por_visitar: #len(por_visitar)>0\n",
    "            nodo, ruta_actual= por_visitar.pop(0)\n",
    "            visitados.add(nodo)\n",
    "            if nodo.codigo == nodo_B:\n",
    "                return ruta_actual\n",
    "            \n",
    "            for hijo in nodo.conexiones:\n",
    "                if hijo not in visitados:\n",
    "                    por_visitar.append([hijo,ruta_actual+[hijo]])\n",
    "        return []"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Archivos"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "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": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "grafo = leer_archivos(\"nodos.txt\", \"conexiones.txt\", echo=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "El Nodo: Nodo(P001)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "['P002', 'P003', 'P210']"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "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": 7,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "grafo = leer_archivos(\"nodos.txt\", \"conexiones.txt\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "scrolled": false,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grafo.hay_ruta(\"P001\",\"P502\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grafo.hay_ruta(\"P001\",\"P505\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Nodo(P001) -> Nodo(P210) -> Nodo(P211) -> Nodo(P003) -> Nodo(P004) -> Nodo(P005) -> Nodo(P101) -> Nodo(P501) -> Nodo(P502)\n",
      "Nodo(P001) -> Nodo(P002) -> Nodo(P003) -> Nodo(P004) -> Nodo(P005) -> Nodo(P101) -> Nodo(P501) -> Nodo(P502)\n",
      "Nodo(P001) -> Nodo(P002) -> Nodo(P005) -> Nodo(P101) -> Nodo(P501) -> Nodo(P502)\n"
     ]
    }
   ],
   "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": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grafo.hay_ruta(\"P001\",\"P502\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Nodo(P001) -> Nodo(P002)\n"
     ]
    }
   ],
   "source": [
    "ruta = grafo.ruta_DFS(\"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": [
    "Como el algoritmo BFS recorre el grafo por niveles, podemos utilizarlo para encontrar la ruta más corta entre dos nodos. Sin necesidad de pensar en algun mas complejo para encontrar esto."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Nodo(P001) -> Nodo(P002) -> Nodo(P005) -> Nodo(P101) -> Nodo(P501) -> Nodo(P502)\n"
     ]
    }
   ],
   "source": [
    "ruta = grafo.ruta_BFS(\"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
}