GIIT_AMA_18_Grafos_Tutorial2

295 days ago by etlopez18

Teoría de Grafos (Tutorial 2)

Representación de grafos

En este tutorial vamos a ver distintas opciones para representar los grafos con Sage. Esto nos permitirá visualizarlos mejor y también familiarizarnos con el modo de trabajar con grafos.

Comencemos con un grafo clásico, el grafo de Petersen (puedes consultar sus propiedades en Wikipedia). Para representar el grafo, podemos usar el comando plot.

P = graphs.PetersenGraph() P.plot() 
       

La representación anterior no permite destacar ninguna propiedad del grafo. Vamos a ir viendo cómo modificar el estilo y la disposición de los vértices del grafo (para obtener todas las opciones, se puede consultar la documentación). En primer lugar, modificaremos el color de los vértices. Para ello se crea un diccionario, un tipo de datos que consiste en un conjunto de parejas, separadas por :. El primer elemento de la pareja se denomina clave y el segundo valor. En el caso de los colores de los vértices de un grafo, la clave será el color y el valor la lista de vértices que se colorean con dicho color. Además, cambiaremos el tamaño de los vértices con vertex_size.

d = {'#FF0000':[0,5], '#FF9900':[1,6], '#FFFF00':[2,7], '#00FF00':[3,8], '#0000FF':[4,9]} P.plot(vertex_colors=d,vertex_size=500) 
       

En el caso de querer cambiar el color de las aristas, funciona del mismo modo. Para ilustrarlo, vamos a tratar de hacer algo más complejo; cambiaremos a color rojo el ciclo exterior. Es decir, todas las aristas cuyos vértices estén en el conjunto {0,1,2,3,4}.

color_aristas={'#FF0000':[ e for e in P.edges() if (e[0] in {0,1,2,3,4}) and (e[1] in {0,1,2,3,4})], '#000000':[ e for e in P.edges() if not(e[0] in {0,1,2,3,4}) or not(e[1] in {0,1,2,3,4})]} color_aristas 
       
P.plot(edge_colors=color_aristas,vertex_colors=d,vertex_size=500) 
       

Además, podemos poner nombres (etiquetas) a las aristas. Para ello, recorremos las aristas y usamos set_edge_label. Para mostrar las etiquetas, usamos la opción edge_labels=true en la función plot. Vamos a marcar las aristas del ciclo exterior como 1,2,3,4,5 y como 0 las del interior.

for e in P.edge_iterator(): # Recorremos las aristas u,v,_=e # Guardamos los valores de los vértices if (u in {0,1,2,3,4}) and (v in {0,1,2,3,4}): if not(min([u,v])==0 and max([u,v])==4): P.set_edge_label(u,v,min([u,v])+1) else: P.set_edge_label(u,v,5) else: P.set_edge_label(e[0],e[1],0) P.plot(edge_colors=color_aristas,vertex_colors=d,vertex_size=500,edge_labels=true) 
       

Además, podemos indicarle que use las etiquetas para colorear el grafo:

P.plot(color_by_label=True,edge_labels=True,vertex_colors=d,vertex_size=500) 
       

Grafo dirigido y/o etiquetado

Todo lo anterior es válido para grafos dirigidos, sin más que cambiar Graph por DiGraph. Por ejemplo, convertimos el grafo de Petersen en un digrafo y aplicamos lo anterior.

P=DiGraph(P) P.plot(vertex_colors=d) 
       

Vamos ahora a cambiar el color de las aristas. En lugar de cambiar todas las aristas exteriores, cambiaremos sólo aquellas que forman un ciclo. Además, no vamos a mostrar los nombres de los vértices (vertex_labels=false).

# Generamos la lista de aristas la=zip([0..4],[1..4]+[0]) la 
       
# Usamos el color rojo para las aristas del ciclo y un gris claro para el resto color_aristas={'#FF0000':[ e for e in P.edges() if (e[0],e[1]) in la], '#AAAAAA':[ e for e in P.edges() if not((e[0],e[1]) in la)]} P.plot(edge_colors=color_aristas,vertex_colors=d,vertex_size=500,vertex_labels=false) 
       

Practica.

1. Representa el grafo de Petersen de modo que los vértices exteriores (del 0 al 4) estén en negro y los interiores en blanco. No representes los nombres de los vértices.

2. Representa en una misma gráfica el grafo de Petersen y su complementario (el grafo compuesto por los mismos vértices y las aristas complementarias). Para ello representa el grafo completo, creando una copia del grafo de Petersen (puedes usar copy o crear otro nuevo con graphs) y añade las aristas que no estén (por ejemplo, recorriendo todas las parejas u,v de vértices del grafo y añadiendo las aristas que no estén). Puedes usar una nueva etiqueta para las aristas que añadas y así simplificas dibujarlas. Dibuja en un color las aristas que no estén en el grafo de Petersen y en otro las que estén.

3. Representa el grafo de Petersen como un digrafo, mostrando en un color todas las aristas menos las que van de los vértices exteriores (0,1,2,3,4) a los interiores (5,6,7,8,9), que se representarán en otro color.

 
       

Ejemplo de creación de grafos a partir de una imagen (OPCIONAL)

Vamos a leer una imagen de un archivo y construir un grafo a partir de ella. La imagen contendrá píxeles blancos en las zonas "por las que podemos pasar" y negros en "las zonas no transitables. El grafo que vamos a construir tendrá un vértice por cada píxel blanco y las aristas unirán los píxes blancos vecinos (tomando como vecinos las cuatro posiciones más próximas - arriba, abajo, izquierda y derecha). La imagen la hemos generado en la hoja Escape del laberinto.

