10_Grafos.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "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.6.9"
    },
    "colab": {
      "name": "10_Grafos.ipynb",
      "provenance": [],
      "collapsed_sections": []
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "PiJ7qzJZxCl0"
      },
      "source": [
        "# 10 Grafos\n",
        "\n",
        "Un *grafo* es una estructura matemática que se utiliza para representar relaciones como las que hay entre las ciudades conectadas por caminos, los cursos con sus requisitos, las componentes conectadas en un circuito eléctrico, las páginas web vinculadas por enlaces, etc."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "QS87M2ysxCl_"
      },
      "source": [
        "## Definiciones básicas\n",
        "\n",
        "Un grafo consiste de un conjunto $V$ de *vértices* (también llamados *nodos*) y un conjunto $E$ de *arcos*. El número de vértices se suele denotar $n$ y el número de arcos como $m$ (o a veces $e$).\n",
        "\n",
        "Se dice que un grafo es *no dirigido* si sus arcos no tiene una dirección asociada. Por ejemplo,\n",
        "\n",
        "![grafo-no-dirigido](https://github.com/ivansipiran/CC3001-Apuntes/blob/main/recursos/grafo-no-dirigido.png?raw=1)\n",
        "\n",
        "$$\n",
        "\\begin{align}\n",
        "V &=\\{v_1,v_2,v_3,v_4,v_5\\}\\\\\n",
        "E &=\\{ \\{v_1,v_2\\},\\{v_1,v_3\\},\\{v_1,v_5\\},\\{v_2,v_3\\},\\{v_3,v_4\\},\\{v_4,v_5\\} \\}\n",
        "\\end{align}\n",
        "$$\n",
        "\n",
        "Un grafo es *dirigido* si sus arcos tienen una orientación. Por ejemplo:\n",
        "\n",
        "![grafo-dirigido](https://github.com/ivansipiran/CC3001-Apuntes/blob/main/recursos/grafo-dirigido.png?raw=1)\n",
        "\n",
        "$$\n",
        "\\begin{align}\n",
        "V &=\\{v_1,v_2,v_3,v_4\\}\\\\\n",
        "E &=\\{ (v_1,v_2), (v_2,v_2), (v_2,v_3), (v_3,v_1), (v_3,v_4), (v_4,v_3) \\}\n",
        "\\end{align}\n",
        "$$\n",
        "\n",
        "Adicionalmente, los grafos pueden tener rótulos asociados a sus vértices o arcos. Estos rótulos pueden representar costos, longitudes, pesos, etc."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "oprDqhuBxCmC"
      },
      "source": [
        "## Representaciones de grafos en memoria\n",
        "\n",
        "Un grafo se puede almacenar en memoria de distintas maneras, las cuales tienen distintos requerimientos de espacio, y ponen también distintas restricciones al tiempo de proceso.\n",
        "\n",
        "### Matriz de adyacencia\n",
        "\n",
        "Un grafo se puede representar a través de una matriz $A$ donde $A[i,j]=1$ si hay un arco que conecta $v_i$ con $v_j$, y $0$ si no.\n",
        "La matriz de adyacencia de un grafo no dirigido es simétrica.\n",
        "\n",
        "Una matriz de adyacencia permite determinar si dos vértices están conectados o no en tiempo constante, pero requieren $\\Theta(n^2)$ bits de memoria. Esto puede ser demasiado para muchos grafos que aparecen en aplicaciones reales, en donde $m<<n^2$. Otro problema es que se requiere tiempo $\\Theta(n)$ para encontrar la lista de vecinos de un vértice dado.\n",
        "\n",
        "### Listas de adyacencia\n",
        "\n",
        "Esta representación consiste en almacenar, para cada nodo, la lista de los nodos adyacentes a él (sus \"vecinos\"). Para el segundo ejemplo anterior, tenemos:\n",
        "\n",
        "$$\n",
        "\\begin{align}\n",
        "\\text{vecinos}[v_1] &= [v_2]\\\\\n",
        "\\text{vecinos}[v_2] &= [v_2, v_3]\\\\\n",
        "\\text{vecinos}[v_3] &= [v_1, v_4]\\\\\n",
        "\\text{vecinos}[v_4] &= [v_3]\n",
        "\\end{align}\n",
        "$$\n",
        "\n",
        "Esto utiliza espacio $\\Theta(m)$ y permite acceso eficiente a los vecinos, pero no permite acceso directo a los arcos.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aT18wdxrxCmE"
      },
      "source": [
        "## Caminos, ciclos y árboles\n",
        "\n",
        "Consideremos un grafo no dirigido.\n",
        "\n",
        "Un *camino* es una secuencia de arcos en que el extremo final de cada arco coincide con el extremo inicial del siguiente en la secuencia. Por ejemplo, los arcos gruesos forman un camino desde $v_2$ a $v_5$ (o viceversa):\n",
        "\n",
        "![camino](https://github.com/ivansipiran/CC3001-Apuntes/blob/main/recursos/camino.png?raw=1)\n",
        "\n",
        "Un camino es *simple* si no se repiten vértices, excepto posiblemente el primero y el último.\n",
        "\n",
        "Un *ciclo* es un camino simple y cerrado (esto es, en que el vértice inicial y final son el mismo). En el siguiente ejemplo los arcos gruesos forman un ciclo:\n",
        "\n",
        "![ciclo](https://github.com/ivansipiran/CC3001-Apuntes/blob/main/recursos/ciclo.png?raw=1)\n",
        "\n",
        "Un grafo que no tiene ciclos se dice que es *acíclico*.\n",
        "\n",
        "Se dice que un grafo es *conexo* si para todo par de vértices del grafo existe un camino que los une. Si un grafo no es conexo, entonces estará compuesto por varias \"islas\", cada una de las cuales se llama una *componente conexa*. Más precisamentem una componente conexa es un subgrafo conexo *maximal* (esto es, que no está estrictamente contenido dentro de un subgrafo conexo mayor).\n",
        "\n",
        "Un *árbol* es un grafo que es *conexo* y *acíclico*. En el siguiente ejemplo, los arcos gruesos forman un árbol:\n",
        "\n",
        "![arbol](https://github.com/ivansipiran/CC3001-Apuntes/blob/main/recursos/arbol.png?raw=1)\n",
        "\n",
        "Si un árbol incluye todos los nodos de un grafo, se dice que es un *árbol cobertor* (*spanning tree*).\n",
        "\n",
        "### Propiedades de los árboles\n",
        "\n",
        "Es fácil demostrar las siguientes propiedades:\n",
        "\n",
        "* Todo árbol con $n$ nodos tiene $n-1$ arcos.\n",
        "* Si se agrega un arco a un árbol, se crea un único ciclo."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5i7S0Lz4xCmH"
      },
      "source": [
        "## Recorridos de grafos\n",
        "\n",
        "En muchas aplicaciones es necesario visitar todos los vértices del grafo a partir de un nodo dado. Algunas aplicaciones son:\n",
        "\n",
        "* Encontrar ciclos\n",
        "* Encontrar componentes conexas\n",
        "* Encontrar árboles cobertores\n",
        "\n",
        "Hay dos enfoque básicos:\n",
        "\n",
        "*Recorrido (o búsqueda) en profundidad (depth-first search)*:\n",
        "\n",
        "La idea es alejarse lo más posible del nodo inicial (sin repetir nodos), luego devolverse un paso e intentar lo mismo por otro camino.\n",
        "\n",
        "*Recorrido (o búsqueda) en amplitud (breadth-first search)*:\n",
        "\n",
        "Se visita a todos los vecinos directos del nodo inicial, luego a los vecinos de los vecinos, etc."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "W4AKJ35dxCmK"
      },
      "source": [
        "### Recorrido en profundidad (DFS)\n",
        "\n",
        "A medida que recorremos el grafo, iremos numerando correlativamente los nodos encontrados $1,2,\\ldots$. Suponemos que todos estos números son cero inicialmente, y para ir asignando esta numeración utilizamos un contador global $n$, también inicializado en cero. A esta numeración asignada la llamamos el Depth-First-Number (DFN).\n",
        "\n",
        "El siguiente algoritmo en seudo-código muestra cómo se puede hacer este tipo de recorrido recursivamente:"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "IfVllNMtxCmO"
      },
      "source": [
        "# seudo-código\n",
        "def DFS(v): # Recorre en profundidad a partir del vértice v    \n",
        "    global n\n",
        "    global DFN\n",
        "    assert DFN[v]==0 # Supone que es primera vez que se visita el vértice v\n",
        "    n=n+1\n",
        "    DFN[v]=n # Numeramos el vértice v\n",
        "    for w in vecinos[v]:\n",
        "        if DFN[w]==0:\n",
        "            DFS(w)  # Visitamos w si no había sido visitado aún"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "tQ705i1fxCmU"
      },
      "source": [
        "Para dar el \"puntapié inicial\" al proceso, hay que hacer que todos los DFN estén en cero, inicializar en cero la variable global $n$ e indicar el nodo de partida $x$:"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "1APUNmBxxCmd"
      },
      "source": [
        "# seudo-código\n",
        "def startDFS(x):\n",
        "    global n\n",
        "    global DFN\n",
        "    n=0\n",
        "    for v in V:\n",
        "        DFN[v]=0\n",
        "    DFS(x)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "PUC3o_N0xCmg"
      },
      "source": [
        "En el siguiente ejemplo mostraremos un posible resultado de aplicar este recorrido a un grafo dado. A la derecha se muestra el mismo grafo, con sus vértices numerados con DFN y marcando más grueso al arco que permitió llegar a por primera vez a cada vértice. A estos arcos los llamamos *arcos de árbol*. A los arcos que permiten llegar a un vértice que ya había sido visitado los llamamos *arcos de retorno* y los mostramos con línea segmentada.\n",
        "\n",
        "![DFS](https://github.com/ivansipiran/CC3001-Apuntes/blob/main/recursos/DFS.png?raw=1)\n",
        "\n",
        "Si hubiera más de una componente conexa, este recorrido no llegaría a todos los nodos. Para recorrer el grafo por completo, podemos ejecutar un DFS sobre cada componente conexa."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "yc_ngYuixCmi"
      },
      "source": [
        "# seudo-código\n",
        "def startDFS(): # recorre el grafo, retorna número de componentes conexas\n",
        "    global n\n",
        "    global ncc\n",
        "    global DFN\n",
        "    n=0\n",
        "    for v in V:\n",
        "        DFN[v]=0\n",
        "    ncc=0 # cuenta el número de componentes conexas\n",
        "    for x in V:\n",
        "        if DFN[x]==0:\n",
        "            ncc=ncc+1\n",
        "            DFS(x)\n",
        "    return ncc"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Fh_5nnD2xCmj"
      },
      "source": [
        "Existe una gran similitud entre el DFS y el recorrido en preorden que vimos para árboles binarios. Tal como ocurrió en esa oportunidad, también es posible programar el recorrido de manera no recursiva utilzando una pila:"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "-UBEKGbGxCmk"
      },
      "source": [
        "# seudo-código\n",
        "def DFSnorecursivo(x): # Recorre en profundidad a partir del vértice x  \n",
        "    n=0\n",
        "    for v in V:\n",
        "        DFN[v]=0\n",
        "    s=Pila()\n",
        "    s.push(x) # el vértice inicial del recorrido\n",
        "    while not s.is_empty():\n",
        "        v=s.pop()\n",
        "        if DFN[v]==0: # primera vez que se visita este nodo\n",
        "            n=n+1\n",
        "            DFN[v]=n      \n",
        "            for w in vecinos[v]:\n",
        "                s.push(w)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GC0KZD71xCmm"
      },
      "source": [
        "### Recorrido en amplitud\n",
        "\n",
        "Este recorrido es análogo al recorrido por niveles que vimos para árboles binarios. Su programación es similar a ``DFSnorecursivo``, sustituyendo la pila por una cola."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "7oI7_hT-xCmn"
      },
      "source": [
        "## Árbol Cobertor Mínimo (*Minimum Spanning Tree*)\n",
        "\n",
        "Para un grafo dado pueden existir muchos árboles cobertores. Si introducimos un concepto de \"peso\" (o \"costo\") sobre los arcos, es interesante tratar de encontrar un árbol cobertor que tenga costo mínimo. El costo de un árbol es la suma de los costos de sus arcos.\n",
        "\n",
        "En esta sección veremos dos algoritmos para encontrar un árbol cobertor mínimo para un grafo no dirigido dado, conexo y con costos asociados a los arcos."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "VV6vUx3hxCmo"
      },
      "source": [
        "### Algoritmo de Kruskal\n",
        "\n",
        "Este es un algoritmo del tipo \"avaro\" (\"greedy\"). Comienza inicialmente con un grafo que contiene sólo los nodos del grafo original, sin arcos. Luego, en cada iteración, se agrega al grafo el arco más barato que no genere un ciclo. El proceso termina cuando el grafo está completamente conectado.\n",
        "\n",
        "En general, la estrategia \"avara\" no garantiza que se encuentre un óptimo global, porque es un método \"miope\", que sólo optimiza las decisiones de corto plazo. Por otra parte, a menudo este tipo de métodos proveen buenas heurísticas, que se acercan al óptimo global. Pero en este caso, afortunadamente, se puede demostrar que el método \"avaro\" logra siempre encontrar el óptimo global, por lo cual un árbol cobertor encontrado por esta vía está garantizado que es un árbol cobertor mínimo.\n",
        "\n",
        "Una forma de ver este algoritmo es diciendo que al principio cada nodo constituye su propia componente conexa, aislado de todos los demás nodos. Durante el proceso de construcción del árbol, se agrega un arco sólo si sus dos extremos se encuentran en componentes conexas distintas, y luego de agregarlo, esas dos componentes conexas se fusionan en una sola.\n",
        "\n",
        "La siguiente animación muestra el algoritmo de Kruskal en funcionamiento. A cada paso, se intenta agregar un arco. Si se descarta, porque formaría un ciclo, se marca con una \"X\" y se pasa al siguiente. Si se acepta, porque une dos componentes conexas distintas, se marca como un arco sólido.\n",
        "\n",
        "![kruskal](https://github.com/ivansipiran/CC3001-Apuntes/blob/main/recursos/kruskal.gif?raw=1)\n",
        "\n",
        "Para la operatoria con componentes conexas supondremos que cada componente conexa se identifica mediante un representante canónico (el \"lider\" del conjunto), y que se dispone de las siguientes operaciones:\n",
        "\n",
        "``Union(a,b)``: Se fusionan las componentes canónicas representadas por a y b, respectivamente.\n",
        "\n",
        "``Find(x)``: Encuentra al representante canónico de la componente conexa a la cual pertenece x.\n",
        "\n",
        "Con estas operaciones, el algoritmo de Kruskal se puede escribir así (en seudo-código):"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "QvbVsBw2xCmp"
      },
      "source": [
        "# seudo-código\n",
        "def kruskal(V,E):\n",
        "    sort(E) # Ordenar los arcos en orden creciente de costo\n",
        "    C = [[v] for v in V] # C es el conjunto de componentes conexas, inicialmente \"singletons\"\n",
        "    T = [] # La lista de los arcos del árbol\n",
        "    for e in E: # consideramos los arcos en orden creciente\n",
        "        if len(C)==1: # queda solo 1 componente conexa\n",
        "            break\n",
        "        (v,w)=vertices(e)      # los dos extremos del arco e\n",
        "        if Find(v) != Find(w): # están en componentes conexas distintas\n",
        "            T.append(e) # Agregar el arco e al árbol\n",
        "            Union(Find(v),Find(w)) # Fusionamos las dos componentes en una sola\n",
        "    return T"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "rB4Pnv9OxCmr"
      },
      "source": [
        "El tiempo que demora este algoritmo está dominado por lo que demora la ordenación del conjunto $E$ de arcos, $\\Theta(m \\log{m})$, más lo que demora realizar $m$ operaciones ``Find``, más $n$ operaciones ``Union``.\n",
        "\n",
        "Es posible implementar ``Union-Find`` de modo que las operaciones ``Union`` demoren tiempo constante, y las operaciones ``Find`` un tiempo casi constante. Más precisamente, el costo amortizado de un Find está acotado por $\\log^*{n}$, donde $\\log^*{n}$ es una función definida como el número de veces que es necesario tomar el logaritmo de un número para que el resultado sea menor que 1.\n",
        "\n",
        "Por lo tanto, el costo total es $\\Theta(m \\log{m})$, lo cual es igual a $\\Theta(m \\log{n})$, porque en todo grafo se tiene que $m=O(n^2)$."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "hfq91VbDxCmt"
      },
      "source": [
        "La correctitud del algoritmo de Kruskal viene del siguiente lema:\n",
        "\n",
        "#### Lema\n",
        "\n",
        "Sea $V'$ subconjunto propio de $V$, y sea $e=\\{v,w\\}$ un arco de costo mínimo tal que $v \\in V'$ y $w \\in V-V'$. Entonces existe un árbol cobertor mínimo que incluye a $e$.\n",
        "\n",
        "Este lema permite muchas estrategias distintas para escoger los arcos del árbol. Un ejemplo es el siguiente algoritmo.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "tVpohtmJxCmu"
      },
      "source": [
        "### Algoritmo de Prim\n",
        "\n",
        "Comenzamos con el arco más barato, y marcamos sus dos extremos como \"alcanzables\". Luego, a cada paso, intentamos extender nuestro conjunto de nodos alcanzables agregando siempre el arco más barato que tenga uno de sus extremos dentro del conjunto alcanzable y el otro fuera de él. De esta manera, el conjunto alcanzable se va extendiendo como una \"mancha de aceite\"."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "y2xIjplvxCmw"
      },
      "source": [
        "# seudo-código\n",
        "def prim(V,E):\n",
        "    e=arco_de_costo_minimo(E)\n",
        "    (v,w)=vertices(e)\n",
        "    T=[e]   # árbol\n",
        "    A=[v,w] # conjunto alcanzable\n",
        "    while A!=V:\n",
        "        e=arco_de_costo_minimo_que_conecta(A,V-A)\n",
        "        (v,w)=vertices(e) # suponemos v en A y w en V-A\n",
        "        T.append(e)\n",
        "        A.append(w)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "rcNIxBcZxCm0"
      },
      "source": [
        "La siguiente animación muestra el algoritmo de Prim en funcionamiento. A cada paso, los arcos candidatos a agregarse se muestran con líneas punteadas. El arco que se acepta, por ser el de menor costo que une al conjunto alcanzable con el resto del grafo se marca como un arco sólido.\n",
        "\n",
        "![prim](https://github.com/ivansipiran/CC3001-Apuntes/blob/main/recursos/prim.gif?raw=1)\n",
        "\n",
        "Para implementar este algoritmo eficientemente, podemos mantener una tabla donde, para cada nodo de $V-A$, almacenamos el costo del arco más barato que lo conecta al conjunto A. Estos costos pueden cambiar en cada iteración, así que hay que recalcularlos para todos los vecinos del nodo que se agrega al conjunto alcanzable.\n",
        "\n",
        "Si se organiza la tabla como una cola de prioridad, el tiempo total es $\\Theta(m \\log{n})$. Si se deja la tabla desordenada y se busca linealmente en cada iteración, el costo es $\\Theta(n^2)$. Esto último es mejor que lo anterior cuando el grafo es denso."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "xwH7Pjl-xCm2"
      },
      "source": [
        "## Distancias mínimas en un grafo dirigido\n",
        "\n",
        "Consideremos un grafo *dirigido* $G=(V,E)$, donde para cada arco $e=(u,v)$ se conoce su largo, o distancia, $d(e)=d(u,v)\\ge 0$. Podemos extender la función $d$ a todo $V\\times V$ si definimos $d(u,v)=\\infty$ cuando $(u,v)\\notin E$.\n",
        "\n",
        "Si se define el largo de un camino como la suma de los largos de los arcos que lo componen, es interesante encontrar los caminos más cortos que unen a nodos del grafo.\n",
        "\n",
        "Este problema se suele estudiar en dos variantes:\n",
        "\n",
        "* Encontrar todos los caminos más cortos desde un nodo \"origen\" $s$ hasta todos los demás nodos del grafo.\n",
        "\n",
        "* Encontrar todos los caminos más cortos entre todos los pares de nodos del grafo. Esto se puede resolver iterando $n$ veces el problema anterior, cambiando cada vez el nodo origen, pero es posible encontrar un algoritmo más simple si se resuelve todo de una vez."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "OnJG0VxVxCm3"
      },
      "source": [
        "### Algoritmo de Dijkstra para los caminos más cortos desde un nodo origen\n",
        "\n",
        "La idea del algoritmo es mantener un conjunto $A$ de nodos \"alcanzables\" desde el nodo origen e ir extendiendo este conjunto en cada iteración.\n",
        "\n",
        "Los nodos alcanzables son aquellos para los cuales ya se ha encontrado su camino óptimo desde el nodo origen. Para esos nodos su distancia óptima al origen es conocida. Inicialmente $A=\\{s\\}$.\n",
        "\n",
        "Para los nodos que todavía no están en $A$ aún no se conoce su camino óptimo desde $s$, pero sí se puede conocer el camino óptimo *que pasa sólo por nodos de* $A$. Esto es, caminos en que todos los nodos intermedios son nodos de $A$. Llamemos a esto su camino óptimo *tentativo*.\n",
        "\n",
        "En cada iteración, el algoritmo encuentra el nodo que no está en $A$ cuyo camino óptimo tentativo tiene largo mínimo. Es fácil demostrar por contradicción que ese camino tiene que ser el camino óptimo para ese nodo. Luego, ese nodo se agrega a $A$ y su camino óptimo tentativo se convierte en su camino óptimo. Luego se actualizan los caminos óptimos tentativos para los demás nodos."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "GxvDy96cxCm4"
      },
      "source": [
        "# seudo-código\n",
        "def Dijkstra(V,E,d,s):\n",
        "    A=[s]\n",
        "    for v in V:\n",
        "        D[v]=d(s,v)\n",
        "    D[s]=0\n",
        "    # D[] almacena las distancias óptimas desde s para los nodos en A\n",
        "    # y las distancias óptimas tentativas para los nodos en V-A\n",
        "    while A!=V:\n",
        "        # Encontramos el nodo v de menor distancia óptima tentativa\n",
        "        v = findmin(D[u] for u in V-A)\n",
        "        # Agregamos v al conjunto alcanzable\n",
        "        A.append(v)\n",
        "        # recalculamos las distancias óptimas tentativas\n",
        "        # considerando la posibilidad de pasar por el nuevo nodo v\n",
        "        for w in vecinos[v]: # los nodos w tal que (v,w) in E\n",
        "            D[w] = min(D[w],D[v]+d(v,w))\n",
        "    # Al terminar, D[] almacena las distancias óptimas definitivas\n",
        "    return D"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "H9budAWLxCm4"
      },
      "source": [
        "Si $D$ se implementa como un arreglo en donde el mínimo se busca secuencialmente, encontrar el mínimo toma tiempo $\\Theta(n)$, con un aporte de $\\Theta(n^2)$ al tiempo total. Por otra parte, recalcular las distancias óptimas tentativas toma en total tiempo $\\Theta(m)$, porque cada arco se usa a lo más una vez. Como $m=O(n^2)$, el tiempo total es $\\Theta(n^2)$.\n",
        "\n",
        "Una forma alternativa de implementar este algoritmo es usando una *cola de prioridad*, por ejemplo un heap, para almacenar los valores de $D$ de los nodos en $V-A$. Así, encontrar y extraer el mínimo toma tiempo $\\Theta(\\log{n})$, lo cual se ejecuta $n$ veces, y cada recálculo toma también tiempo $\\Theta(\\log{n})$, porque hay que cambiar la prioridad del respectivo elemento en el heap, y esto se ejecuta $m$ veces. Por lo tanto, en esta implementación el tiempo total es $\\Theta(m\\log{n})$."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vIyAZzYYxCm5"
      },
      "source": [
        "### Algoritmo de Floyd para todas las distancias más cortas\n",
        "\n",
        "Para aplicar este algoritmo, los nodos se numeran arbitrariamente $1,2,\\ldots,n$. El algoritmo va a construir una matriz $D$ tal que, al final, $D[i,j]$ va a ser el largo del camino más corto que va desde el nodo $i$ hasta el nodo $j$.\n",
        "\n",
        "El invariante del algoritmo es que al comenzar la iteración $k$-ésima, $D[i,j]$ es la distancia mínima entre $i$ y $j$ medida a través de caminos *que pasen sólo por nodos intermedios de numeración* $<k$.\n",
        "\n",
        "En la iteración $k$-ésima se comparan estas distancias óptimas con las que se obtendrían si se pasara una vez por el nodo $k$. Si de esta manera se obtendría un camino más corto, entonces se prefiere este nuevo camino, de lo contrario nos quedamos con el camino antiguo.\n",
        "\n",
        "![floyd](https://github.com/ivansipiran/CC3001-Apuntes/blob/main/recursos/floyd.gif?raw=1)\n",
        "\n",
        "Al terminar esta iteración, las distancias calculadas ahora incluyen la posibilidad de pasar por nodos intermedios de numeración $\\le k$, con lo cual estamos listos para ir a la iteración siguiente.\n",
        "\n",
        "Inicialmente, hacemos $D[i,j]=d(i,j)$ para todo $i,j$ (recordemos la convención de que $d(i,j)=\\infty$ si $(i,j)\\notin E$), excepto que la diagonal es $D[i,i]=0$, porque la distancia óptima de todo nodo a sí mismo es $0$."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "-mXJPHonxCm6"
      },
      "source": [
        "# seudo-código\n",
        "def Floyd(V,E,d):\n",
        "    for i in range(1,n+1):\n",
        "        for j in range(1,n+1):\n",
        "            D[i,j]=d(i,j)\n",
        "        D[i,i]=0\n",
        "    \n",
        "    for k in range(1,n+1):\n",
        "        for i in range(1,n+1):\n",
        "            for j in range(1,n+1):\n",
        "                D[i,j]=min(D[i,j],D[i,k]+D[k,j])\n",
        "    \n",
        "    return D"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vZh2NyStxCm7"
      },
      "source": [
        "El tiempo total que demora este algoritmo claramente es $\\Theta(n^3)$."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "XvH2CRDBxCm7"
      },
      "source": [
        "## Algoritmo de Warshall para cerradura transitiva y reflexiva de un grafo dirigido\n",
        "\n",
        "Dado un grafo dirigido $G=(V,E)$, su *cerradura transitiva y reflexiva* es un grafo $G^*=(V,E^*)$, donde hay un arco $(u,v)\\in E^*$ ssi existe un camino desde $u$ hasta $v$ en $G$. Si se consideran solo caminos de largo $\\ge 1$, el grafo se llama la cerradura transitiva de $G$ y se denota por $G^+$. La diferencia entre $G^+$ y $G^*$ es que para construir $G^+$ se agregan todos los arcos de transitividad, y para $G^*$ se agregan además todos los auto-ciclos.\n",
        "\n",
        "El siguiente ejemplo muestra un grafo dirigido $G$ y su correspondiente cerradura transitiva y reflexiva $G^*$, mostrando en línea punteada los arcos que se agregan.\n",
        "\n",
        "![warshall](https://github.com/ivansipiran/CC3001-Apuntes/blob/main/recursos/warshall.png?raw=1)\n",
        "\n",
        "Supongamos que el grafo $G$ se representa a través de su matriz de adyacencia $A$, con $A[i,j]=1$ si hay un arco entre $v_i$ y $v_j$, y $0$ si no. Queremos calcular la matriz $A^*$ correspondiente al grafo $G^*$. Para el grafo del ejemplo, tendríamos\n",
        "\n",
        "$$\n",
        "A=\n",
        "\\begin{bmatrix}\n",
        "0 & 1 & 0 & 0 \\\\\n",
        "0 & 1 & 0 & 1 \\\\\n",
        "0 & 1 & 0 & 0 \\\\\n",
        "0 & 0 & 1 & 0\n",
        "\\end{bmatrix}\n",
        "~~~~~~\n",
        "A^*=\n",
        "\\begin{bmatrix}\n",
        "1 & 1 & 1 & 1 \\\\\n",
        "0 & 1 & 1 & 1 \\\\\n",
        "0 & 1 & 1 & 1 \\\\\n",
        "0 & 1 & 1 & 1\n",
        "\\end{bmatrix}\n",
        "$$\n",
        "\n",
        "Podemos resolver este problema haciendo uso del algoritmo de Floyd, de la siguiente manera: formamos una matriz de distancias $D$, con\n",
        "\n",
        "$$\n",
        "D[i,j] =\n",
        "\\begin{cases}\n",
        "+\\infty & \\text{if }A[i,j]=0 \\\\\n",
        "0 & \\text{if }A[i,j]=1\n",
        "\\end{cases}\n",
        "$$\n",
        "\n",
        "Luego de aplicar el algoritmo de Floyd, tendremos que la distancia entre dos nodos es $0$ ssi existe un camino entre los dos nodos, así que podemos recuperar la matriz $A^*$ haciendo la sustitución inversa.\n",
        "\n",
        "Yendo más allá, podemos re-examinar el funcionamiento del algoritmo de Floyd sobre esos infinitos y ceros, y ver cuál sería su interpretación si estuvieran operando sobre los ceros y unos originales, respectivamente.\n",
        "\n",
        "El algoritmo de Floyd hace uso de dos operaciones, $+$, y $\\min$. Las dos tablas siguientes muestran el efecto de esas operaciones:\n",
        "\n",
        "| $+$      | $\\infty$ | $0$      |\n",
        "|----------|----------|----------|\n",
        "| $\\infty$ | $\\infty$ | $\\infty$ |\n",
        "| $0$      | $\\infty$ | $0$      |\n",
        "\n",
        "| $\\min$   | $\\infty$ | $0$      |\n",
        "|----------|----------|----------|\n",
        "| $\\infty$ | $\\infty$ | $0$      |\n",
        "| $0$      | $0$      | $0$      |\n",
        "\n",
        "Si reemplazamos $\\infty$ por $0$ y $0$ por $1$, respectivamente, vemos que las tablas resultantes corresponden a las operaciones lógicas $\\wedge$ y $\\vee$:\n",
        "\n",
        "| $\\wedge$ | $0$      | $1$      |\n",
        "|----------|----------|----------|\n",
        "| $0$      | $0$      | $0$      |\n",
        "| $1$      | $0$      | $1$      |\n",
        "\n",
        "| $\\vee$   | $0$      | $1$      |\n",
        "|----------|----------|----------|\n",
        "| $0$      | $0$      | $1$      |\n",
        "| $1$      | $1$      | $1$      |\n",
        "\n",
        "Si reescribimos el algoritmo de Floyd en términos de ceros y unos, con estas operaciones lógicas, obtenermos el algoritmo de Warshall:"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "9ZGuUkSnxCm8"
      },
      "source": [
        "# seudo-código\n",
        "def Warshall(V,E,d):\n",
        "    for i in range(1,n+1):\n",
        "        for j in range(1,n+1):\n",
        "            A[i,j]=1 if (i,j) in E else 0\n",
        "        A[i,i]=1\n",
        "    \n",
        "    for k in range(1,n+1):\n",
        "        for i in range(1,n+1):\n",
        "            for j in range(1,n+1):\n",
        "                A[i,j]=A[i,j] or (A[i,k] and A[k,j])\n",
        "    \n",
        "    return A"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "krQ2whEfxCm9"
      },
      "source": [
        "Tal como en el caso del algoritmo de Floyd, el algoritmo de Warshall obviamente demora tiempo $\\Theta(n^3)$."
      ]
    }
  ]
}