10 Grafos.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 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": {},
   "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](grafo-no-dirigido.png)\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](grafo-dirigido.png)\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": {},
   "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": {},
   "source": [
    "## Caminos, ciclos y árboles\n",
    "\n",
    "Consideremos un grafo no dirigido.\n",
    "\n",
    "Un *camino* es una secuencua 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](camino.png)\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](ciclo.png)\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](arbol.png)\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": {},
   "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": {},
   "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",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "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"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Para dar el \"puntapié inicial\" al proceso, hay que hacer que todos los DFN estén en cero, incializar en cero la variable global $n$ e indicar el nodo de partida $x$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "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)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "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](DFS.png)\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",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# seudo-código\n",
    "def startDFS(): # recorre el grafo, retorna número de componentes conexas\n",
    "    global n\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"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "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",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "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 DFV[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)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "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": {},
   "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": {},
   "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",
    "![kruskal](kruskal.gif)\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",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "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"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "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": {},
   "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": {},
   "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",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "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)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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 agraga 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": "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.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}