{"id":3355,"date":"2013-05-20T16:11:56","date_gmt":"2013-05-20T16:11:56","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=3355"},"modified":"2013-05-22T06:52:18","modified_gmt":"2013-05-22T06:52:18","slug":"i1m2012-el-tad-de-los-grafos-y-su-implemntacion-en-haskell-mediante-vectores-de-adyacencia","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2012-el-tad-de-los-grafos-y-su-implemntacion-en-haskell-mediante-vectores-de-adyacencia\/","title":{"rendered":"I1M2012: El TAD de los grafos y su implementaci\u00f3n en Haskell mediante vectores de adyacencia"},"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 estudiado el tipo abstracto de los grafos y su implementaci\u00f3n en Haskell mediante vectores de adyacencia.<\/p>\n<p>Las transparencias usadas en la clase son las p\u00e1ginas 1-18 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 correspondiente es<\/p>\n<pre lang=\"haskell\">\r\nmodule GrafoConVectorDeAdyacencia \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,p)])\r\n                 deriving (Eq, Show)\r\n\r\n-- (creaGrafo o 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 vs =\r\n    G o (accumArray \r\n         (\\xs x -> xs++[x]) [] cs \r\n         ((if o == 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-- 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 un vector de adyacencia; es decir,\r\n--    ghci> ejGrafoND\r\n--    G ND 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\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,5) [(1,[(2,12),(3,34),(5,78)]),\r\n--                     (2,[(4,55),(5,32)]),\r\n--                     (3,[(4,61),(5,44)]),\r\n--                     (4,[(5,93)]),\r\n--                     (5,[])])\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) = indices 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 _ g) v = map fst (g!v)\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\n--    aristaEn ejGrafoD (5,1)   ==  False\r\n--    aristaEn ejGrafoD (1,5)   ==  True\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-- (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) = head [c | (a,c) <- g!x , a == 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 o g) = [(v1,v2,w) | v1 <- nodos (G o g) , (v2,w) <- g!v1] \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 el tipo abstracto de los grafos y su implementaci\u00f3n en Haskell mediante vectores de adyacencia. Las transparencias usadas en la clase son las p\u00e1ginas 1-18 del tema 22:<\/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\/3355"}],"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=3355"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/3355\/revisions"}],"predecessor-version":[{"id":3361,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/3355\/revisions\/3361"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=3355"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=3355"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=3355"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}