La semana en Exercitium (27 de mayo de 2023)
Esta semana he publicado en Exercitium las soluciones de los siguientes problemas:
- 1. TAD de los polinomios: Factorización de un polinomio
- 2. El tipo abstracto de datos de los grafos
- 3. TAD de los grafos: Grafos completos
- 4. TAD de los grafos: Grafos ciclos
- 5. TAD de los grafos: Número de vértices
A continuación se muestran las soluciones.
1. TAD de los polinomios: Factorización de un polinomio
Usando el tipo abstracto de los polinomios, definir la función
|
1 |
factorizacion :: Polinomio Int -> [Polinomio Int] |
tal que factorizacion p es la lista de la descomposición del polinomio p en factores obtenida mediante el regla de Ruffini. Por ejemplo,
|
1 2 3 4 5 6 7 8 9 10 |
λ> ejPol1 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero)) λ> ejPol1 x^5 + 5*x^2 + 4*x λ> factorizacion ejPol1 [1*x,1*x + 1,x^3 + -1*x^2 + 1*x + 4] λ> ejPol2 = consPol 3 1 (consPol 2 2 (consPol 1 (-1) (consPol 0 (-2) polCero))) λ> ejPol2 x^3 + 2*x^2 + -1*x + -2 λ> factorizacion ejPol2 [1*x + -1,1*x + 1,1*x + 2,1] |
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 |
module Pol_Factorizacion_de_un_polinomio where import TAD.Polinomio (Polinomio, consPol, polCero, esPolCero) import Pol_Termino_independiente_de_un_polinomio (terminoIndep) import Pol_Raices_enteras_de_un_polinomio (divisores) import Pol_Regla_de_Ruffini (cocienteRuffini) import Pol_Reconocimiento_de_raices_por_la_regla_de_Ruffini (esRaizRuffini) import Pol_Transformaciones_polinomios_densas (densaApolinomio) import Test.Hspec (Spec, hspec, it, shouldBe) factorizacion :: Polinomio Int -> [Polinomio Int] factorizacion p | esPolCero p = [p] | otherwise = aux (0 : divisores (terminoIndep p)) where aux [] = [p] aux (r:rs) | esRaizRuffini r p = densaApolinomio [1,-r] : factorizacion (cocienteRuffini r p) | otherwise = aux rs -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ map show (factorizacion ejPol1) `shouldBe` ["1*x","1*x + 1","x^3 + -1*x^2 + 1*x + 4"] it "e2" $ map show (factorizacion ejPol2) `shouldBe` ["1*x + -1","1*x + 1","1*x + 2","1"] where ejPol1 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero)) ejPol2 = consPol 3 1 (consPol 2 2 (consPol 1 (-1) (consPol 0 (-2) polCero))) -- La verificación es -- λ> verifica -- -- e1 -- e2 -- -- Finished in 0.0015 seconds -- 2 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 |
from src.Pol_Raices_enteras_de_un_polinomio import divisores from src.Pol_Reconocimiento_de_raices_por_la_regla_de_Ruffini import \ esRaizRuffini from src.Pol_Regla_de_Ruffini import cocienteRuffini from src.Pol_Termino_independiente_de_un_polinomio import terminoIndep from src.Pol_Transformaciones_polinomios_densas import densaApolinomio from src.TAD.Polinomio import Polinomio, consPol, esPolCero, polCero def factorizacion(p: Polinomio[int]) -> list[Polinomio[int]]: def aux(xs: list[int]) -> list[Polinomio[int]]: if not xs: return [p] r, *rs = xs if esRaizRuffini(r, p): return [densaApolinomio([1, -r])] + factorizacion(cocienteRuffini(r, p)) return aux(rs) if esPolCero(p): return [p] return aux([0] + divisores(terminoIndep(p))) # Verificación # ============ def test_factorizacion() -> None: ejPol1 = consPol(5, 1, consPol(2, 5, consPol(1, 4, polCero()))) assert list(map(str, factorizacion(ejPol1))) \ == ["1*x", "1*x + 1", "x^3 + -1*x^2 + 1*x + 4"] ejPol2 = consPol(3, 1, consPol(2, 2, consPol(1, -1, consPol(0, -2, polCero())))) assert list(map(str, factorizacion(ejPol2))) \ == ["1*x + -1", "1*x + 1", "1*x + 2", "1"] print("Verificado") # La verificación es # >>> test_factorizacion() # Verificado |
2. El tipo abstracto de datos de los grafos
2.1. El tipo abstracto de datos de los grafos
Un grafo es una estructura que consta de un conjunto de vértices y un conjunto de aristas que conectan los vértices entre sí. Cada vértice representa una entidad o un elemento, y cada arista representa una relación o conexión entre dos vértices.
Por ejemplo,
|
1 2 3 4 5 6 7 8 9 10 11 |
12 1 -------- 2 | \78 /| | \ 32/ | | \ / | 34| 5 |55 | / \ | | /44 \ | | / 93\| 3 -------- 4 61 |
representa un grafo no dirigido, lo que significa que las aristas tienen una dirección específica. Cada arista tiene un peso asociado, que puede representar una medida o una valoración de la relación entre los vértices que conecta.
El grafo consta de cinco vértices numerados del 1 al 5. Las aristas especificadas en la lista indican las conexiones entre los vértices y sus respectivos pesos. Por ejemplo, la arista (1,2,12) indica que existe una conexión entre el vértice 1 y el vértice 2 con un peso de 12.
En el grafo representado, se pueden observar las conexiones entre los vértices de la siguiente manera:
- El vértice 1 está conectado con el vértice 2 (peso 12), el vértice 3 (peso 34) y el vértice 5 (peso 78).
- El vértice 2 está conectado con el vértice 4 (peso 55) y el vértice 5 (peso 32).
- El vértice 3 está conectado con el vértice 4 (peso 61) y el vértice 5 (peso 44).
- El vértice 4 está conectado con el vértice 5 (peso 93).
Las operaciones del tipo abstracto de datos (TAD) de los grafos son
|
1 2 3 4 5 6 7 8 9 10 |
creaGrafo :: (Ix v, Num p, Ord v, Ord p) => Orientacion -> (v,v) -> [(v,v,p)] -> Grafo v p creaGrafo' :: (Ix v, Num p, Ord v, Ord p) => Orientacion -> (v,v) -> [(v,v)] -> Grafo v p dirigido :: (Ix v,Num p) => (Grafo v p) -> Bool adyacentes :: (Ix v,Num p) => (Grafo v p) -> v -> [v] nodos :: (Ix v,Num p) => (Grafo v p) -> [v] aristas :: (Ix v,Num p) => (Grafo v p) -> [(v,v,p)] aristaEn :: (Ix v,Num p) => (Grafo v p) -> (v,v) -> Bool peso :: (Ix v,Num p) => v -> v -> (Grafo v p) -> p |
tales que
+ creaGrafo o cs as es un grafo (dirigido o no, según el de o), con el par de cotas cs y listas de aristas as (cada arista es un trío formado por los dos vértices y su peso).
+ creaGrafo' es la versión de creaGrafo para los grafos sin pesos.
+ dirigido g se verifica si g es dirigido.
+ nodos g es la lista de todos los nodos del grafo g.
+ aristas g es la lista de las aristas del grafo g.
+ adyacentes g v es la lista de los vértices adyacentes al nodo v en el grafo g.
+ aristaEn g a se verifica si a es una arista del grafo g.
+ peso v1 v2 g es el peso de la arista que une los vértices v1 y v2 en el grafo g.
Usando el TAD de los grafos, el grafo anterior se puede definir por
|
1 2 3 4 |
creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78), (2,4,55),(2,5,32), (3,4,61),(3,5,44), (4,5,93)] |
con los siguientes argumentos:
- ND: Es un parámetro de tipo Orientacion que indica si el es dirigido o no. En este caso, se utiliza ND, lo que significa “no dirigido”. Por lo tanto, el grafo creado será no dirigido, lo que implica que las aristas no tienen una dirección específica.
- (1,5): Es el par de cotas que define los vértices del grafo. En este caso, el grafo tiene vértices numerados desde 1 hasta 5.
- [(1,2,12),(1,3,34),(1,5,78),(2,4,55),(2,5,32),(3,4,61),(3,5,44),(4,5,93)]: Es una lista de aristas, donde cada arista está representada por un trío de valores. Cada trío contiene los dos vértices que están conectados por la arista y el peso de dicha arista.
Para usar el TAD hay que usar una implementación concreta. En principio, consideraremos las siguientes:
+ mediante lista de adyacencia,
+ mediante vector de adyacencia y
+ mediante matriz de adyacencia.
Hay que elegir la que se desee utilizar, descomentándola y comentando las otras.
2.2. Los grafos en Haskell
2.2.1. El tipo abstracto de datos de los grafos en Haskell
El TAD de los grafos se encuentra en el módulo Grafo.hs cuyo contenido es el siguiente:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
module TAD.Grafo (Orientacion (..), Grafo, creaGrafo, creaGrafo', dirigido, adyacentes, nodos, aristas, aristaEn, peso ) where import TAD.GrafoConListaDeAdyacencia -- import TAD.GrafoConVectorDeAdyacencia -- import TAD.GrafoConMatrizDeAdyacencia |
2.2.2. Implementación de los grafos mediante listas de adyacencia
La implementación se encuentra en el módulo GrafoConListaDeAdyacencia cuyo contenido es el siguiente:
|
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 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 |
{-# LANGUAGE FlexibleInstances #-} module TAD.GrafoConListaDeAdyacencia (Orientacion (..), Grafo, creaGrafo, creaGrafo', dirigido, adyacentes, nodos, aristas, aristaEn, peso ) where -- Librerías auxiliares -- import Data.Array import Data.List -- Orientacion es D (dirigida) ó ND (no dirigida). data Orientacion = D | ND deriving (Eq, Show) -- (Grafo v p) es un grafo con vértices de tipo v y pesos de tipo p. data Grafo v p = G Orientacion ([v],[((v,v),p)]) deriving Eq -- (escribeGrafo g) es la cadena correspondiente al grafo g. Por -- ejemplo, -- λ> escribeGrafo (creaGrafo ND (1,3) [(1,2,0),(2,3,5),(2,2,0)]) -- "G ND ([1,2,3],[((1,2),0),((2,2),0),((2,3),5)])" -- λ> escribeGrafo (creaGrafo D (1,3) [(1,2,0),(2,3,5),(2,2,0)]) -- "G D ([1,2,3],[((1,2),0),((2,2),0),((2,3),5)])" -- λ> escribeGrafo (creaGrafo ND (1,3) [(1,2,0),(2,3,0),(2,2,0)]) -- "G ND ([1,2,3],[(1,2),(2,2),(2,3)])" -- λ> escribeGrafo (creaGrafo D (1,3) [(1,2,0),(2,3,0),(2,2,0)]) -- "G D ([1,2,3],[(1,2),(2,2),(2,3)])" -- λ> escribeGrafo (creaGrafo D (1,3) [(1,2,0),(3,2,0),(2,2,0)]) -- "G D ([1,2,3],[(1,2),(2,2),(3,2)])" -- λ> escribeGrafo (creaGrafo ND (1,3) [(1,2,0),(3,2,0),(2,2,0)]) -- "G ND ([1,2,3],[(1,2),(2,2),(2,3)])" escribeGrafo :: (Ix v,Num p,Eq p,Show v,Show p) => Grafo v p -> String escribeGrafo (G o (vs,as)) = "G " ++ show o ++ " (" ++ show vs ++ "," ++ escribeAristas ++ ")" where aristasReducidas | o == D = as | otherwise = [((x,y),p) | ((x,y),p) <- as, x <= y] escribeAristas | ponderado = show aristasReducidas | otherwise = show [a | (a,_) <- aristasReducidas] ponderado = any (\((_,_),p) -> p /= 0) as -- Procedimiento de escritura de grafos instance (Ix v,Num p,Eq p,Show v,Show p) => Show (Grafo v p) where show = escribeGrafo -- (creaGrafo o cs as) es un grafo (dirigido o no, según el valor de o), -- con el par de cotas cs y listas de aristas as (cada arista es un trío -- formado por los dos vértices y su peso). Por ejemplo, -- λ> creaGrafo ND (1,3) [(1,2,12),(1,3,34)] -- G ND ([1,2,3],[((1,2),12),((1,3),34),((2,1),12),((3,1),34)]) -- λ> creaGrafo D (1,3) [(1,2,12),(1,3,34)] -- G D ([1,2,3],[((1,2),12),((1,3),34)]) -- λ> creaGrafo D (1,4) [(1,2,12),(1,3,34)] -- G D ([1,2,3,4],[((1,2),12),((1,3),34)]) creaGrafo :: (Ix v, Num p, Ord v, Ord p) => Orientacion -> (v,v) -> [(v,v,p)] -> Grafo v p creaGrafo o cs as = G o (range cs, sort ([((x1,x2),p) | (x1,x2,p) <- as] ++ if o == D then [] else [((x2,x1),p) | (x1,x2,p) <- as, x1 /= x2])) -- (creaGrafo' o cs as) es un grafo (dirigido o no, según el valor de o), -- con el par de cotas cs y listas de aristas as (cada arista es un par -- de vértices y se supone que su peso es 0). Por ejemplo, -- λ> creaGrafo' ND (1,3) [(2,1),(1,3)] -- G ND ([1,2,3],[(1,2),(1,3)]) -- λ> creaGrafo' D (1,3) [(2,1),(1,3)] -- G D ([1,2,3],[(1,3),(2,1)]) creaGrafo' :: (Ix v, Num p, Ord v, Ord p) => Orientacion -> (v,v) -> [(v,v)] -> Grafo v p creaGrafo' o cs as = creaGrafo o cs [(v1,v2,0) | (v1,v2) <- as] -- ejGrafoND es el grafo -- 12 -- 1 -------- 2 -- | \78 /| -- | \ 32/ | -- | \ / | -- 34| 5 |55 -- | / \ | -- | /44 \ | -- | / 93\| -- 3 -------- 4 -- 61 -- Se define por ejGrafoND :: Grafo Int Int ejGrafoND = creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78), (2,4,55),(2,5,32), (3,4,61),(3,5,44), (4,5,93)] ejGrafoD :: Grafo Int Int ejGrafoD = creaGrafo D (1,5) [(1,2,12),(1,3,34),(1,5,78), (2,4,55),(2,5,32), (3,4,61),(3,5,44), (4,5,93)] -- (dirigido g) se verifica si g es dirigido. Por ejemplo, -- dirigido ejGrafoD == True -- dirigido ejGrafoND == False dirigido :: (Ix v,Num p) => Grafo v p -> Bool dirigido (G o _) = o == D -- (nodos g) es la lista de todos los nodos del grafo g. Por ejemplo, -- nodos ejGrafoND == [1,2,3,4,5] -- nodos ejGrafoD == [1,2,3,4,5] nodos :: (Ix v,Num p) => Grafo v p -> [v] nodos (G _ (ns,_)) = ns -- (adyacentes g v) es la lista de los vértices adyacentes al nodo v en -- el grafo g. Por ejemplo, -- adyacentes ejGrafoND 4 == [2,3,5] -- adyacentes ejGrafoD 4 == [5] adyacentes :: (Ix v, Num p) => Grafo v p -> v -> [v] adyacentes (G _ (_,e)) v = nub [u | ((w,u),_) <- e, w == v] -- (aristaEn g a) se verifica si a es una arista del grafo g. Por -- ejemplo, -- aristaEn ejGrafoND (5,1) == True -- aristaEn ejGrafoND (4,1) == False -- aristaEn ejGrafoD (5,1) == False -- aristaEn ejGrafoD (1,5) == True aristaEn :: (Ix v,Num p) => Grafo v p -> (v,v) -> Bool aristaEn g (x,y) = y `elem` adyacentes g x -- (peso v1 v2 g) es el peso de la arista que une los vértices v1 y v2 -- en el grafo g. Por ejemplo, -- peso 1 5 ejGrafoND == 78 -- peso 1 5 ejGrafoD == 78 peso :: (Ix v,Num p) => v -> v -> Grafo v p -> p peso x y (G _ (_,gs)) = head [c | ((x',y'),c) <- gs, (x,y) == (x',y')] -- (aristas g) es la lista de las aristas del grafo g. Por ejemplo, -- λ> aristas ejGrafoD -- [((1,2),12),((1,3),34),((1,5),78), -- ((2,4),55),((2,5),32), -- ((3,4),61),((3,5),44), -- ((4,5),93)] -- λ> aristas ejGrafoND -- [((1,2),12),((1,3),34),((1,5),78), -- ((2,1),12),((2,4),55),((2,5),32), -- ((3,1),34),((3,4),61),((3,5),44), -- ((4,2),55),((4,3),61),((4,5),93), -- ((5,1),78),((5,2),32),((5,3),44),((5,4),93)] aristas :: (Ix v,Num p) => Grafo v p -> [((v,v),p)] aristas (G _ (_,g)) = [((v1,v2),p) | ((v1,v2),p) <- g] |
2.2.3. Implementación de los grafos mediante vectores de adyacencia
La implementación se encuentra en el módulo GrafoConVectorDeAdyacencia cuyo contenido es el siguiente:
|
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 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 |
{-# LANGUAGE FlexibleInstances #-} module TAD.GrafoConVectorDeAdyacencia (Orientacion (..), Grafo, creaGrafo, creaGrafo', dirigido, adyacentes, nodos, aristas, aristaEn, peso ) where -- Librerías auxiliares import Data.Array (Array, Ix, accumArray, indices, (!)) import Data.List (sort) import Test.QuickCheck -- Orientacion es D (dirigida) ó ND (no dirigida). data Orientacion = D | ND deriving (Eq, Show) -- (Grafo v p) es un grafo con vértices de tipo v y pesos de tipo p. data Grafo v p = G Orientacion (Array v [(v,p)]) deriving Eq -- (escribeGrafo g) es la cadena correspondiente al grafo g. Por -- ejemplo, -- λ> escribeGrafo (creaGrafo ND (1,3) [(1,2,0),(2,3,5),(2,2,0)]) -- "G ND ([1,2,3],[((1,2),0),((2,2),0),((2,3),5)])" -- λ> escribeGrafo (creaGrafo D (1,3) [(1,2,0),(2,3,5),(2,2,0)]) -- "G D ([1,2,3],[((1,2),0),((2,2),0),((2,3),5)])" -- λ> escribeGrafo (creaGrafo ND (1,3) [(1,2,0),(2,3,0),(2,2,0)]) -- "G ND ([1,2,3],[(1,2),(2,2),(2,3)])" -- λ> escribeGrafo (creaGrafo D (1,3) [(1,2,0),(2,3,0),(2,2,0)]) -- "G D ([1,2,3],[(1,2),(2,2),(2,3)])" -- λ> escribeGrafo (creaGrafo D (1,3) [(1,2,0),(3,2,0),(2,2,0)]) -- "G D ([1,2,3],[(1,2),(2,2),(3,2)])" -- λ> escribeGrafo (creaGrafo ND (1,3) [(1,2,0),(3,2,0),(2,2,0)]) -- "G ND ([1,2,3],[(1,2),(2,2),(2,3)])" escribeGrafo :: (Ix v,Num p,Ord v, Ord p,Show v,Show p) => Grafo v p -> String escribeGrafo g@(G o _) = "G " ++ show o ++ " (" ++ show vs ++ "," ++ escribeAristas ++ ")" where as = sort (aristas g) vs = nodos g aristasReducidas | o == D = as | otherwise = [((x,y),p) | ((x,y),p) <- as, x <= y] escribeAristas | ponderado = show aristasReducidas | otherwise = show [a | (a,_) <- aristasReducidas] ponderado = any (\((_,_),p) -> p /= 0) as -- Procedimiento de escritura de grafos instance (Ix v,Num p,Ord v, Ord p,Show v,Show p) => Show (Grafo v p) where show = escribeGrafo -- (creaGrafo o cs as) es un grafo (dirigido o no, según el valor de o), -- con el par de cotas cs y listas de aristas as (cada arista es un trío -- formado por los dos vértices y su peso). Ver el ejemplo a continuación. creaGrafo :: (Ix v, Num p) => Orientacion -> (v,v) -> [(v,v,p)] -> Grafo v p creaGrafo o cs vs = G o (accumArray (\xs x -> xs++[x]) [] cs ((if o == D then [] else [(x2,(x1,p))|(x1,x2,p) <- vs, x1 /= x2]) ++ [(x1,(x2,p)) | (x1,x2,p) <- vs])) -- (creaGrafo' o cs as) es un grafo (dirigido o no, según el valor de o), -- con el par de cotas cs y listas de aristas as (cada arista es un par -- de vértices y se supone que su peso es 0). Por ejemplo, -- λ> creaGrafo' ND (1,3) [(2,1),(1,3)] -- G ND ([1,2,3],[(1,2),(1,3)]) -- λ> creaGrafo' D (1,3) [(2,1),(1,3)] -- G D ([1,2,3],[(1,3),(2,1)]) creaGrafo' :: (Ix v, Num p, Ord v, Ord p) => Orientacion -> (v,v) -> [(v,v)] -> Grafo v p creaGrafo' o cs as = creaGrafo o cs [(v1,v2,0) | (v1,v2) <- as] -- ejGrafoND es el grafo -- 12 -- 1 -------- 2 -- | \78 /| -- | \ 32/ | -- | \ / | -- 34| 5 |55 -- | / \ | -- | /44 \ | -- | / 93\| -- 3 -------- 4 -- 61 -- representado mediante un vector de adyacencia; es decir, -- λ> ejGrafoND -- G ND ([1,2,3,4,5], -- [((1,2),12),((1,3),34),((1,5),78), -- ((2,4),55),((2,5),32), -- ((3,4),61),((3,5),44), -- ((4,5),93)]) ejGrafoND :: Grafo Int Int ejGrafoND = creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78), (2,4,55),(2,5,32), (3,4,61),(3,5,44), (4,5,93)] -- ejGrafoD es el mismo grafo que ejGrafoND pero orientando las aristas; -- es decir, -- λ> ejGrafoD -- G D ([1,2,3,4,5], -- [((1,2),12),((1,3),34),((1,5),78), -- ((2,4),55),((2,5),32), -- ((3,4),61),((3,5),44), -- ((4,5),93)]) ejGrafoD :: Grafo Int Int ejGrafoD = creaGrafo D (1,5) [(1,2,12),(1,3,34),(1,5,78), (2,4,55),(2,5,32), (3,4,61),(3,5,44), (4,5,93)] -- (dirigido g) se verifica si g es dirigido. Por ejemplo, -- dirigido ejGrafoD == True -- dirigido ejGrafoND == False dirigido :: (Ix v,Num p) => Grafo v p -> Bool dirigido (G o _) = o == D -- (nodos g) es la lista de todos los nodos del grafo g. Por ejemplo, -- nodos ejGrafoND == [1,2,3,4,5] -- nodos ejGrafoD == [1,2,3,4,5] nodos :: (Ix v,Num p) => Grafo v p -> [v] nodos (G _ g) = indices g -- (adyacentes g v) es la lista de los vértices adyacentes al nodo v en -- el grafo g. Por ejemplo, -- adyacentes ejGrafoND 4 == [2,3,5] -- adyacentes ejGrafoD 4 == [5] adyacentes :: (Ix v,Num p) => Grafo v p -> v -> [v] adyacentes (G _ g) v = map fst (g!v) -- (aristaEn g a) se verifica si a es una arista del grafo g. Por -- ejemplo, -- aristaEn ejGrafoND (5,1) == True -- aristaEn ejGrafoND (4,1) == False -- aristaEn ejGrafoD (5,1) == False -- aristaEn ejGrafoD (1,5) == True aristaEn :: (Ix v,Num p) => Grafo v p -> (v,v) -> Bool aristaEn g (x,y) = y `elem` adyacentes g x -- (peso v1 v2 g) es el peso de la arista que une los vértices v1 y v2 -- en el grafo g. Por ejemplo, -- peso 1 5 ejGrafoND == 78 -- peso 1 5 ejGrafoD == 78 peso :: (Ix v,Num p) => v -> v -> Grafo v p -> p peso x y (G _ g) = head [c | (a,c) <- g!x , a == y] -- (aristas g) es la lista de las aristas del grafo g. Por ejemplo, -- λ> aristas ejGrafoD -- [((1,2),12),((1,3),34),((1,5),78), -- ((2,4),55),((2,5),32), -- ((3,4),61),((3,5),44), -- ((4,5),93)] -- λ> aristas ejGrafoND -- [((1,2),12),((1,3),34),((1,5),78), -- ((2,1),12),((2,4),55),((2,5),32), -- ((3,1),34),((3,4),61),((3,5),44), -- ((4,2),55),((4,3),61),((4,5),93), -- ((5,1),78),((5,2),32),((5,3),44),((5,4),93)] aristas :: (Ix v,Num p) => Grafo v p -> [((v,v),p)] aristas (G o g) = [((v1,v2),w) | v1 <- nodos (G o g) , (v2,w) <- g!v1] |
2.2.3. Implementación de los grafos mediante vectores de adyacencia
La implementación se encuentra en el módulo GrafoConMatrizDeAdyacencia cuyo contenido es el siguiente:
|
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 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 |
{-# LANGUAGE FlexibleInstances #-} module TAD.GrafoConMatrizDeAdyacencia (Orientacion (..), Grafo, creaGrafo, creaGrafo', dirigido, adyacentes, nodos, aristas, aristaEn, peso ) where -- Librerías auxiliares -- import Data.Array import Data.Maybe (isJust) import Data.List (sort) import Test.QuickCheck -- Orientacion es D (dirigida) ó ND (no dirigida). data Orientacion = D | ND deriving (Eq, Show) -- (Grafo v p) es un grafo con vértices de tipo v y pesos de tipo p. data Grafo v p = G Orientacion (Array (v,v) (Maybe p)) deriving Eq -- (escribeGrafo g) es la cadena correspondiente al grafo g. Por -- ejemplo, -- λ> escribeGrafo (creaGrafo ND (1,3) [(1,2,0),(2,3,5),(2,2,0)]) -- "G ND ([1,2,3],[((1,2),0),((2,2),0),((2,3),5)])" -- λ> escribeGrafo (creaGrafo D (1,3) [(1,2,0),(2,3,5),(2,2,0)]) -- "G D ([1,2,3],[((1,2),0),((2,2),0),((2,3),5)])" -- λ> escribeGrafo (creaGrafo ND (1,3) [(1,2,0),(2,3,0),(2,2,0)]) -- "G ND ([1,2,3],[(1,2),(2,2),(2,3)])" -- λ> escribeGrafo (creaGrafo D (1,3) [(1,2,0),(2,3,0),(2,2,0)]) -- "G D ([1,2,3],[(1,2),(2,2),(2,3)])" -- λ> escribeGrafo (creaGrafo D (1,3) [(1,2,0),(3,2,0),(2,2,0)]) -- "G D ([1,2,3],[(1,2),(2,2),(3,2)])" -- λ> escribeGrafo (creaGrafo ND (1,3) [(1,2,0),(3,2,0),(2,2,0)]) -- "G ND ([1,2,3],[(1,2),(2,2),(2,3)])" escribeGrafo :: (Ix v,Num p,Ord v, Ord p,Show v,Show p) => Grafo v p -> String escribeGrafo g@(G o _) = "G " ++ show o ++ " (" ++ show vs ++ "," ++ escribeAristas ++ ")" where as = sort (aristas g) vs = nodos g aristasReducidas | o == D = as | otherwise = [((x,y),p) | ((x,y),p) <- as, x <= y] escribeAristas | ponderado = show aristasReducidas | otherwise = show [a | (a,_) <- aristasReducidas] ponderado = any (\((_,_),p) -> p /= 0) as -- Procedimiento de escritura de grafos instance (Ix v,Num p,Ord v, Ord p,Show v,Show p) => Show (Grafo v p) where show = escribeGrafo -- (creaGrafo d cs as) es un grafo (dirigido o no, según el valor de o), -- con el par de cotas cs y listas de aristas as (cada arista es un trío -- formado por los dos vértices y su peso). Ver el ejemplo a continuación. creaGrafo :: (Ix v,Num p) => Orientacion -> (v,v) -> [(v,v,p)] -> Grafo v p creaGrafo D cs as = G D (matrizVacia cs // [((v1,v2),Just c) | (v1,v2,c) <- as]) creaGrafo ND cs as = G ND (matrizVacia cs // ([((v1,v2),Just c) | (v1,v2,c) <- as] ++ [((v2,v1),Just c) | (v1,v2,c) <- as, v1 /= v2])) matrizVacia :: Ix v => (v,v) -> Array (v,v) (Maybe p) matrizVacia (l,u) = listArray ((l,l),(u,u)) (repeat Nothing) -- (creaGrafo' o cs as) es un grafo (dirigido o no, según el valor de o), -- con el par de cotas cs y listas de aristas as (cada arista es un par -- de vértices y se supone que su peso es 0). Por ejemplo, -- λ> creaGrafo' ND (1,3) [(2,1),(1,3)] -- G ND ([1,2,3],[(1,2),(1,3)]) -- λ> creaGrafo' D (1,3) [(2,1),(1,3)] -- G D ([1,2,3],[(1,3),(2,1)]) creaGrafo' :: (Ix v, Num p, Ord v, Ord p) => Orientacion -> (v,v) -> [(v,v)] -> Grafo v p creaGrafo' o cs as = creaGrafo o cs [(v1,v2,0) | (v1,v2) <- as] -- ejGrafoND es el grafo -- 12 -- 1 -------- 2 -- | \78 /| -- | \ 32/ | -- | \ / | -- 34| 5 |55 -- | / \ | -- | /44 \ | -- | / 93\| -- 3 -------- 4 -- 61 -- representado mediante una matriz de adyacencia. -- λ> ejGrafoND -- G ND array ((1,1),(5,5)) -- [((1,1),Nothing),((1,2),Just 12),((1,3),Just 34), -- ((1,4),Nothing),((1,5),Just 78),((2,1),Just 12), -- ((2,2),Nothing),((2,3),Nothing),((2,4),Just 55), -- ((2,5),Just 32),((3,1),Just 34),((3,2),Nothing), -- ((3,3),Nothing),((3,4),Just 61),((3,5),Just 44), -- ((4,1),Nothing),((4,2),Just 55),((4,3),Just 61), -- ((4,4),Nothing),((4,5),Just 93),((5,1),Just 78), -- ((5,2),Just 32),((5,3),Just 44),((5,4),Just 93), -- ((5,5),Nothing)] ejGrafoND :: Grafo Int Int ejGrafoND = creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78), (2,4,55),(2,5,32), (3,4,61),(3,5,44), (4,5,93)] -- ejGrafoD es el mismo grafo que ejGrafoND pero orientando las aristas; -- es decir, -- λ> ejGrafoD -- G D (array ((1,1),(5,5)) -- [((1,1),Nothing),((1,2),Just 12),((1,3),Just 34), -- ((1,4),Nothing),((1,5),Just 78),((2,1),Nothing), -- ((2,2),Nothing),((2,3),Nothing),((2,4),Just 55), -- ((2,5),Just 32),((3,1),Nothing),((3,2),Nothing), -- ((3,3),Nothing),((3,4),Just 61),((3,5),Just 44), -- ((4,1),Nothing),((4,2),Nothing),((4,3),Nothing), -- ((4,4),Nothing),((4,5),Just 93),((5,1),Nothing), -- ((5,2),Nothing),((5,3),Nothing),((5,4),Nothing), -- ((5,5),Nothing)]) ejGrafoD :: Grafo Int Int ejGrafoD = creaGrafo D (1,5) [(1,2,12),(1,3,34),(1,5,78), (2,4,55),(2,5,32), (3,4,61),(3,5,44), (4,5,93)] -- (dirigido g) se verifica si g es dirigido. Por ejemplo, -- dirigido ejGrafoD == True -- dirigido ejGrafoND == False dirigido :: (Ix v,Num p) => Grafo v p -> Bool dirigido (G o _) = o == D -- (nodos g) es la lista de todos los nodos del grafo g. Por ejemplo, -- nodos ejGrafoND == [1,2,3,4,5] -- nodos ejGrafoD == [1,2,3,4,5] nodos :: (Ix v,Num p) => Grafo v p -> [v] nodos (G _ g) = range (l,u) where ((l,_),(u,_)) = bounds g -- (adyacentes g v) es la lista de los vértices adyacentes al nodo v en -- el grafo g. Por ejemplo, -- adyacentes ejGrafoND 4 == [2,3,5] -- adyacentes ejGrafoD 4 == [5] adyacentes :: (Ix v,Num p,Eq p) => Grafo v p -> v -> [v] adyacentes (G o g) v = [v' | v' <- nodos (G o g), isJust (g!(v,v'))] -- (aristaEn g a) se verifica si a es una arista del grafo g. Por -- ejemplo, -- aristaEn ejGrafoND (5,1) == True -- aristaEn ejGrafoND (4,1) == False aristaEn :: (Ix v,Num p,Eq p) => Grafo v p -> (v,v) -> Bool aristaEn (G _o g) (x,y) = isJust (g!(x,y)) -- (peso v1 v2 g) es el peso de la arista que une los vértices v1 y v2 -- en el grafo g. Por ejemplo, -- peso 1 5 ejGrafoND == 78 -- peso 1 5 ejGrafoD == 78 peso :: (Ix v,Num p) => v -> v -> Grafo v p -> p peso x y (G _ g) = w where (Just w) = g!(x,y) -- (aristas g) es la lista de las aristas del grafo g. Por ejemplo, -- λ> aristas ejGrafoD -- [(1,2,12),(1,3,34),(1,5,78),(2,4,55),(2,5,32),(3,4,61), -- (3,5,44),(4,5,93)] -- λ> aristas ejGrafoND -- [(1,2,12),(1,3,34),(1,5,78),(2,1,12),(2,4,55),(2,5,32), -- (3,1,34),(3,4,61),(3,5,44),(4,2,55),(4,3,61),(4,5,93), -- (5,1,78),(5,2,32),(5,3,44),(5,4,93)] aristas :: (Ix v,Num p, Eq p) => Grafo v p -> [((v,v),p)] aristas g@(G _ e) = [((v1,v2),extrae(e!(v1,v2))) | v1 <- nodos g, v2 <- nodos g, aristaEn g (v1,v2)] where extrae (Just w) = w extrae _ = error "Imposible" |
2.3. Los grafos en Python
2.3.1. El tipo abstracto de los grafos en Python
La implementación se encuentra en el módulo Grafo.py cuyo contenido es el siguiente:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
__all__ = [ 'Orientacion', 'Grafo', 'creaGrafo', 'creaGrafo_', 'dirigido', 'adyacentes', 'nodos', 'aristas', 'aristaEn', 'peso' ] from src.TAD.GrafoConListaDeAdyacencia import (Grafo, Orientacion, adyacentes, aristaEn, aristas, creaGrafo, creaGrafo_, dirigido, nodos, peso) |
2.3.2. Implementación de los grafos mediante listas
Se define la clase Grafo con los siguientes métodos:
- dirigido() se verifica si el grafo es dirigido.
- nodos() es la lista de todos los nodos del grafo.
- aristas() es la lista de las aristas del grafo.
- adyacentes(v) es la lista de los vértices adyacentes al vértice v en el grafo.
- aristaEn(a) se verifica si a es una arista del grafo.
- peso(v1, v2) es el peso de la arista que une los vértices v1 y v2 en el grafo.
Por ejemplo,
|
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 |
>>> Grafo(Orientacion.D, (1,3), [((1,2),0),((3,2),0),((2,2),0)]) G D ([1, 2, 3], [(1, 2), (2, 2), (3, 2)]) >>> Grafo(Orientacion.ND, (1,3), [((1,2),0),((3,2),0),((2,2),0)]) G ND ([1, 2, 3], [(1, 2), (2, 2), (2, 3)]) >>> Grafo(Orientacion.ND, (1,3), [((1,2),0),((3,2),5),((2,2),0)]) G ND ([1, 2, 3], [((1, 2), 0), ((2, 2), 0), ((2, 3), 5)]) >>> Grafo(Orientacion.D, (1,3), [((1,2),0),((3,2),5),((2,2),0)]) G D ([1, 2, 3], [((1, 2), 0), ((2, 2), 0), ((3, 2), 5)]) >>> ejGrafoND: Grafo = Grafo(Orientacion.ND, (1, 5), [((1, 2), 12), ((1, 3), 34), ((1, 5), 78), ((2, 4), 55), ((2, 5), 32), ((3, 4), 61), ((3, 5), 44), ((4, 5), 93)]) >>> ejGrafoND G ND ([1, 2, 3, 4, 5], [((1, 2), 12), ((1, 3), 34), ((1, 5), 78), ((2, 4), 55), ((2, 5), 32), ((3, 4), 61), ((3, 5), 44), ((4, 5), 93)]) >> ejGrafoD: Grafo = Grafo(Orientacion.D, (1,5), [((1, 2), 12), ((1, 3), 34), ((1, 5), 78), ((2, 4), 55), ((2, 5), 32), ((3, 4), 61), ((3, 5), 44), ((4, 5), 93)]) >>> ejGrafoD G D ([1, 2, 3, 4, 5], [((1, 2), 12), ((1, 3), 34), ((1, 5), 78), ((2, 4), 55), ((2, 5), 32), ((3, 4), 61), ((3, 5), 44), ((4, 5), 93)]) >>> ejGrafoD.dirigido() True >>> ejGrafoND.dirigido() False >>> ejGrafoND.nodos() [1, 2, 3, 4, 5] >>> ejGrafoD.nodos() [1, 2, 3, 4, 5] >>> ejGrafoND.adyacentes(4) [2, 3, 5] >>> ejGrafoD.adyacentes(4) [5] >>> ejGrafoND.aristaEn((5, 1)) True >>> ejGrafoND.aristaEn((4, 1)) False >>> ejGrafoD.aristaEn((5, 1)) False >>> ejGrafoD.aristaEn((1, 5)) True >>> ejGrafoND.peso(1, 5) 78 >>> ejGrafoD.peso(1, 5) 78 >>> ejGrafoD._aristas [((1, 2), 12), ((1, 3), 34), ((1, 5), 78), ((2, 4), 55), ((2, 5), 32), ((3, 4), 61), ((3, 5), 44), ((4, 5), 93)] >>> ejGrafoND._aristas [((1, 2), 12), ((1, 3), 34), ((1, 5), 78), ((2, 1), 12), ((2, 4), 55), ((2, 5), 32), ((3, 1), 34), ((3, 4), 61), ((3, 5), 44), ((4, 2), 55), ((4, 3), 61), ((4, 5), 93), ((5, 1), 78), ((5, 2), 32), ((5, 3), 44), ((5, 4), 93)] |
Además se definen las correspondientes funciones. Por ejemplo,
|
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 |
>>> creaGrafo(Orientacion.ND, (1,3), [((1,2),12),((1,3),34)]) G ND ([1, 2, 3], [((1, 2), 12), ((1, 3), 34), ((2, 1), 12), ((3, 1), 34)]) >>> creaGrafo(Orientacion.D, (1,3), [((1,2),12),((1,3),34)]) G D ([1, 2, 3], [((1, 2), 12), ((1, 3), 34)]) >>> creaGrafo(Orientacion.D, (1,4), [((1,2),12),((1,3),34)]) G D ([1, 2, 3, 4], [((1, 2), 12), ((1, 3), 34)]) >>> ejGrafoND2: Grafo = creaGrafo(Orientacion.ND, (1,5), [((1,2),12),((1,3),34),((1,5),78), ((2,4),55),((2,5),32), ((3,4),61),((3,5),44), ((4,5),93)]) >>> ejGrafoND2 G ND ([1, 2, 3, 4, 5], [((1, 2), 12), ((1, 3), 34), ((1, 5), 78), ((2, 4), 55), ((2, 5), 32), ((3, 4), 61), ((3, 5), 44), ((4, 5), 93)]) >>> ejGrafoD2: Grafo = creaGrafo(Orientacion.D, (1,5), [((1,2),12),((1,3),34),((1,5),78), ((2,4),55),((2,5),32), ((3,4),61),((3,5),44), ((4,5),93)]) >>> ejGrafoD2 G D ([1, 2, 3, 4, 5], [((1, 2), 12), ((1, 3), 34), ((1, 5), 78), ((2, 4), 55), ((2, 5), 32), ((3, 4), 61), ((3, 5), 44), ((4, 5), 93)]) >>> creaGrafo_(Orientacion.D, (1,3), [(2, 1), (1, 3)]) G D ([1, 2, 3], [(1, 3), (2, 1)]) >>> creaGrafo_(Orientacion.ND, (1,3), [(2, 1), (1, 3)]) G ND ([1, 2, 3], [(1, 2), (1, 3)]) >>> dirigido(ejGrafoD2) True >>> dirigido(ejGrafoND2) False >>> nodos(ejGrafoND2) [1, 2, 3, 4, 5] >>> nodos(ejGrafoD2) [1, 2, 3, 4, 5] >>> adyacentes(ejGrafoND2, 4) [2, 3, 5] >>> adyacentes(ejGrafoD2, 4) [5] >>> aristaEn(ejGrafoND2, (5,1)) True >>> aristaEn(ejGrafoND2, (4,1)) False >>> aristaEn(ejGrafoD2, (5,1)) False >>> aristaEn(ejGrafoD2, (1,5)) True >>> peso(1, 5, ejGrafoND2) 78 >>> peso(1, 5, ejGrafoD2) 78 >>> aristas(ejGrafoD2) [((1, 2), 12), ((1, 3), 34), ((1, 5), 78), ((2, 4), 55), ((2, 5), 32), ((3, 4), 61), ((3, 5), 44), ((4, 5), 93)] >>> aristas(ejGrafoND2) [((1, 2), 12), ((1, 3), 34), ((1, 5), 78), ((2, 1), 12), ((2, 4), 55), ((2, 5), 32), ((3, 1), 34), ((3, 4), 61), ((3, 5), 44), ((4, 2), 55), ((4, 3), 61), ((4, 5), 93), ((5, 1), 78), ((5, 2), 32), ((5, 3), 44), ((5, 4), 93)] |
La implementación se encuentra en el módulo GrafoConListaDeAdyacencia cuyo contenido es el siguiente:
|
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 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 |
from enum import Enum Orientacion = Enum('Orientacion', ['D', 'ND']) Vertice = int Cotas = tuple[Vertice, Vertice] Peso = float Arista = tuple[tuple[Vertice, Vertice], Peso] class Grafo: def __init__(self, _orientacion: Orientacion, _cotas: Cotas, _aristas: list[Arista]): self._orientacion = _orientacion self._cotas = _cotas if _orientacion == Orientacion.ND: simetricas = [((v2, v1), p) for ((v1, v2), p) in _aristas if v1 != v2] self._aristas = sorted(_aristas + simetricas) else: self._aristas = sorted(_aristas) def nodos(self) -> list[Vertice]: (x, y) = self._cotas return list(range(x, 1 + y)) def __repr__(self) -> str: o = self._orientacion vs = nodos(self) ns = self._aristas escribeOrientacion = "D" if o == Orientacion.D else "ND" ponderado = {p for ((_, _), p) in ns} != {0} aristasReducidas = ns if o == Orientacion.D \ else [((x, y), p) for ((x, y), p) in ns if x <= y] escribeAristas = str(aristasReducidas) if ponderado \ else str([a for (a, _) in aristasReducidas]) return f"G {escribeOrientacion} ({vs}, {escribeAristas})" def dirigido(self) -> bool: return self._orientacion == Orientacion.D def adyacentes(self, v: int) -> list[int]: return list(set(u for ((w, u), _) in self._aristas if w == v)) def aristaEn(self, a: tuple[Vertice, Vertice]) -> bool: (x, y) = a return y in self.adyacentes(x) def peso(self, v1: Vertice, v2: Vertice) -> Peso: return [p for ((x1, x2), p) in self._aristas if (x1, x2) == (v1, v2)][0] def creaGrafo(o: Orientacion, cs: Cotas, as_: list[Arista]) -> Grafo: return Grafo(o, cs, as_) def creaGrafo_(o: Orientacion, cs: Cotas, as_: list[tuple[Vertice, Vertice]]) -> Grafo: return Grafo(o, cs, [((v1, v2), 0) for (v1, v2) in as_]) def dirigido(g: Grafo) -> bool: return g.dirigido() def nodos(g: Grafo) -> list[Vertice]: return g.nodos() def adyacentes(g: Grafo, v: Vertice) -> list[Vertice]: return g.adyacentes(v) def aristaEn(g: Grafo, a: tuple[Vertice, Vertice]) -> bool: return g.aristaEn(a) def peso(v1: Vertice, v2: Vertice, g: Grafo) -> Peso: return g.peso(v1, v2) def aristas(g: Grafo) -> list[Arista]: return g._aristas # En los ejemplos se usarán los grafos (no dirigido y dirigido) # correspondientes a # 12 # 1 -------- 2 # | \78 /| # | \ 32/ | # | \ / | # 34| 5 |55 # | / \ | # | /44 \ | # | / 93\| # 3 -------- 4 # 61 # definidos por ejGrafoND: Grafo = Grafo(Orientacion.ND, (1, 5), [((1, 2), 12), ((1, 3), 34), ((1, 5), 78), ((2, 4), 55), ((2, 5), 32), ((3, 4), 61), ((3, 5), 44), ((4, 5), 93)]) ejGrafoD: Grafo = Grafo(Orientacion.D, (1,5), [((1, 2), 12), ((1, 3), 34), ((1, 5), 78), ((2, 4), 55), ((2, 5), 32), ((3, 4), 61), ((3, 5), 44), ((4, 5), 93)]) ejGrafoND2: Grafo = creaGrafo(Orientacion.ND, (1,5), [((1,2),12),((1,3),34),((1,5),78), ((2,4),55),((2,5),32), ((3,4),61),((3,5),44), ((4,5),93)]) ejGrafoD2: Grafo = creaGrafo(Orientacion.D, (1,5), [((1,2),12),((1,3),34),((1,5),78), ((2,4),55),((2,5),32), ((3,4),61),((3,5),44), ((4,5),93)]) |
3. TAD de los grafos: Grafos completos
El grafo completo de orden n, K(n), es un grafo no dirigido cuyos conjunto de vértices es {1,..n} y tiene una arista entre cada par de vértices distintos.
Usando el tipo abstrado de datos de los grafos, definir la función,
|
1 |
completo :: Int -> Grafo Int Int |
tal que completo n es el grafo completo de orden n. Por ejemplo,
|
1 2 |
λ> completo 4 G ND ([1,2,3,4],[(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)]) |
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 |
module Grafo_Grafos_completos where import TAD.Grafo (Grafo, Orientacion (ND), creaGrafo') import Test.Hspec (Spec, hspec, it, shouldBe) completo :: Int -> Grafo Int Int completo n = creaGrafo' ND (1,n) [(x,y) | x <- [1..n], y <- [x+1..n]] -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ show (completo 4) `shouldBe` "G ND ([1,2,3,4],[(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)])" -- La verificación es -- λ> verifica -- -- e1 -- -- Finished in 0.0004 seconds -- 1 example, 0 failures |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
from src.TAD.Grafo import Grafo, Orientacion, creaGrafo_ def completo(n: int) -> Grafo: return creaGrafo_(Orientacion.ND, (1, n), [(x, y) for x in range(1, n + 1) for y in range(x + 1, n+1)]) # Verificación # ============ def test_completo() -> None: assert str(completo(4)) == \ "G ND ([1, 2, 3, 4], [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)])" print("Verificado") # La verificación es # >>> test_completo() # Verificado |
4. TAD de los grafos: Grafos ciclos
El ciclo de orden n, C(n), es un grafo no dirigido cuyo conjunto de vértices es {1,…,n} y las aristas son
|
1 |
(1,2), (2,3), ..., (n-1,n), (n,1) |
Usando el tipo abstrado de datos de los grafos, definir la función,
|
1 |
grafoCiclo :: Int -> Grafo Int Int |
tal que (grafoCiclo n) es el grafo ciclo de orden n. Por ejemplo,
|
1 2 |
λ> grafoCiclo 3 G ND ([1,2,3],[(1,2),(1,3),(2,3)]) |
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 |
module Grafo_Grafos_ciclos where import TAD.Grafo (Grafo, Orientacion (ND), creaGrafo') import Test.Hspec (Spec, hspec, it, shouldBe) grafoCiclo :: Int -> Grafo Int Int grafoCiclo n = creaGrafo' ND (1,n) ((n,1):[(x,x+1) | x <- [1..n-1]]) -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ show (grafoCiclo 3) `shouldBe` "G ND ([1,2,3],[(1,2),(1,3),(2,3)])" -- La verificación es -- λ> verifica -- -- e1 -- -- Finished in 0.0006 seconds -- 1 example, 0 failures |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
from src.TAD.Grafo import Grafo, Orientacion, creaGrafo_ def grafoCiclo(n: int) -> Grafo: return creaGrafo_(Orientacion.ND, (1, n), [(n,1)] + [(x, x + 1) for x in range(1, n)]) # Verificación # ============ def test_grafoCiclo() -> None: assert str(grafoCiclo(3)) == \ "G ND ([1, 2, 3], [(1, 2), (1, 3), (2, 3)])" print("Verificado") # La verificación es # >>> test_grafoCiclo() # Verificado |
5. TAD de los grafos: Número de vértices
Usando el tipo abstrado de datos de los grafos, definir la función,
|
1 |
nVertices :: (Ix v, Num p) => Grafo v p -> Int |
tal que nVertices g es el número de vértices del grafo g. Por ejemplo,
|
1 2 |
nVertices (creaGrafo' D (1,5) [(1,2),(3,1)]) == 5 nVertices (creaGrafo' ND (2,4) [(1,2),(3,1)]) == 3 |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
1 2 3 4 5 6 7 |
module Grafo_Numero_de_vertices where import TAD.Grafo (Grafo, Orientacion (D, ND), nodos, creaGrafo') import Data.Ix nVertices :: (Ix v, Num p) => Grafo v p -> Int nVertices = length . nodos |
|
1 2 3 4 5 |
from src.TAD.Grafo import Grafo, Orientacion, creaGrafo_, nodos def nVertices(g: Grafo) -> int: return len(nodos(g)) |