¡Recomienda este blog!

martes, 30 de noviembre de 2010

Estructura de los datos: Grafos en Haskell

Introducción

Terminología.

1. Se dice que G es completo si A = V x V, esto es, si todas las aristas
posibles pertenecen a A.

2. Se dice que G es no dirigido si
∀ v1, v2 ∈ V : (v1, v2) ∈ A ⇒ (v2, v1) ∈ A

3. Se dice que dos vértices v1, v2 ∈ V son adyacentes o vecinos si
existe una arista a ∈ A conectándolos. Si el grafo es dirigido y
(v1, v2) ∈ A , decimos que v1 es adyacente a v2 y v2 es adyacente
desde v1.

4. Una secuencia de vértices v1, ..., vm ,decimos que es un camino si
∀ i ∈ {1, . . .,m-1}, (vi, vi+1) ∈ A.

5. Se dice que un camino es simple si cada vértice sólo aparece una
vez en la secuencia.

6. Se dice que v1, v2 ∈ V están conectados si existe un camino en
G de v1 a v2.

7. Un grafo no dirigido es conexo si para cada par de vértices
distintos vi, vj existe un camino que los conecta.

8. Un grafo dirigido es fuertemente conexo si para cada par de
vértices distintos, vi , vj existe un camino de vi a vj.

9. Un ciclo es un camino para el que los vértices inicial y final
coinciden, y los vértices intermedios solo aparecen una vez en
la secuencia.

10. Un grafo es acíclico si no contiene ciclos.

Especificación algebraica.


Definición formal (Haskell) de grafo no dirigido.

Podemos dar varias definiciones formales de grafo ( aunque usaremos la 1º para nuestros ejemplos ):

-- 1. Similar a Conjunto:
data Grafo a = GVacio | Nodo a (Grafo a) | Arco a a (Grafo a)
g1 :: Grafo Int
g1 = Arco 1 3 (Arco 1 2 (Arco 2 3 (Nodo 4 (Nodo 3 (Nodo 2 (Nodo 1 GVacio))))))

-- 2. Par nodos + aristas como pares:
data Grafo2 a = G2 [a] [(a, a)]
g2 :: Grafo2 Int
g2 = G2 [1,2,3,4] [(1,3), (1,2), (2,3)]

-- 3. Par nodos + aristas como operación sucesor:
data Grafo3 a = G3 [a] (a -> [a])
g3 :: Grafo3 Int
suc :: Int -> [Int]
suc 1 = [2,3]; suc 2 = [1,3]; suc 3 = [1,2]; suc _ = []
g3 = G3 [1,2,3,4] suc

Las operaciones generadoras no son libres (en ningún caso).

-- Axiomas de equivalencia para la 1ª forma:

-- los extremos de un arco deben existir, y pueden estar en cualquier orden:
Arco n m g = if existe n g && existe m g
then Arco m n g
else GVacio -- o un dato Error definido en data, o error “no existe extremo”


-- los nodos o arcos repetidos no hacen diferente a un grafo:
Nodo m (Nodo n g) = if (n == m)
then Nodo n g
else Nodo n (Nodo m g) -- pueden intercambiarse las posiciones
Arco n’ m’ (Arco n m g) = if (n == n’ && m == m’) or (n == m’ && m == n’)
then Arco n m g
else Arco n m (Arco n’ m’ g) -- pueden intercambiarse las posiciones


-- podemos suponer todo Nodo mas interno (anterior) que todo Arco:
Nodo n’ (Arco n m g) = Arco n m (Nodo n’ g)

Operaciones básicas según la forma 1

-- Suponemos grafos en forma normal (sin repeticiones, no errores, y arcos antes que nodos).
-- Para cualquier operación op puede implementarse otra op0 que obtiene previamente la forma normal del grafo:
op0 … grafo … = op … (fn grafo) …

fn :: (Eq a) => Grafo a -> Grafo a -- forma normal de un grafo:
fn g = let gre = reordena g in -- parte Nodo dentro de parte Arista
if aristasok gre -- los nodos de las aristas estan en el grafo
then quitarrepes gre -- quita aristas y nodos repetidos
else GVacio

