Simulación y visualización de cuplajes planares en grafos bipartitos aleatorios

Contenido:

* Preliminares -- contexto y conceptos generales

* Explicación del applet -- descripción de funcionamiento del applet

* Simulación -- ingreso de parámetros para la simulación del applet

PRELIMINARES

Introducción

Dadas dos palabras X e Y sobre un alfabeto finito cualquiera, el problema de la Longest Common Subsequence (LCS) -- en castellano Subsecuencia Común Más Larga -- consiste, como su nombre sugiere, en encontrar cuál es el largo máximo que puede tener una palabra que sea subsecuencia de X e Y simultáneamente. Por ejemplo, si consideramos X=matematicas e Y=astronomia, una LCS (y en este caso la única) es atmia. El largo de una LCS se usa comúnmente como criterio de comparación de palabras, pues está relacionada con la cantidad de "pasos" necesarios para ir de una palabra a la otra mediante operaciones de inserción, eliminación y reemplazo de caracteres. Es posible encontrar aplicaciones de lo anterior en la biología molecular (comparación de cadenas de ADN) y en computación (comparación de archivos), entre otras.

Nuestro objetivo es presentar brevemente algunos temas relacionados directamente con el problema de LCS de manera de que sea más fácil entender el funcionamiento del applet que hace la simulación gráfica.

Cuplajes planares

Un problema similar al LCS es el problema de Longest Increasing Subsequence (LIS) -- en castellano, Subsecuencia Creciente Más Larga -- el cual consiste en, dada una permutación P de los números 1,2,...,n, encontrar el largo máximo que puede tener una subsecuencia de P que sea creciente. Por ejemplo, si P=(6,2,8,5,7,4,1,9,3) entonces una LIS (también la única) es R=(2,5,7,9). Un problema de LIS se reduce a uno de tipo LCS. Para ello, interpretamos una permutación R=(R₁,R₂,...,R_n) sobre los números 1,2,...,n como la palabra R₁R₂...R_n. Es fácil ver que una LIS entre P y Q correspnde a una LCS entre P y Q=(1,2,...,n).

Una visión más general de los problemas anteriores se obtiene al estudiar los Planar Matchings (PM) -- en castellano, cuplajes planares. Sea G=(W,M;E) un grafo bipartito, es decir, W y M son conjuntos de nodos tales que todo arco e en E posee un extremo en W y otro en M. Supongamos además que dibujamos los nodos del grafo sobre dos rectas paralelas en forma ordenada (los nodos de W en una recta y los de M en la otra) y que los arcos los dibujamos como líneas rectas. Por ejemplo, si tomamos W=(A,B,C,D,E,F) , M=(1,2,3,4) y E={A1,B1,B3,C2,C3,D3,D4,E1,F2}, obtenemos:

Un matching -- en castellano, cuplaje -- en un grafo arbitrario (no necesariamente bipartito) es cualquier conjunto de arcos que no comparten extremos; un PM es un matching en donde los arcos no se cruzan ni comparten extremos. Obviamente un matching será o no planar dependiendo de la forma en que se dibuje, pero en nuestro caso de grafos bipartitos hemos dicho que los nodos se dibujan en forma ordenada y los arcos como líneas rectas, por lo que no existe dicha ambiguedad.

Si agregamos costos a los arcos, un problema de interés es encontrar un matching planar de costo máximo. Este problema está relacionado con el de LCS ya que todo par de palabras puede representarse convenientemente como un grafo bipartito donde los arcos unen a los caracteres coincidentes de ambas palabras. Volviendo a tomar las palabras X=matematicas e Y=astronomia el grafo que los representa sería:

Así, calcular la LCS entre dos palabras no es más que calcular el matching planar de costo máximo del grafo bipartito asociado a dichas palabras, donde todos los arcos tienen costo igual a 1. Más aún, aprovechando la generalidad que otorga ver el problema LCS como uno de matching, se nos ocurren ideas nuevas que dan mayor alcance al concepto de comparación de palabras: podemos, por ejemplo, agregar más arcos al grafo asociado a dos palabras cuando los caracteres tengan cierta similitud o cuando compartan algún atributo, y asociarle un costo menor al que tienen los arcos que unen caracteres iguales. Por ejemplo, podemos agregar un arco con costo 0.5 que una los caracteres 'a' y '@'.

El algoritmo

Existe un algoritmo que calcula en tiempo O(n*m) el largo de la LCS entre dos palabras, donde n y m son los largos de las palabras. Dicho algoritmo va calculando progresivamente las LCS de las porciones iniciales de ambas palabras, guardando los valores calculados en una matriz de n+1 por m+1. Si llamamos S a dicha matriz, la componente S[i][j] (con i=0,...,n , j=0,...m) se calcula (para i,j>0) de la siguiente manera:

