<\/a>
\nSoluciones en Haskell<\/b><\/p>\nLa definici\u00f3n del generador es<\/p>\n
\n{-# LANGUAGE FlexibleInstances #-}\n{-# OPTIONS_GHC -fno-warn-orphans #-}\n\nmodule TAD.GrafoGenerador where\n\nimport TAD.Grafo (Grafo, Orientacion (D, ND), creaGrafo)\nimport Test.QuickCheck (Arbitrary, Gen, arbitrary, choose, vectorOf)\n\n-- (generaGND n ps) es el grafo completo de orden n tal que los pesos\n-- est\u00e1n determinados por ps. Por ejemplo,\n-- \u03bb> generaGND 3 [4,2,5]\n-- G ND ([1,2,3],[((1,2),4),((1,3),2),((2,3),5)])\n-- \u03bb> generaGND 3 [4,-2,5]\n-- G ND ([1,2,3],[((1,2),4),((2,3),5)])\ngeneraGND :: Int -> [Int] -> Grafo Int Int\ngeneraGND n ps = creaGrafo ND (1,n) l3\n where l1 = [(x,y) | x <- [1..n], y <- [1..n], x < y]\n l2 = zip l1 ps\n l3 = [(x,y,z) | ((x,y),z) <- l2, z > 0]\n\n-- (generaGD n ps) es el grafo completo de orden n tal que los pesos\n-- est\u00e1n determinados por ps. Por ejemplo,\n-- \u03bb> generaGD 3 [4,2,5]\n-- G D ([1,2,3],[((1,1),4),((1,2),2),((1,3),5)])\n-- \u03bb> generaGD 3 [4,2,5,3,7,9,8,6]\n-- G D ([1,2,3],[((1,1),4),((1,2),2),((1,3),5),\n-- ((2,1),3),((2,2),7),((2,3),9),\n-- ((3,1),8),((3,2),6)])\ngeneraGD :: Int -> [Int] -> Grafo Int Int\ngeneraGD n ps = creaGrafo D (1,n) l3\n where l1 = [(x,y) | x <- [1..n], y <- [1..n]]\n l2 = zip l1 ps\n l3 = [(x,y,z) | ((x,y),z) <- l2, z > 0]\n\n-- genGD es un generador de grafos dirigidos. Por ejemplo,\n-- \u03bb> sample genGD\n-- G D ([1],[])\n-- G D ([1,2],[((1,1),5),((2,1),4)])\n-- G D ([1,2],[((1,1),3),((1,2),3)])\n-- G D ([1,2,3,4,5,6],[])\n-- G D ([1,2],[((2,2),16)])\n-- ...\ngenGD :: Gen (Grafo Int Int)\ngenGD = do\n n <- choose (1,10)\n xs <- vectorOf (n*n) arbitrary\n return (generaGD n xs)\n\n-- genGND es un generador de grafos dirigidos. Por ejemplo,\n-- \u03bb> sample genGND\n-- G ND ([1,2,3,4,5,6,7,8],[])\n-- G ND ([1],[])\n-- G ND ([1,2,3,4,5],[((1,2),2),((2,3),5),((3,4),5),((3,5),5)])\n-- G ND ([1,2,3,4,5],[((1,2),6),((1,3),5),((1,5),1),((3,5),9),((4,5),6)])\n-- G ND ([1,2,3,4],[((1,2),5),((3,4),2)])\n-- G ND ([1,2,3],[])\n-- G ND ([1,2,3,4],[((1,2),5),((1,4),14),((2,4),10)])\n-- G ND ([1,2,3,4,5],[((1,5),8),((4,5),5)])\n-- G ND ([1,2,3,4],[((1,2),1),((1,4),4),((2,3),4),((3,4),5)])\n-- G ND ([1,2,3],[((1,2),8),((1,3),8),((2,3),3)])\n-- ...\ngenGND :: Gen (Grafo Int Int)\ngenGND = do\n n <- choose (1,10)\n xs <- vectorOf (n*n) arbitrary\n return (generaGND n xs)\n\n-- genG es un generador de grafos. Por ejemplo,\n-- \u03bb> sample genG\n-- G ND ([1,2,3,4,5,6],[])\n-- G D ([1],[((1,1),2)])\n-- G D ([1,2],[((1,1),9)])\n-- ...\ngenG :: Gen (Grafo Int Int)\ngenG = do\n d <- choose (True,False)\n n <- choose (1,10)\n xs <- vectorOf (n*n) arbitrary\n if d then return (generaGD n xs)\n else return (generaGND n xs)\n\n-- Los grafos est\u00e1 contenido en la clase de los objetos generables\n-- aleatoriamente.\ninstance Arbitrary (Grafo Int Int) where\n arbitrary = genG\n<\/pre>\nLa comprobaci\u00f3n de la propiedad es<\/p>\n
\nmodule Grafo_Propiedades_de_grados_positivos_y_negativos where\n\nimport TAD.Grafo (Grafo, nodos)\nimport TAD.GrafoGenerador\nimport Grafo_Grados_positivos_y_negativos (gradoPos, gradoNeg)\nimport Test.QuickCheck\n\n-- La propiedad es\nprop_sumaGrados :: Grafo Int Int -> Bool\nprop_sumaGrados g =\n sum [gradoPos g v | v <- vs] == sum [gradoNeg g v | v <- vs]\n where vs = nodos g\n\n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheck prop_sumaGrados\n-- +++ OK, passed 100 tests.\n<\/pre>\n<\/a>
\nSoluciones en Python<\/b><\/p>\nLa definici\u00f3n del generador es<\/p>\n
\nfrom hypothesis import strategies as st\nfrom hypothesis.strategies import composite\n\nfrom src.TAD.Grafo import Orientacion, creaGrafo_\n\n\n# Generador de aristas. Por ejemplo,\n# >>> gen_aristas(5).example()\n# [(2, 5), (4, 5), (1, 2), (2, 3), (4, 1)]\n# >>> gen_aristas(5).example()\n# [(3, 4)]\n# >>> gen_aristas(5).example()\n# [(5, 3), (3, 2), (1, 3), (5, 2)]\n@composite\ndef gen_aristas(draw, n):\n as_ = draw(st.lists(st.tuples(st.integers(1,n),\n st.integers(1,n)),\n unique=True))\n return as_\n\n# Generador de grafos no dirigidos. Por ejemplo,\n# >>> gen_grafoND().example()\n# G ND ([1, 2, 3, 4, 5], [(1, 4), (5, 5)])\n# >>> gen_grafoND().example()\n# G ND ([1], [])\n# >>> gen_grafoND().example()\n# G ND ([1, 2, 3, 4, 5, 6, 7, 8], [(7, 7)])\n# >>> gen_grafoND().example()\n# G ND ([1, 2, 3, 4, 5, 6], [(1, 3), (2, 4), (3, 3), (3, 5)])\n@composite\ndef gen_grafoND(draw):\n n = draw(st.integers(1,10))\n as_ = [(x, y) for (x, y ) in draw(gen_aristas(n)) if x <= y]\n return creaGrafo_(Orientacion.ND, (1,n), as_)\n\n# Generador de grafos dirigidos. Por ejemplo,\n# >>> gen_grafoD().example()\n# G D ([1, 2, 3, 4], [(3, 3), (4, 1)])\n# >>> gen_grafoD().example()\n# G D ([1, 2], [(1, 1), (2, 1), (2, 2)])\n# >>> gen_grafoD().example()\n# G D ([1, 2], [])\n@composite\ndef gen_grafoD(draw):\n n = draw(st.integers(1,10))\n as_ = draw(gen_aristas(n))\n return creaGrafo_(Orientacion.D, (1,n), as_)\n\n# Generador de grafos. Por ejemplo,\n# >>> gen_grafo().example()\n# G ND ([1, 2, 3, 4, 5, 6, 7], [(1, 3)])\n# >>> gen_grafo().example()\n# G D ([1], [])\n# >>> gen_grafo().example()\n# G D ([1, 2, 3, 4, 5, 6, 7], [(1, 3), (3, 4), (5, 5)])\n@composite\ndef gen_grafo(draw):\n o = draw(st.sampled_from([Orientacion.D, Orientacion.ND]))\n if o == Orientacion.ND:\n return draw(gen_grafoND())\n return draw(gen_grafoD())\n<\/pre>\nLa comprobaci\u00f3n de la propiedad es<\/p>\n
\nfrom hypothesis import given\n\nfrom src.Grafo_Grados_positivos_y_negativos import gradoNeg, gradoPos\nfrom src.TAD.Grafo import nodos\nfrom src.TAD.GrafoGenerador import gen_grafo\n\n\n# La propiedad es\n@given(gen_grafo())\ndef test_sumaGrados(g):\n vs = nodos(g)\n assert sum((gradoPos(g, v) for v in vs)) == sum((gradoNeg(g, v) for v in vs))\n\n# La comprobaci\u00f3n es\n# src> poetry run pytest -q Grafo_Propiedades_de_grados_positivos_y_negativos.py\n# 1 passed in 0.31s\n<\/pre>\n","protected":false},"excerpt":{"rendered":"Definir un generador de grafos para comprobar propiedades de grafos con QuickCheck y hacer el tipo de los Grafos un subtipo de Arbitrary. Usando el generador, con QuickCheck que para cualquier grafo g, las sumas de los grados positivos y la de los grados negativos de los v\u00e9rtices de g son iguales. Soluciones A continuaci\u00f3n…<\/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":[588],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8180"}],"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=8180"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8180\/revisions"}],"predecessor-version":[{"id":8196,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8180\/revisions\/8196"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=8180"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=8180"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=8180"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}