Un ciclo en un grafo G es una secuencia [v(1),v(2),v(3),…,v(n)] de nodos de G tal que:<\/p>\n
Definir la funci\u00f3n<\/p>\n
\n ciclos :: Grafo Int Int -> [[Int]]\n<\/pre>\ntal que (ciclos g) es la lista de ciclos de g. Por ejemplo, si g1 y g2 son los grafos definidos por<\/p>\n
\n g1, g2 :: Grafo Int Int\n g1 = creaGrafo D (1,4) [(1,2,0),(2,3,0),(2,4,0),(4,1,0)]\n g2 = creaGrafo D (1,4) [(1,2,0),(2,1,0),(2,4,0),(4,1,0)]\n<\/pre>\nentonces<\/p>\n
\n ciclos g1 == [[1,2,4,1],[2,4,1,2],[4,1,2,4]]\n ciclos g2 == [[1,2,1],[1,2,4,1],[2,1,2],[2,4,1,2],[4,1,2,4]]\n<\/pre>\nNota: Este ejercicio debe realizarse usando \u00fanicamente las funciones de la librer\u00eda de grafos (I1M.Grafo) que se describe aqu\u00ed<\/a> y se encuentra aqu\u00ed<\/a>.<\/p>\nSoluciones<\/h4>\n\nimport Data.List (nub, subsequences, permutations, sort)\nimport I1M.Grafo\n\n-- 1\u00aa definici\u00f3n (por fuerza bruta)\n-- ================================\n\nciclos1 :: Grafo Int Int -> [[Int]]\nciclos1 g = \n sort [ys | (x:xs) <- concatMap permutations (subsequences (nodos g)) \n , let ys = (x:xs) ++ [x]\n , esCiclo ys g]\n\n-- (esCiclo vs g) se verifica si vs es un ciclo en el grafo g. Por\n-- ejemplo, \nesCiclo :: [Int] -> Grafo Int Int -> Bool\nesCiclo vs g = \n all (aristaEn g) (zip vs (tail vs)) &&\n head vs == last vs &&\n length (nub vs) == length vs - 1 \n\n-- 2\u00aa definici\u00f3n\n-- =============\n\nciclos2 :: Grafo Int Int -> [[Int]]\nciclos2 g = sort [ys | (x:xs) <- caminos g\n , let ys = (x:xs) ++ [x]\n , esCiclo ys g]\n\n-- (caminos g) es la lista de los caminos en el grafo g. Por ejemplo,\n-- caminos g1 == [[1,2,3],[1,2,4],[2,3],[2,4,1],[3],[4,1,2,3]]\ncaminos :: Grafo Int Int -> [[Int]]\ncaminos g = concatMap (caminosDesde g) (nodos g)\n\n-- (caminosDesde g v) es la lista de los caminos en el grafo g a partir\n-- del v\u00e9rtice v. Por ejemplo,\n-- caminosDesde g1 1 == [[1],[1,2],[1,2,3],[1,2,4]]\n-- caminosDesde g1 2 == [[2],[2,3],[2,4],[2,4,1]]\n-- caminosDesde g1 3 == [[3]]\n-- caminosDesde g1 4 == [[4],[4,1],[4,1,2],[4,1,2,3]]\ncaminosDesde :: Grafo Int Int -> Int -> [[Int]]\ncaminosDesde g v = \n map (reverse . fst) $\n concat $ \n takeWhile (not.null) (iterate (concatMap sucesores) [([v],[v])])\n where sucesores (x:xs,ys) = [(z:x:xs,z:ys) | z <- adyacentes g x\n , z `notElem` ys]\n\n-- 3\u00aa soluci\u00f3n (Pedro Mart\u00edn)\n-- ==========================\n\nciclos3 :: Grafo Int Int -> [[Int]]\nciclos3 g = concat [aux [n] (adyacentes g n) | n <- nodos g] where \n aux _ [] = []\n aux xs (y:ys)\n | notElem y xs = aux (xs ++ [y]) (adyacentes g y) ++ aux xs ys\n | y == head xs = (xs ++ [y]) : aux xs ys\n | otherwise = aux xs ys\n\n-- 4\u00aa soluci\u00f3n (Chema Cort\u00e9s)\n-- ==========================\n\nciclos4 :: Grafo Int Int -> [[Int]]\nciclos4 g = concat [ caminos a a [] | a <- nodos g ] where\n -- caminos posibles de b hasta a, sin pasar dos veces por un mismo nodo\n caminos a b vs\n | a == b && (not.null) vs = [[b]]\n | otherwise = [ b:xs | c <- adyacentes g b\n , c `notElem` vs\n , xs <- caminos a c (c:vs)]\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- ghci> let ejemplo n = creaGrafo D (1,n) ((n,1,0) : [(i,i+1,0) | i <- [1..n-1]])\n-- \n-- ghci> length (ciclos1 (ejemplo 9))\n-- 9\n-- (4.92 secs, 1371229152 bytes)\n--\n-- ghci> length (ciclos2 (ejemplo 9))\n-- 9\n-- (0.01 secs, 2577736 bytes)\n-- \n-- ghci> length (ciclos3 (ejemplo 9))\n-- 9\n-- (0.01 secs, 1038932 bytes)\n-- \n-- ghci> length (ciclos4 (ejemplo 9))\n-- 9\n-- (0.01 secs, 2589288 bytes)\n-- \n-- ghci> length (ciclos2 (ejemplo 400))\n-- 400\n-- (11.74 secs, 5148997000 bytes)\n-- \n-- ghci> length (ciclos3 (ejemplo 400))\n-- 400\n-- (4.99 secs, 936520100 bytes)\n-- \n-- ghci> length (ciclos4 (ejemplo 400))\n-- 400\n-- (1.56 secs, 66701772 bytes)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"Un ciclo en un grafo G es una secuencia [v(1),v(2),v(3),…,v(n)] de nodos de G tal que: (v(1),v(2)), (v(2),v(3)), (v(3),v(4)), …, (v(n-1),v(n)) son aristas de G, v(1) = v(n), y salvo v(1) = v(n), todos los v(i) son distintos entre s\u00ed. Definir la funci\u00f3n ciclos :: Grafo Int Int -> [[Int]] tal que (ciclos g) es…<\/p>\n","protected":false},"author":1,"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":[7],"tags":[498,453],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/1463"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=1463"}],"version-history":[{"count":8,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/1463\/revisions"}],"predecessor-version":[{"id":1518,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/1463\/revisions\/1518"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=1463"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=1463"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=1463"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}