Klajskdljalk

Grafos
Lic. Wilber Ramos Lovón

Grafos en Haskell

• Tenemos al igual que en los arrays la posibilidad
de representar grafos en Haskell de dos formas:
• Representación de grafos conociendolos
sucesores.
• Representación de un grafo como una instancia
de una clase.

Representación de grafos conociendo
los sucesores:
• data Grafo a = G [a] (a->[a])
•

vértices

funciones querepresenta aristas

• g :: Grafo Int
• g = G[1,2,3,4,5,6] suc
• Where
•
•
•
•

suc 1 = [2,3]
suc 2 = [4]
suc 3 = [4]
suc _ = []

El ejemplo que a continuación se propone calcula elsucesor de un nodo en el grafo propuesto
anteriormente:

• sucesor :: Int-> (Grafo Int) -> [Int]
• sucesor x (G(h:hs) suc)
• | x == h = suc x
• | otherwise = sucesor x (G hs suc)

Podemostambién crear grafos en los cuales
introducir un valor (peso ) a cada arista.
• data GrafoP a p = GP [a] (a->[(a,p)])
•

Tipo de los vértices

Peso de aristas entre cada nodo

• De esta formaquedan totalmente definidos tanto los
vértices, los sucesores y los pesos de las aristas .

Representación en Haskell:
• gp :: GrafoP Int Int
• gp = GP [1,2,3,4,5] suc
• where
•
•
•
•suc 1 = [(2,5),(3,8)]
suc 2 = [(4,2)]
suc 3 = [(4,1)]
suc _ = []

Haskell da la posibilidad de representación
de grafos utilizando las clases.
• Definiremos una clase con dos funcionesesenciales: vértices y sucesor.
class (Eq a) => Grafo a
where
vertices :: [a]; devuelve los vértices de un grafo.
sucesor :: a -> [a]; devuelve los vértices
sucesores

• La representaciónanteriormente expuesta:
class (Eq a) => Grafo a
• La interpretación que se le da es que el tipo
de Grafo definido como a tiene que ser el
mismo que el definido en Eq para que se
puedan comparar loselementos.
• También podríamos interpretar la definición
de Grafo como una subclase de Eq.

• A continuación definiremos una serie de
métodos para resolver problemas de
búsquedas de caminos.
(...