I1M2012: El TAD de los grafos y su implementación en Haskell mediante vectores de adyacencia
En la clase de hoy de Informática de 1º del Grado en Matemáticas hemos estudiado el tipo abstracto de los grafos y su implementación en Haskell mediante vectores de adyacencia.
Las transparencias usadas en la clase son las páginas 1-18 del tema 22:
El código correspondiente es
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 |
module GrafoConVectorDeAdyacencia (Orientacion (..), Grafo, creaGrafo, -- (Ix v,Num p) => Orientacion -> (v,v) -> [(v,v,p)] -> -- Grafo v p dirigido, -- (Ix v,Num p) => (Grafo v p) -> Bool adyacentes, -- (Ix v,Num p) => (Grafo v p) -> v -> [v] nodos, -- (Ix v,Num p) => (Grafo v p) -> [v] aristas, -- (Ix v,Num p) => (Grafo v p) -> [(v,v,p)] aristaEn, -- (Ix v,Num p) => (Grafo v p) -> (v,v) -> Bool peso -- (Ix v,Num p) => v -> v -> (Grafo v p) -> p ) where -- --------------------------------------------------------------------- -- Librerías auxiliares -- -- --------------------------------------------------------------------- import Data.Array -- Orientacion es D (dirigida) ó ND (no dirigida). data Orientacion = D | ND deriving (Eq, Show) -- (Grafo v p) es un grafo con vértices de tipo v y pesos de tipo p. data Grafo v p = G Orientacion (Array v [(v,p)]) deriving (Eq, Show) -- (creaGrafo o cs as) es un grafo (dirigido o no, según el valor de o), -- con el par de cotas cs y listas de aristas as (cada arista es un trío -- formado por los dos vértices y su peso). Ver el ejemplo a continuación. creaGrafo :: (Ix v, Num p) => Orientacion -> (v,v) -> [(v,v,p)] -> Grafo v p creaGrafo o cs vs = G o (accumArray (\xs x -> xs++[x]) [] cs ((if o == D then [] else [(x2,(x1,p))|(x1,x2,p) <- vs, x1 /= x2]) ++ [(x1,(x2,p)) | (x1,x2,p) <- vs])) -- ejGrafoND es el grafo -- 12 -- 1 -------- 2 -- | \78 /| -- | \ 32/ | -- | \ / | -- 34| 5 |55 -- | / \ | -- | /44 \ | -- | / 93\| -- 3 -------- 4 -- 61 -- representado mediante un vector de adyacencia; es decir, -- ghci> ejGrafoND -- G ND array (1,5) [(1,[(2,12),(3,34),(5,78)]), -- (2,[(1,12),(4,55),(5,32)]), -- (3,[(1,34),(4,61),(5,44)]), -- (4,[(2,55),(3,61),(5,93)]), -- (5,[(1,78),(2,32),(3,44),(4,93)])]) ejGrafoND = creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78), (2,4,55),(2,5,32), (3,4,61),(3,5,44), (4,5,93)] -- ejGrafoD es el mismo grafo que ejGrafoND pero orientando las aristas; -- es decir, -- ghci> ejGrafoD -- G D array (1,5) [(1,[(2,12),(3,34),(5,78)]), -- (2,[(4,55),(5,32)]), -- (3,[(4,61),(5,44)]), -- (4,[(5,93)]), -- (5,[])]) ejGrafoD = creaGrafo D (1,5) [(1,2,12),(1,3,34),(1,5,78), (2,4,55),(2,5,32), (3,4,61),(3,5,44), (4,5,93)] -- (dirigido g) se verifica si g es dirigido. Por ejemplo, -- dirigido ejGrafoD == True -- dirigido ejGrafoND == False dirigido :: (Ix v,Num p) => (Grafo v p) -> Bool dirigido (G o _) = o == D -- (nodos g) es la lista de todos los nodos del grafo g. Por ejemplo, -- nodos ejGrafoND == [1,2,3,4,5] -- nodos ejGrafoD == [1,2,3,4,5] nodos :: (Ix v,Num p) => (Grafo v p) -> [v] nodos (G _ g) = indices g -- (adyacentes g v) es la lista de los vértices adyacentes al nodo v en -- el grafo g. Por ejemplo, -- adyacentes ejGrafoND 4 == [2,3,5] -- adyacentes ejGrafoD 4 == [5] adyacentes :: (Ix v,Num p) => (Grafo v p) -> v -> [v] adyacentes (G _ g) v = map fst (g!v) -- (aristaEn g a) se verifica si a es una arista del grafo g. Por -- ejemplo, -- aristaEn ejGrafoND (5,1) == True -- aristaEn ejGrafoND (4,1) == False -- aristaEn ejGrafoD (5,1) == False -- aristaEn ejGrafoD (1,5) == True aristaEn :: (Ix v,Num p) => (Grafo v p) -> (v,v) -> Bool aristaEn g (x,y) = y `elem` adyacentes g x -- (peso v1 v2 g) es el peso de la arista que une los vértices v1 y v2 -- en el grafo g. Por ejemplo, -- peso 1 5 ejGrafoND == 78 -- peso 1 5 ejGrafoD == 78 peso :: (Ix v,Num p) => v -> v -> (Grafo v p) -> p peso x y (G _ g) = head [c | (a,c) <- g!x , a == y] -- (aristas g) es la lista de las aristas del grafo g. Por ejemplo, -- ghci> aristas ejGrafoD -- [(1,2,12),(1,3,34),(1,5,78),(2,4,55),(2,5,32),(3,4,61), -- (3,5,44),(4,5,93)] -- ghci> aristas ejGrafoND -- [(1,2,12),(1,3,34),(1,5,78),(2,1,12),(2,4,55),(2,5,32), -- (3,1,34),(3,4,61),(3,5,44),(4,2,55),(4,3,61),(4,5,93), -- (5,1,78),(5,2,32),(5,3,44),(5,4,93)] aristas :: (Ix v,Num p) => (Grafo v p) -> [(v,v,p)] aristas (G o g) = [(v1,v2,w) | v1 <- nodos (G o g) , (v2,w) <- g!v1] |