Vistiendo a Batman
Orden topológico en grafos dirigidos acíclicos
Probablemente muchos de vosotros pensaréis que la vida de un superhéroe es relativamente fácil. Vale, trabajan ocho horas diarias como el resto de los mortales (de los mortales que tienen la suerte de trabajar, claro) pero gracias a sus superpoderes no suelen tener muchos problemas en acabar con los villanos. Sin embargo su vida fuera del trabajo es como la de cualquiera de nosotros, porque cuando no trabajan no tienen superpoderes. Únicamente pueden hacer uso de sus superpoderes cuando llevan sus trajes de superhéroes.
De hecho, la propia tarea de ponerse estos trajes ya es en sí misma complicada. Quizás tengáis la siguiente imagen mental de un superhéroe vistiéndose rápidamente para acabar con el mal:
Pero la realidad es muy distinta. Los trajes de los superhéroes actuales no son como los de antes, cuando eran mucho más simples. Ahora la moda obliga a llevar multitud de complementos a conjunto si uno no quiere considerarse un superhéroe de segunda categoría. Yo me imagino, por ejemplo, a Bruce Wayne enfrentado a su guardarropas en la batcueva a todos los elementos que componen su traje de Batman.
Quizás os sorprenda saber que Batman lleva dos calzoncillos, uno por dentro del pantalón (con su logo y su marca) y otro por fuera (en negro, a juego con el resto de elementos). En serio, no preguntéis por qué es así. Además, se ve obligado a llevar unos calcetines gruesos porque siempre tiene frío en los pies.
Y tanta pieza hace que sea un auténtico problema el orden en que debe vestirse. Sin ir más lejos, un día que tenía una llamada de emergencia del comisario James Gordon se dio cuenta de que se había vestido sin sus calcetines y tuvo que volver a vestirse de cintura hacia abajo, por lo que llegó tarde y Dos Caras consiguió robar el banco de Gotham.
La pregunta que nos hacemos es, ¿podemos ayudar a Batman a vestirse en el orden correcto? ¿Y podemos extender esta solución a otros superhéroes?
Grafos
Antes de explicar cómo solucionar este problema déjame que te hable un poco de grafos. Un grafo es una estructura matemática compuesta de nodos unidos mediante aristas, tal y como puedes ver en la imagen de la izquierda. En este grafo, por conveniencia, los nodos se han numerado con valores del 1 al 6. Las aristas definen algún tipo de relación entre los nodos, y no tiene por qué haber aristas entre todos los pares de nodos. Otra característica de este grafo es que es conexo, es decir, no existe ningún nodo aislado del resto, por lo que podemos ir de un nodo a cualquier otro siguiendo algunas aristas.
Pero los grafos que me interesan para resolver el problema de Batman son los denominados grafos dirigidos. En estos grafos las aristas tienen una dirección (para que no se enfaden mis amigos físicos, la palabra exacta es sentido) , de modo que podemos asignarles un nodo de origen y un nodo de destino. En el grafo de la izquierda, por ejemplo, hay una arista que parte del nodo 1 y llega al 2, pero no hay ninguna arista en sentido contrario, del nodo 2 al 1. Podemos asignar a cada nodo un número de aristas de salida y un número de aristas de llegada. Por ejemplo, el nodo 5 tiene dos aristas de llegada y una de salida.
Fíjate en otra característica del grafo anterior, tiene un ciclo: si empezamos por el nodo 2 podemos llegar por la arista que sale de él al nodo 6, de éste al nodo 5, y de nuevo al nodo 2. Si el grafo no tiene ningún ciclo se denomina acíclico.
A nosotros nos van a interesar en este artículo los grafos dirigidos acíclicos (DAG, del inglés directed acyclic graph). Estos grafos tienen una gran importancia en diversos campos de las matemáticas y otras ciencias.
Orden topológico en DAG
Para ayudar a Batman a vestirse vamos a empezar creando un grafo dirigido acíclico en el que cada una de las prendas o complementos será un nodo. Además entre dos objetos en los que exista una precedencia en el momento de vestir dibujaremos una arista entre la primera prenda y la segunda. Para que lo entiendas mejor, como Batman debe ponerse los calcetines antes que las botas habrá una flecha que saldrá en los calcetines y terminará en las botas. También habrá, por ejemplo, una flecha que partirá de la camiseta y llegará a la capa. Siguiendo todas las precedencias entre prendas, podríamos dibujar el siguiente grafo (puede que a ti te salga distinto porque decidas que los calcetines van por dentro de los pantalones y no por fuera).
Ahora nos interesa ordenar estas prendas de ropa de forma que Batman puede vestirse sin problemas. Para ello hay que tener en cuenta que una prenda determinada de este grafo no puede aparecer después de otra a la que apunte con una flecha, o a la que se pueda llegar siguiendo varias flechas. Por ejemplo, en la ordenación final no pueden aparecer las botas antes que los calcetines. A esta ordenación de un DAG se la denomina ordenación topológica. Debes tener en cuenta que distintas ordenaciones topológicas pueden ser igualmente correctas. Por ejemplo, en el grafo se observa que Batman podría elegir como última prenda para vestirse la máscara, el logo que va sobre el pecho, las botas o el cinturón.
Voy a explicarte un algoritmo que permite calcular el orden topológico de cualquier DAG de una forma sistemática. Para ello, vamos a empezar eligiendo todas aquellas prendas (nodos) que no tienen aristas de entrada. (al ser un grafo acíclico debe haber al menos un nodo así). En este caso sólo hay una prenda así, los calzoncillos interiores, así que esta será la primera prenda que deberá ponerse Batman (¡qué sorpresa, eh!). A continuación eliminamos este nodo del grafo y todas las aristas que salen de él. Nuestro grafo quedaría del siguiente modo:
En la parte inferior de la figura iremos añadiendo las prendas en el orden en que debe ponérselas Batman. Ahora vamos a repetir el proceso anterior con este nuevo grafo, es decir, localizar las prendas sin aristas de entrada. Ahora le tocaría a los pantalones, así que los añadimos a nuestra lista ordenada y los borramos del grafo junto con sus aristas.
Ya puedes imaginar que vamos a seguir con el mismo proceso, pero ahora nos encontramos con que hay tres prendas sin aristas de entrada: la camiseta, los calzoncillos exteriores y los calcetines. Para proceder de la forma más sistemática y concreta posible (como debe ser un algoritmo) añadiremos estos objetos a nuestra lista ordenada de arriba a abajo.
Si sigues aplicando el procedimiento al grafo restante tres veces más obtendrías la siguiente lista de objetos que Batman debe ponerse siguiendo el orden de izquierda a derecha.
Espero que hayas entendido este algoritmo para ordenar los nodos de un grafo dirigido acíclico (en este caso para ayudar a Batman a vestirse). Un algoritmo no es más que una “receta” exacta y no ambigua que describe un procedimiento. En informática solemos utilizar pseudocódigo para describir algoritmos; básicamente, redactamos un procedimiento con lenguaje natural (no lenguaje de programación). ¿Te animas a leer el pseudocódigo del algoritmo de ordenación topológica y compararlo con la descripción anterior?
Si has llegado hasta aquí puede que estés pensando: «Eso lo hubiera podido pensar yo sin enrollarme con teoría de grafos ». Cierto, pero sólo te serviría para grafos pequeños como el anterior. Imagínate ahora que tienes un grafo como el siguiente, que muestra las dependencias de los distintos módulos de un biblioteca auxiliar para programar en C++:
La ordenación topológica de grafos dirigidos acíclicos se utiliza cuando hay una serie de tareas con dependencias entre sí. Como ejemplos se podrían citar la planificación de proyectos y diversos problemas relacionados con la informática, como la compilación de programas y la reevaluación de celdas de una hoja de cálculo.
Referencias
- Si quieres seguir aprendiendo más cosas de teoría de grafos de forma divertida es imprescindible que sigas en Twitter a Clara Grima y leas su blog Mati y sus mateaventuras.
- Desde que conocí a Carlos Lobato que he querido escribir un artículo de divulgación con superhéroes. Por fin he cumplido mi deseo, aunque no llego ni de lejos a su altura y experiencia como divulgador. Si veis el vídeo de su charla en Naukas 2014 seguro que me daréis la razón.
Si te apetece escribir algún comentario, puedes hacerlo buscando los signos ‘+’ que se encuentran a la derecha de cada párrafo. Y si te ha gustado, puedes recomendar este artículo haciendo clic en el botón al final del texto.
