TAD de los grafos: Incidentes de un vértice
En un un grafo g, los incidentes de un vértice v es el conjuntos de vértices x de g para los que hay un arco (o una arista) de x a v; es decir, que v es adyacente a x.
Usando el tipo abstracto de datos de los grafos, definir la función,
|
1 |
incidentes :: (Ix v,Num p) => (Grafo v p) -> v -> [v] |
tal que incidentes g v es la lista de los vértices incidentes en 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)] λ> incidentes g1 1 [3] λ> incidentes g1 2 [1,2,3] λ> incidentes g1 3 [] λ> g2 = creaGrafo' ND (1,3) [(1,2),(2,2),(3,1),(3,2)] λ> incidentes g2 1 [2,3] λ> incidentes g2 2 [1,2,3] λ> incidentes 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 |
module Grafo_Incidentes_de_un_vertice where import TAD.Grafo (Grafo, Orientacion (D, ND), nodos, adyacentes, creaGrafo') import Data.Ix import Test.Hspec incidentes :: (Ix v,Num p) => Grafo v p -> v -> [v] incidentes g v = [x | x <- nodos g, v `elem` adyacentes g x] -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ incidentes g1 1 `shouldBe` [3] it "e2" $ incidentes g1 2 `shouldBe` [1,2,3] it "e3" $ incidentes g1 3 `shouldBe` [] it "e4" $ incidentes g2 1 `shouldBe` [2,3] it "e5" $ incidentes g2 2 `shouldBe` [1,2,3] it "e6" $ incidentes 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.TAD.Grafo import (Grafo, Orientacion, Vertice, adyacentes, creaGrafo_, nodos) def incidentes(g: Grafo, v: Vertice) -> list[Vertice]: return [x for x in nodos(g) if v in adyacentes(g, x)] # Verificación # ============ def test_incidentes() -> 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 incidentes(g1,1) == [3] assert incidentes(g1,2) == [1, 2, 3] assert incidentes(g1,3) == [] assert incidentes(g2, 1) == [2, 3] assert incidentes(g2, 2) == [1, 2, 3] assert incidentes(g2, 3) == [1, 2] print("Verificado") # La verificación es # >>> test_incidentes() # Verificado |