Componentes conexas de un grafo.


Empezamos la primera entrega de tres con una breve introducción a teoría de grafos antes de meternos en programación. Creo que la introducción es necesaria dado que este método está muy orientado a tratamiento de grafos y pares de datos, en este caso en forma de aristas entre dos vértices. Esta introducción es, sin embargo, extremadamente simple, y no debe echar atrás a nadie.

Nuestro problema es el de identificar regiones distintas de un mapa de dos colores. A nuestro programa llegará la información del mapa, por ejemplo esta imagen:

grafo

Consideremos una matriz equivalente:

\begin{pmatrix}  0 & 0 & 0 & 0 & 0 & 0\\  0 & 1 & 1 & 0 & 0& 0\\  0 & 1 & 1 & 0 & 1& 0\\  0 & 0 & 0 & 0 & 1& 0\\  0 & 0 & 0 & 0 & 0& 0  \end{pmatrix}

Reconocemos claramente dos regiones o componentes en blanco, pero el ordenador no lo hace. Nuestro programa extraerá información que nos permita tratar esas dos regiones.

Pasemos ahora a los grafos. Un grafo es un conjunto de dos elementos, esos dos elementos son vértices y aristas. Las definiciones de cada uno de ellos son más que evidentes como para ponerlas, pero vayamos a la parte matemática.

En matemáticas todo tiene un nombre. A un grafo, como es común a los conjuntos, se les suele designar por una letra mayúscula, en el caso de los grafos es común encontrar la letra G. Llamemos pues a nuestro grafo G. Como hemos dicho, este grafo tendrá dos elementos, vértices y aristas. Cada uno de ellos es a su vez un conjunto que contiene elementos, los vértices y las aristas. A los vértices se les llama V y a las aristas E. Nuestro grafo es, siguiendo con esta nomenclatura: G=\left\lbrace V,E \right\rbrace.

Pongamos ahora un grafo de ejemplo:

Construyamos el conjunto que define al grafo. Como siempre, tendremos dos subconjuntos, uno de vértices y uno de aristas. En este caso tenemos cinco vértices llamados v_i \hspace{20px} i=1,2,3,4,5. Las aristas se nombran con los vértices de sus extremos, por ejemplo la arista que va de v_1 a v_2 es v_1v_2. Nuestro grafo es:

G=\left\lbrace V,E \right\rbrace\\ V = \left\lbrace v_1, v_2, v_3, v_4, v_5 \right\rbrace\\ E = \left\lbrace v_1v_2,v_1v_3,v_1v_4,v_1v_5,v_2v_4,v_2v_5 \right\rbrace

Cuidado con no repetir aristas, v_1v_2 es lo mismo que v_2v_1 (no pasa lo mismo en un digrafo).

Lo que queda por definir es la matriz de adyacencia de un grafo. La matriz de adyacencia es una matriz cuadrada de m\times m, tal que m es el número de vértices. Si cada casilla de la matriz es a_{ij}, entonces:

a_{ij} = 0 \hspace{20px}\text{si} v_iv_j \not \in E\\    a_{ij} = 1 \hspace{20px}\text{si} v_iv_j \in E

Es decir, la casilla de la fila i y la columna j vale 1 si los vértices v_i y v_j están conectado por una arista, y 0 si no lo están. Por ejemplo, la matriz de adyacencia del grafo anterior sería:

\begin{pmatrix}  0 & 1 & 1 & 1 &1 \\  1 & 0 & 0 & 1 & 1\\  1 & 0 & 0 & 0 & 0\\  1 & 1 & 0 & 0 & 0\\  1 & 1 & 0 & 0 & 0  \end{pmatrix}

La matriz de adyacencia es una manera muy util de analizar un grafo computacionalmente, y por eso nos interesa, además de tener otras características mucho más útiles.

