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