Comenzaremos cargando la imagen y convieriéndola en una matriz. El siguiente código hace eso, aunque su explicación queda fuera de los objetivos de esta asignatura.

# Cargamos una librería para manejar las imágenes import matplotlib.image as mpimg # Cargamos la imagen (está guardada en DATA) img=mpimg.imread(DATA+'lab.png') # Definimos una matriz a partir de la imagen (usaremos el canal r del rgb) M=Matrix(img[:,:,0].copy(order='C')) # Para representar la imagen, utilizaremos matrix_plot GM=matrix_plot(M,frame=false,origin='lower',ymin=0,ymax=M.dimensions()[0]) GM 
       

Vamos a crear el grafo a partir de la matriz. Crearemos una función que reciba la matriz y, opcionalmente, un nivel (nivel) y un ancho mínimo (d). El procedimiento para construir el grafo será el siguiente:

  • Obtenemos las dimensiones de la matriz y creamos un grafo vacío.
  • Recorremos la matriz. Si  el valor es mayor que el nivel, agregamos un vértice al grafo en esa posición. Si en la posición inferior o izquierda el valor es superior al nivel, añadimos la arista correspondiente.
  • Finalmente, colocamos cada vértice en la posición (x,y) correspondiente a su posición en la matriz.
def mapa_a_grafo(M,nivel=0.99,d=1): # Definimos las dimensiones m,n=M.dimensions() # Creamos un grafo vacío g=Graph({}) # Recorremos cada uno de los píxeles de la imagen / valores de la matriz for j in range(1,m-1,d): # para cada fila for i in range(1,n-1,d): # para cada columna # Si es blanco, añadimos vértice en el píxel if M[j,i]>nivel: g.add_vertex((j,i)) # Si hay blanco en la posición superior, los unimos con una arista if j>1 and M[j-d,i]>nivel: g.add_edge([(j-d,i),(j,i)]) # Si hay blanco a la izquierda, los unimos con una arista if i>1 and M[j,i-d]>nivel: g.add_edge([(j,i),(j,i-d)]) # La siguiente línea indica que los vértices se dibujarán en la posición x,y dada por los índices de la matriz g.set_pos({k:(k[1],k[0]) for k in g.vertices()}) return g 
       

Ahora ya podemos utilizar la función y representar el grafo asociado a la imagen.

G=mapa_a_grafo(M) GM+G.plot(vertex_labels=false,vertex_size=30) 
       

Vamos a encontrar un camino entre el vértice (1,1) y el (39,59). La idea es la siguiente:

  1. Partimos el vértice inicial.
  2. Si la posición inmediatamente a la derecha está libre, nos movemos a esa posición y quedamos mirando en la dirección que nos hemos movido.
  3. Si no está libre, giramos hacia la izquierda y comprobamos si la posición que nos queda ahora enfrente está libre.
  4. Repetimos 3 hasta que la posición que quede enfrente esté libre.
  5. Si no hemos llegado al vértice final, volvemos a 2.

Este proceso se denomina "backtracking" o "recorrido en profundidad".

def pos_sig(pos,direccion): # Función que recibe una posición (dos coordenadas) y una dirección (1 número del 0 al 3) # y devuelve el resultado de "moverse" en esa dirección return (pos[0]+direccion[0],pos[1]+direccion[1]) def camino(g,v_inicial,v_final): # Función que recibe un grafo (con vértices pares de puntos y aristas uniendo puntos "vecinos") y # un vértice inicial y otro final y devuelve un camino entre los vértices. # Establecemos la posición y dirección iniciales, la meta y las direcciones en las que "nos movemos" pos=v_inicial; direccion=0; meta=v_final; direcciones=[(1,0),(0,1),(-1,0),(0,-1)] # Guardaremos las posiciones que visitamos en una lista y un contador para no quedarnos en un bucle infinito posiciones=[pos] contador=0 while pos[0]!=meta[0] or pos[1]!=meta[1]: # Hasta llegar al final direccion=(direccion+1)%4 # Giramos a la derecha while not(g.has_edge(pos,pos_sig(pos,direcciones[direccion]))): direccion=(direccion-1)%4 # Giramos a la izquierda # Como delante está libre, avanzamos pos=pos_sig(pos,direcciones[direccion]) # Si la posición a la que llegamos ya la habíamos visitado, la borramos del camino if len(posiciones)>1 and posiciones[-2][0]==pos[0] and posiciones[-2][1]==pos[1]: posiciones.pop() else: posiciones+=[pos] contador+=1 if contador>10000 or (pos[0]==1 and pos[1]==1 and direccion==0): # Si no llegamos a ninguna parte print u'¡No encuentro el camino!' return -1 return posiciones 
       
# Marcamos el camino en azul G=mapa_a_grafo(M) GM+G.plot(vertex_labels=false,vertex_size=30,vertex_colors={(0,0,1):camino(G,(1,1),(39,59))}) 
       

Practica

1. Encuentra una camino entre la posición (1,1) y la (39,1)

2. Prueba a eliminar el "backtraking" de la función. Es decir, elimina la parte que borra vértices de la lista de vértices visitamos. ¿Qué sucede?

3. Modifica la función que crea el grafo a partir de la imagen para que también considere los vecinos "en diagonal".

4. Calcula la secuencia de grados del laberinto y usa la función creada en la primera práctica para ver si es conexo. A partir de esa información, ¿es un árbol?