I1M2012: Implementación en Haskell de los grafos mediante matrices. Algoritmos de recorrido de grafos
En la clase de hoy de Informática de 1º del Grado en Matemáticas hemos estudiado una segunda implementación en Haskell del tipo abstracto de los grafos usando matrices de adyacencia.
Además, hemos estudiado los algoritmos de recorrido de los grafos en profundidad y en anchura.
Las transparencias usadas en la clase son las páginas 19-38 del tema 22:
El código de la implementación de grafos mediante matrices de adyacencia 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 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 |
module GrafoConMatrizDeAdyacencia (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) (Maybe p)) deriving (Eq, Show) -- (creaGrafo d 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@(l,u) as = G o (matrizVacia // ([((x1,x2),Just w) | (x1,x2,w) <- as] ++ if o == D then [] else [((x2,x1),Just w) | (x1,x2,w) <- as, x1 /= x2])) where matrizVacia = array ((l,l),(u,u)) [((x1,x2),Nothing) | x1 <- range cs, x2 <- range cs] -- ejGrafoND es el grafo -- 12 -- 1 -------- 2 -- | \78 /| -- | \ 32/ | -- | \ / | -- 34| 5 |55 -- | / \ | -- | /44 \ | -- | / 93\| -- 3 -------- 4 -- 61 -- representado mediante una matriz de adyacencia. -- ghci> ejGrafoND -- G ND array ((1,1),(5,5)) -- [((1,1),Nothing),((1,2),Just 12),((1,3),Just 34), -- ((1,4),Nothing),((1,5),Just 78),((2,1),Just 12), -- ((2,2),Nothing),((2,3),Nothing),((2,4),Just 55), -- ((2,5),Just 32),((3,1),Just 34),((3,2),Nothing), -- ((3,3),Nothing),((3,4),Just 61),((3,5),Just 44), -- ((4,1),Nothing),((4,2),Just 55),((4,3),Just 61), -- ((4,4),Nothing),((4,5),Just 93),((5,1),Just 78), -- ((5,2),Just 32),((5,3),Just 44),((5,4),Just 93), -- ((5,5),Nothing)] 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,1),(5,5)) -- [((1,1),Nothing),((1,2),Just 12),((1,3),Just 34), -- ((1,4),Nothing),((1,5),Just 78),((2,1),Nothing), -- ((2,2),Nothing),((2,3),Nothing),((2,4),Just 55), -- ((2,5),Just 32),((3,1),Nothing),((3,2),Nothing), -- ((3,3),Nothing),((3,4),Just 61),((3,5),Just 44), -- ((4,1),Nothing),((4,2),Nothing),((4,3),Nothing), -- ((4,4),Nothing),((4,5),Just 93),((5,1),Nothing), -- ((5,2),Nothing),((5,3),Nothing),((5,4),Nothing), -- ((5,5),Nothing)]) 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) = range (l,u) where ((l,_),(u,_)) = bounds 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 o g) v = [v' | v' <- nodos (G o g), (g!(v,v')) /= Nothing] -- (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 :: (Ix v,Num p) => (Grafo v p) -> (v,v) -> Bool aristaEn (G _o g) (x,y)= (g!(x,y)) /= Nothing -- (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) = w where (Just w) = g!(x,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@(G o e) = [(v1,v2,extrae(e!(v1,v2))) | v1 <- nodos g, v2 <- nodos g, aristaEn g (v1,v2)] where extrae (Just w) = w |
El código del recorridos de grafos en profundidad 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 |
module RecorridoEnProfundidad where -- --------------------------------------------------------------------- -- Librerías auxiliares -- -- --------------------------------------------------------------------- -- Nota: Elegir una implementación de los grafos. import GrafoConVectorDeAdyacencia -- import GrafoConMatrizDeAdyacencia -- --------------------------------------------------------------------- -- Ejemplo de grafo -- -- --------------------------------------------------------------------- -- g es el grafo -- +---> 2 <---+ -- | | -- | | -- 1 --> 3 --> 6 --> 5 -- | | -- | | -- +---> 4 <---------+ g = creaGrafo D (1,6) [(1,2,0),(1,3,0),(1,4,0),(3,6,0),(5,4,0),(6,2,0),(6,5,0)] -- --------------------------------------------------------------------- -- Recorrido en profundidad -- -- --------------------------------------------------------------------- -- (recorridoEnProfundidad i g) es el recorrido en profundidad del grafo g -- desde el vértice i. Por ejemplo, -- recorridoEnProfundidad 1 g == [1,2,3,6,5,4] recorridoEnProfundidad i g = rp [i] [] where rp [] vis = vis rp (c:cs) vis | c `elem` vis = rp cs vis | otherwise = rp ((adyacentes g c)++cs) (vis++[c]) -- Traza del cálculo de (recorridoEnProfundidad 1 g) -- recorridoEnProfundidad 1 g -- = rp [1] [] -- = rp [2,3,4] [1] -- = rp [3,4] [1,2] -- = rp [6,4] [1,2,3] -- = rp [2,5,4] [1,2,3,6] -- = rp [5,4] [1,2,3,6] -- = rp [4,4] [1,2,3,6,5] -- = rp [4] [1,2,3,6,5,4] -- = rp [] [1,2,3,6,5,4] -- = [1,2,3,6,5,4] -- --------------------------------------------------------------------- -- Recorrido en profundidad con acumuladores -- -- --------------------------------------------------------------------- -- (recorridoEnProfundidad' i g) es el recorrido en profundidad del -- grafo g desde el vértice i, usando la lista de los visitados como -- acumulador. Por ejemplo, -- recorridoEnProfundidad' 1 g == [1,2,3,6,5,4] recorridoEnProfundidad' i g = reverse (rp [i] []) where rp [] vis = vis rp (c:cs) vis | c `elem` vis = rp cs vis | otherwise = rp ((adyacentes g c)++cs) (c:vis) -- Traza del cálculo de (recorridoEnProfundidad' 1 g) -- RecorridoEnProfundidad' 1 g -- = reverse (rp [1] []) -- = reverse (rp [2,3,4] [1]) -- = reverse (rp [3,4] [2,1]) -- = reverse (rp [6,4] [3,2,1]) -- = reverse (rp [2,5,4] [6,3,2,1]) -- = reverse (rp [5,4] [6,3,2,1]) -- = reverse (rp [4,4] [5,6,3,2,1]) -- = reverse (rp [4] [4,5,6,3,2,1]) -- = reverse (rp [] [4,5,6,3,2,1]) -- = reverse [4,5,6,3,2,1] -- = [1,2,3,6,5,4] |
El código del recorridos de grafos en anchura 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 |
module RecorridoEnAnchura where -- --------------------------------------------------------------------- -- Librerías auxiliares -- -- --------------------------------------------------------------------- -- Nota: Elegir una implementación de los grafos. import GrafoConVectorDeAdyacencia -- import GrafoConMatrizDeAdyacencia -- --------------------------------------------------------------------- -- Ejemplo de grafo -- -- --------------------------------------------------------------------- -- g es el grafo -- +---> 2 <---+ -- | | -- | | -- 1 --> 3 --> 6 --> 5 -- | | -- | | -- +---> 4 <---------+ g = creaGrafo D (1,6) [(1,2,0),(1,3,0),(1,4,0),(3,6,0),(5,4,0),(6,2,0),(6,5,0)] -- --------------------------------------------------------------------- -- Recorrido en anchura con colas -- -- --------------------------------------------------------------------- -- (recorridoEnAnchura i g) es el recorrido en anchura del grafo g -- desde el vértice i, usando colas. Por ejemplo, -- recorridoEnAnchura 1 g == [1,4,3,2,6,5] recorridoEnAnchura i g = reverse (ra [i] []) where ra [] vis = vis ra (c:cs) vis | c `elem` vis = ra cs vis | otherwise = ra (cs ++ adyacentes g c) (c:vis) -- Traza del cálculo de (recorridoEnProfundidad 1 g) -- RecorridoEnAnchura 1 g -- = ra [1] [] -- = ra [2,3,4] [1] -- = ra [3,4] [2,1] -- = ra [4,6] [3,2,1] -- = ra [6] [4,3,2,1] -- = ra [2,5] [6,4,3,2,1] -- = ra [5] [6,4,3,2,1] -- = ra [4] [5,6,4,3,2,1] -- = ra [] [5,6,4,3,2,1] -- = [1,2,3,4,6,5] |