{"id":3371,"date":"2013-05-23T16:09:30","date_gmt":"2013-05-23T16:09:30","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=3371"},"modified":"2013-05-26T11:41:10","modified_gmt":"2013-05-26T11:41:10","slug":"i1m20102-ejercicios-sobre-la-implementacion-en-haskell-del-tad-de-los-grafos-mediante-listas-de-pares","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m20102-ejercicios-sobre-la-implementacion-en-haskell-del-tad-de-los-grafos-mediante-listas-de-pares\/","title":{"rendered":"I1M20102 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-12\">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 29\u00aa relaci\u00f3n.<\/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-12\/temas\/tema-22.pdf\r\n-- y usando la mismas signatura.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Signatura                                                          --\r\n-- ---------------------------------------------------------------------\r\n\r\nmodule Rel_29_sol\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\nimport Data.List\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Representaci\u00f3n de los grafos mediante listas                       --\r\n-- ---------------------------------------------------------------------\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 ([v],[((v,v),p)])\r\n                 deriving (Eq, Show)\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 o no, seg\u00fan el\r\n-- valor de o), con el par de cotas cs y listas de aristas as (cada\r\n-- arista es un tr\u00edo formado por los dos v\u00e9rtices y su peso). Por\r\n-- ejemplo, \r\n--    ghci> creaGrafo ND (1,3) [(1,2,12),(1,3,34)]\r\n--    G ND ([1,2,3],[((1,2),12),((1,3),34),((2,1),12),((3,1),34)])\r\n--    ghci> creaGrafo D (1,3) [(1,2,12),(1,3,34)]\r\n--    G D ([1,2,3],[((1,2),12),((1,3),34)])\r\n--    ghci> creaGrafo D (1,4) [(1,2,12),(1,3,34)]\r\n--    G D ([1,2,3,4],[((1,2),12),((1,3),34)])\r\n-- ---------------------------------------------------------------------\r\n\r\ncreaGrafo :: (Ix v, Num p) => \r\n             Orientacion -> (v,v) -> [(v,v,p)] -> Grafo v p\r\ncreaGrafo o cs as = \r\n    G o (range cs, [((x1,x2),w) | (x1,x2,w) <- as] ++ \r\n                    if o == D then []\r\n                    else [((x2,x1),w) | (x1,x2,w) <- as, x1 \/= x2])\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2. Definir, con creaGrafo, la constante \r\n--    ejGrafoND :: Grafo Int Int \r\n-- para representar el siguiente grafo no dirigido\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--    ghci> ejGrafoND\r\n--    G ND ([1,2,3,4,5],\r\n--          [((1,2),12),((1,3),34),((1,5),78),((2,4),55),((2,5),32),\r\n--           ((3,4),61),((3,5),44),((4,5),93),((2,1),12),((3,1),34),\r\n--           ((5,1),78),((4,2),55),((5,2),32),((4,3),61),((5,3),44),\r\n--           ((5,4),93)])\r\n-- ---------------------------------------------------------------------\r\n\r\nejGrafoND :: Grafo Int Int \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-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. Definir, con creaGrafo, la constante \r\n--    ejGrafoD :: Grafo Int Int \r\n-- para representar el grafo anterior donde se considera que las aristas\r\n-- son los pares (x,y) con x < y. Por ejemplo,\r\n--    ghci> ejGrafoD\r\n--    G D ([1,2,3,4,5],\r\n--         [((1,2),12),((1,3),34),((1,5),78),((2,4),55),((2,5),32),\r\n--          ((3,4),61),((3,5),44),((4,5),93)])\r\n-- ---------------------------------------------------------------------\r\n\r\nejGrafoD :: Grafo Int Int\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-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. Definir la funci\u00f3n\r\n--    dirigido :: (Ix v,Num p) => (Grafo v p) -> Bool\r\n-- tal que (dirigido g) se verifica si g es dirigido. Por ejemplo,\r\n--    dirigido ejGrafoD   ==  True\r\n--    dirigido ejGrafoND  ==  False\r\n-- ---------------------------------------------------------------------\r\n\r\ndirigido :: (Ix v,Num p) => (Grafo v p) -> Bool\r\ndirigido (G o _) = o == D\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5. 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 ejGrafoND  ==  [1,2,3,4,5]\r\n--    nodos ejGrafoD   ==  [1,2,3,4,5]\r\n-- ---------------------------------------------------------------------\r\n\r\nnodos :: (Ix v,Num p) => (Grafo v p) -> [v]\r\nnodos (G _ (ns,_)) = ns\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 6. 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 ejGrafoND 4  ==  [5,2,3]\r\n--    adyacentes ejGrafoD  4  ==  [5]\r\n-- ---------------------------------------------------------------------\r\n\r\nadyacentes :: (Ix v, Num p) => Grafo v p -> v -> [v]\r\nadyacentes (G _ (_,e)) v = nub [u | ((w,u),_) <- e, w == v]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 7. 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 ejGrafoND (5,1)  ==  True\r\n--    aristaEn ejGrafoND (4,1)  ==  False\r\n--    aristaEn ejGrafoD  (5,1)  ==  False\r\n--    aristaEn ejGrafoD  (1,5)  ==  True\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 8. 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 ejGrafoND  ==  78\r\n--    peso 1 5 ejGrafoD   ==  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 9. Definir la funci\u00f3n\r\n--    aristas :: (Ix v,Num p) => Grafo v p -> [(v,v,p)]\r\n-- (aristasD 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\n-- ---------------------------------------------------------------------\r\n\r\naristas :: (Ix v,Num p) => Grafo v p -> [(v,v,p)]\r\naristas (G _ (_,g)) = [(v1,v2,p) | ((v1,v2),p) <- g]\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":"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\/3371"}],"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=3371"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/3371\/revisions"}],"predecessor-version":[{"id":3373,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/3371\/revisions\/3373"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=3371"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=3371"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=3371"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}