Grafos y algoritmos de búsquedas

En las páginas previas de Árboles y Árboles Binarios ya estuvimos trabajando con algoritmos de búsqueda. Vimos profundidad primero y ancho primero para buscar elementos dentro de una estructura de árbol. En esta página vamos a entrar en más detalles sobre los algoritmos de búsqueda.

Grafos

Un grafo es una estructura que tiene nodos interrelacionados. En los nodos generalmente se guarda información. Los árboles que ya vimos son en efecto un tipo particular de grafos en los cuales no se producen ciclos. Por ejemplo, un grafo que conecta distintas ciudades. En este caso cara arista representa una ruta entre ambas ciudades. La ruta la consideramos como "bidireccional", pero hay variantes de grafos en la que la relación es unidireccional (a esos grafos se los denomina dígrafo).

Implementación del TDA grafo en python

Son muchas las formas de modelar un grafo, se puede pensar en nodos enlazados al estilo de los árboles que ya vimos. Como un grafo no tiene raíz, vamos a querer consultarlo a partir de cualquier elemento. Por eso nuestra implementación la vamos a realizar un diccionario que nos relacione un elemento con sus vecinos.

class Grafo(object):

    def __init__(self):

        self.relaciones = {}

    def __str__(self):

        return str(self.relaciones)

def agregar(grafo, elemento):

    grafo.relaciones.update({elemento:[]})

def relacionar(grafo, elemento1, elemento2):

    relacionarUnilateral(grafo, elemento1, elemento2)

    relacionarUnilateral(grafo, elemento2, elemento1)

def relacionarUnilateral(grafo, origen, destino):

    grafo.relaciones[origen].append(destino)

Y el ejemplo de como construirlo:

buenosAires = "BuenosAires"

sanPedro = "San Pedro"

rosario = "Rosario"

cordoba = "Cordoba"

villaMaria = "Villa Maria"

sanLuis = "San Luis"

mendoza = "Mendoza"

bahiaBlancha = "Bahia Blanca"

grafo = Grafo()

agregar(grafo, buenosAires)

agregar(grafo, sanLuis)

agregar(grafo, sanPedro)

agregar(grafo, rosario)

agregar(grafo, cordoba)

agregar(grafo, villaMaria)

agregar(grafo, bahiaBlanca)

agregar(grafo, mendoza)

relacionar(grafo, buenosAires, sanPedro)

relacionar(grafo, buenosAires, sanLuis)

relacionar(grafo, buenosAires, bahiaBlanca)

relacionar(grafo, buenosAires, sanLuis)

relacionar(grafo, sanLuis, mendoza)

relacionar(grafo, sanLuis, villaMaria)

relacionar(grafo, sanLuis, bahiaBlanca)

relacionar(grafo, villaMaria, cordoba)

relacionar(grafo, villaMaria, rosario)

relacionar(grafo, rosario, sanPedro)

Recorridos

Los conceptos de profundidad primero y ancho primero también son aplicables a los grafos, pero necesitamos hacer cierta modificación para eliminar los ciclos. La manera de detectar ciclos es tener cierta memoria sobre los nodos que ya hemos visitado, para evitar recorrer el camino que ya recorrimos.

Profundidad Primero

Modificamos el algoritmo que teníamos para árboles, para utiizar una semilla que nos permite saber si un nodo fue visitado o no

def profundidadPrimero(grafo, elementoInicial, funcion, elementosRecorridos = []):

    if elementoInicial in elementosRecorridos:

        return

    funcion(elementoInicial)

    elementosRecorridos.append(elementoInicial)

    for vecino in grafo.relaciones[elementoInicial]:

        profundidadPrimero(grafo, vecino, funcion, elementosRecorridos)

Lo probamos con:

def imprimir (elemento):

    print elemento

profundidadPrimero(grafo, buenosAires, imprimir)

La salida es:

BuenosAires

San Pedro

Rosario

Villa Maria

San Luis

Mendoza

Bahia Blanca

Cordoba

Esto es equivalente a recorrer el árbol que se formaría de eliminar las aristas que forman ciclos:

