TAD de los grafos: Lazos de un grafo
Usando el tipo abstracto de datos de los grafos, definir las funciones,
|
1 2 |
lazos :: (Ix v,Num p) => Grafo v p -> [(v,v)] nLazos :: (Ix v,Num p) => Grafo v p -> Int |
tales que
lazos ges el conjunto de los lazos (es decir, aristas cuyos extremos son iguales) del grafog. Por ejemplo,
|
1 2 3 4 5 6 |
λ> ej1 = creaGrafo' D (1,3) [(1,1),(2,3),(3,2),(3,3)] λ> ej2 = creaGrafo' ND (1,3) [(2,3),(3,1)] λ> lazos ej1 [(1,1),(3,3)] λ> lazos ej2 [] |
nLazos ges el número de lazos del grafog. Por ejemplo,
|
1 2 3 4 |
λ> nLazos ej1 2 λ> nLazos ej2 0 |
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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
module Grafo_Lazos_de_un_grafo where import TAD.Grafo (Grafo, Orientacion (D, ND), nodos, aristaEn, creaGrafo') import Data.Ix (Ix) import Test.Hspec (Spec, hspec, it, shouldBe) lazos :: (Ix v,Num p) => Grafo v p -> [(v,v)] lazos g = [(x,x) | x <- nodos g, aristaEn g (x,x)] nLazos :: (Ix v,Num p) => Grafo v p -> Int nLazos = length . lazos -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ lazos ej1 `shouldBe` [(1,1),(3,3)] it "e2" $ lazos ej2 `shouldBe` [] it "e3" $ nLazos ej1 `shouldBe` 2 it "e4" $ nLazos ej2 `shouldBe` 0 where ej1, ej2 :: Grafo Int Int ej1 = creaGrafo' D (1,3) [(1,1),(2,3),(3,2),(3,3)] ej2 = creaGrafo' ND (1,3) [(2,3),(3,1)] -- La verificación es -- λ> verifica -- -- e1 -- e2 -- e3 -- e4 -- -- Finished in 0.0005 seconds -- 4 examples, 0 failures |
|
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 |
from src.TAD.Grafo import (Grafo, Orientacion, Vertice, aristaEn, creaGrafo_, nodos) def lazos(g: Grafo) -> list[tuple[Vertice, Vertice]]: return [(x, x) for x in nodos(g) if aristaEn(g, (x, x))] def nLazos(g: Grafo) -> int: return len(lazos(g)) # Verificación # ============ def test_lazos() -> None: ej1 = creaGrafo_(Orientacion.D, (1,3), [(1,1),(2,3),(3,2),(3,3)]) ej2 = creaGrafo_(Orientacion.ND, (1,3), [(2,3),(3,1)]) assert lazos(ej1) == [(1,1),(3,3)] assert lazos(ej2) == [] assert nLazos(ej1) == 2 assert nLazos(ej2) == 0 print("Verificado") # La verificación es # >>> test_lazos() # Verificado |