TAD de los grafos: Grafos completos
El grafo completo de orden n, K(n), es un grafo no dirigido cuyos conjunto de vértices es {1,..n} y tiene una arista entre cada par de vértices distintos.
Usando el tipo abstracto de datos de los grafos, definir la función,
|
1 |
completo :: Int -> Grafo Int Int |
tal que completo n es el grafo completo de orden n. Por ejemplo,
|
1 2 |
λ> completo 4 G ND ([1,2,3,4],[(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)]) |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
module Grafo_Grafos_completos where import TAD.Grafo (Grafo, Orientacion (ND), creaGrafo') import Test.Hspec (Spec, hspec, it, shouldBe) completo :: Int -> Grafo Int Int completo n = creaGrafo' ND (1,n) [(x,y) | x <- [1..n], y <- [x+1..n]] -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ show (completo 4) `shouldBe` "G ND ([1,2,3,4],[(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)])" -- La verificación es -- λ> verifica -- -- e1 -- -- Finished in 0.0004 seconds -- 1 example, 0 failures |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
from src.TAD.Grafo import Grafo, Orientacion, creaGrafo_ def completo(n: int) -> Grafo: return creaGrafo_(Orientacion.ND, (1, n), [(x, y) for x in range(1, n + 1) for y in range(x + 1, n+1)]) # Verificación # ============ def test_completo() -> None: assert str(completo(4)) == \ "G ND ([1, 2, 3, 4], [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)])" print("Verificado") # La verificación es # >>> test_completo() # Verificado |