{"id":4820,"date":"2015-03-23T19:10:47","date_gmt":"2015-03-23T18:10:47","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=4820"},"modified":"2015-03-24T09:12:22","modified_gmt":"2015-03-24T08:12:22","slug":"i1m2014-ejercicios-sobre-la-implementacion-del-tad-de-grafos-mediante-listas","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2014-ejercicios-sobre-la-implementacion-del-tad-de-grafos-mediante-listas\/","title":{"rendered":"I1M2014: Ejercicios sobre la implementaci\u00f3n del TAD de grafos mediante listas"},"content":{"rendered":"<p>En la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-14\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> se ha comentado las soluciones de los ejercicios de la  relaci\u00f3n 24 que consiste en la implementaci\u00f3n del TAD de los grafos mediante lista.<\/p>\n<p>Las soluciones de los ejercicios de la relaci\u00f3n es el siguiente<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\n-- ---------------------------------------------------------------------\n-- Introducci\u00f3n                                                       --\n-- ---------------------------------------------------------------------\n\n-- El objetivo de esta relaci\u00f3n es implementar el TAD de los grafos\n-- mediante listas, de manera an\u00e1loga a las implementaciones estudiadas\n-- en el tema 22 que se encuentran en \n--    http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-14\/temas\/tema-22.pdf\n-- y usando la mismas signatura.\n\n-- ---------------------------------------------------------------------\n-- Signatura                                                          --\n-- ---------------------------------------------------------------------\n\nmodule Rel_24_sol\n    (Orientacion (..),\n     Grafo,\n     creaGrafo,  -- (Ix v,Num p) => Orientacion -> (v,v) -> [(v,v,p)] -> \n                 --                 Grafo v p\n     dirigido,   -- (Ix v,Num p) => (Grafo v p) -> Bool\n     adyacentes, -- (Ix v,Num p) => (Grafo v p) -> v -> [v]\n     nodos,      -- (Ix v,Num p) => (Grafo v p) -> [v]\n     aristas,    -- (Ix v,Num p) => (Grafo v p) -> [(v,v,p)]\n     aristaEn,   -- (Ix v,Num p) => (Grafo v p) -> (v,v) -> Bool\n     peso        -- (Ix v,Num p) => v -> v -> (Grafo v p) -> p\n    ) where\n\n-- ---------------------------------------------------------------------\n-- Librer\u00edas auxiliares                                               --\n-- ---------------------------------------------------------------------\n\nimport Data.Array\nimport Data.List\n\n-- ---------------------------------------------------------------------\n-- Representaci\u00f3n de los grafos mediante listas                       --\n-- ---------------------------------------------------------------------\n\n-- Orientacion es D (dirigida) \u00f3 ND (no dirigida).\ndata Orientacion = D | ND\n                   deriving (Eq, Show)\n\n-- (Grafo v p) es un grafo con v\u00e9rtices de tipo v y pesos de tipo p.\ndata Grafo v p = G Orientacion ([v],[((v,v),p)])\n                 deriving (Eq, Show)\n\n-- ---------------------------------------------------------------------\n-- Ejercicios                                                         --\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1. Definir la funci\u00f3n\n--    creaGrafo :: (Ix v, Num p) => Bool -> (v,v) -> [(v,v,p)] -> Grafo v p\n-- tal que (creaGrafo d cs as) es un grafo (dirigido o no, seg\u00fan el\n-- valor de o), con el par de cotas cs y listas de aristas as (cada\n-- arista es un tr\u00edo formado por los dos v\u00e9rtices y su peso). Por\n-- ejemplo, \n--    ghci> creaGrafo ND (1,3) [(1,2,12),(1,3,34)]\n--    G ND ([1,2,3],[((1,2),12),((1,3),34),((2,1),12),((3,1),34)])\n--    ghci> creaGrafo D (1,3) [(1,2,12),(1,3,34)]\n--    G D ([1,2,3],[((1,2),12),((1,3),34)])\n--    ghci> creaGrafo D (1,4) [(1,2,12),(1,3,34)]\n--    G D ([1,2,3,4],[((1,2),12),((1,3),34)])\n-- ---------------------------------------------------------------------\n\ncreaGrafo :: (Ix v, Num p) => \n             Orientacion -> (v,v) -> [(v,v,p)] -> Grafo v p\ncreaGrafo o cs as = \n    G o (range cs, [((x1,x2),w) | (x1,x2,w) <- as] ++ \n                    if o == D then []\n                    else [((x2,x1),w) | (x1,x2,w) <- as, x1 \/= x2])\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2. Definir, con creaGrafo, la constante \n--    ejGrafoND :: Grafo Int Int \n-- para representar el siguiente grafo no dirigido\n--             12\n--        1 -------- 2\n--        | \\78     \/|\n--        |  \\   32\/ |\n--        |   \\   \/  |\n--      34|     5    |55\n--        |   \/   \\  |\n--        |  \/44   \\ |\n--        | \/     93\\|\n--        3 -------- 4\n--             61\n--    ghci> ejGrafoND\n--    G ND ([1,2,3,4,5],\n--          [((1,2),12),((1,3),34),((1,5),78),((2,4),55),((2,5),32),\n--           ((3,4),61),((3,5),44),((4,5),93),((2,1),12),((3,1),34),\n--           ((5,1),78),((4,2),55),((5,2),32),((4,3),61),((5,3),44),\n--           ((5,4),93)])\n-- ---------------------------------------------------------------------\n\nejGrafoND :: Grafo Int Int \nejGrafoND = creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78),\n                                (2,4,55),(2,5,32),\n                                (3,4,61),(3,5,44),\n                                (4,5,93)]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3. Definir, con creaGrafo, la constante \n--    ejGrafoD :: Grafo Int Int \n-- para representar el grafo anterior donde se considera que las aristas\n-- son los pares (x,y) con x < y. Por ejemplo,\n--    ghci> ejGrafoD\n--    G D ([1,2,3,4,5],\n--         [((1,2),12),((1,3),34),((1,5),78),((2,4),55),((2,5),32),\n--          ((3,4),61),((3,5),44),((4,5),93)])\n-- ---------------------------------------------------------------------\n\nejGrafoD :: Grafo Int Int\nejGrafoD = creaGrafo D (1,5) [(1,2,12),(1,3,34),(1,5,78),\n                              (2,4,55),(2,5,32),\n                              (3,4,61),(3,5,44),\n                              (4,5,93)]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4. Definir la funci\u00f3n\n--    dirigido :: (Ix v,Num p) => (Grafo v p) -> Bool\n-- tal que (dirigido g) se verifica si g es dirigido. Por ejemplo,\n--    dirigido ejGrafoD   ==  True\n--    dirigido ejGrafoND  ==  False\n-- ---------------------------------------------------------------------\n\ndirigido :: (Ix v,Num p) => (Grafo v p) -> Bool\ndirigido (G o _) = o == D\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5. Definir la funci\u00f3n\n--    nodos :: (Ix v,Num p) => (Grafo v p) -> [v]\n-- tal que (nodos g) es la lista de todos los nodos del grafo g. Por\n-- ejemplo, \n--    nodos ejGrafoND  ==  [1,2,3,4,5]\n--    nodos ejGrafoD   ==  [1,2,3,4,5]\n-- ---------------------------------------------------------------------\n\nnodos :: (Ix v,Num p) => (Grafo v p) -> [v]\nnodos (G _ (ns,_)) = ns\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6. Definir la funci\u00f3n\n--    adyacentes :: (Ix v, Num p) => Grafo v p -> v -> [v]\n-- tal que (adyacentes g v) es la lista de los v\u00e9rtices adyacentes al\n-- nodo v en el grafo g. Por ejemplo,\n--    adyacentes ejGrafoND 4  ==  [5,2,3]\n--    adyacentes ejGrafoD  4  ==  [5]\n-- ---------------------------------------------------------------------\n\nadyacentes :: (Ix v, Num p) => Grafo v p -> v -> [v]\nadyacentes (G _ (_,e)) v = nub [u | ((w,u),_) <- e, w == v]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7. Definir la funci\u00f3n\n--    aristaEn :: (Ix v,Num p) => Grafo v p -> (v,v) -> Bool\n-- (aristaEn g a) se verifica si a es una arista del grafo g. Por\n-- ejemplo,\n--    aristaEn ejGrafoND (5,1)  ==  True\n--    aristaEn ejGrafoND (4,1)  ==  False\n--    aristaEn ejGrafoD  (5,1)  ==  False\n--    aristaEn ejGrafoD  (1,5)  ==  True\n-- ---------------------------------------------------------------------\n\naristaEn :: (Ix v,Num p) => Grafo v p -> (v,v) -> Bool\naristaEn g (x,y) = y `elem` adyacentes g x\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 8. Definir la funci\u00f3n\n--    peso :: (Ix v,Num p) => v -> v -> Grafo v p -> p\n-- tal que (peso v1 v2 g) es el peso de la arista que une los v\u00e9rtices\n-- v1 y v2 en el grafo g. Por ejemplo,\n--    peso 1 5 ejGrafoND  ==  78\n--    peso 1 5 ejGrafoD   ==  78\n-- ---------------------------------------------------------------------\n\npeso :: (Ix v,Num p) => v -> v -> Grafo v p -> p\npeso x y (G _ (_,gs)) = head [c | ((x',y'),c) <- gs, x==x', y==y']\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9. Definir la funci\u00f3n\n--    aristas :: (Ix v,Num p) => Grafo v p -> [(v,v,p)]\n-- (aristasD g) es la lista de las aristas del grafo g. Por ejemplo, \n--    ghci> aristas ejGrafoD\n--    [(1,2,12),(1,3,34),(1,5,78),(2,4,55),(2,5,32),(3,4,61),\n--     (3,5,44),(4,5,93)] \n--    ghci> aristas ejGrafoND\n--    [(1,2,12),(1,3,34),(1,5,78),(2,1,12),(2,4,55),(2,5,32),\n--     (3,1,34),(3,4,61),(3,5,44),(4,2,55),(4,3,61),(4,5,93),\n--     (5,1,78),(5,2,32),(5,3,44),(5,4,93)]\n-- ---------------------------------------------------------------------\n\naristas :: (Ix v,Num p) => Grafo v p -> [(v,v,p)]\naristas (G _ (_,g)) = [(v1,v2,p) | ((v1,v2),p) <- g]\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas se ha comentado las soluciones de los ejercicios de la relaci\u00f3n 24 que consiste en la implementaci\u00f3n del TAD de los grafos mediante lista. Las soluciones de los ejercicios de la relaci\u00f3n es el siguiente<\/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":[238],"tags":[270,305],"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\/4820"}],"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=4820"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4820\/revisions"}],"predecessor-version":[{"id":4822,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4820\/revisions\/4822"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=4820"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=4820"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=4820"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}