Si X[i]=Y[j], entonces S[i][j] se calcula como S[i][j]=S[i-1][j-1]+1, lo cual se interpreta como si tuviéramos las porciones iniciales de las palabras de largos i-1 y j-1 respectivamente y le agregásemos los caracteres X[i] e Y[j] a cada porción inicial. Como ambos caracteres coinciden, le sumamos 1 al valor que había en S[i-1][j-1].
Si, por el contrario, X[i]!=Y[j] entonces S[i][j] se calcula como S[i][j]=max(S[i][j-1],S[i-1][j]). Esto se interpreta como si en el paso anterior hubiésemos podido estar en dos situaciones: con las porciones iniciales de largo i y j-1 donde luego le agregamos el caracter Y[j] a la segunda porción; o bien con las porciones iniciales de largo i-1 y j donde luego se agrega el caracter X[i] a la primera porción. Como cualquiera de las dos situaciones es posible, debemos tomar el máximo de ambas (sin sumar nada, pues los caracteres X[i] e Y[j] no coinciden).

Veamos un ejemplo para entender mejor el funcionamiento del algoritmo:


		m   a   t   e   m   a   t   i   c   a   s

	    0 - 0 - 0 - 0 - 0 - 0 - 0 - 0 - 0 - 0 - 0 - 0
	    |	| \               \               \
	a   0 - 0   1 - 1 - 1 - 1   1 - 1 - 1 - 1   1 - 1
	    |   |   |   |   |   |   |   |   |   |   | \
	s   0 - 0   1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1   2
	    |   |   | \               \                 |
	t   0 - 0   1   2 - 2 - 2 - 2   2 - 2 - 2 - 2 - 2
	    |   |   |   |   |   |   |   |   |   |   |   |
	r   0 - 0   1   2 - 2 - 2 - 2 - 2 - 2 - 2 - 2 - 2
	    |   |   |   |   |   |   |   |   |   |   |   |
	o   0 - 0   1   2 - 2 - 2 - 2 - 2 - 2 - 2 - 2 - 2
	    |   |   |   |   |   |   |   |   |   |   |   |
	n   0 - 0   1   2 - 2 - 2 - 2 - 2 - 2 - 2 - 2 - 2
	    |   |   |   |   |   |   |   |   |   |   |   |
	o   0 - 0   1   2 - 2 - 2 - 2 - 2 - 2 - 2 - 2 - 2
	    | \     |   |   | \
	m   0   1 - 1   2 - 2   3 - 3 - 3 - 3 - 3 - 3 - 3
	    |   |   |   |   |   |   |   | \
	i   0   1 - 1   2 - 2   3 - 3 - 3   4 - 4 - 4 - 4
	    |   | \     |   |   | \         |   | \
	a   0   1   2 - 2 - 2   3   4 - 4 - 4 - 4   5 - 5

Los números indican los valores calculados de la matriz y las líneas indican desde dónde fue actualizado dicho valor. Cada vez que los caracteres de las palabras coinciden se observa una línea diagonal, pues el valor fue actualizado desde la fila y columna anteriores, mientras que cuando los caracteres no coinciden aparece una línea vertical u horizontal (o ambas en caso de que el máximo se alcance en los dos valores simultáneamente). Notar que S[i][j]=0 en caso de que i=0 o bien j=0. Estos valores no provienen de ningún otro valor de la matriz y son consistentes con su significado: la LCS entre cualquier string y el string vacío es siempre cero. El valor de la LCS global queda guardado en S[n][m], y la subsecuencia misma puede encontrarse remontando el camino desde abajo a la derecha hasta arriba a la izquierda, recordando, cada vez que pasamos por una línea diagonal, el caracter que produjo esa diagonal.

El algoritmo en sí recorre la matriz por filas o columnas actualizando los valores de acuerdo a lo dicho anteriormente. Escrito en pseudo-código, quedaría así:

    int lcs_length(char * A, char * B)
    {
	pedir memoria para la matriz S;

	for( i = 0; i <= n ; i++ )
		S[i][0]=0;
	for( j = 0; j <= m ; j++ )
		S[0][j]=0;

	for (i = 1; i <= n; i++)
	    for (j = 1; j <= m; j++)
	    {
		if (A[i] == B[j]) S[i][j] = 1 + S[i-1][j-1];
		else S[i][j] = max(S[i-1][j], S[i][j-1]);
	    }
	return S[n][m];
    }

Introduciendo más aleatoriedad

Supongamos ahora que X e Y son ambos del mismo tamaño (|X|=|Y|=n) y que son generados aleatoriamente sobre un alfabeto de tamaño k, es decir, por cada string realizamos n veces el experimento de elegir uno de los k posibles caracteres, cada uno con probabilidad 1/k de aparecer, independiente del resto. Llamemos L_n a la variable aleatoria que indica el largo de la LCS entre X e Y. Por argumentos de sub-aditividad es posible demostrar que

µ_k=lim_n (E(L_n)/n)
existe para cualquier k. Sin embargo, su valor exacto es aún desconocido, incluso para el caso en que k=2.

