{"id":3359,"date":"2013-05-21T16:46:45","date_gmt":"2013-05-21T16:46:45","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=3359"},"modified":"2013-05-22T06:47:18","modified_gmt":"2013-05-22T06:47:18","slug":"i1m2012-implementacion-en-haskell-de-los-grafos-mediante-matrices-algoritmos-de-recorrido-de-grafos","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2012-implementacion-en-haskell-de-los-grafos-mediante-matrices-algoritmos-de-recorrido-de-grafos\/","title":{"rendered":"I1M2012: Implementaci\u00f3n en Haskell de los grafos mediante matrices. Algoritmos de recorrido de grafos"},"content":{"rendered":"<p>En la clase de hoy de <a  href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-12\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos estudiado una segunda implementaci\u00f3n en Haskell del tipo abstracto de los grafos usando matrices de adyacencia.<\/p>\n<p>Adem\u00e1s, hemos estudiado los algoritmos de recorrido de los grafos en profundidad y en anchura.<\/p>\n<p>Las transparencias usadas en la clase son las p\u00e1ginas 19-38 del <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-12\/temas\/tema-22t.pdf\">tema 22<\/a>:<br \/>\n<!--more--><br \/>\n<div class=\"jetpack-video-wrapper\"><iframe src='https:\/\/www.slideshare.net\/slideshow\/embed_code\/7761061' width='1290' height='1057' sandbox=\"allow-popups allow-scripts allow-same-origin allow-presentation\" allowfullscreen webkitallowfullscreen mozallowfullscreen><\/iframe><\/div><\/p>\n<p>El c\u00f3digo de la implementaci\u00f3n de grafos mediante matrices de adyacencia es<\/p>\n<pre lang=\"haskell\">\r\nmodule GrafoConMatrizDeAdyacencia\r\n    (Orientacion (..),\r\n     Grafo,\r\n     creaGrafo,  -- (Ix v,Num p) => Orientacion -> (v,v) -> [(v,v,p)] -> \r\n                 --                 Grafo v p\r\n     dirigido,   -- (Ix v,Num p) => (Grafo v p) -> Bool\r\n     adyacentes, -- (Ix v,Num p) => (Grafo v p) -> v -> [v]\r\n     nodos,      -- (Ix v,Num p) => (Grafo v p) -> [v]\r\n     aristas,    -- (Ix v,Num p) => (Grafo v p) -> [(v,v,p)]\r\n     aristaEn,   -- (Ix v,Num p) => (Grafo v p) -> (v,v) -> Bool\r\n     peso        -- (Ix v,Num p) => v -> v -> (Grafo v p) -> p\r\n    ) where\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Librer\u00edas auxiliares                                               --\r\n-- ---------------------------------------------------------------------\r\n\r\nimport Data.Array\r\n\r\n-- Orientacion es D (dirigida) \u00f3 ND (no dirigida).\r\ndata Orientacion = D | ND\r\n                   deriving (Eq, Show)\r\n\r\n-- (Grafo v p) es un grafo con v\u00e9rtices de tipo v y pesos de tipo p.\r\ndata Grafo v p = G Orientacion (Array (v,v) (Maybe p))\r\n                 deriving (Eq, Show)\r\n\r\n-- (creaGrafo d cs as) es un grafo (dirigido o no, seg\u00fan el valor de o),\r\n-- con el par de cotas cs y listas de aristas as (cada arista es un tr\u00edo\r\n-- formado por los dos v\u00e9rtices y su peso). Ver el ejemplo a continuaci\u00f3n.\r\ncreaGrafo :: (Ix v, Num p) => Orientacion -> (v,v) -> [(v,v,p)] -> (Grafo v p)\r\ncreaGrafo o cs@(l,u) as \r\n    = G o (matrizVacia \/\/ \r\n            ([((x1,x2),Just w) | (x1,x2,w) <- as] ++\r\n             if o == D then []\r\n             else [((x2,x1),Just w) | (x1,x2,w) <- as, x1 \/= x2]))\r\n      where\r\n      matrizVacia = array ((l,l),(u,u)) \r\n                          [((x1,x2),Nothing) | x1 <- range cs, \r\n                                               x2 <- range cs]\r\n\r\n-- ejGrafoND es el grafo\r\n--             12\r\n--        1 -------- 2\r\n--        | \\78     \/|\r\n--        |  \\   32\/ |\r\n--        |   \\   \/  |\r\n--      34|     5    |55\r\n--        |   \/   \\  |\r\n--        |  \/44   \\ |\r\n--        | \/     93\\|\r\n--        3 -------- 4\r\n--             61\r\n-- representado mediante una matriz de adyacencia.\r\n--    ghci> ejGrafoND\r\n--    G ND array ((1,1),(5,5)) \r\n--               [((1,1),Nothing),((1,2),Just 12),((1,3),Just 34),\r\n--                ((1,4),Nothing),((1,5),Just 78),((2,1),Just 12),\r\n--                ((2,2),Nothing),((2,3),Nothing),((2,4),Just 55),\r\n--                ((2,5),Just 32),((3,1),Just 34),((3,2),Nothing),\r\n--                ((3,3),Nothing),((3,4),Just 61),((3,5),Just 44),\r\n--                ((4,1),Nothing),((4,2),Just 55),((4,3),Just 61),\r\n--                ((4,4),Nothing),((4,5),Just 93),((5,1),Just 78),\r\n--                ((5,2),Just 32),((5,3),Just 44),((5,4),Just 93),\r\n--                ((5,5),Nothing)]\r\nejGrafoND = creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78),\r\n                                (2,4,55),(2,5,32),\r\n                                (3,4,61),(3,5,44),\r\n                                (4,5,93)]\r\n\r\n-- ejGrafoD es el mismo grafo que ejGrafoND pero orientando las aristas;\r\n-- es decir,\r\n--    ghci> ejGrafoD\r\n--    G D (array ((1,1),(5,5)) \r\n--               [((1,1),Nothing),((1,2),Just 12),((1,3),Just 34),\r\n--                ((1,4),Nothing),((1,5),Just 78),((2,1),Nothing),\r\n--                ((2,2),Nothing),((2,3),Nothing),((2,4),Just 55),\r\n--                ((2,5),Just 32),((3,1),Nothing),((3,2),Nothing),\r\n--                ((3,3),Nothing),((3,4),Just 61),((3,5),Just 44),\r\n--                ((4,1),Nothing),((4,2),Nothing),((4,3),Nothing),\r\n--                ((4,4),Nothing),((4,5),Just 93),((5,1),Nothing),\r\n--                ((5,2),Nothing),((5,3),Nothing),((5,4),Nothing),\r\n--                ((5,5),Nothing)])\r\nejGrafoD = creaGrafo D (1,5) [(1,2,12),(1,3,34),(1,5,78),\r\n                              (2,4,55),(2,5,32),\r\n                              (3,4,61),(3,5,44),\r\n                              (4,5,93)]\r\n\r\n-- (dirigido g) se verifica si g es dirigido. Por ejemplo,\r\n--    dirigido ejGrafoD   ==  True\r\n--    dirigido ejGrafoND  ==  False\r\ndirigido :: (Ix v,Num p) => (Grafo v p) -> Bool\r\ndirigido (G o _) = o == D\r\n\r\n-- (nodos g) es la lista de todos los nodos del grafo g. Por ejemplo,\r\n--    nodos ejGrafoND  ==  [1,2,3,4,5]\r\n--    nodos ejGrafoD   ==  [1,2,3,4,5]\r\nnodos :: (Ix v,Num p) => (Grafo v p) -> [v]\r\nnodos (G _ g) = range (l,u) \r\n    where ((l,_),(u,_)) = bounds g\r\n\r\n-- (adyacentes g v) es la lista de los v\u00e9rtices adyacentes al nodo v en\r\n-- el grafo g. Por ejemplo,\r\n--    adyacentes ejGrafoND 4  ==  [2,3,5]\r\n--    adyacentes ejGrafoD  4  ==  [5]\r\nadyacentes :: (Ix v,Num p) => (Grafo v p) -> v -> [v]\r\nadyacentes (G o g) v = \r\n    [v' | v' <- nodos (G o g), (g!(v,v')) \/= Nothing]\r\n\r\n-- (aristaEn g a) se verifica si a es una arista del grafo g. Por\r\n-- ejemplo,\r\n--    aristaEn ejGrafoND (5,1)  ==  True\r\n--    aristaEn ejGrafoND (4,1)  ==  False\r\naristaEn :: (Ix v,Num p) => (Grafo v p) -> (v,v) -> Bool\r\naristaEn (G _o g) (x,y)= (g!(x,y)) \/= Nothing\r\n\r\n-- (peso v1 v2 g) es el peso de la arista que une los v\u00e9rtices v1 y v2\r\n-- en el grafo g. Por ejemplo,\r\n--    peso 1 5 ejGrafoND  ==  78\r\n--    peso 1 5 ejGrafoD   ==  78\r\npeso :: (Ix v,Num p) => v -> v -> (Grafo v p) -> p\r\npeso x y (G _ g)  = w where (Just w) = g!(x,y)\r\n\r\n-- (aristas g) es la lista de las aristas del grafo g. Por ejemplo, \r\n--    ghci> aristas ejGrafoD\r\n--    [(1,2,12),(1,3,34),(1,5,78),(2,4,55),(2,5,32),(3,4,61),\r\n--     (3,5,44),(4,5,93)] \r\n--    ghci> aristas ejGrafoND\r\n--    [(1,2,12),(1,3,34),(1,5,78),(2,1,12),(2,4,55),(2,5,32),\r\n--     (3,1,34),(3,4,61),(3,5,44),(4,2,55),(4,3,61),(4,5,93),\r\n--     (5,1,78),(5,2,32),(5,3,44),(5,4,93)]\r\naristas :: (Ix v,Num p) => (Grafo v p) -> [(v,v,p)]\r\naristas g@(G o e) = [(v1,v2,extrae(e!(v1,v2))) \r\n                     | v1 <- nodos g, \r\n                       v2 <- nodos g,\r\n                       aristaEn g (v1,v2)]\r\n    where extrae (Just w) = w\r\n<\/pre>\n<p>El c\u00f3digo del recorridos de grafos en profundidad es<\/p>\n<pre lang=\"haskell\">\r\nmodule RecorridoEnProfundidad where\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Librer\u00edas auxiliares                                               --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Nota: Elegir una implementaci\u00f3n de los grafos.\r\nimport GrafoConVectorDeAdyacencia\r\n-- import GrafoConMatrizDeAdyacencia\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejemplo de grafo                                                   --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- g es el grafo\r\n--    +---> 2 <---+\r\n--    |           |\r\n--    |           |\r\n--    1 --> 3 --> 6 --> 5\r\n--    |                 |\r\n--    |                 |\r\n--    +---> 4 <---------+\r\n\r\ng = creaGrafo D (1,6) \r\n              [(1,2,0),(1,3,0),(1,4,0),(3,6,0),(5,4,0),(6,2,0),(6,5,0)]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Recorrido en profundidad                                            --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- (recorridoEnProfundidad i g) es el recorrido en profundidad del grafo g\r\n-- desde el v\u00e9rtice i. Por ejemplo,\r\n--    recorridoEnProfundidad 1 g  ==  [1,2,3,6,5,4]\r\nrecorridoEnProfundidad i g = rp [i] []\r\n    where \r\n      rp [] vis    = vis\r\n      rp (c:cs) vis \r\n          | c `elem` vis = rp cs vis\r\n          | otherwise    = rp ((adyacentes g c)++cs) (vis++[c])\r\n\r\n-- Traza del c\u00e1lculo de (recorridoEnProfundidad 1 g)\r\n--    recorridoEnProfundidad 1 g\r\n--    = rp [1]     []\r\n--    = rp [2,3,4] [1]\r\n--    = rp [3,4]   [1,2]\r\n--    = rp [6,4]   [1,2,3]\r\n--    = rp [2,5,4] [1,2,3,6]\r\n--    = rp [5,4]   [1,2,3,6]\r\n--    = rp [4,4]   [1,2,3,6,5]\r\n--    = rp [4]     [1,2,3,6,5,4]\r\n--    = rp []      [1,2,3,6,5,4]\r\n--    = [1,2,3,6,5,4]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Recorrido en profundidad con acumuladores                           --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- (recorridoEnProfundidad' i g) es el recorrido en profundidad del\r\n-- grafo g desde el v\u00e9rtice i, usando la lista de los visitados como\r\n-- acumulador. Por ejemplo, \r\n--    recorridoEnProfundidad' 1 g  ==  [1,2,3,6,5,4]\r\nrecorridoEnProfundidad' i g = reverse (rp [i] [])\r\n    where\r\n      rp [] vis     = vis\r\n      rp (c:cs) vis \r\n          | c `elem` vis = rp cs vis\r\n          | otherwise    = rp ((adyacentes g c)++cs) (c:vis)\r\n\r\n-- Traza del c\u00e1lculo de (recorridoEnProfundidad' 1 g)\r\n--    RecorridoEnProfundidad' 1 g\r\n--    = reverse (rp [1]     [])\r\n--    = reverse (rp [2,3,4] [1])\r\n--    = reverse (rp [3,4]   [2,1])\r\n--    = reverse (rp [6,4]   [3,2,1])\r\n--    = reverse (rp [2,5,4] [6,3,2,1])\r\n--    = reverse (rp [5,4]   [6,3,2,1])\r\n--    = reverse (rp [4,4]   [5,6,3,2,1])\r\n--    = reverse (rp [4]     [4,5,6,3,2,1])\r\n--    = reverse (rp []      [4,5,6,3,2,1])\r\n--    = reverse [4,5,6,3,2,1]\r\n--    = [1,2,3,6,5,4]\r\n<\/pre>\n<p>El c\u00f3digo del recorridos de grafos en anchura es<\/p>\n<pre lang=\"haskell\">\r\nmodule RecorridoEnAnchura where\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Librer\u00edas auxiliares                                               --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Nota: Elegir una implementaci\u00f3n de los grafos.\r\nimport GrafoConVectorDeAdyacencia\r\n-- import GrafoConMatrizDeAdyacencia\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejemplo de grafo                                                   --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- g es el grafo\r\n--    +---> 2 <---+\r\n--    |           |\r\n--    |           |\r\n--    1 --> 3 --> 6 --> 5\r\n--    |                 |\r\n--    |                 |\r\n--    +---> 4 <---------+\r\ng = creaGrafo D (1,6) \r\n              [(1,2,0),(1,3,0),(1,4,0),(3,6,0),(5,4,0),(6,2,0),(6,5,0)]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Recorrido en anchura con colas                                      --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- (recorridoEnAnchura i g) es el recorrido en anchura del grafo g\r\n-- desde el v\u00e9rtice i, usando colas. Por ejemplo, \r\n--    recorridoEnAnchura 1 g  ==  [1,4,3,2,6,5]\r\nrecorridoEnAnchura i g = reverse (ra [i] [])\r\n    where \r\n      ra [] vis    = vis\r\n      ra (c:cs) vis \r\n          | c `elem` vis = ra cs vis\r\n          | otherwise    = ra (cs ++ adyacentes g c) (c:vis)\r\n\r\n-- Traza del c\u00e1lculo de (recorridoEnProfundidad 1 g)\r\n--    RecorridoEnAnchura 1 g\r\n--    = ra [1]     []\r\n--    = ra [2,3,4] [1]\r\n--    = ra [3,4]   [2,1]\r\n--    = ra [4,6]   [3,2,1]\r\n--    = ra [6]     [4,3,2,1]\r\n--    = ra [2,5]   [6,4,3,2,1]\r\n--    = ra [5]     [6,4,3,2,1]\r\n--    = ra [4]     [5,6,4,3,2,1]\r\n--    = ra []      [5,6,4,3,2,1]\r\n--    = [1,2,3,4,6,5]\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas hemos estudiado una segunda implementaci\u00f3n en Haskell del tipo abstracto de los grafos usando matrices de adyacencia. Adem\u00e1s, hemos estudiado los algoritmos de recorrido de los grafos en profundidad y en anchura. Las transparencias usadas en la clase son las p\u00e1ginas 19-38&#8230;<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[1],"tags":[270,298],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/3359"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=3359"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/3359\/revisions"}],"predecessor-version":[{"id":3360,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/3359\/revisions\/3360"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=3359"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=3359"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=3359"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}