TAD de los grafos: Grado positivo y negativo de un vértice
El grado positivo de un vértice v de un grafo g es el número de vértices de g adyacentes con v y su grado negativo es el número de vértices de g incidentes con v.
Usando el tipo abstracto de datos de los grafos, definir las funciones,
|
1 2 |
gradoPos :: (Ix v,Num p) => Grafo v p -> v -> Int gradoNeg :: (Ix v,Num p) => Grafo v p -> v -> Int |
tales que
+ gradoPos g v es el grado positivo del vértice v en el grafo g. Por ejemplo,
|
1 2 3 4 5 6 7 8 |
λ> g1 = creaGrafo' ND (1,5) [(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)] λ> g2 = creaGrafo' D (1,5) [(1,2),(1,3),(1,5),(2,4),(2,5),(4,3),(4,5)] λ> gradoPos g1 5 4 λ> gradoPos g2 5 0 λ> gradoPos g2 1 3 |
gradoNeg g ves el grado negativo del vérticeven el grafog. Por ejemplo,
|
1 2 3 4 5 6 |
λ> gradoNeg g1 5 4 λ> gradoNeg g2 5 3 λ> gradoNeg g2 1 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 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
module Grafo_Grados_positivos_y_negativos where import TAD.Grafo (Grafo, Orientacion (D, ND), adyacentes, creaGrafo') import Data.Ix (Ix) import Grafo_Incidentes_de_un_vertice (incidentes) import Test.Hspec (Spec, hspec, it, shouldBe) -- 1ª definición de gradoPos gradoPos :: (Ix v,Num p) => Grafo v p -> v -> Int gradoPos g v = length (adyacentes g v) -- 2ª definición de gradoPos gradoPos2 :: (Ix v,Num p) => Grafo v p -> v -> Int gradoPos2 g = length . adyacentes g -- 1ª definición de gradoNeg gradoNeg :: (Ix v,Num p) => Grafo v p -> v -> Int gradoNeg g v = length (incidentes g v) -- 2ª definición de gradoNeg gradoNeg2 :: (Ix v,Num p) => Grafo v p -> v -> Int gradoNeg2 g = length . incidentes g -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ gradoPos g1 5 `shouldBe` 4 it "e2" $ gradoPos g2 5 `shouldBe` 0 it "e3" $ gradoPos g2 1 `shouldBe` 3 it "e4" $ gradoNeg g1 5 `shouldBe` 4 it "e5" $ gradoNeg g2 5 `shouldBe` 3 it "e6" $ gradoNeg g2 1 `shouldBe` 0 it "e7" $ gradoPos2 g1 5 `shouldBe` 4 it "e8" $ gradoPos2 g2 5 `shouldBe` 0 it "e9" $ gradoPos2 g2 1 `shouldBe` 3 it "e10" $ gradoNeg2 g1 5 `shouldBe` 4 it "e11" $ gradoNeg2 g2 5 `shouldBe` 3 it "e12" $ gradoNeg2 g2 1 `shouldBe` 0 where g1, g2 :: Grafo Int Int g1 = creaGrafo' ND (1,5) [(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)] g2 = creaGrafo' D (1,5) [(1,2),(1,3),(1,5),(2,4),(2,5),(4,3),(4,5)] -- La verificación es -- λ> verifica -- -- def. 1 -- e1 -- e2 -- e3 -- e4 -- e5 -- e6 -- def. 2 -- e1 -- e2 -- e3 -- e4 -- e5 -- e6 -- -- Finished in 0.0013 seconds -- 12 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 26 27 28 29 |
from src.Grafo_Incidentes_de_un_vertice import incidentes from src.TAD.Grafo import Grafo, Orientacion, Vertice, adyacentes, creaGrafo_ def gradoPos(g: Grafo, v: Vertice) -> int: return len(adyacentes(g, v)) def gradoNeg(g: Grafo, v: Vertice) -> int: return len(incidentes(g, v)) # Verificación # ============ def test_GradoPosNeg() -> None: g1 = creaGrafo_(Orientacion.ND, (1,5), [(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)]) g2 = creaGrafo_(Orientacion.D, (1,5), [(1,2),(1,3),(1,5),(2,4),(2,5),(4,3),(4,5)]) assert gradoPos(g1, 5) == 4 assert gradoPos(g2, 5) == 0 assert gradoPos(g2, 1) == 3 assert gradoNeg(g1, 5) == 4 assert gradoNeg(g2, 5) == 3 assert gradoNeg(g2, 1) == 0 print("Verificado") # La verificación es # >>> test_GradoPosNeg() # Verificado |