TAD de los grafos: Contiguos de un vértice
En un un grafo g, los contiguos de un vértice v es el conjuntos de vértices x de g tales que x es adyacente o incidente con v.
Usando el tipo abstracto de datos de los grafos, definir la función,
|
1 |
contiguos :: (Ix v,Num p) => Grafo v p -> v -> [v] |
tal que contiguos g v es el conjunto de los vértices de g contiguos con el vértice v. Por ejemplo,
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
λ> g1 = creaGrafo' D (1,3) [(1,2),(2,2),(3,1),(3,2)] λ> contiguos g1 1 [2,3] λ> contiguos g1 2 [2,1,3] λ> contiguos g1 3 [1,2] λ> g2 = creaGrafo' ND (1,3) [(1,2),(2,2),(3,1),(3,2)] λ> contiguos g2 1 [2,3] λ> contiguos g2 2 [1,2,3] λ> contiguos g2 3 [1,2] |
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 |
module Grafo_Contiguos_de_un_vertice where import TAD.Grafo (Grafo, Orientacion (D, ND), adyacentes, creaGrafo') import Grafo_Incidentes_de_un_vertice (incidentes) import Data.List (nub) import Data.Ix import Test.Hspec contiguos :: (Ix v,Num p) => Grafo v p -> v -> [v] contiguos g v = nub (adyacentes g v ++ incidentes g v) -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ contiguos g1 1 `shouldBe` [2,3] it "e2" $ contiguos g1 2 `shouldBe` [2,1,3] it "e3" $ contiguos g1 3 `shouldBe` [1,2] it "e4" $ contiguos g2 1 `shouldBe` [2,3] it "e5" $ contiguos g2 2 `shouldBe` [1,2,3] it "e6" $ contiguos g2 3 `shouldBe` [1,2] where g1, g2 :: Grafo Int Int g1 = creaGrafo' D (1,3) [(1,2),(2,2),(3,1),(3,2)] g2 = creaGrafo' ND (1,3) [(1,2),(2,2),(3,1),(3,2)] -- La verificación es -- λ> verifica -- -- e1 -- e2 -- e3 -- e4 -- e5 -- e6 -- -- Finished in 0.0005 seconds -- 6 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 |
from src.Grafo_Incidentes_de_un_vertice import incidentes from src.TAD.Grafo import Grafo, Orientacion, Vertice, adyacentes, creaGrafo_ def contiguos(g: Grafo, v: Vertice) -> list[Vertice]: return list(set(adyacentes(g, v) + incidentes(g, v))) # Verificación # ============ def test_contiguos() -> None: g1 = creaGrafo_(Orientacion.D, (1,3), [(1,2),(2,2),(3,1),(3,2)]) g2 = creaGrafo_(Orientacion.ND, (1,3), [(1,2),(2,2),(3,1),(3,2)]) assert contiguos(g1, 1) == [2, 3] assert contiguos(g1, 2) == [1, 2, 3] assert contiguos(g1, 3) == [1, 2] assert contiguos(g2, 1) == [2, 3] assert contiguos(g2, 2) == [1, 2, 3] assert contiguos(g2, 3) == [1, 2] print("Verificado") # La verificación es # >>> test_contiguos() # Verificado |