reordena :: Grafo a -> Grafo a
reordena g = aux g GVacio

aux :: Grafo a -> Grafo a -> Grafo a -- acumula nodos en el 2º parámetro
aux (Nodo n g) h = aux g (Nodo n h)
aux (Arco x y g) h = Arco x y (aux g h)
aux GVacio h = h

aristasok :: (Eq a) => Grafo a -> Bool
aristasok (Arco x y g) = (esta x g) && (esta y g) && (aristasok g)
aristasok _ = True

quitarrepes :: (Eq a) => Grafo a -> Grafo a
quitarrepes GVacio = GVacio
quitarrepes (Nodo x g) = if esta x g then quitarrepes g else Nodo x (quitarrepes g)
quitarrepes (Arco x y g) = if adyacentes x y g then quitarrepes g else Arco x y (quitarrepes g)

-- Otras funciones implementadas.

esta :: (Eq a) => a -> Grafo a -> Bool
esta _ GVacio = False
esta x (Nodo y g) = x==y || esta x g
esta x (Arco _ _ g) = esta x g -- sólo mira en los nodos

􀂄 adyacentes :: (Eq a) => a -> a -> Grafo a -> Bool
adyacentes x y (Arco u v g) = x==u && y==v || x==v && y==u || adyacentes x y g
adyacentes _ _ _ = False

􀂄 gvacio :: Grafo a -> Bool
gvacio GVacio = True
gvacio _ = False

􀂄 borranodo :: (Eq a) => a -> Grafo a -> Grafo a
borranodo _ GVacio = GVacio
borranodo n (Arco x y g) = if n==x || n==y then borranodo n g else Arco x y (borranodo n g)
borranodo n (Nodo x g) = if n==x then g else Nodo x (borranodo n g)

􀂄 borraarco :: (Eq a) => a -> a -> Grafo a -> Grafo a
borraarco x y (Arco u v g) = if x==u && y==v || x==v && y==u
then g else Arco u v (borraarco x y g)
borraarco _ _ g = g

􀂄 sucesores :: (Eq a) => a -> Grafo a -> [a]
sucesores x (Arco y z g) | (x==y) = z : sucesores x g
| (x==z) = y : sucesores x g
| True = sucesores x g
sucesores _ _ = []

Ejemplo que nos pude caer en un examen: Especificar en Haskell la operación:

mas :: Grafo a -> a -> Grafo a


que a partir de un grafo en forma normal, le añade un nuevo nodo y todos los arcos necesarios para conectar este nodo con todos los demás. La salida debe darse en forma normal, sin hacer uso de la operación fn.

Por ejemplo, si tenemos el grafo:

g1 = Arco 1 3 (Arco 1 2 (Arco 2 3 (Nodo 4 (Nodo 3 (Nodo 2 (Nodo 1 GVacio))))))

entonces, al evaluar mas g1 5 obtendremos:

Arco 5 4 (Arco 5 3 (Arco 5 2 (Arco 5 1 (Arco 1 3 (Arco 1 2 (Arco 2 3 (Nodo 5 (Nodo 4 (Nodo 3 (Nodo 2 (Nodo 1 GVacio)))))))))))

(salvo el orden en los arcos y los nodos).

-- Solución.

mas :: Grafo a -> a -> Grafo a
mas g n = auxMas (listaNodos g ) g n

auxMas :: [a] -> Grafo a -> a -> Grafo a
auxMas (x:xs) g n = Arco n x (auxMas xs g n)
auxMas [] (Arco x y g) n = Arco x y (auxMas [] g n)
auxMas x g n = Nodo n g

listaNodos :: Grafo a -> [a]
listaNodos (Arco _ _ g) = listaNodos g
listaNodos ( Nodo x GVacio ) = x:[]
listaNodos ( Nodo x g ) = x:listaNodos g

0 comentarios:

Publicar un comentario