Con esto de grafos tenemos suficiente para nuestro algoritmo. Lo que haremos será tratar una matriz como si fuese un grafo para hallar las componentes conexas de este. El código está en Matlab, pero es un código muy simple que debería ser fácilmente portable. Tenemos mucho pase de argumentos a funciones recursivas, así que para C hay que usar punteros al pasar toda esta información.

Lo que haremos será pasar a la función una matriz de ceros y unos, los unos formarán los puntos que queremos hallar. Haremos una función que a partir de esa matriz saque los pares de vértices y la matriz de adyacencia. Haremos luego otra función que use la matriz de adyacencia para sacar las componentes conexas.

Esto se puede hacer en Matlab con muy pocas lineas, ya que tiene funciones internas que lo hacen por nosotros. dmperm realiza la descomposición Dulmage-Mendelsohn, que con una matriz de adyacencia permite sacar las componentes conexas de un grafo. Sin embargo, no creo que esto tenga gracia cuando lo que queremos es aprender, así que programaremos la función nosotros mismos.

Este método es más eficiente cuando lo que tenemos so pares de vértices conectados, y no mucho cuando lo que tenemos es una matriz en la que los vértices están siempre conectados de la misma manera, pero bueno, lo aplicaremos. Dependerá de tí inventar y aplicar métodos eficientes a cada problema.

Empecemos definiendo una matriz cualquiera en la que hallaremos las regiones, para tener un ejemplo sobre el que ir aplicando.

matriz = [0 1 1 0 0 0;1 1 1 0 0 0;0 1 1 0 1 1;0 0 0 0 0 1;0 0 0 0 1 1]
matriz =
 0   1   1   0   0   0
 1   1   1   0   0   0
 0   1   1   0   1   1
 0   0   0   0   0   1
 0   0   0   0   1   1

Vemos claramente dos regiones en la matriz, nuestra función debe detectarlas. Lo primero que necesitamos es sacar la matriz de adyacencia del grafo. Y para eso necesitamos pares de vértices. Crearemos una función que a partir de esa matriz nos saque pares de vértices. Lo primero que hará será numerar la matriz. Dejará los ceros como están, y las casillas ocupadas las numerará del 1 en adelante. Definimos nuestra función. Como entrada debe recibir la matriz, evidentemente. Como salida tendrá la matriz de adyacencia y la matriz numerada (esta última no la volveremos a usar, pero está bien tenerla).

Creamos un archivo pairs.m que contenga la función pairs, y definimos la función:

function [m_adyacencia,B] = pairs (A)
m = size(A,1);
n = size(A,2);
B = zeros(m,n);
contador = 1;

La variable m contiene el número de filas de la matriz, la variable n contiene el número de columnas. Creamos también la matriz B, que será la matriz numerada, y de momento que sea todo ceros. Ahora recorreremos la matriz B, y le vamos dando números (usando la variable contador), según encuentr casillas en la matriz de entrada:


for i=1:n
for j=1:m
if A(j,i)!=0
B(j,i) = contador;
contador = contador+1;
end
end
end

Como vemos el código de matlab es muy simple, casi pseudocódigo, así que debería ser fácilmente trasladable. De todos modos, si no sabes como pasar a C/C++ algo de esto, pregúntame.

Hasta aquí ya tenemos la matriz numerada. Si ejecutamos la función pasándole nuestra matriz, obtenemos de salida:

B =
0    2    5    0    0    0
1    3    6    0    0    0
0    4    7    0    8   10
0    0    0    0    0   11
0    0    0    0    9   12

Ahora necesitamos la matriz de adyacencia. Lo que haremos será sacar una lista de pares y usar la función accumarray para crear la matriz. No me gusta usar funciones internas de este modo, pero es tan simple que no creo que importe. Si lo quieres programar, sería tan fácil como crear una matriz de 12×12, ya que en este caso es el número de vértices. Luego recorremos la matriz creada, y para cada i,j, vemos si esos vértices están conectados, si lo están, le damos un 1, si no, le damos un 0.

