IPython notebook explicando búsquedas en grafos (BFS y DFS). Curso Algoritmos, Universidad Nacional de Colombia.

busquedas.ipynb

{
 "metadata": {
  "name": ""
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "B\u00fasqueda en grafos\n",
      "==================\n",
      "\n",
      "El objetivo de los algoritmos de b\u00fasqueda es recorrer un grafo de manera que se visiten todos sus v\u00e9rtices, o por lo menos aquellos que sean alcanzables desde un nodo de inicio. Hay dos tipos principales de b\u00fasqueda: b\u00fasqueda en profundidad y b\u00fasqueda en amplitud. \n",
      "\n",
      "B\u00fasqueda en profundidad\n",
      "-----------------------\n",
      "\n",
      "El objetivo de la b\u00fasqueda en profundidad es avanzar en un camino de b\u00fasqueda tanto como sea posible. Este se logra a trav\u00e9s de un proceso recursivo y una estrategia de marcado de nodos, que le permite al algoritmo saber que nodos se han visitado ya. Las marcas corresponden a colores con el siguiente significado:\n",
      "\n",
      "* Blanco: el nodo no ha sido visitado aun.\n",
      "* Gris: el nodo ya se visit\u00f3, pero no se han terminado de procesar sus descendientes.\n",
      "* Negro: el nodo ya se termin\u00f3 de procesar.\n",
      "\n",
      "La siguiente funci\u00f3n implementa el algoritmo de b\u00fasqeda en profundidad (DFS por sus siglas en Ingl\u00e9s). La funci\u00f3n recibe el grafo (G), el nodo desde el que comienza (node) y un arreglo con la informaci\u00f3n de color para cada nodo."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def DFS_Visit(G, node, color):\n",
      "    color[node] = 'gray'\n",
      "    total_marked = 1\n",
      "    for neighbor in G[node]:\n",
      "        if color[neighbor] == 'white':\n",
      "            total_marked += DFS_Visit(G, neighbor, color)\n",
      "    color[node] = 'black'\n",
      "    return total_marked"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 67
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "A continuaci\u00f3n vamos a probar el algoritmo sobre el siguiente grafo:\n",
      "![alt text](http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/Gifs/bfs1.gif)"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Graph construction\n",
      "\n",
      "def make_link(G, node1, node2):\n",
      "    if node1 not in G:\n",
      "        G[node1] = {}\n",
      "    (G[node1])[node2] = 1\n",
      "    if node2 not in G:\n",
      "        G[node2] = {}\n",
      "    (G[node2])[node1] = 1\n",
      "    return G\n",
      "\n",
      "edges1 = [('v', 'r'), ('r', 's'), ('s', 'w'), ('w', 't'), \n",
      "         ('w', 'x'), ('t', 'x'), ('t', 'u'), ('x', 'y'),\n",
      "         ('u', 'y')]\n",
      "\n",
      "G1 = {}\n",
      "for v1, v2 in edges1:\n",
      "    make_link(G1, v1, v2)\n",
      "\n",
      "# Initialization of 'color' array\n",
      "color = {}\n",
      "for v in G1:\n",
      "    color[v] = 'white'\n",
      "\n",
      "# Run DFS starting from node 's'\n",
      "num_nodes = DFS_Visit(G1, 't', color)\n",
      "\n",
      "print \"Number of visited nodes:\", num_nodes\n",
      "\n",
      "print color\n",
      "\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Number of visited nodes: 8\n",
        "{'s': 'black', 'r': 'black', 'u': 'black', 't': 'black', 'w': 'black', 'v': 'black', 'y': 'black', 'x': 'black'}\n"
       ]
      }
     ],
     "prompt_number": 69
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Como se puede ver, la funci\u00f3n visit\u00f3 los 8 nodos del grafo y por lo tanto su color final es negro. \n",
      "\n",
      "### Conectividad\n",
      "\n",
      "Podemos usar la funci\u00f3n para determinar si hay un camino que conecte dos nodos:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def connected(G, v1, v2):\n",
      "    color = {}\n",
      "    for v in G1:\n",
      "        color[v] = 'white'\n",
      "    DFS_Visit(G, v1, color)\n",
      "    return color[v2] == 'black'\n",
      "        "
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 70
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Vamos a probarla sobre un grafo correspondiente al anterior, pero al cual se le ha removido el arco que conecta los nodos 's' y 'w'."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "edges2 = [('v', 'r'), ('r', 's'), ('w', 't'), \n",
      "         ('w', 'x'), ('t', 'x'), ('t', 'u'), ('x', 'y'),\n",
      "         ('u', 'y')]\n",
      "\n",
      "G2 = {}\n",
      "for v1, v2 in edges2:\n",
      "    make_link(G2, v1, v2)\n",
      "    \n",
      "print connected(G2, 'v', 's')\n",
      "print connected(G2, 'v', 'y')"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "True\n",
        "False\n"
       ]
      }
     ],
     "prompt_number": 72
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "### Camino entre dos nodos\n",
      "\n",
      "Para poder calcular el camino entre dos v\u00e9rtices encontrado por DFS, necesitamos llevar un registro del orden en que se visitan los v\u00e9rtices, en particular a trav\u00e9s de que v\u00e9rtice se lleg\u00f3 a otro v\u00e9rtice. Esto se llevar\u00e1 a cabo con una arreglo adicional, `parent`, el cual indicar\u00e1 para cada v\u00e9rtice el nodo a trav\u00e9s del cual fue alcanzado, es decir su padre.\n"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def DFS_Visit_p(G, node, color, parent):\n",
      "    color[node] = 'gray'\n",
      "    total_marked = 1\n",
      "    for neighbor in G[node]:\n",
      "        if color[neighbor] == 'white':\n",
      "            parent[neighbor] = node\n",
      "            total_marked += DFS_Visit_p(G, neighbor, color, parent)\n",
      "    color[node] = 'black'\n",
      "    return total_marked"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 77
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Para calcular el camino entre dos v\u00e9rtices `v1` y `v2`, invocamos DFS con `v1` como v\u00e9rtice de arranque, y despu\u00e9s usamos el arreglo `parent` para calcular el camino en caso de que este exista."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def path(G, v1, v2):\n",
      "    color = {}\n",
      "    parent = {}\n",
      "    for v in G:\n",
      "        color[v] = 'white'\n",
      "        parent[v] = None\n",
      "    DFS_Visit_p(G, v1, color, parent)\n",
      "    pathlist = []\n",
      "    node = v2\n",
      "    while node <> None:\n",
      "        pathlist.append(node)\n",
      "        node = parent[node]\n",
      "    if color[v2] == 'black':\n",
      "        return pathlist[::-1] # los v\u00e9rtices en pathlist est\u00e1n en orden inverso, [::-1] los invierte\n",
      "    else:\n",
      "        return []\n",
      "\n",
      "print path(G1, 't', 'r')"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "['t', 'x', 'w', 's', 'r']\n"
       ]
      }
     ],
     "prompt_number": 80
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "### Componentes conexas\n",
      "\n",
      "Una componente conexa de un grafo no dirigido es un subgrafo (maximal) en el cual todos los v\u00e9rtices est\u00e1n conectados. La siguiente funci\u00f3n calcula el n\u00famero de componentes conexas.\n"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def connected_components(G):\n",
      "    color = {}\n",
      "    parent = {}\n",
      "    for v in G:\n",
      "        color[v] = 'white'\n",
      "        parent[v] = None\n",
      "    count = 0\n",
      "    for v in G:\n",
      "        if color[v] == 'white':\n",
      "            count += 1\n",
      "            DFS_Visit_p(G, v, color, parent)\n",
      "    return count\n",
      "\n",
      "edges3 = [('v', 'r'), ('r', 's'), ('w', 't'), \n",
      "         ('w', 'x'), ('t', 'x'),\n",
      "         ('u', 'y')]\n",
      "G3 = {}\n",
      "for v1, v2 in edges3:\n",
      "    make_link(G3, v1, v2)\n",
      "    \n",
      "\n",
      "print connected_components(G1)\n",
      "print connected_components(G2)\n",
      "print connected_components(G3)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1\n",
        "2\n",
        "3\n"
       ]
      }
     ],
     "prompt_number": 51
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "### Versi\u00f3n iterativa\n",
      "La versi\u00f3n de DFS anterior es recursiva, sin embargo es posible formular el mismo algoritmo de una manera iterativa:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def DFS_iterative(G, node):\n",
      "    color = {}\n",
      "    parent = {}\n",
      "    for v in G:\n",
      "        color[v] = 'white'\n",
      "    color[node] = 'gray'\n",
      "    parent[node] = None\n",
      "    nodelist = [node]\n",
      "    total_marked = 1\n",
      "    while nodelist <> []:\n",
      "        u = nodelist.pop()\n",
      "        for neighbor in G[u].keys()[::-1]:\n",
      "            if color[neighbor] == 'white':\n",
      "                color[neighbor] = 'gray'\n",
      "                parent[neighbor] = u\n",
      "                nodelist.append(neighbor)\n",
      "                total_marked += 1\n",
      "        color[u] = 'black'\n",
      "    return total_marked, parent"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 91
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Probemos el algoritmo en el Grafo 1 definido anteriormente:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print DFS_iterative(G1, 's')"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "(8, {'s': None, 'r': 's', 'u': 'y', 't': 'w', 'w': 's', 'v': 'r', 'y': 'x', 'x': 'w'})\n"
       ]
      }
     ],
     "prompt_number": 92
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "B\u00fasqueda en amplitud\n",
      "--------------------\n",
      "\n",
      "En la b\u00fasqueda en amplitud se procesan los nodos por niveles, es decir, el primer nodo que se visita es el nodo de arranque 's', segundo los nodos que est\u00e1n a una distancia 1 de 's', despu\u00e9s los nodos que est\u00e1n a una distancia 2 de 's' y as\u00ed sucesivamente. Esto se logra con un cambio simple en el c\u00f3digo de la b\u00fasqueda en profundidad iterativa:\n"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def BFS_iterative(G, node):\n",
      "    color = {}\n",
      "    depth = {}\n",
      "    parent = {}\n",
      "    for v in G:\n",
      "        color[v] = 'white'\n",
      "    color[node] = 'gray'\n",
      "    depth[node] = 0\n",
      "    parent[node] = None\n",
      "    nodelist = [node]\n",
      "    total_marked = 1\n",
      "    while nodelist <> []:\n",
      "        u = nodelist[0]\n",
      "        nodelist.remove(nodelist[0])\n",
      "        for neighbor in G[u]:\n",
      "            if color[neighbor] == 'white':\n",
      "                color[neighbor] = 'gray'\n",
      "                depth[neighbor] = depth[u] + 1\n",
      "                parent[neighbor] = u\n",
      "                nodelist.append(neighbor)\n",
      "                total_marked += 1\n",
      "        color[u] = 'black'\n",
      "    return total_marked, parent, depth"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 90
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print BFS_iterative(G1, 'w')\n",
      "print '================================='\n",
      "print DFS_iterative(G1, 'w')\n",
      "\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "(8, {'s': 'w', 'r': 's', 'u': 't', 't': 'w', 'w': None, 'v': 'r', 'y': 'x', 'x': 'w'}, {'s': 1, 'r': 2, 'u': 2, 't': 1, 'w': 0, 'v': 3, 'y': 2, 'x': 1})\n",
        "=================================\n",
        "(8, {'s': 'w', 'r': 's', 'u': 'y', 't': 'w', 'w': None, 'v': 'r', 'y': 'x', 'x': 'w'})\n"
       ]
      }
     ],
     "prompt_number": 95
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": []
    }
   ],
   "metadata": {}
  }
 ]
}