TAD de los grafos: Grafos ciclos
El ciclo de orden n, C(n), es un grafo no dirigido cuyo conjunto de vértices es {1,…,n} y las aristas son
|
1 |
(1,2), (2,3), ..., (n-1,n), (n,1) |
Usando el tipo abstracto de datos de los grafos, definir la función,
|
1 |
grafoCiclo :: Int -> Grafo Int Int |
tal que (grafoCiclo n) es el grafo ciclo de orden n. Por ejemplo,
|
1 2 |
λ> grafoCiclo 3 G ND ([1,2,3],[(1,2),(1,3),(2,3)]) |
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_ciclos where import TAD.Grafo (Grafo, Orientacion (ND), creaGrafo') import Test.Hspec (Spec, hspec, it, shouldBe) grafoCiclo :: Int -> Grafo Int Int grafoCiclo n = creaGrafo' ND (1,n) ((n,1):[(x,x+1) | x <- [1..n-1]]) -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ show (grafoCiclo 3) `shouldBe` "G ND ([1,2,3],[(1,2),(1,3),(2,3)])" -- La verificación es -- λ> verifica -- -- e1 -- -- Finished in 0.0006 seconds -- 1 example, 0 failures |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
from src.TAD.Grafo import Grafo, Orientacion, creaGrafo_ def grafoCiclo(n: int) -> Grafo: return creaGrafo_(Orientacion.ND, (1, n), [(n,1)] + [(x, x + 1) for x in range(1, n)]) # Verificación # ============ def test_grafoCiclo() -> None: assert str(grafoCiclo(3)) == \ "G ND ([1, 2, 3], [(1, 2), (1, 3), (2, 3)])" print("Verificado") # La verificación es # >>> test_grafoCiclo() # Verificado |