LUA / Graficos

Bienvenidos sean a este post, como cualquier lenguaje razonable se nos permite multiple implementaciones para graficos cada uno mejor adaptado para cada algortimo, a continuacion veremos una simple implementacion orientada a objetos donde representamos nodos como objetos (en realidad son tablas) y arcos como referencias entre nodos, representaremos cada nodo como una tabla con dos campos:

• nombre, con el nombre del nodo
• ady, el conjunto de nodos adyacentes a este

Debido a que leeremos el grafico desde un archivo de texto necesitaremos una manera de encontrar un nodo dado su nombre, asi que deberemos usar una tabla extra para el mapeo de nombres y nodos, pasando un nombre la funcion nombreAnodo devuelve el correspondiente nodo:

local function nombreAnodo(grafico, nombre)
	if not grafico[nombre] then
		grafico[nombre] = { nombre = nombre, ady = {} }
	end
	return grafico[nombre]
end

En este caso pasaremos dos valores, uno llamado grafico y otro nombre donde primero chequearemos si no existe el nombre solicitado y en este caso procede a crear uno nuevo con este nombre y sus adyacentes (ady), en caso de existir ignora este condicional y lo devuelve, veamos el siguiente codigo:

function leerGrafico()
	local grafico = {}
	for linea in io.lines() do
		local nombredesde, nombrea = string.match(linea, "(%S+)%s+(%S+)")
		local desde = nombreAnodo(grafico, nombredesde)
		local hacia = nombreAnodo(grafico, nombrea)
		desde.ady[hacia] = true
	end
	return grafico
end

Esta funcion sera la encargada de construir un grafico, lee un archivo donde cada linea tiene dos nombres de nodos, esto significa que hay un arco desde el primer nodo al segundo, por cada linea usa string.match para separar la linea en dos nombres, encuentra el nodo correspondiente para estos nombres (creando los nodos si es necesario) y conecta los mismos, veamos el siguiente codigo:

function encontrarcamino(actual, hacia, camino, visitado)
	camino = camino or {}
	visitado = visitado or {}
	if visitado[actual] then
		return nil
	end
	
	visitado[actual] = true
	camino[#camino + 1] = actual
	if actual == hacia then
		return camino
	end
	
	for nodo in pairs(actual.ady) do
		local c = encontrarcamino(nodo, hacia, camino, visitado)
		if c then return c end
	end

	camino[#camino] = nil
end

Este codigo ilustra un algoritmo usando tales graficos, la funcion encontrarcamino busca por un camino entre los dos nodos usando una transversal de primera profundidad, su primer parametro es el nodo actual, el segundo es su meta, el tercero mantiene el camino desde el origen al nodo actual y el ultimo es un conjunto con todos los nodos visitados (para evitar bucles), podemos observar como el algoritmo manipula nodos sin usar sus nombres directamente, como dijimos visitado es un conjunto de nodos no de nombres de nodos y de forma similar camino es una lista de nodos, para verificar este codigo agregamos una funcion que imprima un camino y un codigo para ponerlos a todos a trabajar:

function imprimircamino(camino)
	for i=1, #camino do
		print(camino[i], nombre)
	end
end

g = leerGrafico()
a = nombreAnodo(g, "a")
b = nombreAnodo(g, "b")
c = encontrarcamino(a, b)
if c then imprimircamino(p) end

En este caso primero creamos la funcion imprimircamino a la cual le pasaremos el dato camino, esta usara un bucle for que imprimira el nodo y el nombre almacenado en camino, despues crearemos un objeto llamado g al cual le pasaremos a leerGrafico para que lea el archivo donde esta la informacion, nuestro siguiente paso sera crear otro objeto llamado a donde usaremos nombreAnodo y lo rescatara o lo asignara, el siguiente objeto hara exactamente lo mismo pero se llama b, una vez que tienen la informacion requerida llamamos a encontrarcamino y le enviamos los valores de a y b, y esto lo almacenamos en un objeto llamado c, por ultimo el condicional verifica que exista algo en c y si es verdad llama a imprimircamino pasando a c para proceder con el grafico.

En resumen, hoy hemos visto como se puede trabajar con graficos en Lua, su sintaxis, las herramientas necesarias, unos codigos de ejemplo para sus algoritmos, y una implementacion basica, espero les haya sido util sigueme en Twitter o Facebook para recibir una notificacion cada vez que subo un nuevo post en este blog, nos vemos en el proximo post.