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,
contiguos :: (Ix v,Num p) => Grafo v p -> v -> [v] |
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,
λ> 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] |
λ> 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.
Soluciones en Haskell
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 |
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
Soluciones en Python
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 |
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