{"id":1359,"date":"2011-05-09T14:37:38","date_gmt":"2011-05-09T14:37:38","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=1359"},"modified":"2011-05-13T05:46:46","modified_gmt":"2011-05-13T05:46:46","slug":"i1m2010-ejercicios-sobre-la-implementacion-en-haskell-del-tad-de-los-gragos-mediante-listas-de-pares","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2010-ejercicios-sobre-la-implementacion-en-haskell-del-tad-de-los-gragos-mediante-listas-de-pares\/","title":{"rendered":"I1M2010: Ejercicios sobre la implementaci\u00f3n en Haskell del TAD de los grafos mediante listas de pares"},"content":{"rendered":"<p>En la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-10\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos comentando las soluciones a los ejercicios sobre la implementaci\u00f3n en Haskell del tipo abstracto de datos de los grafos mediante listas de pares de la <a href=\"https:\/\/www.glc.us.es\/~jalonso\/ejerciciosI1M2010\/index.php5\/Relaci%C3%B3n_29\">29\u00aa relaci\u00f3n<\/a>.<\/p>\n<p>Los ejercicios y su soluci\u00f3n se muestran a continuaci\u00f3n<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\r\n-- ---------------------------------------------------------------------\r\n-- Introducci\u00f3n                                                       --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- El objetivo de esta relaci\u00f3n es implementar el TAD de los grafos\r\n-- mediante listas, de manera an\u00e1loga a las implementaciones estudiadas\r\n-- en el tema 22 que se encuentran en \r\n--    http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-10\/temas\/tema-22.pdf\r\n-- y usando la mismas signatura.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Signatura                                                          --\r\n-- ---------------------------------------------------------------------\r\n\r\nmodule GrafoConListasDePares\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\nimport Data.List\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Representaci\u00f3n de los grafos mediante listas                       --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- (Grafo v p) es un grafo con v\u00e9rtices de tipo v y pesos de tipo p.\r\nnewtype Grafo v p = G [((v,v),p)]\r\n    deriving (Eq, Show)\r\n\r\n-- grafoL 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\ngrafoL :: Grafo Int Int\r\ngrafoL = G [((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\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicios                                                         --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1. Definir la funci\u00f3n\r\n--    creaGrafo :: (Ix v, Num p) => Bool -> (v,v) -> [(v,v,p)] -> Grafo v p\r\n-- tal que (creaGrafo d cs as) es un grafo (dirigido si d es True y no\r\n-- dirigido en caso contrario), con el par de cotas cs y listas de\r\n-- aristas as (cada arista es un tr\u00edo formado por los dos v\u00e9rtices y su\r\n-- peso). Por ejemplo,\r\n--    ghci> creaGrafo True (1,3) [(1,2,12),(1,3,34)]\r\n--    G [((1,2),12),((1,3),34)]\r\n--    ghci> creaGrafo False (1,3) [(1,2,12),(1,3,34)]\r\n--    G [((1,2),12),((1,3),34),((2,1),12),((3,1),34)]\r\n-- ---------------------------------------------------------------------\r\n\r\ncreaGrafo :: (Ix v, Num p) => Bool -> (v,v) -> [(v,v,p)] -> Grafo v p\r\ncreaGrafo d cs as = \r\n    G ([((x1,x2),w) | \r\n        (x1,x2,w) <- as] ++ \r\n        if d then []\r\n        else [((x2,x1),w) | (x1,x2,w) <- as, x1 \/= x2])\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2. Definir la funci\u00f3n\r\n--    adyacentes :: (Ix v, Num p) => Grafo v p -> v -> [v]\r\n-- tal que (adyacentes g v) es la lista de los v\u00e9rtices adyacentes al\r\n-- nodo v en el grafo g. Por ejemplo,\r\n--    adyacentes grafoL 4  ==  [2,3,5]\r\n-- ---------------------------------------------------------------------\r\n\r\nadyacentes :: (Ix v, Num p) => Grafo v p -> v -> [v]\r\nadyacentes (G g) v = nub [u | ((w,u),_) <- g, w == v]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. Definir la funci\u00f3n\r\n--    nodos :: (Ix v,Num p) => Grafo v p -> [v]\r\n-- tal que (nodos g) es la lista de todos los nodos del grafo g. Por\r\n-- ejemplo, \r\n--    nodos grafoL  ==  [1,2,3,4,5]\r\n-- ---------------------------------------------------------------------\r\n\r\nnodos :: (Ix v,Num p) => Grafo v p -> [v]\r\nnodos (G g) = nub [x | ((x,_),_) <- g] ++ [y | ((_,y),_) <- g]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. Definir la funci\u00f3n\r\n--    aristaEn :: (Ix v,Num p) => Grafo v p -> (v,v) -> Bool\r\n-- (aristaEn g a) se verifica si a es una arista del grafo g. Por\r\n-- ejemplo,\r\n--    aristaEn grafoL (5,1)  ==  True\r\n--    aristaEn grafoL (4,1)  ==  False\r\n-- ---------------------------------------------------------------------\r\n\r\naristaEn :: (Ix v,Num p) => Grafo v p -> (v,v) -> Bool\r\naristaEn g (x,y) = y `elem` adyacentes g x\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5. Definir la funci\u00f3n\r\n--    peso :: (Ix v,Num p) => v -> v -> Grafo v p -> p\r\n-- tal que (peso v1 v2 g) es el peso de la arista que une los v\u00e9rtices\r\n-- v1 y v2 en el grafo g. Por ejemplo,\r\n--    peso 1 5 grafoL  ==  78\r\n-- ---------------------------------------------------------------------\r\n\r\npeso :: (Ix v,Num p) => v -> v -> Grafo v p -> p\r\npeso x y (G gs) = head [c | ((x',y'),c) <- gs, x==x', y==y']\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 6. Definir la funci\u00f3n\r\n--    aristasD :: (Ix v,Num p) => Grafo v p -> [(v,v,p)]\r\n-- (aristasD g) es la lista de las aristas del grafo dirigido g. Por\r\n-- ejemplo, \r\n--    ghci> aristasD grafoL\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\n-- ---------------------------------------------------------------------\r\n\r\naristasD :: (Ix v,Num p) => Grafo v p -> [(v,v,p)]\r\naristasD (G g) = [(v1,v2,p) | ((v1,v2),p) <- g]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 7. Definir la funci\u00f3n\r\n--    aristasND :: (Ix v,Num p) => Grafo v p -> [(v,v,p)]\r\n-- tal que (aristasND g) es la lista de las aristas del grafo no\r\n-- dirigido g. Por ejemplo, \r\n--    ghci> aristasND grafoL\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\n-- ---------------------------------------------------------------------\r\n\r\naristasND :: (Ix v,Num p) => Grafo v p -> [(v,v,p)]\r\naristasND (G g) = [(v1,v2,p) | ((v1,v2),p) <- g, v1 < v2]\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 comentando las soluciones a los ejercicios sobre la implementaci\u00f3n en Haskell del tipo abstracto de datos de los grafos mediante listas de pares de la 29\u00aa relaci\u00f3n. Los ejercicios y su soluci\u00f3n se muestran a continuaci\u00f3n<\/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":[133],"tags":[287],"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\/1359"}],"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=1359"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1359\/revisions"}],"predecessor-version":[{"id":1364,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1359\/revisions\/1364"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=1359"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=1359"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=1359"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}