GIIT_AMA_1718_T2_Tutorial 3

517 days ago by GIIT_AMA_1718

Tutorial 3

Generadores de grafos

Sage nos permite generar los grafos de modo exhaustivo, por ejemplo, para comprobar conjeturas u obtener ejemplos. Para ello tenemos la función graphs que recibe el número de vértices y devuelve la lista de grafos (salvo isomorfismos) con ese número de vértices.

# Todos los grafos con tres vértices (salvo isomorfismos) L=[] for G in graphs(3): L.append(G) graphs_list.show_graphs(L) 
       

Hay que tener en cuenta que el número de grafos posibles crece a gran velocidad, así que sólo podremos probar con un número pequeño de vértices y aristas.

# Contamos los grafos con 2, 3, 4, ... 7 vértices for i in [2..7]: print len([g for g in graphs(i)]) 
       

También se puede restringir la lista a los grafos con un determinado número de aristas, usando la opción size.

# Todos los grafos con 5 vértices y 7 aristas L=[] for g in graphs(5, size=7): L.append(g) graphs_list.show_graphs(L) 
       

Practica

1. Crea una función que reciba un grafo y devuelva su secuencia de grados.

2. Genera todos los grafos 4 regulares de 7 vértices.

3. Genera todos los grafos regulares de 7 vértices. Trata de optimizar el código para que tarde poco tiempo.

 
       

Ejemplo de creación de grafos a partir de una imagen

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?

 
       

Grafo de una función recursiva (opcional)

Si tenemos una función recursiva, podemos considerar el grafo cuyos vértices son cada uno de los conjuntos de parámetros para los que se ha llamado la función y tenemos una arista que va desde un vértice v a otro w si la función con parámetro v llama a w.

El siguiente "decorador" crea el grafo de llamadas de  una función recursiva.

def grafo_llamadas(f): class G(object): def __init__(self, f): self.f=f self.stack = [] self.g = DiGraph() def __call__(self, *args, **kwds): if self.stack: sargs = ','.join(str(a) for a in args) last = ','.join(str(a) for a in self.stack[-1]) if self.g.has_edge(last, sargs): l = self.g.edge_label(last, sargs) self.g.set_edge_label(last, sargs, l + 1) else: self.g.add_edge(last, sargs, 1) else: self.g = DiGraph() self.stack.append(args) v = self.f(*args) self.stack.pop() return v def grafo(self): return self.g return G(f) 
       

Para usar el decorador, debemos escribir @grafo_llamadas en la celda en la que definamos la función.

@grafo_llamadas def fibo(n): if n<=2: return 1 else: return fibo(n-1) + fibo(n-2) 
       

El decorador nos generará el grafo de llamadas cada vez que ejecutemos la función. Las etiquetas de las aristas indican cuantas veces se ha pasado por esa arista en la llamada.

fibo(6) g = fibo.grafo() g.show(edge_labels=True) 
       
fibo(7) g = fibo.grafo() g.show(edge_labels=True) 
       

El decorador @cached_function hace que una función recursiva vaya guardando los valores que calcula.

@grafo_llamadas @cached_function def fibo_cached(n): if n<=2: return 1 else: return fibo_cached(n-1) + fibo_cached(n-2) 
       
fibo_cached(6) g = fibo_cached.grafo() g.show(edge_labels=True) 
       

Veamos un segundo ejemplo con las particiones de un número (una partición de un número natural n es una sucesión de números k1, ..., kr tal que n=k1+k2+...+kr).

@grafo_llamadas def particiones(n, k): if k == n: return [[1]*n] if k == 1: return [[n]] if not(0 < k < n): return [] ls1 = [p+[1] for p in particiones(n-1, k-1)] ls2 = [[parte+1 for parte in p] for p in particiones(n-k, k)] return ls1 + ls2 
       
particiones(8,3) g = particiones.grafo() g.show(edge_labels=True, figsize=(8,8), vertex_size=500) 
       
particiones(10,4) g = particiones.grafo() g.show(edge_labels=True, figsize=(8,8), vertex_size=500)