{"id":8220,"date":"2023-06-21T06:00:34","date_gmt":"2023-06-21T04:00:34","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=8220"},"modified":"2023-06-14T13:07:46","modified_gmt":"2023-06-14T11:07:46","slug":"21-jun-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/21-jun-23\/","title":{"rendered":"TAD de los grafos: Nodos conectados en un grafo"},"content":{"rendered":"<p>Usando el <a href=\"https:\/\/bit.ly\/45cQ3Fo\">tipo abstracto de datos de los grafos<\/a>, definir la funci\u00f3n,<\/p>\n<pre lang=\"text\">\n   conectados :: Grafo Int Int -> Int -> Int -> Bool\n<\/pre>\n<p>tal que <code>conectados g v1 v2<\/code> se verifica si los v\u00e9rtices <code>v1<\/code> y <code>v2<\/code> est\u00e1n conectados en el grafo <code>g<\/code>. Por ejemplo, si grafo1 es el grafo definido por<\/p>\n<pre lang=\"text\">\n   grafo1 :: Grafo Int Int\n   grafo1 = creaGrafo' D (1,6) [(1,3),(1,5),(3,5),(5,1),(5,50),\n                                (2,4),(2,6),(4,6),(4,4),(6,4)]\n<\/pre>\n<p>entonces,<\/p>\n<pre lang=\"text\">\n   conectados grafo1 1 3  ==  True\n   conectados grafo1 1 4  ==  False\n   conectados grafo1 6 2  ==  False\n   conectados grafo1 3 1  ==  True\n<\/pre>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nmodule Grafo_Nodos_conectados_en_un_grafo where\n\nimport TAD.Grafo (Grafo, Orientacion (D, ND), adyacentes, creaGrafo')\nimport Data.List (union)\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\nconectados :: Grafo Int Int -> Int -> Int -> Bool\nconectados g v1 v2 = v2 `elem` conectadosAux g [] [v1]\n\nconectadosAux :: Grafo Int Int -> [Int] -> [Int] -> [Int]\nconectadosAux _ vs [] = vs\nconectadosAux g vs (w:ws)\n  | w `elem` vs = conectadosAux g vs ws\n  | otherwise = conectadosAux g ([w] `union` vs) (ws `union` adyacentes g w)\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    conectados grafo1 1 3  `shouldBe`  True\n  it \"e2\" $\n    conectados grafo1 1 4  `shouldBe`  False\n  it \"e3\" $\n    conectados grafo1 6 2  `shouldBe`  False\n  it \"e4\" $\n    conectados grafo1 3 1  `shouldBe`  True\n  it \"e5\" $\n    conectados grafo2 1 3  `shouldBe`  True\n  it \"e6\" $\n    conectados grafo2 1 4  `shouldBe`  False\n  it \"e7\" $\n    conectados grafo2 6 2  `shouldBe`  True\n  it \"e8\" $\n    conectados grafo2 3 1  `shouldBe`  True\n  where\n    grafo1, grafo2 :: Grafo Int Int\n    grafo1 = creaGrafo' D (1,6) [(1,3),(1,5),(3,5),(5,1),(5,50),\n                                 (2,4),(2,6),(4,6),(4,4),(6,4)]\n\n    grafo2 = creaGrafo' ND (1,6) [(1,3),(1,5),(3,5),(5,1),(5,50),\n                                  (2,4),(2,6),(4,6),(4,4),(6,4)]\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--    e2\n--    e3\n--    e4\n--    e5\n--    e6\n--    e7\n--    e8\n--\n--    Finished in 0.0032 seconds\n--    8 examples, 0 failures\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom src.TAD.Grafo import Grafo, Orientacion, Vertice, adyacentes, creaGrafo_\n\n\ndef unionV(xs: list[Vertice], ys: list[Vertice]) -> list[Vertice]:\n    return list(set(xs) | set(ys))\n\ndef conectadosAux(g: Grafo, vs: list[Vertice], ws: list[Vertice]) -> list[Vertice]:\n    if not ws:\n        return vs\n    w, *ws = ws\n    if w in vs:\n        return conectadosAux(g, vs, ws)\n    return conectadosAux(g, unionV([w], vs), unionV(ws, adyacentes(g, w)))\n\ndef conectados(g: Grafo, v1: Vertice, v2: Vertice) -> bool:\n    return v2 in conectadosAux(g, [], [v1])\n\n\n# Verificaci\u00f3n\n# ============\n\ndef test_conectados() -> None:\n    grafo1 = creaGrafo_(Orientacion.D,\n                        (1,6),\n                        [(1,3),(1,5),(3,5),(5,1),(5,50),\n                         (2,4),(2,6),(4,6),(4,4),(6,4)])\n    grafo2 = creaGrafo_(Orientacion.ND,\n                        (1,6),\n                        [(1,3),(1,5),(3,5),(5,1),(5,50),\n                         (2,4),(2,6),(4,6),(4,4),(6,4)])\n    assert conectados(grafo1, 1, 3)\n    assert not conectados(grafo1, 1, 4)\n    assert not conectados(grafo1, 6, 2)\n    assert conectados(grafo1, 3, 1)\n    assert conectados(grafo2, 1, 3)\n    assert not conectados(grafo2, 1, 4)\n    assert conectados(grafo2, 6, 2)\n    assert conectados(grafo2, 3, 1)\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_conectados()\n#    Verificado\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Usando el tipo abstracto de datos de los grafos, definir la funci\u00f3n, conectados :: Grafo Int Int -> Int -> Int -> Bool tal que conectados g v1 v2 se verifica si los v\u00e9rtices v1 y v2 est\u00e1n conectados en el grafo g. Por ejemplo, si grafo1 es el grafo definido por grafo1 :: Grafo&#8230;<\/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":[581],"tags":[453],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8220"}],"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=8220"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8220\/revisions"}],"predecessor-version":[{"id":8221,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8220\/revisions\/8221"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=8220"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=8220"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=8220"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}