Ancho primero

De manera similar, podemos modificar el algoritmo de ancho primero para detectar los ciclos

def anchoPrimero(grafo, elementoInicial, funcion, cola = deque(), elementosRecorridos = []):

    if not elementoInicial in elementosRecorridos:

        funcion(elementoInicial)

        elementosRecorridos.append(elementoInicial)

        if(len(grafo.relaciones[elementoInicial]) > 0):

            cola.extend(grafo.relaciones[elementoInicial])

    if len(cola) != 0 :

        anchoPrimero(grafo, cola.popleft(), funcion, cola, elementosRecorridos)

En este caso la salida para

anchoPrimero(grafo, buenosAires, imprimir)

es:

BuenosAires

San Pedro

San Luis

Bahia Blanca

Rosario

Mendoza

Villa Maria

Cordoba

Y para visualizar el árbol subyacente, nos permitimos reordenar la ubicación visual de cada nodo para visualizar que las relaciones que se eliminan son las que unen elementos del primer nivel:

Caminos y Pesos

Un camino es una sucesión de nodos que se puede recorrer siguiendo las aristas de los grafos. Por ejemplo, si quiero ir de Buenos Aires a Villa María puedo ir de por 3 caminos:

Camino 1: Buenos Aires, San Pedro, Rosario, Villa María
Camino 2: Buenos Aires, San Luis, Villa María
Camino 3: Buenos Aires, Bahia Blanca, San Luis, Villa María.

Si contamos la cantidad de pasos, el primer camino tiene 3 pasos, el segundo tiene 2 pasos y el tercero 3 pasos.

Sin embargo, el criterio de contar pasos no parece ser útil si quiero conocer el camino mínimo para viajar de Buenos Aires a Villa María. Para resolver ese problema nos falta agregar la cantidad de km que hay entre cada ciudad. Este valor, que es la distancia en km en nuestro caso concreto, lo vamos a generalizar con el nombre de peso para cualquier grafo y representa el costo de transicionar por una arista.

Ahora, para cada camino, la distancia sería:

Camino 1: Buenos Aires, San Pedro, Rosario, Villa María = 175 + 160 + 245 = 575
Camino 2: Buenos Aires, San Luis, Villa María = 790 + 350 = 1140
Camino 3: Buenos Aires, Bahia Blanca, San Luis, Villa María = 660 + 800 + 260 = 1720

Los grafos que no tienen pesos pueden ser vistos como grafos cuyos pesos tienen el valor de 1, de esa manera el costo de un camino es la suma de pasos.

Implementación en python

Vamos a modificar nuestro TDA para que soporte la idea de pesos.

class Grafo(object):

    def __init__(self):

        self.relaciones = {}

    def __str__(self):

        return str(self.relaciones)

class Arista(object):

    def __init__(self, elemento, peso):

        self.elemento = elemento

        self.peso = peso

    def __str__(self):

        return str(self.elemento) + str(self.peso)

def agregar(grafo, elemento):

    grafo.relaciones.update({elemento:[]})

def relacionar(grafo, elemento1, elemento2, peso = 1):

    relacionarUnilateral(grafo, elemento1, elemento2, peso)

    relacionarUnilateral(grafo, elemento2, elemento1, peso)

def relacionarUnilateral(grafo, origen, destino, peso):

    grafo.relaciones[origen].append(Arista(destino, peso))

Cálculo del costo del camino mínimo (Algoritmo de Dijkstra)

El algoritmo de Dijkstra es utilizado para calcular los costos mínimos de los caminos. Podemos encontrar una descripción detallada aqui.y un tutorial en forma de video aqui

La idea del algoritmo es ir recorriendo el grafo etiquetando cada nodo. La etiqueta de un nodo esta compuesto por la distancia acumulada hasta ese nodo y el nodo anterior.

Etiqueta(nodo) = (Peso_Acumulado, NodoAnterior)