Nosotros lo haremos de otro modo, sacaremos una lista con pares de vértices conectados, el código es el siguiente: (reiniciamos el contador a 1 porque reciclamos la variable para el siguiente bucle)


contador = 1;
for i=1:m
for j=1:n
if B(i,j)!=0
if i>1
if B(i-1,j)!=0
pares(contador,:) = [B(i,j) B(i-1,j)];
contador = contador+1;
end
end
if i<size(B,1)
if B(i+1,j)!=0
pares(contador,:) = [B(i,j) B(i+1,j)];
contador = contador+1;
end
end
if j>1
if B(i,j-1)!=0
pares(contador,:) = [B(i,j) B(i,j-1)];
contador = contador+1;
end
end
if j<size(B,2)
if B(i,j+1)!=0
pares(contador,:) = [B(i,j) B(i,j+1)];
contador = contador+1;
end
end
end
end
end

El código es simple. Recorremos la matriz B. Para cada vértice que encuentre, es decir, si es diferente de 0, entonces mira sus cuatro vecinos, y si alguno es diferente de cero, mete sus valores en una lista “pares”, que es un matriz de X filas y 2 columnas. Al pasárselo a nuestra matriz queda la siguiente lista:

pares =

2    3
2    5
5    6
5    2
1    3
3    2
3    4
3    1
3    6
6    5
6    7
6    3
4    3
4    7
7    6
7    4
8   10
10   11
10    8
11   10
11   12
9   12
12   11
12    9

Vemos que los vértices han sido conectados bien. Esta lista, sin embargo, no la necesitamos, pero la función accumarray, nos devuelve la matriz de adyacencia a partir de ella, así que no hay más que sacarla.

m_adyacencia = accumarray(pares,1);

El código completo es el siguiente (más fácil de leer, no se porqué wordpress no saca las tabulaciones): http://pastebin.com/2K3H2KHY

Ya lo tenemos. Llamamos a la función de la siguiente manera:

>> [m,b]=pairs(matriz);

m es la matriz de adyacencia y b la matriz original numerada. Puedes hacer spy(m) para visualizar la matriz.

Ahora vamos con nuestra función que detectará el número de componentes conexas. Nos devolverá la información en dos variables. La primera de ellas es un vector con los vértices permutados, la llamaremos p, la segunda será otro vector con los cortes en el anterior, me explico. Vemos que nuestra matriz tiene dos componentes, la primera está formada por los vértices: 1,2,3,4,5,6,7, y la segunda por los vértices: 8,9,10,11,12. El vector p podría ser:

p = [1 2 3 4 5 6 7 8 9 10 11 12].

Encontramos la primera componente en los elementos del 1 al 7, y a partir del 8 la segunda. El vector c sería entonces:

c = [1 8 13]. Esto hace que podamos ver cada componente viendo los elementos de p desde c(x) hasta c(x+1)-1.

La función hará lo siguiente:

En un array tendremos los vértices numerados y en orden. Ahora empezamos a recorrer la matriz de adyacencia. Por cada fila que se recorra, en el array de vértices borramos ese vértice, para saber que ya ha sido recorrido. Bien, recorremos la matriz fila por fila. Empieza por la primera, es decir, la del primer vértice, si encuentra alguna casilla que sea 1, entonces es que el 1 está conectado con el vértice al que corresponde esa columna. Una vez visto, borramos este vértice del array de vértices y saltamos a una función recursiva que haga lo mismo con la fila del vértice encontrado. Lo que hacemos así es recorrer toda la matriz recursivamente en busca de vértices unidos.Conforme vamos encontrando vértices los vamos metiendo en ese orden el vector de vértices permutados p.

Para rellenar el vector c, lo que hacemos es, simplemente, cada vez que la función principal llegue al final de una fila, le ponemos el lugar siguiente del vector de vértices permutados. ¿Por qué? Porque cuando llega al final de una fila significa que ya ha recorrido recursivamente todos los posibles vértices con los que podía estar conectado, así que hemos llegado al final de una componente, lo apuntamos, y saltamos de fila.

