TAD de los grafos - Generadores de grafos
Definir un generador de grafos para comprobar propiedades de grafos con QuickCheck y hacer el tipo de los Grafos un subtipo de Arbutrary.
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értices de g son iguales.
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
Soluciones en Haskell
La definición del generador es
{-# LANGUAGE FlexibleInstances #-} {-# OPTIONS_GHC -fno-warn-orphans #-} module TAD.GrafoGenerador where import TAD.Grafo (Grafo, Orientacion (D, ND), creaGrafo) import Test.QuickCheck (Arbitrary, Gen, arbitrary, choose, vectorOf) -- (generaGND n ps) es el grafo completo de orden n tal que los pesos -- están determinados por ps. Por ejemplo, -- λ> generaGND 3 [4,2,5] -- G ND ([1,2,3],[((1,2),4),((1,3),2),((2,3),5)]) -- λ> generaGND 3 [4,-2,5] -- G ND ([1,2,3],[((1,2),4),((2,3),5)]) generaGND :: Int -> [Int] -> Grafo Int Int generaGND n ps = creaGrafo ND (1,n) l3 where l1 = [(x,y) | x <- [1..n], y <- [1..n], x < y] l2 = zip l1 ps l3 = [(x,y,z) | ((x,y),z) <- l2, z > 0] -- (generaGD n ps) es el grafo completo de orden n tal que los pesos -- están determinados por ps. Por ejemplo, -- λ> generaGD 3 [4,2,5] -- G D ([1,2,3],[((1,1),4),((1,2),2),((1,3),5)]) -- λ> generaGD 3 [4,2,5,3,7,9,8,6] -- G D ([1,2,3],[((1,1),4),((1,2),2),((1,3),5), -- ((2,1),3),((2,2),7),((2,3),9), -- ((3,1),8),((3,2),6)]) generaGD :: Int -> [Int] -> Grafo Int Int generaGD n ps = creaGrafo D (1,n) l3 where l1 = [(x,y) | x <- [1..n], y <- [1..n]] l2 = zip l1 ps l3 = [(x,y,z) | ((x,y),z) <- l2, z > 0] -- genGD es un generador de grafos dirigidos. Por ejemplo, -- λ> sample genGD -- G D ([1],[]) -- G D ([1,2],[((1,1),5),((2,1),4)]) -- G D ([1,2],[((1,1),3),((1,2),3)]) -- G D ([1,2,3,4,5,6],[]) -- G D ([1,2],[((2,2),16)]) -- ... genGD :: Gen (Grafo Int Int) genGD = do n <- choose (1,10) xs <- vectorOf (n*n) arbitrary return (generaGD n xs) -- genGND es un generador de grafos dirigidos. Por ejemplo, -- λ> sample genGND -- G ND ([1,2,3,4,5,6,7,8],[]) -- G ND ([1],[]) -- G ND ([1,2,3,4,5],[((1,2),2),((2,3),5),((3,4),5),((3,5),5)]) -- G ND ([1,2,3,4,5],[((1,2),6),((1,3),5),((1,5),1),((3,5),9),((4,5),6)]) -- G ND ([1,2,3,4],[((1,2),5),((3,4),2)]) -- G ND ([1,2,3],[]) -- G ND ([1,2,3,4],[((1,2),5),((1,4),14),((2,4),10)]) -- G ND ([1,2,3,4,5],[((1,5),8),((4,5),5)]) -- G ND ([1,2,3,4],[((1,2),1),((1,4),4),((2,3),4),((3,4),5)]) -- G ND ([1,2,3],[((1,2),8),((1,3),8),((2,3),3)]) -- ... genGND :: Gen (Grafo Int Int) genGND = do n <- choose (1,10) xs <- vectorOf (n*n) arbitrary return (generaGND n xs) -- genG es un generador de grafos. Por ejemplo, -- λ> sample genG -- G ND ([1,2,3,4,5,6],[]) -- G D ([1],[((1,1),2)]) -- G D ([1,2],[((1,1),9)]) -- ... genG :: Gen (Grafo Int Int) genG = do d <- choose (True,False) n <- choose (1,10) xs <- vectorOf (n*n) arbitrary if d then return (generaGD n xs) else return (generaGND n xs) -- Los grafos está contenido en la clase de los objetos generables -- aleatoriamente. instance Arbitrary (Grafo Int Int) where arbitrary = genG
La comprobación de la propiedad es
module Grafo_Propiedades_de_grados_positivos_y_negativos where import TAD.Grafo (Grafo, nodos) import TAD.GrafoGenerador import Grafo_Grados_positivos_y_negativos (gradoPos, gradoNeg) import Test.QuickCheck -- La propiedad es prop_sumaGrados :: Grafo Int Int -> Bool prop_sumaGrados g = sum [gradoPos g v | v <- vs] == sum [gradoNeg g v | v <- vs] where vs = nodos g -- La comprobación es -- λ> quickCheck prop_sumaGrados -- +++ OK, passed 100 tests.
Soluciones en Python
La definición del generador es
from hypothesis import strategies as st from hypothesis.strategies import composite from src.TAD.Grafo import Orientacion, creaGrafo_ # Generador de aristas. Por ejemplo, # >>> gen_aristas(5).example() # [(2, 5), (4, 5), (1, 2), (2, 3), (4, 1)] # >>> gen_aristas(5).example() # [(3, 4)] # >>> gen_aristas(5).example() # [(5, 3), (3, 2), (1, 3), (5, 2)] @composite def gen_aristas(draw, n): as_ = draw(st.lists(st.tuples(st.integers(1,n), st.integers(1,n)), unique=True)) return as_ # Generador de grafos no dirigidos. Por ejemplo, # >>> gen_grafoND().example() # G ND ([1, 2, 3, 4, 5], [(1, 4), (5, 5)]) # >>> gen_grafoND().example() # G ND ([1], []) # >>> gen_grafoND().example() # G ND ([1, 2, 3, 4, 5, 6, 7, 8], [(7, 7)]) # >>> gen_grafoND().example() # G ND ([1, 2, 3, 4, 5, 6], [(1, 3), (2, 4), (3, 3), (3, 5)]) @composite def gen_grafoND(draw): n = draw(st.integers(1,10)) as_ = [(x, y) for (x, y ) in draw(gen_aristas(n)) if x <= y] return creaGrafo_(Orientacion.ND, (1,n), as_) # Generador de grafos dirigidos. Por ejemplo, # >>> gen_grafoD().example() # G D ([1, 2, 3, 4], [(3, 3), (4, 1)]) # >>> gen_grafoD().example() # G D ([1, 2], [(1, 1), (2, 1), (2, 2)]) # >>> gen_grafoD().example() # G D ([1, 2], []) @composite def gen_grafoD(draw): n = draw(st.integers(1,10)) as_ = draw(gen_aristas(n)) return creaGrafo_(Orientacion.D, (1,n), as_) # Generador de grafos. Por ejemplo, # >>> gen_grafo().example() # G ND ([1, 2, 3, 4, 5, 6, 7], [(1, 3)]) # >>> gen_grafo().example() # G D ([1], []) # >>> gen_grafo().example() # G D ([1, 2, 3, 4, 5, 6, 7], [(1, 3), (3, 4), (5, 5)]) @composite def gen_grafo(draw): o = draw(st.sampled_from([Orientacion.D, Orientacion.ND])) if o == Orientacion.ND: return draw(gen_grafoND()) return draw(gen_grafoD())
La comprobación de la propiedad es
from hypothesis import given from src.Grafo_Grados_positivos_y_negativos import gradoNeg, gradoPos from src.TAD.Grafo import nodos from src.TAD.GrafoGenerador import gen_grafo # La propiedad es @given(gen_grafo()) def test_sumaGrados(g): vs = nodos(g) assert sum((gradoPos(g, v) for v in vs)) == sum((gradoNeg(g, v) for v in vs)) # La comprobación es # src> poetry run pytest -q Grafo_Propiedades_de_grados_positivos_y_negativos.py # 1 passed in 0.31s