El algoritmo genera la etiqueta del primer elemento usando 0 como acumulado y None como nodo anterior. y luego procede recursivamente:
Elije el nodo etiquetado con menor valor y que no esté marcado como "procesado".
Se generan las etiquetas de los nodos vecinos.
Si algun nodo vecino ya estaba etiquetado, se queda con la etiqueta que tenga menor valor acumulado y descarta la otra.
Se marca el nodo actual como "procesado"

El algoritmo termina cuando el nodo destino es marcado como permanente. El valor del acumulado en la etiqueta es el costo del camino, y siguiendo el valor anterior se puede obtener el camino.

Implementación en python

Estas son las funciones principales:

def caminoMinimo(grafo, origen, destino):

    etiquetas = {origen:(0,None)}

    dijkstra(grafo, destino, etiquetas, [])

    return construirCamino(etiquetas, origen, destino)

def construirCamino(etiquetas, origen, destino):

    print origen, destino

    if origen == destino:

        return [origen]

    return construirCamino(etiquetas, origen, anterior(etiquetas[destino])) + [destino]

def dijkstra(grafo, destino, etiquetas, procesados):

    nodoActual = menorValorNoProcesado(etiquetas, procesados)

    if nodoActual == destino:

        return

    procesados.append(nodoActual)

    for vecino in vecinoNoProcesado(grafo, nodoActual, procesados):

        generarEtiqueta(grafo, vecino, nodoActual, etiquetas)

    dijkstra(grafo, destino, etiquetas, procesados)

def generarEtiqueta(grafo, nodo, anterior, etiquetas):

    etiquetaNodoAnterior = etiquetas[anterior]

    etiquetaPropuesta = peso(grafo, anterior, nodo) + acumulado(etiquetaNodoAnterior),anterior

    if (not(etiquetas.has_key(nodo)) or  acumulado(etiquetaPropuesta) < acumulado(etiquetas[nodo]) ):

        etiquetas.update({nodo:etiquetaPropuesta})

Y estas son las funciones auxiliares:

def aristas(grafo, nodo):

    return grafo.relaciones[nodo]

def vecinoNoProcesado(grafo, nodo, procesados):

    aristasDeVecinosNoProcesados = filter(lambda x: not x in procesados, aristas(grafo,nodo))

    return [arista.elemento for arista in aristasDeVecinosNoProcesados]

def peso(grafo, nodoOrigen, nodoDestino):

    return reduce(lambda x,y: x if x.elemento == nodoDestino else y, grafo.relaciones[nodoOrigen]).peso

def acumulado(etiqueta):

    return etiqueta[0]

def anterior(etiqueta):

    return etiqueta[1]

def menorValorNoProcesado(etiquetas, procesados):

    etiquetadosSinProcesar = filter(lambda (nodo,_):not nodo in procesados, etiquetas.iteritems())

    return min(etiquetadosSinProcesar, key=lambda (_, (acum, __)): acum)[0]

Estos son los distintos pasos por los que pasa el algoritmo para calcular el mejor camino entre Buenos Aires y Villa Maria

En rojo marcamos los nodos ya procesados para mejor visualización
En negrita se marca el menor acumulado que determina el nodo a procesar
En azul se marcan los cambios con respecto a la iteración anterior.

-----------------------------

nodoActual: BuenosAires

procesados []

etiquetas {'BuenosAires': (0, None)}

-----------------------------

nodoActual: San Pedro

procesados ['BuenosAires']

etiquetas { 'Bahia Blanca': (660, 'BuenosAires'),

'BuenosAires': (0, None),

'San Luis': (790, 'BuenosAires'),

'San Pedro': (175, 'BuenosAires')}

-----------------------------

nodoActual: Rosario

procesados ['BuenosAires', 'San Pedro']

etiquetas { 'Bahia Blanca': (660, 'BuenosAires'),

'BuenosAires': (0, None),

'San Luis': (790, 'BuenosAires'),

'San Pedro': (175, 'BuenosAires'),

'Rosario': (335, 'San Pedro')}

-----------------------------

nodoActual: Villa Maria

procesados ['BuenosAires', 'San Pedro', 'Rosario']