Empecemos. Primero inicializamos algunas variables que nos serán útiles:

function [p,c] = clases(A)

p(1) = 1;
c(1) = 1;
for i=1:size(A,1)
vert(i) = i;
end
m = size(A,1);
controlador = 2;
cont=1;

Evidentemente los primeros valores de p y de c serán 1, así que se los vamos poniendo. Creamos también el vector de vértices que iremos borrando conforme los encontramos (vert). m lo usaremos como información del tamaño de la matriz. size(A,1) devuelve el número de filas de la matriz A, puesto que la matriz de adyacencia es siempre cuadrada, con ese ya tenemos su tamaño. “controlador” la usaremos para ir apuntando los lugares del vector c, y cont lo mismo pero con el vector p.

Ya podemos empezar. Empezamos a recorrer la matriz, cada fila la recorremos si y sólo si no ha sido recorrida ya, es decir, si está en el vector de vértices vert. Si no ha sido recorrida entonces la recorremos, metiendo ya su valor en p. Y a continuación recorremos la fila buscando conexiones. Al final de todo miramos si está en la última columna de la fila, en ese caso metemos un nuevo valor en c.

for i=1:m
if vert(i) == i
p(cont) = i;
vert(i) = 0;
cont = cont+1;
for j=1:m
if A(i,j) == 1 && vert(j) != 0
p(cont) = j;
vert(j) = 0;
cont = cont+1;
A(i,j) = 0;
A(j,i) = 0;
[A,vert,p,c,cont]=fila(A,vert,p,c,cont,j);
end
if j==m
c(controlador) = cont;
controlador = controlador+1;
end
end
end
end

El código completo aquí: http://pastebin.com/ezr5dgGh

Veamos lo que hace  si encuentra una conexión ( partir de la fila 16 del código completo de la función). Primero mete el vértice en p y borra ese vértice de vert. Luego borra la casilla de la matriz de adyacencia, y a continuación llama a la función fila. Esta será nuestra función recursiva. Recorrerá la fila del nuevo vértice haciendo lo mismo. (Fíjate que, puesto que la matriz de adyacencia es simétrica con respecto a la diagonal, borramos tanto A(i,j) como A(j,i)). A la función fila debemos pasarle todos los contadores, vectores y, por supuesto, la matriz, para que pueda trabajar. Y nos devolverá todos los cambios que les haya hecho. En MatLab la salida de la función es lo que hay antes del igual.

Veamos ahora nuestra función fila.

function [A,vert,p,c,cont]=fila(A,vert,p,c,cont,filas)
m = size(A,1);

for i=1:m
if A(filas,i) == 1 && vert(i) != 0
p(cont) = i;
vert(i) = 0;
cont = cont+1;
A(i,filas) = 0;
A(filas,i) = 0;
[A,vert,p,c,cont]=fila(A,vert,p,c,cont,i);
end
end

Enlace: http://pastebin.com/Hjwew3cX

Habiendo visto lo anterior, no tiene mucho misterio. Recorre la fila buscando conexiones, y si encuentra alguna, entonces hace lo mismo que hacíamos desde fuera de la función, mete la conexión en el vector p, borra el dato de vert y las casillas de la matriz de adyacencia, y se llama a sí misma con la nueva fila.

Nos ahorramos en la función principal algo de tiempo algorítmico haciendo que no recorra filas que ya han sido recorridas, y así es un poco más rápido. De todos modos, dudo de su eficiencia a gran escala. Con pequeños grafos no matriciales es un algoritmo útil. Es decir, cuando lo que tengamos sea una lista de pares de vértices conectados.

Ya hemos acabado, probemos nuestro algoritmo con la misma matriz de antes:

