{"id":4809,"date":"2015-03-18T18:54:02","date_gmt":"2015-03-18T17:54:02","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=4809"},"modified":"2015-03-19T18:55:37","modified_gmt":"2015-03-19T17:55:37","slug":"i1m2014-implementacion-en-haskell-de-los-algoritmos-de-kruskal-y-de-prim","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2014-implementacion-en-haskell-de-los-algoritmos-de-kruskal-y-de-prim\/","title":{"rendered":"I1M2014: Implementaci\u00f3n en Haskell de los algoritmos de Kruskal y de Prim"},"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>hemos estudiado la implementaci\u00f3n en Haskell de los algoritmos de Kruskal y de Prim para calcular los \u00e1rboles de expansi\u00f3n m\u00ednimo.<\/p>\n<p>Las transparencias usadas en la clase son las p\u00e1ginas 44-57 <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-14\/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 se muestra a continuaci\u00f3n<\/p>\n<pre lang=\"haskell\">\n-- ---------------------------------------------------------------------\n-- Importaciones                                                      --\n-- ---------------------------------------------------------------------\n\nimport Data.List\nimport Data.Ix\nimport I1M.Grafo -- Se instala con http:\/\/bit.ly\/1AKmUQB \nimport I1M.Tabla -- Se instala con http:\/\/bit.ly\/1AKmUQB \n\n-- ---------------------------------------------------------------------\n-- Ejemplos                                                           --\n-- ---------------------------------------------------------------------\n\ng1 :: Grafo Int Int    \ng1 = 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\ng2 :: Grafo Int Int    \ng2 = creaGrafo D (1,5) [(1,2,13),(1,3,11),(1,5,78),\n                        (2,4,12),(2,5,32),\n                        (3,4,14),(3,5,44),\n                        (4,5,93)]\n\ng3 = creaGrafo D (1,7) [(1,2,1),(1,4,4),\n                        (2,3,2),(2,4,6),(2,5,4),\n                        (3,5,5),(3,6,6),\n                        (4,5,3),(4,7,4),\n                        (5,6,8),(5,7,7),\n                        (6,7,3)] \n\n-- ---------------------------------------------------------------------\n-- Algoritmo de Kruskal                                               --\n-- ---------------------------------------------------------------------\n\n-- (kruskal g) es el \u00e1rbol de expansi\u00f3n m\u00ednimo del grafo g calculado\n-- mediante el algoritmo de Kruskal. Por ejemplo,\n--    kruskal g1  ==  [(55,2,4),(34,1,3),(32,2,5),(12,1,2)]\n--    kruskal g2  ==  [(32,2,5),(13,1,2),(12,2,4),(11,1,3)]\n--    kruskal g3  ==  [(4,4,7),(4,1,4),(3,6,7),(3,4,5),(2,2,3),(1,1,2)]\nkruskal :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)]\nkruskal g = kruskal' cola                      -- Cola de prioridad\n                     (tabla [(x,x) | x <- ns]) -- Tabla de raices\n                     []                        -- \u00c1rbol de expansi\u00f3n\n                     (length ns - 1)           -- Aristas por colocar\n    where ns   = nodos g\n          cola = sort [(p,x,y) | (x,y,p) <- aristas g]\n\nkruskal' ((p,x,y):as) t ae n \n    | n == 0      = ae\n    | actualizado = kruskal' as t' ((p,x,y):ae) (n-1)\n    | otherwise   = kruskal' as t  ae           n\n    where (actualizado,t') = buscaActualiza (x,y) t\n\n-- (buscaActualiza a t) es el par formado por False y la tabla t, si los\n-- dos v\u00e9rtices de la arista a tienen la misma ra\u00edz en t y el par\n-- formado por True y la tabla obtenida a\u00f1adi\u00e9ndole a t la arista\n-- formada por el v\u00e9rtice de a de mayor ra\u00edz y la ra\u00edz del v\u00e9rtice de\n-- a de menor ra\u00edz. Por ejemplo,\n--    ghci> let t = crea [(1,1),(2,2),(3,1),(4,1)]\n--    ghci> buscaActualiza (2,3) t\n--    (True,Tbl [(1,1),(2,1),(3,1),(4,1)])\n--    ghci> buscaActualiza (3,4) t\n--    (False,Tbl [(1,1),(2,2),(3,1),(4,1)])\nbuscaActualiza :: (Eq n, Ord n) => (n,n) -> Tabla n n -> (Bool,Tabla n n)\nbuscaActualiza (x,y) t \n    | x' == y'  = (False, t) \n    | y' <  x'  = (True, modifica (x,y') t)\n    | otherwise = (True, modifica (y,x') t)\n    where x' = raiz t x \n          y' = raiz t y\n\n-- (raiz t n) es la ra\u00edz de n en la tabla t. Por ejemplo,\n--    raiz (crea [(1,1),(3,1),(4,3),(5,4),(2,6),(6,6)]) 5  == 1\n--    raiz (crea [(1,1),(3,1),(4,3),(5,4),(2,6),(6,6)]) 2  == 6\nraiz:: Eq n => Tabla n n -> n -> n\nraiz t x | v == x    = v\n         | otherwise = raiz t v\n         where v = valor t x\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Ejemplos de Kruskal                                              --\n-- ---------------------------------------------------------------------\n\n-- cola = [(12,1,2),(32,2,5),(34,1,3),(44,3,5),(55,2,4),(61,3,4),(78,1,5),(93,4,5)]\n-- t    = Tbl [(1,1),(2,2),(3,3),(4,4),(5,5)]\n-- ae   = []\n-- n    = 4\n--\n-- cola = [(32,2,5),(34,1,3),(44,3,5),(55,2,4),(61,3,4),(78,1,5),(93,4,5)]\n-- t    = Tbl [(1,1),(2,1),(3,3),(4,4),(5,5)]\n-- ae   = [(12,1,2)]\n-- n    = 3\n--\n-- cola = [(34,1,3),(44,3,5),(55,2,4),(61,3,4),(78,1,5),(93,4,5)]\n-- t    = Tbl [(1,1),(2,1),(3,3),(4,4),(5,1)]\n-- ae   = [(32,2,5),(12,1,2)]\n-- n    = 2\n--\n-- cola = [(44,3,5),(55,2,4),(61,3,4),(78,1,5),(93,4,5)]\n-- t    = Tbl [(1,1),(2,1),(3,1),(4,4),(5,1)]\n-- ae   = [(34,1,3),(32,2,5),(12,1,2)]\n-- n    = 1\n--\n-- cola = [(55,2,4),(61,3,4),(78,1,5),(93,4,5)]\n-- t    = Tbl [(1,1),(2,1),(3,1),(4,4),(5,1)]\n-- ae   = [(34,1,3),(32,2,5),(12,1,2)]\n-- n    = 1\n--\n-- cola = [(61,3,4),(78,1,5),(93,4,5)]\n-- t    = Tbl [(1,1),(2,1),(3,1),(4,1),(5,1)]\n-- ae   = [(55,2,4),(34,1,3),(32,2,5),(12,1,2)]\n-- n    = 0\n\n-- ---------------------------------------------------------------------\n-- El algoritmo de Prim                                                  --\n-- ---------------------------------------------------------------------\n\n-- (prim g) es el \u00e1rbol de expansi\u00f3n m\u00ednimo del grafo g calculado\n-- mediante el algoritmo de Prim. Por ejemplo,\n--    prim g1  ==  [(55,2,4),(34,1,3),(32,2,5),(12,1,2)]\n--    prim g2  ==  [(32,2,5),(12,2,4),(13,1,2),(11,1,3)]\nprim :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)]\nprim g = prim' [n]              -- Nodos colocados\n               ns               -- Nodos por colocar \n               []               -- \u00c1rbol de expansi\u00f3n\n               (aristas g)      -- Aristas del grafo\n         where (n:ns) = nodos g\n\nprim' t [] ae as = ae\nprim' t r  ae as = prim' (v':t) (delete v' r) (e:ae) as\n    where e@(c,u', v') = minimum [(c,u,v)| (u,v,c) <- as,\n                                           elem u t, \n                                           elem v r]\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticashemos estudiado la implementaci\u00f3n en Haskell de los algoritmos de Kruskal y de Prim para calcular los \u00e1rboles de expansi\u00f3n m\u00ednimo. Las transparencias usadas en la clase son las p\u00e1ginas 44-57 tema 22.<\/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":[244,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\/4809"}],"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=4809"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4809\/revisions"}],"predecessor-version":[{"id":4810,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4809\/revisions\/4810"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=4809"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=4809"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=4809"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}