En parte motivados por la dificultad de atacar directamente el problema de la determinación de µ_k es que Kiwi, Loebl y Matousek han estudiado el problema que se plantea a continuación. Si ponemos atención al algoritmo que calcula la LCS nos daremos cuenta que no es necesario conocer las palabras en sí, sino que basta con saber si el caracter X[i] coincide o no con Y[j] para cada i y j, lo cual puede almacenarse como una matriz binaria de n por m en la que la coordenada i y j valdrá 1 si X[i]=Y[j], y 0 en otro caso. Ahora, el algoritmo descrito más arriba sigue funcionando de igual manera ante cualquier matriz binaria, sin importar si dicha matriz proviene o no de un cruce de palabras (como el lector podrá rápidamente convencerse, no cualquier matriz binaria proviene de un cruce de palabras). Más aun, el algoritmo determina un PM de largo máximo en el grafo bipartito G=(W,M;E) tal que W=M={1,2,...,n} y el arco (i,j) está en E si y sólo si la coordenada (i,j) de la referida matriz es no nula. Es en este punto en que se nos ocurre, en lugar de generar dos palabras aleatorios, generar una matriz binaria aleatoria donde cada valor de la matriz vale 1 con probabilidad p y 0 con probabilidad 1-p, donde p es un valor arbitrario entre 0 y 1.

Explicación del applet

Funcionamiento del applet

El applet recibe ciertos parámetros entregados por el usuario, luego aplica el algoritmo explicado más arriba, y finalmente genera una imagen que muestra al usuario los resultados obtenidos. El applet ocupa dos programas para obtener la imagen final, y conviene entender qué hace cada uno:

El primer programa se encarga de generar una matriz binaria de acuerdo a uno de tres modelos:
- Modelo Ulam: se genera una permutación aleatoria del conjunto {1,2,..,n} (donde n es entregado por el usuario), y la matriz que se obtiene es la respectiva matriz de permutación.
- Modelo LCS: se generan dos palabras aleatorias de largos n y m sobre un alfabeto de tamaño k (n,m y k entregados por el usuario), y la matriz se obtiene al hacer el cruce de ambas palabras, es decir, la coordenada i,j de la matriz valdrá 1 si el caracter i del primer string coincide con el caracter j del segundo; 0 en otro caso.
- Modelo Erdös: la matriz es de n por m donde cada coordenada vale 1 con probabilidad p y vale 0 con probabilidad1-p (p es entregado por el usuario).
El segundo programa toma la matriz binaria generada por el primer programa y le aplica el algoritmo para calcular el PM. Luego genera la imagen final de acuerdo a uno de los siguientes formatos de dibujo:
- Formato de malla: se dibuja la matriz como una cuadrícula de n por m donde la casilla (i,j) se pinta de un color dependiendo de cuál es el largo total de los PM más largos determinados a partir de las matrices de coordenadas {1,...,i}x{1,...,j} y {i+1,...,n}x{j+1,...,n}. Aquellas casillas que pertenecen a PMs de largo cercano al del PM global más largo son pintadas con colores oscuros; aquellas que pertenecen a PMs más cortos son pintadas con colores gradualmente más claros.
- Formato de árbol: se obtiene un árbol de prefijos similar al que aparece más arriba en la sección del algoritmo, con la diferencia de que acá no se dibujan los números de las casillas, simplemente se dibujan las líneas. Por cada casilla se dibuja una sola línea que indica desde dónde fue calculado su valor. En caso de que el máximo se alcance en más de un valor se le puede decir al programa qué orden (prioridad) seguir; por ejemplo, se le puede indicar que dibuje la diagonal si es posible y si no lo es, que elija al azar una de las otras posibilidades (hemos agregado la opción, además de devolverse por la misma fila o columna, de pasar directamente a la fila y columna anteriores). Además se dibujará un círculo por cada 1 que aparece en la matriz.

Ejemplos

A continuación se muestran algunos ejemplos de las imágenes que se pueden obtener con el applet.

Modelo LCS de 100x100 con alfabeto de tamaño 10, formato de malla:

Modelo Erdös de 800x800 con probabilidad 0.02, formato de malla:

Modelo Erdös de 50x100 con probabilidad 0.1, formato de Árbol con prioridad Aleatorio-Diagonal, color plano:

Modelo LCS de 200x200 con alfabeto de tamaño 10, formato de Árbol con prioridad Diagonal-Aleatorio, color descendente:

SIMULACIÓN

Finalmente, presentamos el applet que permite obtener las imágenes. En los casos en que hay aleatoriedad se puede ingresar una "semilla" que da la pauta para la generación de números aleatorios, de manera que para la misma semilla se recupera exactamente la misma imagen.

Tenga en consideración que el máximo de filas y/o columnas permitido es de 800, por razones de tiempo y espacio en disco.

Diseñado por:		Roberto Cortez y Marcos Kiwi.
Implementado por:		Roberto Cortez (Enero de 2005)
Revisado en:		Mozilla 1.0 (Enero de 2005)

La implementación de esta demo fue finaciada por el Núcleo Milenio en Información y Aleatoriedad.