{"id":1531,"date":"2011-08-30T15:30:00","date_gmt":"2011-08-30T15:30:00","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=1531"},"modified":"2011-09-05T10:33:26","modified_gmt":"2011-09-05T10:33:26","slug":"el-tipo-abstracto-de-datos-de-los-grafos-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/el-tipo-abstracto-de-datos-de-los-grafos-en-haskell\/","title":{"rendered":"El tipo abstracto de datos de los grafos en Haskell"},"content":{"rendered":"<p>Continuando la serie dedicada a los <a href=\"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/tag\/tipo-abstracto-de-datos\/\">tipos de datos abstractos (TAD) en Haskell<\/a>, hoy le toca el turno a los grafos. En los pr\u00f3ximos, estudiaremos algoritmos sobre grafos basados en este TAD.<\/p>\n<p>Informalmente, un <a href=\"http:\/\/en.wikipedia.org\/wiki\/Graph_(mathematics)\">grafo<\/a> es un conjunto de objetos llamados <i>v\u00e9rtices<\/i> o <i>nodos<\/i> unidos por enlaces llamados <i>aristas<\/i> o <i>arcos<\/i>.<\/p>\n<p>El contenido del este art\u00edculo es el siguiente: <\/p>\n<ul>\n<li>la signatura del TAD de los grafos;<\/li>\n<li>la implementaci\u00f3n de los grafos mediante vectores de adyacencia y<\/li>\n<li>la implementaci\u00f3n de los grafos mediante matrices de adyacencia.<\/li>\n<\/ul>\n<p><!--more--><\/p>\n<h3>La signatura del TAD de los grafos<\/h3>\n<p>Las signatura de las operaciones del TAD de los grafos son las siguientes:<\/p>\n<pre lang=\"haskell\">\r\ncreaGrafo  :: (Ix v,Num p) => Bool -> (v,v) -> [(v,v,p)] \r\n                              -> Grafo v p\r\nadyacentes :: (Ix v,Num p) => (Grafo v p) -> v -> [v]\r\nnodos      :: (Ix v,Num p) => (Grafo v p) -> [v]\r\naristasND  :: (Ix v,Num p) => (Grafo v p) -> [(v,v,p)]\r\naristasD   :: (Ix v,Num p) => (Grafo v p) -> [(v,v,p)]\r\naristaEn   :: (Ix v,Num p) => (Grafo v p) -> (v,v) -> Bool\r\npeso       :: (Ix v,Num p) => v -> v -> (Grafo v p) -> p\r\n<\/pre>\n<p>con el siguiente significado<\/p>\n<ul>\n<li> <i>(creaGrafo d cs as)<\/i> es un grafo (dirigido si d es True y no dirigido en caso contrario), con el par de cotas cs y listas de aristas as (cada arista es un tr\u00edo formado por los dos v\u00e9rtices y su peso).<\/li>\n<li> <i>(adyacentes g v)<\/i> es la lista de los v\u00e9rtices adyacentes al nodo v en el grafo g.<\/li>\n<li> <i>(nodos g)<\/i> es la lista de todos los nodos del grafo g.<\/li>\n<li> <i>(aristasND g)<\/i> es la lista de las aristas del grafo no dirigido g.<\/li>\n<li> <i>(aristasD g)<\/i> es la lista de las aristas del grafo dirigido g.<\/li>\n<li> <i>(aristaEn g a)<\/i> se verifica si a es una arista del grafo g.<\/li>\n<li> <i>(peso v1 v2 g)<\/i> es el peso de la arista que une los v\u00e9rtices v1 y v2 en el grafo g.<\/li>\n<\/ul>\n<p>Por ejemplo,<\/p>\n<pre lang=\"haskell\">\r\ncreaGrafo False (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<\/pre>\n<p>crea el grafo<\/p>\n<pre>\r\n       12\r\n  1 -------- 2\r\n  | \\78     \/|\r\n  |  \\   32\/ |\r\n  |   \\   \/  |\r\n34|     5    |55\r\n  |   \/   \\  |\r\n  |  \/44   \\ |\r\n  | \/     93\\|\r\n  3 -------- 4\r\n       61\r\n<\/pre>\n<h3>Implementaci\u00f3n de los grafos mediante vectores de adyacencia<\/h3>\n<pre lang=\"haskell\">\r\nmodule GrafoConVectorDeAdyacencia \r\n    (Grafo,\r\n     creaGrafo,  -- (Ix v,Num p) => Bool -> (v,v) -> [(v,v,p)] -> Grafo v p\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     aristasND,  -- (Ix v,Num p) => (Grafo v p) -> [(v,v,p)]\r\n     aristasD,   -- (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-- (Grafo v p) es un grafo con v\u00e9rtices de tipo v y pesos de tipo p.\r\ntype Grafo v p = Array v [(v,p)]\r\n\r\n-- grafoVA 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 un vector de adyacencia.\r\ngrafoVA = array (1,5) [(1,[(2,12),(3,34),(5,78)]),\r\n                       (2,[(1,12),(4,55),(5,32)]),\r\n                       (3,[(1,34),(4,61),(5,44)]),\r\n                       (4,[(2,55),(3,61),(5,93)]),\r\n                       (5,[(1,78),(2,32),(3,44),(4,93)])]\r\n\r\n-- (creaGrafo d cs as) es un grafo (dirigido si d es True y no dirigido\r\n-- en caso contrario), con el par de cotas cs y listas de aristas as\r\n-- (cada arista es un tr\u00edo formado por los dos v\u00e9rtices y su peso). Ver\r\n-- el ejemplo a continuaci\u00f3n.\r\ncreaGrafo :: (Ix v, Num p) => Bool -> (v,v) -> [(v,v,p)] -> Grafo v p\r\ncreaGrafo d cs vs =\r\n    accumArray \r\n     (\\xs x -> xs++[x]) [] cs \r\n     ((if d then []\r\n       else [(x2,(x1,p))|(x1,x2,p) <- vs, x1 \/= x2]) ++\r\n      [(x1,(x2,p)) | (x1,x2,p) <- vs])\r\n\r\n-- grafoVA' es el mismo grafo que grafoVA pero creado con creaGrafo. Por\r\n-- ejemplo, \r\n--    ghci> grafoVA'\r\n--    array (1,5) [(1,[(2,12),(3,34),(5,78)]),\r\n--                 (2,[(1,12),(4,55),(5,32)]),\r\n--                 (3,[(1,34),(4,61),(5,44)]),\r\n--                 (4,[(2,55),(3,61),(5,93)]),\r\n--                 (5,[(1,78),(2,32),(3,44),(4,93)])]\r\ngrafoVA' = creaGrafo False (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-- (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 grafoVA' 4  ==  [2,3,5]\r\nadyacentes :: (Ix v,Num p) => (Grafo v p) -> v -> [v]\r\nadyacentes g v = map fst (g!v)\r\n\r\n-- (nodos g) es la lista de todos los nodos del grafo g. Por ejemplo,\r\n--    nodos grafoVA'  ==  [1,2,3,4,5]\r\nnodos :: (Ix v,Num p) => (Grafo v p) -> [v]\r\nnodos g = indices g\r\n\r\n-- (aristaEn g a) se verifica si a es una arista del grafo g. Por\r\n-- ejemplo,\r\n--    aristaEn grafoVA' (5,1)  ==  True\r\n--    aristaEn grafoVA' (4,1)  ==  False\r\naristaEn :: (Ix v,Num p) => (Grafo v p) -> (v,v) -> Bool\r\naristaEn g (x,y) = elem y (adyacentes g x)\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 grafoVA'  ==  78\r\npeso :: (Ix v,Num p) => v -> v -> (Grafo v p) -> p\r\npeso x y g = head [c | (a,c) <- g!x , a == y]\r\n\r\n-- (aristasD g) es la lista de las aristas del grafo dirigido g. Por\r\n-- ejemplo, \r\n--    ghci> aristasD grafoVA'\r\n--    [(1,2,12),(1,3,34),(1,5,78),\r\n--     (2,1,12),(2,4,55),(2,5,32),\r\n--     (3,1,34),(3,4,61),(3,5,44),\r\n--     (4,2,55),(4,3,61),(4,5,93),\r\n--     (5,1,78),(5,2,32),(5,3,44),(5,4,93)]\r\naristasD :: (Ix v,Num p) => (Grafo v p) -> [(v,v,p)]\r\naristasD g = [(v1,v2,w) | v1 <- nodos g , (v2,w) <- g!v1] \r\n\r\n-- (aristasND g) es la lista de las aristas del grafo no dirigido g. Por\r\n-- ejemplo, \r\n--    ghci> aristasND grafoVA'\r\n--    [(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\naristasND :: (Ix v,Num p) => (Grafo v p) -> [(v,v,p)]\r\naristasND g = \r\n    [(v1,v2,w) | v1 <- nodos g , (v2,w) <- g!v1 , v1 < v2] \r\n<\/pre>\n<h3>Implementaci\u00f3n de los grafos mediante matrices de adyacencia<\/h3>\n<pre lang=\"haskell\">\r\nmodule GrafoConMatrizDeAdyacencia \r\n    (Grafo,\r\n     creaGrafo,  -- (Ix v,Num p) => Bool -> (v,v) -> [(v,v,p)] -> Grafo v p\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     aristasND,  -- (Ix v,Num p) => (Grafo v p) -> [(v,v,p)]\r\n     aristasD,   -- (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-- (Grafo v p) es un grafo con v\u00e9rtices de tipo v y pesos de tipo p.\r\ntype Grafo v p = Array (v,v) (Maybe p)\r\n\r\n-- grafoMA 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\ngrafoMA = array ((1, 1), (5, 5)) \r\n                [((1, 1),Nothing), ((1, 2),Just 10), ((1, 3),Just 20), \r\n                 ((1, 4),Nothing), ((1, 5),Nothing), ((2, 1),Nothing), \r\n                 ((2, 2),Nothing), ((2, 3),Nothing), ((2, 4),Just 30), \r\n                 ((2, 5),Nothing), ((3, 1),Nothing), ((3, 2),Nothing), \r\n                 ((3, 3),Nothing), ((3, 4),Just 40), ((3, 5),Nothing), \r\n                 ((4, 1),Nothing), ((4, 2),Nothing), ((4, 3),Nothing), \r\n                 ((4, 4),Nothing), ((4, 5),Just 50), ((5, 1),Nothing), \r\n                 ((5, 2),Nothing), ((5, 3),Nothing), ((5, 4),Nothing), \r\n                 ((5, 5),Nothing)]\r\n\r\n-- (creaGrafo d cs as) es un grafo (dirigido si de es True y no dirigido\r\n-- en caso contrario), con el par de cotas cs y listas de aristas as\r\n-- (cada arista es un tr\u00edo formado por los dos v\u00e9rtices y su peso). Ver\r\n-- el ejemplo a continuaci\u00f3n.\r\ncreaGrafo :: (Ix v, Num p) => Bool -> (v,v) -> [(v,v,p)] -> (Grafo v p)\r\ncreaGrafo dir cs@(l,u) as \r\n    = matrizVacia \/\/ \r\n      ([((x1,x2),Just w) | (x1,x2,w) <- as] ++\r\n       if dir 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-- grafoMA' es el mismo grafo que grafoMA pero creado con creaGrafo. Por\r\n-- ejemplo, \r\n--    ghci> grafoMA'\r\n--    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\ngrafoMA' = creaGrafo False (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-- (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 grafoMA' 4  ==  [2,3,5]\r\nadyacentes :: (Ix v,Num p) => (Grafo v p) -> v -> [v]\r\nadyacentes g v1 = \r\n    [v2 | v2 <- nodos g, (g!(v1,v2)) \/= Nothing]\r\n\r\n-- (nodos g) es la lista de todos los nodos del grafo g. Por ejemplo,\r\n--    nodos grafoMA'  ==  [1,2,3,4,5]\r\nnodos :: (Ix v,Num p) => (Grafo v p) -> [v]\r\nnodos g = range (l,u) \r\n    where ((l,_),(u,_)) = bounds g\r\n\r\n-- (aristaEn g a) se verifica si a es una arista del grafo g. Por\r\n-- ejemplo,\r\n--    aristaEn grafoMA' (5,1)  ==  True\r\n--    aristaEn grafoMA' (4,1)  ==  False\r\naristaEn :: (Ix v,Num p) => (Grafo v p) -> (v,v) -> Bool\r\naristaEn 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 grafoMA'  ==  78\r\npeso :: (Ix v,Num p) => v -> v -> (Grafo v p) -> p\r\npeso x y g  = w where (Just w) = g!(x,y)\r\n\r\n-- (aristasD g) es la lista de las aristas del grafo dirigido g. Por\r\n-- ejemplo, \r\n--    ghci> aristasD grafoMA'\r\n--    [(1,2,12),(1,3,34),(1,5,78),\r\n--     (2,1,12),(2,4,55),(2,5,32),\r\n--     (3,1,34),(3,4,61),(3,5,44),\r\n--     (4,2,55),(4,3,61),(4,5,93),\r\n--     (5,1,78),(5,2,32),(5,3,44),(5,4,93)]\r\naristasD :: (Ix v,Num p) => (Grafo v p) -> [(v,v,p)]\r\naristasD g = [(v1,v2,extrae(g!(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\r\n-- (aristasND g) es la lista de las aristas del grafo no dirigido g. Por\r\n-- ejemplo, \r\n--    ghci> aristasND grafoMA'\r\n--    [(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\naristasND :: (Ix v,Num p) => (Grafo v p) -> [(v,v,p)]\r\naristasND g = [(v1,v2,extrae(g!(v1,v2)))\r\n               | v1 <- nodos g, \r\n                 v2 <- range (v1,u),\r\n                 aristaEn g (v1,v2)]\r\n    where (_,(u,_)) = bounds g          \r\n          extrae (Just w) = w\r\n<\/pre>\n<p>\nEl objetivo de la serie es la elaboraci\u00f3n de los temas de TAD del curso de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m\">Inform\u00e1tica del Grado en Matem\u00e1ticas<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Continuando la serie dedicada a los tipos de datos abstractos (TAD) en Haskell, hoy le toca el turno a los grafos. En los pr\u00f3ximos, estudiaremos algoritmos sobre grafos basados en este TAD. Informalmente, un grafo es un conjunto de objetos llamados v\u00e9rtices o nodos unidos por enlaces llamados aristas o arcos. El contenido del este&#8230;<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","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":[5],"tags":[270,124],"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\/1531"}],"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=1531"}],"version-history":[{"count":11,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1531\/revisions"}],"predecessor-version":[{"id":1560,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1531\/revisions\/1560"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=1531"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=1531"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=1531"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}