etiquetas {'Villa Maria': (580, 'Rosario'),

'San Luis': (790, 'BuenosAires'),

'San Pedro': (175, 'BuenosAires'),

'Bahia Blanca': (660, 'BuenosAires'),

'BuenosAires': (0, None),

'Rosario': (335, 'San Pedro')}

Otro ejemplo de camino mínimo con Dijkstra

En el siguiente grafo (tomado del video tutorial) vamos a calcular el camino entre E y A (es distinto al ejemplo del tutorial).

Vamos a programar el grafo y ejecutar el pedido:

a = "a"

b = "b"

c = "c"

d = "d"

e = "e"

f = "f"

g = "g"

h = "h"

grafo = Grafo()

agregar(grafo, a)

agregar(grafo, b)

agregar(grafo, c)

agregar(grafo, d)

agregar(grafo, e)

agregar(grafo, f)

agregar(grafo, g)

agregar(grafo, h)

relacionar(grafo, a, c, 1)

relacionar(grafo, a, b, 3)

relacionar(grafo, b, d, 1)

relacionar(grafo, b, g, 5)

relacionar(grafo, c, f, 5)

relacionar(grafo, c, d, 2)

relacionar(grafo, d, f, 2)

relacionar(grafo, d, e, 4)

relacionar(grafo, e, h, 1)

relacionar(grafo, e, g, 2)

relacionar(grafo, f, h, 3)

print caminoMinimo(grafo, e, a)

La salida es:

['e', 'd', 'c', 'a']

Analicemos paso a paso con la misma convención que usamos en el ejemplo anterior:

En rojo marcamos los nodos ya procesados
En negrita se marca el menor acumulado que determina el nodo a procesar
En azul se marcan los cambios con respecto a la iteración anterior.

-----------------------------

Nodo Actual: e

Procesados []

Etiquetas {'e': (0, None)}

-----------------------------

Nodo Actual: h

Procesados ['e']

Etiquetas {'h': (1, 'e'),

'e': (0, None),

'd': (4, 'e'),

'g': (2, 'e')}

-----------------------------

Nodo Actual: g

Procesados ['e', 'h']

Etiquetas {'h': (1, 'e'),

'e': (0, None),

'd': (4, 'e'),

'g': (2, 'e'),

'f': (4, 'h')}

-----------------------------

Nodo Actual: d

Procesados ['e', 'h', 'g']

Etiquetas {'b': (7, 'g'),

'e': (0, None),

'd': (4, 'e'),

'g': (2, 'e'),

'f': (4, 'h'),

'h': (1, 'e')}

-----------------------------

Nodo Actual: f

Procesados ['e', 'h', 'g', 'd']

Etiquetas {'c': (6, 'd'),

'b': (5, 'd'),

'e': (0, None),

'd': (4, 'e'),

'g': (2, 'e'),

'f': (4, 'h'),

'h': (1, 'e')}

-----------------------------

Nodo Actual: b

Procesados ['e', 'h', 'g', 'd', 'f']

Etiquetas {'c': (6, 'd'),

'b': (5, 'd'),

'e': (0, None),

'd': (4, 'e'),

'g': (2, 'e'),

'f': (4, 'h'),

'h': (1, 'e')}

-----------------------------

Nodo Actual: c

Procesados ['e', 'h', 'g', 'd', 'f', 'b']

Etiquetas {'a': (8, 'b'),

'c': (6, 'd'),

'b': (5, 'd'),

'e': (0, None),

'd': (4, 'e'),

'g': (2, 'e'),

'f': (4, 'h'),

'h': (1, 'e')}

-----------------------------

Nodo Actual: a

Procesados ['e', 'h', 'g', 'd', 'f', 'b', 'c']

Etiquetas {'a': (7, 'c'),

'c': (6, 'd'),

'b': (5, 'd'),

'e': (0, None),

'd': (4, 'e'),

'g': (2, 'e'),

'f': (4, 'h'),

'h': (1, 'e')}

Código Fuente

grafos.py
grafosMain.py
grafosConPesos.py
grafosConPesosMain.py (nodos ciudades)
grafosConPesosMain2.py (nodos letras)