{"id":7940,"date":"2023-05-27T16:52:43","date_gmt":"2023-05-27T14:52:43","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=7940"},"modified":"2023-05-27T16:52:43","modified_gmt":"2023-05-27T14:52:43","slug":"27-may-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/27-may-23\/","title":{"rendered":"La semana en Exercitium (27 de mayo de 2023)"},"content":{"rendered":"<p>Esta semana he publicado en <a href=\"http:\/\/bit.ly\/2sqPtGs\">Exercitium<\/a> las soluciones de los siguientes problemas:<\/p>\n<ul>\n<li><a href=\"#ej1\">1. TAD de los polinomios: Factorizaci\u00f3n de un polinomio<\/a><\/li>\n<li><a href=\"#ej2\">2. El tipo abstracto de datos de los grafos<\/a><\/li>\n<li><a href=\"#ej3\">3. TAD de los grafos: Grafos completos<\/a><\/li>\n<li><a href=\"#ej4\">4. TAD de los grafos: Grafos ciclos<\/a><\/li>\n<li><a href=\"#ej5\">5. TAD de los grafos: N\u00famero de v\u00e9rtices<\/a><\/li>\n<\/ul>\n<p>A continuaci\u00f3n se muestran las soluciones.<br \/>\n<!--more--><br \/>\n<a name=\"ej1\"><\/a><\/p>\n<h3>1. TAD de los polinomios: Factorizaci\u00f3n de un polinomio<\/h3>\n<p>Usando el <a href=\"https:\/\/bit.ly\/3KwqXYu\">tipo abstracto de los polinomios<\/a>, definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   factorizacion :: Polinomio Int -> [Polinomio Int]\n<\/pre>\n<p>tal que <code>factorizacion p<\/code> es la lista de la descomposici\u00f3n del polinomio <code>p<\/code> en factores obtenida mediante el regla de Ruffini. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> ejPol1 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))\n   \u03bb> ejPol1\n   x^5 + 5*x^2 + 4*x\n   \u03bb> factorizacion ejPol1\n   [1*x,1*x + 1,x^3 + -1*x^2 + 1*x + 4]\n   \u03bb> ejPol2 = consPol 3 1 (consPol 2 2 (consPol 1 (-1) (consPol 0 (-2) polCero)))\n   \u03bb> ejPol2\n   x^3 + 2*x^2 + -1*x + -2\n   \u03bb> factorizacion ejPol2\n   [1*x + -1,1*x + 1,1*x + 2,1]\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 Pol_Factorizacion_de_un_polinomio where\n\nimport TAD.Polinomio (Polinomio, consPol, polCero, esPolCero)\nimport Pol_Termino_independiente_de_un_polinomio (terminoIndep)\nimport Pol_Raices_enteras_de_un_polinomio (divisores)\nimport Pol_Regla_de_Ruffini (cocienteRuffini)\nimport Pol_Reconocimiento_de_raices_por_la_regla_de_Ruffini (esRaizRuffini)\nimport Pol_Transformaciones_polinomios_densas (densaApolinomio)\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\nfactorizacion :: Polinomio Int -> [Polinomio Int]\nfactorizacion p\n  | esPolCero p = [p]\n  | otherwise   = aux (0 : divisores (terminoIndep p))\n  where\n    aux [] = [p]\n    aux (r:rs)\n        | esRaizRuffini r p =\n            densaApolinomio [1,-r] : factorizacion (cocienteRuffini r p)\n        | otherwise = aux rs\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    map show (factorizacion ejPol1)\n      `shouldBe` [\"1*x\",\"1*x + 1\",\"x^3 + -1*x^2 + 1*x + 4\"]\n  it \"e2\" $\n    map show (factorizacion ejPol2)\n      `shouldBe` [\"1*x + -1\",\"1*x + 1\",\"1*x + 2\",\"1\"]\n  where\n    ejPol1 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))\n    ejPol2 = consPol 3 1 (consPol 2 2 (consPol 1 (-1) (consPol 0 (-2) polCero)))\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--    e2\n--\n--    Finished in 0.0015 seconds\n--    2 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.Pol_Raices_enteras_de_un_polinomio import divisores\nfrom src.Pol_Reconocimiento_de_raices_por_la_regla_de_Ruffini import \\\n    esRaizRuffini\nfrom src.Pol_Regla_de_Ruffini import cocienteRuffini\nfrom src.Pol_Termino_independiente_de_un_polinomio import terminoIndep\nfrom src.Pol_Transformaciones_polinomios_densas import densaApolinomio\nfrom src.TAD.Polinomio import Polinomio, consPol, esPolCero, polCero\n\n\ndef factorizacion(p: Polinomio[int]) -> list[Polinomio[int]]:\n    def aux(xs: list[int]) -> list[Polinomio[int]]:\n        if not xs:\n            return [p]\n        r, *rs = xs\n        if esRaizRuffini(r, p):\n            return [densaApolinomio([1, -r])] + factorizacion(cocienteRuffini(r, p))\n        return aux(rs)\n\n    if esPolCero(p):\n        return [p]\n    return aux([0] + divisores(terminoIndep(p)))\n\n# Verificaci\u00f3n\n# ============\n\ndef test_factorizacion() -> None:\n    ejPol1 = consPol(5, 1, consPol(2, 5, consPol(1, 4, polCero())))\n    assert list(map(str, factorizacion(ejPol1))) \\\n        == [\"1*x\", \"1*x + 1\", \"x^3 + -1*x^2 + 1*x + 4\"]\n    ejPol2 = consPol(3, 1, consPol(2, 2, consPol(1, -1, consPol(0, -2, polCero()))))\n    assert list(map(str, factorizacion(ejPol2))) \\\n        == [\"1*x + -1\", \"1*x + 1\", \"1*x + 2\", \"1\"]\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_factorizacion()\n#    Verificado\n<\/pre>\n<p><a name=\"ej2\"><\/a><\/p>\n<h3>2. El tipo abstracto de datos de los grafos<\/h3>\n<h4>2.1. El tipo abstracto de datos de los grafos<\/h4>\n<p>Un grafo es una estructura que consta de un conjunto de v\u00e9rtices y un conjunto de aristas que conectan los v\u00e9rtices entre s\u00ed. Cada v\u00e9rtice representa una entidad o un elemento, y cada arista representa una relaci\u00f3n o conexi\u00f3n entre dos v\u00e9rtices.<\/p>\n<p>Por ejemplo,<\/p>\n<pre lang=\"text\">\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<\/pre>\n<p>representa un grafo no dirigido, lo que significa que las aristas  tienen una direcci\u00f3n espec\u00edfica. Cada arista tiene un peso asociado, que puede representar una medida o una valoraci\u00f3n de la relaci\u00f3n entre los v\u00e9rtices que conecta.<\/p>\n<p>El grafo consta de cinco v\u00e9rtices numerados del 1 al 5. Las aristas especificadas en la lista indican las conexiones entre los v\u00e9rtices y sus respectivos pesos. Por ejemplo, la arista (1,2,12) indica que existe una conexi\u00f3n entre el v\u00e9rtice 1 y el v\u00e9rtice 2 con un peso de 12.<\/p>\n<p>En el grafo representado, se pueden observar las conexiones entre los v\u00e9rtices de la siguiente manera:<\/p>\n<ul>\n<li>El v\u00e9rtice 1 est\u00e1 conectado con el v\u00e9rtice 2 (peso 12), el v\u00e9rtice 3 (peso 34) y el v\u00e9rtice 5 (peso 78).<\/li>\n<li>El v\u00e9rtice 2 est\u00e1 conectado con el v\u00e9rtice 4 (peso 55) y el v\u00e9rtice 5 (peso 32).<\/li>\n<li>El v\u00e9rtice 3 est\u00e1 conectado con el v\u00e9rtice 4 (peso 61) y el v\u00e9rtice 5 (peso 44).<\/li>\n<li>El v\u00e9rtice 4 est\u00e1 conectado con el v\u00e9rtice 5 (peso 93).<\/li>\n<\/ul>\n<p>Las operaciones del tipo abstracto de datos (TAD) de los grafos son<\/p>\n<pre lang=\"text\">\n   creaGrafo  :: (Ix v, Num p, Ord v, Ord p) =>\n                  Orientacion -> (v,v) -> [(v,v,p)] -> Grafo v p\n   creaGrafo' :: (Ix v, Num p, Ord v, Ord p) =>\n                  Orientacion -> (v,v) -> [(v,v)] -> 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<\/pre>\n<p>tales que<br \/>\n+ <code>creaGrafo o cs as<\/code> es un grafo (dirigido o no, seg\u00fan el  de <code>o<\/code>), con el par de cotas <code>cs<\/code> y listas de aristas <code>as<\/code> (cada arista es un tr\u00edo formado por los dos v\u00e9rtices y su peso).<br \/>\n+ <code>creaGrafo'<\/code> es la versi\u00f3n de creaGrafo para los grafos sin pesos.<br \/>\n+ <code>dirigido g<\/code> se verifica si <code>g<\/code> es dirigido.<br \/>\n+ <code>nodos g<\/code> es la lista de todos los nodos del grafo <code>g<\/code>.<br \/>\n+ <code>aristas g<\/code> es la lista de las aristas del grafo <code>g<\/code>.<br \/>\n+ <code>adyacentes g v<\/code> es la lista de los v\u00e9rtices adyacentes al nodo <code>v<\/code> en el grafo <code>g<\/code>.<br \/>\n+ <code>aristaEn g a<\/code> se verifica si <code>a<\/code> es una arista del grafo <code>g<\/code>.<br \/>\n+ <code>peso v1 v2 g<\/code> es el peso de la arista que une los v\u00e9rtices <code>v1<\/code> y <code>v2<\/code> en el grafo <code>g<\/code>.<\/p>\n<p>Usando el TAD de los grafos, el grafo anterior se puede definir por<\/p>\n<pre lang=\"text\">\n   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<\/pre>\n<p>con los siguientes argumentos:<\/p>\n<ul>\n<li>ND: Es un par\u00e1metro de tipo Orientacion que indica si el  es dirigido o no. En este caso, se utiliza ND, lo que significa &#8220;no dirigido&#8221;. Por lo tanto, el grafo creado ser\u00e1 no dirigido, lo que implica que las aristas no tienen una direcci\u00f3n espec\u00edfica.<\/li>\n<li>(1,5): Es el par de cotas que define los v\u00e9rtices del grafo. En este caso, el grafo tiene v\u00e9rtices numerados desde 1 hasta 5.<\/li>\n<li>[(1,2,12),(1,3,34),(1,5,78),(2,4,55),(2,5,32),(3,4,61),(3,5,44),(4,5,93)]: Es una lista de aristas, donde cada arista est\u00e1 representada por un tr\u00edo de valores. Cada tr\u00edo contiene los dos v\u00e9rtices que est\u00e1n conectados por la arista y el peso de dicha arista.<\/li>\n<\/ul>\n<p>Para usar el TAD hay que usar una implementaci\u00f3n concreta. En principio, consideraremos las siguientes:<br \/>\n+ mediante lista de adyacencia,<br \/>\n+ mediante vector de adyacencia y<br \/>\n+ mediante matriz de adyacencia.<\/p>\n<p>Hay que elegir la que se desee utilizar, descoment\u00e1ndola y comentando las otras.<\/p>\n<h4>2.2. Los grafos en Haskell<\/h4>\n<h5>2.2.1. El tipo abstracto de datos de los grafos en Haskell<\/h5>\n<p>El TAD de los grafos se encuentra en el m\u00f3dulo <a href=\"https:\/\/bit.ly\/3WiMOb6\">Grafo.hs<\/a> cuyo contenido es el siguiente:<\/p>\n<pre lang=\"haskell\">\nmodule TAD.Grafo\n  (Orientacion (..),\n   Grafo,\n   creaGrafo,\n   creaGrafo',\n   dirigido,\n   adyacentes,\n   nodos,\n   aristas,\n   aristaEn,\n   peso\n  ) where\n\nimport TAD.GrafoConListaDeAdyacencia\n-- import TAD.GrafoConVectorDeAdyacencia\n-- import TAD.GrafoConMatrizDeAdyacencia\n<\/pre>\n<h5>2.2.2. Implementaci\u00f3n de los grafos mediante listas de adyacencia<\/h5>\n<p>La implementaci\u00f3n se encuentra en el m\u00f3dulo <a href=\"https:\/\/bit.ly\/3ME0cDG\">GrafoConListaDeAdyacencia<\/a> cuyo contenido es el siguiente:<\/p>\n<pre lang=\"haskell\">\n{-# LANGUAGE FlexibleInstances #-}\n\nmodule TAD.GrafoConListaDeAdyacencia\n    (Orientacion (..),\n     Grafo,\n     creaGrafo,\n     creaGrafo',\n     dirigido,\n     adyacentes,\n     nodos,\n     aristas,\n     aristaEn,\n     peso\n    ) where\n\n-- Librer\u00edas auxiliares                                               --\nimport Data.Array\nimport Data.List\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\n\n-- (escribeGrafo g) es la cadena correspondiente al grafo g. Por\n-- ejemplo,\n--    \u03bb> escribeGrafo (creaGrafo ND (1,3) [(1,2,0),(2,3,5),(2,2,0)])\n--    \"G ND ([1,2,3],[((1,2),0),((2,2),0),((2,3),5)])\"\n--    \u03bb> escribeGrafo (creaGrafo D (1,3) [(1,2,0),(2,3,5),(2,2,0)])\n--    \"G D ([1,2,3],[((1,2),0),((2,2),0),((2,3),5)])\"\n--    \u03bb> escribeGrafo (creaGrafo ND (1,3) [(1,2,0),(2,3,0),(2,2,0)])\n--    \"G ND ([1,2,3],[(1,2),(2,2),(2,3)])\"\n--    \u03bb> escribeGrafo (creaGrafo D (1,3) [(1,2,0),(2,3,0),(2,2,0)])\n--    \"G D ([1,2,3],[(1,2),(2,2),(2,3)])\"\n--    \u03bb> escribeGrafo (creaGrafo D (1,3) [(1,2,0),(3,2,0),(2,2,0)])\n--    \"G D ([1,2,3],[(1,2),(2,2),(3,2)])\"\n--    \u03bb> escribeGrafo (creaGrafo ND (1,3) [(1,2,0),(3,2,0),(2,2,0)])\n--    \"G ND ([1,2,3],[(1,2),(2,2),(2,3)])\"\nescribeGrafo :: (Ix v,Num p,Eq p,Show v,Show p) => Grafo v p -> String\nescribeGrafo (G o (vs,as)) =\n  \"G \" ++ show o ++ \" (\" ++ show vs ++ \",\" ++ escribeAristas ++ \")\"\n  where\n    aristasReducidas\n      | o == D    = as\n      | otherwise = [((x,y),p) | ((x,y),p) <- as, x <= y]\n    escribeAristas\n      | ponderado = show aristasReducidas\n      | otherwise = show [a | (a,_) <- aristasReducidas]\n    ponderado = any (\\((_,_),p) -> p \/= 0) as\n\n-- Procedimiento de escritura de grafos\ninstance (Ix v,Num p,Eq p,Show v,Show p) => Show (Grafo v p) where\n  show = escribeGrafo\n\n-- (creaGrafo o cs as) es un grafo (dirigido o no, seg\u00fan el valor de o),\n-- con el par de cotas cs y listas de aristas as (cada arista es un tr\u00edo\n-- formado por los dos v\u00e9rtices y su peso). Por ejemplo,\n--    \u03bb> 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--    \u03bb> creaGrafo D (1,3) [(1,2,12),(1,3,34)]\n--    G D ([1,2,3],[((1,2),12),((1,3),34)])\n--    \u03bb> creaGrafo D (1,4) [(1,2,12),(1,3,34)]\n--    G D ([1,2,3,4],[((1,2),12),((1,3),34)])\ncreaGrafo :: (Ix v, Num p, Ord v, Ord p) =>\n             Orientacion -> (v,v) -> [(v,v,p)] -> Grafo v p\ncreaGrafo o cs as =\n  G o (range cs,\n       sort ([((x1,x2),p) | (x1,x2,p) <- as] ++\n             if o == D then []\n             else [((x2,x1),p) | (x1,x2,p) <- as, x1 \/= x2]))\n\n-- (creaGrafo' o cs as) es un grafo (dirigido o no, seg\u00fan el valor de o),\n-- con el par de cotas cs y listas de aristas as (cada arista es un par\n-- de v\u00e9rtices y se supone que su peso es 0). Por ejemplo,\n--    \u03bb> creaGrafo' ND (1,3) [(2,1),(1,3)]\n--    G ND ([1,2,3],[(1,2),(1,3)])\n--    \u03bb> creaGrafo' D (1,3) [(2,1),(1,3)]\n--    G D ([1,2,3],[(1,3),(2,1)])\ncreaGrafo' :: (Ix v, Num p, Ord v, Ord p) =>\n              Orientacion -> (v,v) -> [(v,v)] -> Grafo v p\ncreaGrafo' o cs as =\n  creaGrafo o cs [(v1,v2,0) | (v1,v2) <- as]\n\n-- ejGrafoND es el grafo\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-- Se define por\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\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-- (dirigido g) se verifica si g es dirigido. Por ejemplo,\n--    dirigido ejGrafoD   ==  True\n--    dirigido ejGrafoND  ==  False\ndirigido :: (Ix v,Num p) => Grafo v p -> Bool\ndirigido (G o _) = o == D\n\n-- (nodos g) es la lista de todos los nodos del grafo g. Por ejemplo,\n--    nodos ejGrafoND  ==  [1,2,3,4,5]\n--    nodos ejGrafoD   ==  [1,2,3,4,5]\nnodos :: (Ix v,Num p) => Grafo v p -> [v]\nnodos (G _ (ns,_)) = ns\n\n-- (adyacentes g v) es la lista de los v\u00e9rtices adyacentes al nodo v en\n-- el grafo g. Por ejemplo,\n--    adyacentes ejGrafoND 4  ==  [2,3,5]\n--    adyacentes ejGrafoD  4  ==  [5]\nadyacentes :: (Ix v, Num p) => Grafo v p -> v -> [v]\nadyacentes (G _ (_,e)) v = nub [u | ((w,u),_) <- e, w == v]\n\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\naristaEn :: (Ix v,Num p) => Grafo v p -> (v,v) -> Bool\naristaEn g (x,y) = y `elem` adyacentes g x\n\n-- (peso v1 v2 g) es el peso de la arista que une los v\u00e9rtices v1 y v2\n-- en el grafo g. Por ejemplo,\n--    peso 1 5 ejGrafoND  ==  78\n--    peso 1 5 ejGrafoD   ==  78\npeso :: (Ix v,Num p) => v -> v -> Grafo v p -> p\npeso x y (G _ (_,gs)) = head [c | ((x',y'),c) <- gs, (x,y) == (x',y')]\n\n-- (aristas g) es la lista de las aristas del grafo g. Por ejemplo,\n--    \u03bb> aristas ejGrafoD\n--    [((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--    \u03bb> aristas ejGrafoND\n--    [((1,2),12),((1,3),34),((1,5),78),\n--     ((2,1),12),((2,4),55),((2,5),32),\n--     ((3,1),34),((3,4),61),((3,5),44),\n--     ((4,2),55),((4,3),61),((4,5),93),\n--     ((5,1),78),((5,2),32),((5,3),44),((5,4),93)]\naristas :: (Ix v,Num p) => Grafo v p -> [((v,v),p)]\naristas (G _ (_,g)) = [((v1,v2),p) | ((v1,v2),p) <- g]\n<\/pre>\n<h5>2.2.3. Implementaci\u00f3n de los grafos mediante vectores de adyacencia<\/h5>\n<p>La implementaci\u00f3n se encuentra en el m\u00f3dulo <a href=\"https:\/\/bit.ly\/45k2QWE\">GrafoConVectorDeAdyacencia<\/a> cuyo contenido es el siguiente:<\/p>\n<pre lang=\"haskell\">\n{-# LANGUAGE FlexibleInstances #-}\n\nmodule TAD.GrafoConVectorDeAdyacencia\n  (Orientacion (..),\n   Grafo,\n   creaGrafo,\n   creaGrafo',\n   dirigido,\n   adyacentes,\n   nodos,\n   aristas,\n   aristaEn,\n   peso\n  ) where\n\n-- Librer\u00edas auxiliares\nimport Data.Array (Array, Ix, accumArray, indices, (!))\nimport Data.List (sort)\nimport Test.QuickCheck\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 (Array v [(v,p)])\n  deriving Eq\n\n-- (escribeGrafo g) es la cadena correspondiente al grafo g. Por\n-- ejemplo,\n--    \u03bb> escribeGrafo (creaGrafo ND (1,3) [(1,2,0),(2,3,5),(2,2,0)])\n--    \"G ND ([1,2,3],[((1,2),0),((2,2),0),((2,3),5)])\"\n--    \u03bb> escribeGrafo (creaGrafo D (1,3) [(1,2,0),(2,3,5),(2,2,0)])\n--    \"G D ([1,2,3],[((1,2),0),((2,2),0),((2,3),5)])\"\n--    \u03bb> escribeGrafo (creaGrafo ND (1,3) [(1,2,0),(2,3,0),(2,2,0)])\n--    \"G ND ([1,2,3],[(1,2),(2,2),(2,3)])\"\n--    \u03bb> escribeGrafo (creaGrafo D (1,3) [(1,2,0),(2,3,0),(2,2,0)])\n--    \"G D ([1,2,3],[(1,2),(2,2),(2,3)])\"\n--    \u03bb> escribeGrafo (creaGrafo D (1,3) [(1,2,0),(3,2,0),(2,2,0)])\n--    \"G D ([1,2,3],[(1,2),(2,2),(3,2)])\"\n--    \u03bb> escribeGrafo (creaGrafo ND (1,3) [(1,2,0),(3,2,0),(2,2,0)])\n--    \"G ND ([1,2,3],[(1,2),(2,2),(2,3)])\"\nescribeGrafo :: (Ix v,Num p,Ord v, Ord p,Show v,Show p) => Grafo v p -> String\nescribeGrafo g@(G o _) =\n  \"G \" ++ show o ++ \" (\" ++ show vs ++ \",\" ++ escribeAristas ++ \")\"\n  where\n    as = sort (aristas g)\n    vs = nodos g\n    aristasReducidas\n      | o == D    = as\n      | otherwise = [((x,y),p) | ((x,y),p) <- as, x <= y]\n    escribeAristas\n      | ponderado = show aristasReducidas\n      | otherwise = show [a | (a,_) <- aristasReducidas]\n    ponderado = any (\\((_,_),p) -> p \/= 0) as\n\n-- Procedimiento de escritura de grafos\ninstance (Ix v,Num p,Ord v, Ord p,Show v,Show p) => Show (Grafo v p) where\n  show = escribeGrafo\n\n-- (creaGrafo o cs as) es un grafo (dirigido o no, seg\u00fan el valor de o),\n-- con el par de cotas cs y listas de aristas as (cada arista es un tr\u00edo\n-- formado por los dos v\u00e9rtices y su peso). Ver el ejemplo a continuaci\u00f3n.\ncreaGrafo :: (Ix v, Num p) => Orientacion -> (v,v) -> [(v,v,p)] -> Grafo v p\ncreaGrafo o cs vs =\n  G o (accumArray (\\xs x -> xs++[x]) [] cs\n                  ((if o == D then []\n                    else [(x2,(x1,p))|(x1,x2,p) <- vs, x1 \/= x2]) ++\n                   [(x1,(x2,p)) | (x1,x2,p) <- vs]))\n\n-- (creaGrafo' o cs as) es un grafo (dirigido o no, seg\u00fan el valor de o),\n-- con el par de cotas cs y listas de aristas as (cada arista es un par\n-- de v\u00e9rtices y se supone que su peso es 0). Por ejemplo,\n--    \u03bb> creaGrafo' ND (1,3) [(2,1),(1,3)]\n--    G ND ([1,2,3],[(1,2),(1,3)])\n--    \u03bb> creaGrafo' D (1,3) [(2,1),(1,3)]\n--    G D ([1,2,3],[(1,3),(2,1)])\ncreaGrafo' :: (Ix v, Num p, Ord v, Ord p) =>\n              Orientacion -> (v,v) -> [(v,v)] -> Grafo v p\ncreaGrafo' o cs as =\n  creaGrafo o cs [(v1,v2,0) | (v1,v2) <- as]\n\n-- ejGrafoND es el grafo\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-- representado mediante un vector de adyacencia; es decir,\n--    \u03bb> ejGrafoND\n--    G ND ([1,2,3,4,5],\n--          [((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)])\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-- ejGrafoD es el mismo grafo que ejGrafoND pero orientando las aristas;\n-- es decir,\n--    \u03bb> ejGrafoD\n--    G D ([1,2,3,4,5],\n--         [((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)])\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-- (dirigido g) se verifica si g es dirigido. Por ejemplo,\n--    dirigido ejGrafoD   ==  True\n--    dirigido ejGrafoND  ==  False\ndirigido :: (Ix v,Num p) => Grafo v p -> Bool\ndirigido (G o _) = o == D\n\n-- (nodos g) es la lista de todos los nodos del grafo g. Por ejemplo,\n--    nodos ejGrafoND  ==  [1,2,3,4,5]\n--    nodos ejGrafoD   ==  [1,2,3,4,5]\nnodos :: (Ix v,Num p) => Grafo v p -> [v]\nnodos (G _ g) = indices g\n\n-- (adyacentes g v) es la lista de los v\u00e9rtices adyacentes al nodo v en\n-- el grafo g. Por ejemplo,\n--    adyacentes ejGrafoND 4  ==  [2,3,5]\n--    adyacentes ejGrafoD  4  ==  [5]\nadyacentes :: (Ix v,Num p) => Grafo v p -> v -> [v]\nadyacentes (G _ g) v = map fst (g!v)\n\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\naristaEn :: (Ix v,Num p) => Grafo v p -> (v,v) -> Bool\naristaEn g (x,y) = y `elem` adyacentes g x\n\n-- (peso v1 v2 g) es el peso de la arista que une los v\u00e9rtices v1 y v2\n-- en el grafo g. Por ejemplo,\n--    peso 1 5 ejGrafoND  ==  78\n--    peso 1 5 ejGrafoD   ==  78\npeso :: (Ix v,Num p) => v -> v -> Grafo v p -> p\npeso x y (G _ g) = head [c | (a,c) <- g!x , a == y]\n\n-- (aristas g) es la lista de las aristas del grafo g. Por ejemplo,\n--    \u03bb> aristas ejGrafoD\n--    [((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--    \u03bb> aristas ejGrafoND\n--    [((1,2),12),((1,3),34),((1,5),78),\n--     ((2,1),12),((2,4),55),((2,5),32),\n--     ((3,1),34),((3,4),61),((3,5),44),\n--     ((4,2),55),((4,3),61),((4,5),93),\n--     ((5,1),78),((5,2),32),((5,3),44),((5,4),93)]\naristas :: (Ix v,Num p) => Grafo v p -> [((v,v),p)]\naristas (G o g) = [((v1,v2),w) | v1 <- nodos (G o g) , (v2,w) <- g!v1]\n<\/pre>\n<h5>2.2.3. Implementaci\u00f3n de los grafos mediante vectores de adyacencia<\/h5>\n<p>La implementaci\u00f3n se encuentra en el m\u00f3dulo <a href=\"https:\/\/bit.ly\/3Os4Ju3\">GrafoConMatrizDeAdyacencia<\/a> cuyo contenido es el siguiente:<\/p>\n<pre lang=\"haskell\">\n{-# LANGUAGE FlexibleInstances #-}\n\nmodule TAD.GrafoConMatrizDeAdyacencia\n  (Orientacion (..),\n   Grafo,\n   creaGrafo,\n   creaGrafo',\n   dirigido,\n   adyacentes,\n   nodos,\n   aristas,\n   aristaEn,\n   peso\n  ) where\n\n-- Librer\u00edas auxiliares                                               --\nimport Data.Array\nimport Data.Maybe (isJust)\nimport Data.List (sort)\nimport Test.QuickCheck\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 (Array (v,v) (Maybe p))\n  deriving Eq\n\n-- (escribeGrafo g) es la cadena correspondiente al grafo g. Por\n-- ejemplo,\n--    \u03bb> escribeGrafo (creaGrafo ND (1,3) [(1,2,0),(2,3,5),(2,2,0)])\n--    \"G ND ([1,2,3],[((1,2),0),((2,2),0),((2,3),5)])\"\n--    \u03bb> escribeGrafo (creaGrafo D (1,3) [(1,2,0),(2,3,5),(2,2,0)])\n--    \"G D ([1,2,3],[((1,2),0),((2,2),0),((2,3),5)])\"\n--    \u03bb> escribeGrafo (creaGrafo ND (1,3) [(1,2,0),(2,3,0),(2,2,0)])\n--    \"G ND ([1,2,3],[(1,2),(2,2),(2,3)])\"\n--    \u03bb> escribeGrafo (creaGrafo D (1,3) [(1,2,0),(2,3,0),(2,2,0)])\n--    \"G D ([1,2,3],[(1,2),(2,2),(2,3)])\"\n--    \u03bb> escribeGrafo (creaGrafo D (1,3) [(1,2,0),(3,2,0),(2,2,0)])\n--    \"G D ([1,2,3],[(1,2),(2,2),(3,2)])\"\n--    \u03bb> escribeGrafo (creaGrafo ND (1,3) [(1,2,0),(3,2,0),(2,2,0)])\n--    \"G ND ([1,2,3],[(1,2),(2,2),(2,3)])\"\nescribeGrafo :: (Ix v,Num p,Ord v, Ord p,Show v,Show p) => Grafo v p -> String\nescribeGrafo g@(G o _) =\n  \"G \" ++ show o ++ \" (\" ++ show vs ++ \",\" ++ escribeAristas ++ \")\"\n  where\n    as = sort (aristas g)\n    vs = nodos g\n    aristasReducidas\n      | o == D    = as\n      | otherwise = [((x,y),p) | ((x,y),p) <- as, x <= y]\n    escribeAristas\n      | ponderado = show aristasReducidas\n      | otherwise = show [a | (a,_) <- aristasReducidas]\n    ponderado = any (\\((_,_),p) -> p \/= 0) as\n\n-- Procedimiento de escritura de grafos\ninstance (Ix v,Num p,Ord v, Ord p,Show v,Show p) => Show (Grafo v p) where\n  show = escribeGrafo\n\n-- (creaGrafo d cs as) es un grafo (dirigido o no, seg\u00fan el valor de o),\n-- con el par de cotas cs y listas de aristas as (cada arista es un tr\u00edo\n-- formado por los dos v\u00e9rtices y su peso). Ver el ejemplo a continuaci\u00f3n.\ncreaGrafo :: (Ix v,Num p) => Orientacion -> (v,v) -> [(v,v,p)] -> Grafo v p\ncreaGrafo D cs as =\n  G D (matrizVacia cs \/\/ [((v1,v2),Just c) | (v1,v2,c) <- as])\ncreaGrafo ND cs as =\n  G ND (matrizVacia cs \/\/ ([((v1,v2),Just c) | (v1,v2,c) <- as] ++\n                           [((v2,v1),Just c) | (v1,v2,c) <- as, v1 \/= v2]))\n\nmatrizVacia :: Ix v => (v,v) -> Array (v,v) (Maybe p)\nmatrizVacia (l,u) =\n  listArray ((l,l),(u,u)) (repeat Nothing)\n\n-- (creaGrafo' o cs as) es un grafo (dirigido o no, seg\u00fan el valor de o),\n-- con el par de cotas cs y listas de aristas as (cada arista es un par\n-- de v\u00e9rtices y se supone que su peso es 0). Por ejemplo,\n--    \u03bb> creaGrafo' ND (1,3) [(2,1),(1,3)]\n--    G ND ([1,2,3],[(1,2),(1,3)])\n--    \u03bb> creaGrafo' D (1,3) [(2,1),(1,3)]\n--    G D ([1,2,3],[(1,3),(2,1)])\ncreaGrafo' :: (Ix v, Num p, Ord v, Ord p) =>\n              Orientacion -> (v,v) -> [(v,v)] -> Grafo v p\ncreaGrafo' o cs as =\n  creaGrafo o cs [(v1,v2,0) | (v1,v2) <- as]\n\n-- ejGrafoND es el grafo\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-- representado mediante una matriz de adyacencia.\n--    \u03bb> ejGrafoND\n--    G ND array ((1,1),(5,5))\n--               [((1,1),Nothing),((1,2),Just 12),((1,3),Just 34),\n--                ((1,4),Nothing),((1,5),Just 78),((2,1),Just 12),\n--                ((2,2),Nothing),((2,3),Nothing),((2,4),Just 55),\n--                ((2,5),Just 32),((3,1),Just 34),((3,2),Nothing),\n--                ((3,3),Nothing),((3,4),Just 61),((3,5),Just 44),\n--                ((4,1),Nothing),((4,2),Just 55),((4,3),Just 61),\n--                ((4,4),Nothing),((4,5),Just 93),((5,1),Just 78),\n--                ((5,2),Just 32),((5,3),Just 44),((5,4),Just 93),\n--                ((5,5),Nothing)]\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-- ejGrafoD es el mismo grafo que ejGrafoND pero orientando las aristas;\n-- es decir,\n--    \u03bb> ejGrafoD\n--    G D (array ((1,1),(5,5))\n--               [((1,1),Nothing),((1,2),Just 12),((1,3),Just 34),\n--                ((1,4),Nothing),((1,5),Just 78),((2,1),Nothing),\n--                ((2,2),Nothing),((2,3),Nothing),((2,4),Just 55),\n--                ((2,5),Just 32),((3,1),Nothing),((3,2),Nothing),\n--                ((3,3),Nothing),((3,4),Just 61),((3,5),Just 44),\n--                ((4,1),Nothing),((4,2),Nothing),((4,3),Nothing),\n--                ((4,4),Nothing),((4,5),Just 93),((5,1),Nothing),\n--                ((5,2),Nothing),((5,3),Nothing),((5,4),Nothing),\n--                ((5,5),Nothing)])\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-- (dirigido g) se verifica si g es dirigido. Por ejemplo,\n--    dirigido ejGrafoD   ==  True\n--    dirigido ejGrafoND  ==  False\ndirigido :: (Ix v,Num p) => Grafo v p -> Bool\ndirigido (G o _) = o == D\n\n-- (nodos g) es la lista de todos los nodos del grafo g. Por ejemplo,\n--    nodos ejGrafoND  ==  [1,2,3,4,5]\n--    nodos ejGrafoD   ==  [1,2,3,4,5]\nnodos :: (Ix v,Num p) => Grafo v p -> [v]\nnodos (G _ g) = range (l,u)\n  where ((l,_),(u,_)) = bounds g\n\n-- (adyacentes g v) es la lista de los v\u00e9rtices adyacentes al nodo v en\n-- el grafo g. Por ejemplo,\n--    adyacentes ejGrafoND 4  ==  [2,3,5]\n--    adyacentes ejGrafoD  4  ==  [5]\nadyacentes :: (Ix v,Num p,Eq p) => Grafo v p -> v -> [v]\nadyacentes (G o g) v =\n  [v' | v' <- nodos (G o g), isJust (g!(v,v'))]\n\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\naristaEn :: (Ix v,Num p,Eq p) => Grafo v p -> (v,v) -> Bool\naristaEn (G _o g) (x,y) = isJust (g!(x,y))\n\n-- (peso v1 v2 g) es el peso de la arista que une los v\u00e9rtices v1 y v2\n-- en el grafo g. Por ejemplo,\n--    peso 1 5 ejGrafoND  ==  78\n--    peso 1 5 ejGrafoD   ==  78\npeso :: (Ix v,Num p) => v -> v -> Grafo v p -> p\npeso x y (G _ g)  = w where (Just w) = g!(x,y)\n\n-- (aristas g) es la lista de las aristas del grafo g. Por ejemplo,\n--    \u03bb> 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--    \u03bb> 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)]\naristas :: (Ix v,Num p, Eq p) => Grafo v p -> [((v,v),p)]\naristas g@(G _ e) = [((v1,v2),extrae(e!(v1,v2)))\n                     | v1 <- nodos g,\n                       v2 <- nodos g,\n                       aristaEn g (v1,v2)]\n  where extrae (Just w) = w\n        extrae _        = error \"Imposible\"\n<\/pre>\n<h4>2.3. Los grafos en Python<\/h4>\n<h5>2.3.1. El tipo abstracto de los grafos en Python<\/h5>\n<p>La implementaci\u00f3n se encuentra en el m\u00f3dulo <a href=\"https:\/\/bit.ly\/3InmTcQ\">Grafo.py<\/a> cuyo contenido es el siguiente:<\/p>\n<pre lang=\"python\">\n__all__ = [\n    'Orientacion',\n    'Grafo',\n    'creaGrafo',\n    'creaGrafo_',\n    'dirigido',\n    'adyacentes',\n    'nodos',\n    'aristas',\n    'aristaEn',\n    'peso'\n    ]\n\nfrom src.TAD.GrafoConListaDeAdyacencia import (Grafo, Orientacion, adyacentes,\n                                               aristaEn, aristas, creaGrafo,\n                                               creaGrafo_, dirigido, nodos, peso)\n<\/pre>\n<h5>2.3.2. Implementaci\u00f3n de los grafos mediante listas<\/h5>\n<p>Se define la clase Grafo con los siguientes m\u00e9todos:<\/p>\n<ul>\n<li>dirigido() se verifica si el grafo es dirigido.<\/li>\n<li>nodos() es la lista de todos los nodos del grafo.<\/li>\n<li>aristas() es la lista de las aristas del grafo.<\/li>\n<li>adyacentes(v) es la lista de los v\u00e9rtices adyacentes al v\u00e9rtice v en el grafo.<\/li>\n<li>aristaEn(a) se verifica si a es una arista del grafo.<\/li>\n<li>peso(v1, v2) es el peso de la arista que une los v\u00e9rtices v1 y v2 en el grafo.<\/li>\n<\/ul>\n<p>Por ejemplo,<\/p>\n<pre lang=\"text\">\n>>> Grafo(Orientacion.D, (1,3), [((1,2),0),((3,2),0),((2,2),0)])\nG D ([1, 2, 3], [(1, 2), (2, 2), (3, 2)])\n>>> Grafo(Orientacion.ND, (1,3), [((1,2),0),((3,2),0),((2,2),0)])\nG ND ([1, 2, 3], [(1, 2), (2, 2), (2, 3)])\n>>> Grafo(Orientacion.ND, (1,3), [((1,2),0),((3,2),5),((2,2),0)])\nG ND ([1, 2, 3], [((1, 2), 0), ((2, 2), 0), ((2, 3), 5)])\n>>> Grafo(Orientacion.D, (1,3), [((1,2),0),((3,2),5),((2,2),0)])\nG D ([1, 2, 3], [((1, 2), 0), ((2, 2), 0), ((3, 2), 5)])\n>>> ejGrafoND: Grafo = Grafo(Orientacion.ND,\n                             (1, 5),\n                             [((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>>> ejGrafoND\nG ND ([1, 2, 3, 4, 5],\n      [((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>> ejGrafoD: Grafo = Grafo(Orientacion.D,\n                           (1,5),\n                           [((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>>> ejGrafoD\nG D ([1, 2, 3, 4, 5],\n     [((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>>> ejGrafoD.dirigido()\nTrue\n>>> ejGrafoND.dirigido()\nFalse\n>>> ejGrafoND.nodos()\n[1, 2, 3, 4, 5]\n>>> ejGrafoD.nodos()\n[1, 2, 3, 4, 5]\n>>> ejGrafoND.adyacentes(4)\n[2, 3, 5]\n>>> ejGrafoD.adyacentes(4)\n[5]\n>>> ejGrafoND.aristaEn((5, 1))\nTrue\n>>> ejGrafoND.aristaEn((4, 1))\nFalse\n>>> ejGrafoD.aristaEn((5, 1))\nFalse\n>>> ejGrafoD.aristaEn((1, 5))\nTrue\n>>> ejGrafoND.peso(1, 5)\n78\n>>> ejGrafoD.peso(1, 5)\n78\n>>> ejGrafoD._aristas\n[((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>>> ejGrafoND._aristas\n[((1, 2), 12), ((1, 3), 34), ((1, 5), 78),\n ((2, 1), 12), ((2, 4), 55), ((2, 5), 32),\n ((3, 1), 34), ((3, 4), 61), ((3, 5), 44),\n ((4, 2), 55), ((4, 3), 61), ((4, 5), 93),\n ((5, 1), 78), ((5, 2), 32), ((5, 3), 44),\n ((5, 4), 93)]\n<\/pre>\n<p>Adem\u00e1s se definen las correspondientes funciones. Por ejemplo,<\/p>\n<pre lang=\"text\">\n>>> creaGrafo(Orientacion.ND, (1,3), [((1,2),12),((1,3),34)])\nG ND ([1, 2, 3], [((1, 2), 12), ((1, 3), 34), ((2, 1), 12), ((3, 1), 34)])\n>>> creaGrafo(Orientacion.D, (1,3), [((1,2),12),((1,3),34)])\nG D ([1, 2, 3], [((1, 2), 12), ((1, 3), 34)])\n>>> creaGrafo(Orientacion.D, (1,4), [((1,2),12),((1,3),34)])\nG D ([1, 2, 3, 4], [((1, 2), 12), ((1, 3), 34)])\n>>> ejGrafoND2: Grafo = creaGrafo(Orientacion.ND,\n                                  (1,5),\n                                  [((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>>> ejGrafoND2\nG ND ([1, 2, 3, 4, 5],\n      [((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>>> ejGrafoD2: Grafo = creaGrafo(Orientacion.D,\n                                 (1,5),\n                                 [((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>>> ejGrafoD2\nG D ([1, 2, 3, 4, 5],\n     [((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>>> creaGrafo_(Orientacion.D, (1,3), [(2, 1), (1, 3)])\nG D ([1, 2, 3], [(1, 3), (2, 1)])\n>>> creaGrafo_(Orientacion.ND, (1,3), [(2, 1), (1, 3)])\nG ND ([1, 2, 3], [(1, 2), (1, 3)])\n>>> dirigido(ejGrafoD2)\nTrue\n>>> dirigido(ejGrafoND2)\nFalse\n>>> nodos(ejGrafoND2)\n[1, 2, 3, 4, 5]\n>>> nodos(ejGrafoD2)\n[1, 2, 3, 4, 5]\n>>> adyacentes(ejGrafoND2, 4)\n[2, 3, 5]\n>>> adyacentes(ejGrafoD2, 4)\n[5]\n>>> aristaEn(ejGrafoND2, (5,1))\nTrue\n>>> aristaEn(ejGrafoND2, (4,1))\nFalse\n>>> aristaEn(ejGrafoD2, (5,1))\nFalse\n>>> aristaEn(ejGrafoD2, (1,5))\nTrue\n>>> peso(1, 5, ejGrafoND2)\n78\n>>> peso(1, 5, ejGrafoD2)\n78\n>>> aristas(ejGrafoD2)\n[((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>>> aristas(ejGrafoND2)\n[((1, 2), 12), ((1, 3), 34), ((1, 5), 78),\n ((2, 1), 12), ((2, 4), 55), ((2, 5), 32),\n ((3, 1), 34), ((3, 4), 61), ((3, 5), 44),\n ((4, 2), 55), ((4, 3), 61), ((4, 5), 93),\n ((5, 1), 78), ((5, 2), 32), ((5, 3), 44), ((5, 4), 93)]\n<\/pre>\n<p>La implementaci\u00f3n se encuentra en el m\u00f3dulo <a href=\"https:\/\/bit.ly\/3MDU3Y4\">GrafoConListaDeAdyacencia<\/a> cuyo contenido es el siguiente:<\/p>\n<pre lang=\"python\">\nfrom enum import Enum\n\nOrientacion = Enum('Orientacion', ['D', 'ND'])\n\nVertice = int\nCotas = tuple[Vertice, Vertice]\nPeso = float\nArista = tuple[tuple[Vertice, Vertice], Peso]\n\nclass Grafo:\n    def __init__(self,\n                 _orientacion: Orientacion,\n                 _cotas: Cotas,\n                 _aristas: list[Arista]):\n        self._orientacion = _orientacion\n        self._cotas = _cotas\n        if _orientacion == Orientacion.ND:\n            simetricas = [((v2, v1), p) for ((v1, v2), p)\n                          in _aristas\n                          if v1 != v2]\n            self._aristas = sorted(_aristas + simetricas)\n        else:\n            self._aristas = sorted(_aristas)\n\n    def nodos(self) -> list[Vertice]:\n        (x, y) = self._cotas\n        return list(range(x, 1 + y))\n\n    def __repr__(self) -> str:\n        o = self._orientacion\n        vs = nodos(self)\n        ns = self._aristas\n        escribeOrientacion = \"D\" if o == Orientacion.D else \"ND\"\n        ponderado = {p for ((_, _), p) in ns} != {0}\n        aristasReducidas = ns if o == Orientacion.D \\\n            else [((x, y), p)\n                  for ((x, y), p) in ns\n                  if x <= y]\n        escribeAristas = str(aristasReducidas) if ponderado \\\n            else str([a for (a, _) in aristasReducidas])\n        return f\"G {escribeOrientacion} ({vs}, {escribeAristas})\"\n\n    def dirigido(self) -> bool:\n        return self._orientacion == Orientacion.D\n\n    def adyacentes(self, v: int) -> list[int]:\n        return list(set(u for ((w, u), _)\n                        in self._aristas\n                        if w == v))\n\n    def aristaEn(self, a: tuple[Vertice, Vertice]) -> bool:\n        (x, y) = a\n        return y in self.adyacentes(x)\n\n    def peso(self, v1: Vertice, v2: Vertice) -> Peso:\n        return [p for ((x1, x2), p)\n                in self._aristas\n                if (x1, x2) == (v1, v2)][0]\n\ndef creaGrafo(o: Orientacion,\n              cs: Cotas,\n              as_: list[Arista]) -> Grafo:\n    return Grafo(o, cs, as_)\n\ndef creaGrafo_(o: Orientacion,\n              cs: Cotas,\n              as_: list[tuple[Vertice, Vertice]]) -> Grafo:\n    return Grafo(o, cs, [((v1, v2), 0) for (v1, v2) in as_])\n\ndef dirigido(g: Grafo) -> bool:\n    return g.dirigido()\n\ndef nodos(g: Grafo) -> list[Vertice]:\n    return g.nodos()\n\ndef adyacentes(g: Grafo, v: Vertice) -> list[Vertice]:\n    return g.adyacentes(v)\n\ndef aristaEn(g: Grafo, a: tuple[Vertice, Vertice]) -> bool:\n    return g.aristaEn(a)\n\ndef peso(v1: Vertice, v2: Vertice, g: Grafo) -> Peso:\n    return g.peso(v1, v2)\n\ndef aristas(g: Grafo) -> list[Arista]:\n    return g._aristas\n\n# En los ejemplos se usar\u00e1n los grafos (no dirigido y dirigido)\n# correspondientes a\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# definidos por\nejGrafoND: Grafo = Grafo(Orientacion.ND,\n                         (1, 5),\n                         [((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)])\nejGrafoD: Grafo = Grafo(Orientacion.D,\n                        (1,5),\n                        [((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\nejGrafoND2: Grafo = creaGrafo(Orientacion.ND,\n                              (1,5),\n                              [((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\nejGrafoD2: Grafo = creaGrafo(Orientacion.D,\n                             (1,5),\n                             [((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<\/pre>\n<p><a name=\"ej3\"><\/a><\/p>\n<h3>3. TAD de los grafos: Grafos completos<\/h3>\n<p>El grafo completo de orden n, K(n), es un grafo no dirigido cuyos conjunto de v\u00e9rtices es {1,..n} y tiene una arista entre cada par de v\u00e9rtices distintos.<\/p>\n<p>Usando el <a href=\"https:\/\/bit.ly\/45cQ3Fo\">tipo abstrado de datos de los grafos<\/a>, definir la funci\u00f3n,<\/p>\n<pre lang=\"text\">\n   completo :: Int -> Grafo Int Int\n<\/pre>\n<p>tal que <code>completo n<\/code> es el grafo completo de orden <code>n<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> completo 4\n   G ND ([1,2,3,4],[(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)])\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_Grafos_completos where\n\nimport TAD.Grafo (Grafo, Orientacion (ND), creaGrafo')\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\ncompleto :: Int -> Grafo Int Int\ncompleto n =\n  creaGrafo' ND (1,n) [(x,y) | x <- [1..n], y <- [x+1..n]]\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    show (completo 4) `shouldBe`\n    \"G ND ([1,2,3,4],[(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)])\"\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--\n--    Finished in 0.0004 seconds\n--    1 example, 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, creaGrafo_\n\ndef completo(n: int) -> Grafo:\n    return creaGrafo_(Orientacion.ND,\n                      (1, n),\n                      [(x, y)\n                       for x in range(1, n + 1)\n                       for y in range(x + 1, n+1)])\n\n# Verificaci\u00f3n\n# ============\n\ndef test_completo() -> None:\n    assert str(completo(4)) == \\\n        \"G ND ([1, 2, 3, 4], [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)])\"\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_completo()\n#    Verificado\n<\/pre>\n<p><a name=\"ej4\"><\/a><\/p>\n<h3>4. TAD de los grafos: Grafos ciclos<\/h3>\n<p>El ciclo de orden n, C(n), es un grafo no dirigido cuyo conjunto de v\u00e9rtices es {1,...,n} y las aristas son<\/p>\n<pre lang=\"text\">\n   (1,2), (2,3), ..., (n-1,n), (n,1)\n<\/pre>\n<p>Usando el <a href=\"https:\/\/bit.ly\/45cQ3Fo\">tipo abstrado de datos de los grafos<\/a>, definir la funci\u00f3n,<\/p>\n<pre lang=\"text\">\n   grafoCiclo :: Int -> Grafo Int Int\n<\/pre>\n<p>tal que (grafoCiclo n) es el grafo ciclo de orden n. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> grafoCiclo 3\n   G ND ([1,2,3],[(1,2),(1,3),(2,3)])\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_Grafos_ciclos where\n\nimport TAD.Grafo (Grafo, Orientacion (ND), creaGrafo')\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\ngrafoCiclo :: Int -> Grafo Int Int\ngrafoCiclo n =\n  creaGrafo' ND (1,n) ((n,1):[(x,x+1) | x <- [1..n-1]])\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    show (grafoCiclo 3) `shouldBe`\n    \"G ND ([1,2,3],[(1,2),(1,3),(2,3)])\"\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--\n--    Finished in 0.0006 seconds\n--    1 example, 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, creaGrafo_\n\n\ndef grafoCiclo(n: int) -> Grafo:\n    return creaGrafo_(Orientacion.ND,\n                      (1, n),\n                      [(n,1)] + [(x, x + 1) for x in range(1, n)])\n\n# Verificaci\u00f3n\n# ============\n\ndef test_grafoCiclo() -> None:\n    assert str(grafoCiclo(3)) == \\\n        \"G ND ([1, 2, 3], [(1, 2), (1, 3), (2, 3)])\"\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_grafoCiclo()\n#    Verificado\n<\/pre>\n<p><a name=\"ej5\"><\/a><\/p>\n<h3>5. TAD de los grafos: N\u00famero de v\u00e9rtices<\/h3>\n<p>Usando el <a href=\"https:\/\/bit.ly\/45cQ3Fo\">tipo abstrado de datos de los grafos<\/a>, definir la funci\u00f3n,<\/p>\n<pre lang=\"text\">\n   nVertices :: (Ix v, Num p) => Grafo v p ->  Int\n<\/pre>\n<p>tal que <code>nVertices g<\/code> es el n\u00famero de v\u00e9rtices del grafo <code>g<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   nVertices (creaGrafo' D (1,5) [(1,2),(3,1)])   ==  5\n   nVertices (creaGrafo' ND (2,4) [(1,2),(3,1)])  ==  3\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_Numero_de_vertices where\n\nimport TAD.Grafo (Grafo, Orientacion (D, ND), nodos, creaGrafo')\nimport Data.Ix\n\nnVertices :: (Ix v, Num p) => Grafo v p ->  Int\nnVertices = length . nodos\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, creaGrafo_, nodos\n\n\ndef nVertices(g: Grafo) -> int:\n    return len(nodos(g))\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Esta semana he publicado en Exercitium las soluciones de los siguientes problemas: 1. TAD de los polinomios: Factorizaci\u00f3n de un polinomio 2. El tipo abstracto de datos de los grafos 3. TAD de los grafos: Grafos completos 4. TAD de los grafos: Grafos ciclos 5. TAD de los grafos: N\u00famero de v\u00e9rtices A continuaci\u00f3n se&#8230;<\/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":[],"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\/7940"}],"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=7940"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7940\/revisions"}],"predecessor-version":[{"id":7941,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7940\/revisions\/7941"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=7940"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=7940"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=7940"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}