matriz = [0 1 1 0 0 0;1 1 1 0 0 0;0 1 1 0 1 1;0 0 0 0 0 1;0 0 0 0 1 1]
matriz =
 0   1   1   0   0   0
 1   1   1   0   0   0
 0   1   1   0   1   1
 0   0   0   0   0   1
 0   0   0   0   1   1

Bien, lo primero conseguimos la matriz de adyacencia y la matriz numerada (esta última para orientarnos):

>>[m_ad,B] = pairs(matriz)

 

>> m_ad
m_ad =

0   0   1   0   0   0   0   0   0   0   0   0
0   0   1   0   1   0   0   0   0   0   0   0
1   1   0   1   0   1   0   0   0   0   0   0
0   0   1   0   0   0   1   0   0   0   0   0
0   1   0   0   0   1   0   0   0   0   0   0
0   0   1   0   1   0   1   0   0   0   0   0
0   0   0   1   0   1   0   0   0   0   0   0
0   0   0   0   0   0   0   0   0   1   0   0
0   0   0   0   0   0   0   0   0   0   0   1
0   0   0   0   0   0   0   1   0   0   1   0
0   0   0   0   0   0   0   0   0   1   0   1
0   0   0   0   0   0   0   0   1   0   1   0

>> B
B =

0    2    5    0    0    0
1    3    6    0    0    0
0    4    7    0    8   10
0    0    0    0    0   11
0    0    0    0    9   12

Todo va bien. Tenemos nuestra matriz de adyacencia, pasémosla a la función clases:

[p,c] = clases(m_ad)

 

p =

1    3    2    5    6    7    4    8   10   11   12    9

c =

1    8   13

Ahí tenemos nuestros resultados. En p tenemos nuestra lista de vértices permutados del 1 al 12. En c tenemos los cortes. Tenemos 3, así que tenemos 2 componentes conexas, exactamente las que vemos en la matriz. La primera va de 1 a 8-1=7, es decir: 1, 3, 2, 5, 6, 7 y 4. Como vemos en la matriz, es correcto. La segunda va de 8 a 13-1 = 12, es decir: 8, 10, 11, 12 y 9, que como vemos también son los vértices que forman la segunda componente.

Pues esto es todo por hoy. Se que es un algoritmo no muy eficaz para este tipo de blob finding, sin embargo, es muy útil si lo que recibimos son, como he dicho antes, listas de pares de vértices conectados, ya que sacamos la matriz y se la pasamos a “clases”.

Como deberes dejo un par de cosas. La más chunga, pasar este código a C/C++, que me encantaría verlo. La mayoría de cosas no son muy complicadas, pero sí un engorro seguramente tener que pasar un montón de datos por referencia a la función recursiva, y mucha probabilidad de error. Pero nada que no se resuelva con paciencia.

La segunda, corregir un error de nuestro programa en la función pairs. No reconoce vértices sueltos que recorra después del último par de vértices, aunque si los reconoce si hay alguno anterior, ya que crea la matriz sólo con pares. Intenta arreglarlo, tampoco debería ser difícil.

Un saludo a todos y espero que haya gustado. El próximo será mucho más programar y menos abstracto. Se podrá visualizar mejor lo que hacemos.

P.D.: Archivos de fuente subidos aquí: http://neowriter.eshost.es/

Anuncios
Esta entrada fue publicada en Componentes conexas, Manuales, Manuales largos y etiquetada , , , , , , , , , , . Guarda el enlace permanente.

4 respuestas a Componentes conexas de un grafo.

  1. Pingback: Componentes conexas. Introducción e índice. « White-Hat Hacking

  2. Pingback: DUO | White-Hat Hacking

  3. Pingback: Acertijo matemático | White-Hat Hacking

  4. Ana dijo:

    Hola! Podrias por favor decirme como pasar la parte de las componentes conexas a c++? Te lo agradeceria muchisimo, soy nueva en todo esto y lo necesito para una tarea. Gracias!

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s