TAD de los grafos: Nodos conectados en un grafo
Usando el tipo abstracto de datos de los grafos, definir la función,
|
1 |
conectados :: Grafo Int Int -> Int -> Int -> Bool |
tal que conectados g v1 v2 se verifica si los vértices v1 y v2 están conectados en el grafo g. Por ejemplo, si grafo1 es el grafo definido por
|
1 2 3 |
grafo1 :: Grafo Int Int grafo1 = creaGrafo' D (1,6) [(1,3),(1,5),(3,5),(5,1),(5,50), (2,4),(2,6),(4,6),(4,4),(6,4)] |
entonces,
|
1 2 3 4 |
conectados grafo1 1 3 == True conectados grafo1 1 4 == False conectados grafo1 6 2 == False conectados grafo1 3 1 == True |
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 |
module Grafo_Nodos_conectados_en_un_grafo where import TAD.Grafo (Grafo, Orientacion (D, ND), adyacentes, creaGrafo') import Data.List (union) import Test.Hspec (Spec, hspec, it, shouldBe) conectados :: Grafo Int Int -> Int -> Int -> Bool conectados g v1 v2 = v2 `elem` conectadosAux g [] [v1] conectadosAux :: Grafo Int Int -> [Int] -> [Int] -> [Int] conectadosAux _ vs [] = vs conectadosAux g vs (w:ws) | w `elem` vs = conectadosAux g vs ws | otherwise = conectadosAux g ([w] `union` vs) (ws `union` adyacentes g w) -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ conectados grafo1 1 3 `shouldBe` True it "e2" $ conectados grafo1 1 4 `shouldBe` False it "e3" $ conectados grafo1 6 2 `shouldBe` False it "e4" $ conectados grafo1 3 1 `shouldBe` True it "e5" $ conectados grafo2 1 3 `shouldBe` True it "e6" $ conectados grafo2 1 4 `shouldBe` False it "e7" $ conectados grafo2 6 2 `shouldBe` True it "e8" $ conectados grafo2 3 1 `shouldBe` True where grafo1, grafo2 :: Grafo Int Int grafo1 = creaGrafo' D (1,6) [(1,3),(1,5),(3,5),(5,1),(5,50), (2,4),(2,6),(4,6),(4,4),(6,4)] grafo2 = creaGrafo' ND (1,6) [(1,3),(1,5),(3,5),(5,1),(5,50), (2,4),(2,6),(4,6),(4,4),(6,4)] -- La verificación es -- λ> verifica -- -- e1 -- e2 -- e3 -- e4 -- e5 -- e6 -- e7 -- e8 -- -- Finished in 0.0032 seconds -- 8 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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
from src.TAD.Grafo import Grafo, Orientacion, Vertice, adyacentes, creaGrafo_ def unionV(xs: list[Vertice], ys: list[Vertice]) -> list[Vertice]: return list(set(xs) | set(ys)) def conectadosAux(g: Grafo, vs: list[Vertice], ws: list[Vertice]) -> list[Vertice]: if not ws: return vs w, *ws = ws if w in vs: return conectadosAux(g, vs, ws) return conectadosAux(g, unionV([w], vs), unionV(ws, adyacentes(g, w))) def conectados(g: Grafo, v1: Vertice, v2: Vertice) -> bool: return v2 in conectadosAux(g, [], [v1]) # Verificación # ============ def test_conectados() -> None: grafo1 = creaGrafo_(Orientacion.D, (1,6), [(1,3),(1,5),(3,5),(5,1),(5,50), (2,4),(2,6),(4,6),(4,4),(6,4)]) grafo2 = creaGrafo_(Orientacion.ND, (1,6), [(1,3),(1,5),(3,5),(5,1),(5,50), (2,4),(2,6),(4,6),(4,4),(6,4)]) assert conectados(grafo1, 1, 3) assert not conectados(grafo1, 1, 4) assert not conectados(grafo1, 6, 2) assert conectados(grafo1, 3, 1) assert conectados(grafo2, 1, 3) assert not conectados(grafo2, 1, 4) assert conectados(grafo2, 6, 2) assert conectados(grafo2, 3, 1) print("Verificado") # La verificación es # >>> test_conectados() # Verificado |