Grafos – Exercitium

TAD de los grafos: Algoritmo de Prim

José A. Alonso, 23-junio-2023, Haskell y Python

El algoritmo de Prim calcula un árbol recubridor mínimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el valor de la suma de todas las aristas del árbol es el mínimo.

El algoritmo de Prim funciona de la siguiente manera:

Inicializar un árbol con un único vértice, elegido arbitrariamente, del grafo.
Aumentar el árbol por un lado. Llamamos lado a la unión entre dos vértices: de las posibles uniones que pueden conectar el árbol a los vértices que no están aún en el árbol, encontrar el lado de menor distancia y unirlo al árbol.
Repetir el paso 2 (hasta que todos los vértices pertenezcan al árbol)

Usando el tipo abstracto de datos de los grafos, definir la función,

   prim :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)]

tal que prim g es el árbol de expansión mínimo del grafo g calculado mediante el algoritmo de Prim. Por ejemplo, si g1, g2, g3 y g4 son los grafos definidos por

   g1, g2, g3, g4 :: Grafo Int Int
   g1 = 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)]
   g2 = creaGrafo ND (1,5) [(1,2,13),(1,3,11),(1,5,78),
                            (2,4,12),(2,5,32),
                            (3,4,14),(3,5,44),
                            (4,5,93)]
   g3 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6),
                            (2,3,7),
                            (3,4,8),(3,5,7),
                            (4,5,5),
                            (5,6,3),(5,7,9),
                            (6,7,11)]
   g4 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6),
                            (2,3,7),
                            (3,4,8),(3,5,1),
                            (4,5,5),
                            (5,6,3),(5,7,9),
                            (6,7,11)]

entonces

   prim g1  == [(55,2,4),(34,1,3),(32,2,5),(12,1,2)]
   prim g2  == [(32,2,5),(12,2,4),(13,1,2),(11,1,3)]
   prim g3  == [(9,5,7),(7,2,3),(5,5,4),(3,6,5),(6,1,6),(5,1,2)]

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

module Grafo_Algoritmo_de_Prim where
 
import TAD.Grafo (Grafo, Orientacion (ND), aristas, creaGrafo, nodos)
import Data.Ix (Ix)
import Data.List (delete)
import Test.Hspec (Spec, hspec, it, shouldBe)
 
g1, g2, g3, g4 :: Grafo Int Int
g1 = 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)]
g2 = creaGrafo ND (1,5) [(1,2,13),(1,3,11),(1,5,78),
                         (2,4,12),(2,5,32),
                         (3,4,14),(3,5,44),
                         (4,5,93)]
g3 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6),
                         (2,3,7),
                         (3,4,8),(3,5,7),
                         (4,5,5),
                         (5,6,3),(5,7,9),
                         (6,7,11)]
g4 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6),
                         (2,3,7),
                         (3,4,8),(3,5,1),
                         (4,5,5),
                         (5,6,3),(5,7,9),
                         (6,7,11)]
 
prim :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)]
prim g = prim' [n]              -- Nodos colocados
               ns               -- Nodos por colocar
               []               -- Árbol de expansión
               (aristas g)      -- Aristas del grafo
  where
    (n:ns) = nodos g
    prim' _ _ _  []  = []
    prim' _ [] ae _  = ae
    prim' t r  ae as = prim' (v':t) (delete v' r) (e:ae) as
      where e@(_,_, v') = minimum [(c,u,v)| ((u,v),c) <- as,
                                             u `elem` t,
                                             v `elem` r]
 
-- Verificación
-- ============
 
verifica :: IO ()
verifica = hspec spec
 
spec :: Spec
spec = do
  it "e1" $
    prim g1 `shouldBe` [(55,2,4),(34,1,3),(32,2,5),(12,1,2)]
  it "e2" $
    prim g2 `shouldBe` [(32,2,5),(12,2,4),(13,1,2),(11,1,3)]
  it "e3" $
    prim g3 `shouldBe` [(9,5,7),(7,2,3),(5,5,4),(3,6,5),(6,1,6),(5,1,2)]
 
-- La verificación es
--    λ> verifica
--
--    e1
--    e2
--    e3
--
--    Finished in 0.0026 seconds
--    3 examples, 0 failures

module Grafo_Algoritmo_de_Prim where import TAD.Grafo (Grafo, Orientacion (ND), aristas, creaGrafo, nodos) import Data.Ix (Ix) import Data.List (delete) import Test.Hspec (Spec, hspec, it, shouldBe) g1, g2, g3, g4 :: Grafo Int Int g1 = 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)] g2 = creaGrafo ND (1,5) [(1,2,13),(1,3,11),(1,5,78), (2,4,12),(2,5,32), (3,4,14),(3,5,44), (4,5,93)] g3 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6), (2,3,7), (3,4,8),(3,5,7), (4,5,5), (5,6,3),(5,7,9), (6,7,11)] g4 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6), (2,3,7), (3,4,8),(3,5,1), (4,5,5), (5,6,3),(5,7,9), (6,7,11)] prim :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)] prim g = prim' [n] -- Nodos colocados ns -- Nodos por colocar [] -- Árbol de expansión (aristas g) -- Aristas del grafo where (n:ns) = nodos g prim' _ _ _ [] = [] prim' _ [] ae _ = ae prim' t r ae as = prim' (v':t) (delete v' r) (e:ae) as where e@(_,_, v') = minimum [(c,u,v)| ((u,v),c) <- as, u `elem` t, v `elem` r] -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ prim g1 `shouldBe` [(55,2,4),(34,1,3),(32,2,5),(12,1,2)] it "e2" $ prim g2 `shouldBe` [(32,2,5),(12,2,4),(13,1,2),(11,1,3)] it "e3" $ prim g3 `shouldBe` [(9,5,7),(7,2,3),(5,5,4),(3,6,5),(6,1,6),(5,1,2)] -- La verificación es -- λ> verifica -- -- e1 -- e2 -- e3 -- -- Finished in 0.0026 seconds -- 3 examples, 0 failures

Soluciones en Python

from src.TAD.Grafo import (Grafo, Orientacion, Peso, Vertice, aristas,
                           creaGrafo, nodos)
 
g1 = 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)])
g2 = creaGrafo (Orientacion.ND,
                (1,5),
                [((1,2),13),((1,3),11),((1,5),78),
                 ((2,4),12),((2,5),32),
                 ((3,4),14),((3,5),44),
                 ((4,5),93)])
g3 = creaGrafo (Orientacion.ND,
                (1,7),
                [((1,2),5),((1,3),9),((1,5),15),((1,6),6),
                 ((2,3),7),
                 ((3,4),8),((3,5),7),
                 ((4,5),5),
                 ((5,6),3),((5,7),9),
                 ((6,7),11)])
g4 = creaGrafo (Orientacion.ND,
                (1,7),
                [((1,2),5),((1,3),9),((1,5),15),((1,6),6),
                 ((2,3),7),
                 ((3,4),8),((3,5),1),
                 ((4,5),5),
                 ((5,6),3),((5,7),9),
                 ((6,7),11)])
 
def prim(g: Grafo) -> list[tuple[Peso, Vertice, Vertice]]:
    n, *ns = nodos(g)
    def prim_(t: list[Vertice],
              r: list[Vertice],
              ae: list[tuple[Peso, Vertice, Vertice]],
              as_: list[tuple[tuple[Vertice, Vertice], Peso]]) \
              -> list[tuple[Peso, Vertice, Vertice]]:
        if not as_:
            return []
        if not r:
            return ae
        e = min(((c,u,v)
                 for ((u,v),c) in as_
                 if u in t and v in r))
        (_,_, v_) = e
        return prim_([v_] + t, [x for x in r if x != v_], [e] + ae, as_)
    return prim_([n], ns, [], aristas(g))
 
# Verificación
# ============
 
def test_prim() -> None:
    assert prim(g1)  == [(55,2,4),(34,1,3),(32,2,5),(12,1,2)]
    assert prim(g2)  == [(32,2,5),(12,2,4),(13,1,2),(11,1,3)]
    assert prim(g3)  == [(9,5,7),(7,2,3),(5,5,4),(3,6,5),(6,1,6),(5,1,2)]
    print("Verificado")
 
# La verificación es
#    >>> test_prim()
#    Verificado

Leer más →

TAD de los grafos: Algoritmo de Kruskal

José A. Alonso, 22-junio-2023, Haskell y Python

El algoritmo de Kruskal calcula un árbol recubridor mínimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el valor de la suma de todas las aristas del árbol es el mínimo.

El algoritmo de Kruskal funciona de la siguiente manera:

se crea un bosque B (un conjunto de árboles), donde cada vértice del grafo es un árbol separado
se crea un conjunto C que contenga a todas las aristas del grafo
mientras C es no vacío,
- eliminar una arista de peso mínimo de C
- si esa arista conecta dos árboles diferentes se añade al bosque, combinando los dos árboles en un solo árbol
- en caso contrario, se desecha la arista

Al acabar el algoritmo, el bosque tiene un solo componente, el cual forma un árbol de expansión mínimo del grafo.

Usando el tipo abstracto de datos de los grafos, definir la función,

   kruskal :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)]

tal que kruskal g es el árbol de expansión mínimo del grafo g calculado mediante el algoritmo de Kruskal. Por ejemplo, si g1, g2, g3 y g4 son los grafos definidos por

   g1, g2, g3, g4 :: Grafo Int Int
   g1 = 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)]
   g2 = creaGrafo ND (1,5) [(1,2,13),(1,3,11),(1,5,78),
                            (2,4,12),(2,5,32),
                            (3,4,14),(3,5,44),
                            (4,5,93)]
   g3 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6),
                            (2,3,7),
                            (3,4,8),(3,5,7),
                            (4,5,5),
                            (5,6,3),(5,7,9),
                            (6,7,11)]
   g4 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6),
                            (2,3,7),
                            (3,4,8),(3,5,1),
                            (4,5,5),
                            (5,6,3),(5,7,9),
                            (6,7,11)]

entonces

   kruskal g1  ==  [(55,2,4),(34,1,3),(32,2,5),(12,1,2)]
   kruskal g2  ==  [(32,2,5),(13,1,2),(12,2,4),(11,1,3)]
   kruskal g3  ==  [(9,5,7),(7,2,3),(6,1,6),(5,4,5),(5,1,2),(3,5,6)]
   kruskal g4  ==  [(9,5,7),(6,1,6),(5,4,5),(5,1,2),(3,5,6),(1,3,5)]

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

module Grafo_Algoritmo_de_Kruskal where
 
import TAD.Grafo (Grafo, Orientacion (ND), aristas, creaGrafo, nodos)
import Data.Ix (Ix)
import qualified Data.Map as M (Map, (!), fromList, keys, update)
import Data.List (sort)
import Test.Hspec (Spec, hspec, it, shouldBe)
 
g1, g2, g3, g4 :: Grafo Int Int
g1 = 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)]
g2 = creaGrafo ND (1,5) [(1,2,13),(1,3,11),(1,5,78),
                         (2,4,12),(2,5,32),
                         (3,4,14),(3,5,44),
                         (4,5,93)]
g3 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6),
                         (2,3,7),
                         (3,4,8),(3,5,7),
                         (4,5,5),
                         (5,6,3),(5,7,9),
                         (6,7,11)]
g4 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6),
                         (2,3,7),
                         (3,4,8),(3,5,1),
                         (4,5,5),
                         (5,6,3),(5,7,9),
                         (6,7,11)]
 
kruskal :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)]
kruskal g = aux (sort [(p,x,y) | ((x,y),p) <- aristas g])
                (M.fromList [(x,x) | x <- nodos g])
                []
                (length (nodos g) - 1)
  where aux _  _ ae 0 = ae
        aux [] _ _  _ = error "Imposible"
        aux ((p,x,y):as) d ae n
          | actualizado = aux as d' ((p,x,y):ae) (n-1)
          | otherwise   = aux as d ae n
          where (actualizado,d') = buscaActualiza (x,y) d
 
-- (raiz d n) es la raíz de n en el diccionario. Por ejemplo,
--    raiz (M.fromList [(1,1),(3,1),(4,3),(5,4),(2,6),(6,6)]) 5  == 1
--    raiz (M.fromList [(1,1),(3,1),(4,3),(5,4),(2,6),(6,6)]) 2  == 6
raiz :: (Eq n, Ord n) => M.Map n n -> n -> n
raiz d x | v == x    = v
         | otherwise = raiz d v
  where v = d M.! x
 
-- (buscaActualiza a d) es el par formado por False y el diccionario d,
-- si los dos vértices de la arista a tienen la misma raíz en d y el par
-- formado por True y la tabla obtenida añadiéndole a d la arista
-- formada por el vértice de a de mayor raíz y la raíz del vértice de a
-- de menor raíz. Y actualizando las raices de todos los elementos
-- afectados por la raíz añadida. Por ejemplo,
--   λ> d = M.fromList [(1,1),(2,1),(3,3),(4,4),(5,5),(6,5),(7,7)]
--   λ> buscaActualiza (5,4) d
--   (True,fromList [(1,1),(2,1),(3,3),(4,4),(5,4),(6,4),(7,7)])
--   λ> d' = snd it
--   λ> buscaActualiza (6,1) d'
--   (True,fromList [(1,1),(2,1),(3,3),(4,1),(5,1),(6,1),(7,7)])
buscaActualiza :: (Eq n, Ord n) => (n,n) -> M.Map n n -> (Bool,M.Map n n)
buscaActualiza (x,y) d
  | x' == y'  = (False, d)
  | y' <  x'  = (True, modificaR x (d M.! x) y' d)
  | otherwise = (True, modificaR y (d M.! y) x' d)
  where x' = raiz d x
        y' = raiz d y
 
-- (modificaR x y y' d) actualiza d como sigue:
-- + el valor de todas las claves z con valor y es y'
-- + el valor de todas las claves z con (z > x) con valor x es y'
modificaR :: (Eq n, Ord n) => n -> n -> n -> M.Map n n -> M.Map n n
modificaR x y y' d = aux2 ds (aux1 cs d)
  where cs = M.keys d
        ds = filter (>x) cs
        aux1 [] tb = tb
        aux1 (a:as) tb | tb M.! a == y = aux1 as (M.update (\_ -> Just y') a tb)
                       | otherwise     = aux1 as tb
        aux2 [] tb = tb
        aux2 (b:bs) tb | tb M.! b == x = aux2 bs (M.update (\_ -> Just y') b tb)
                       | otherwise     = aux2 bs tb
 
-- Traza del diccionario correspondiente al grafo g3
-- =================================================
 
-- Lista de aristas, ordenadas según su peso:
-- [(3,5,6),(5,1,2),(5,4,5),(6,1,6),(7,2,3),(7,3,5),(8,3,4),(9,1,3),(9,5,7),(11,6,7),(15,1,5)]
--
-- Inicial
--   fromList [(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(7,7)]
--
-- Después de añadir la arista (5,6) de peso 3
--   fromList [(1,1),(2,2),(3,3),(4,4),(5,5),(6,5),(7,7)]
--
-- Después de añadir la arista (1,2) de peso 5
--   fromList [(1,1),(2,1),(3,3),(4,4),(5,5),(6,5),(7,7)]
--
-- Después de añadir la arista (4,5) de peso 5
--   fromList [(1,1),(2,1),(3,3),(4,4),(5,4),(6,4),(7,7)]
--
-- Después de añadir la arista (1,6) de peso 6
--   fromList [(1,1),(2,1),(3,3),(4,1),(5,1),(6,1),(7,7)]
--
-- Después de añadir la arista (2,3) de peso 7
--   fromList [(1,1),(2,1),(3,1),(4,1),(5,1),(6,1),(7,7)]
--
-- Las posibles aristas a añadir son:
-- + la (3,5) con peso 7, que no es posible pues la raíz de 3
--   coincide con la raíz de 5, por lo que formaría un ciclo
-- + la (3,4) con peso 8, que no es posible pues la raíz de 3
--   coincide con la raíz de 4, por lo que formaría un ciclo
-- + la (1,3) con peso 9, que no es posible pues la raíz de 3
--   coincide con la raíz de 1, por lo que formaría un ciclo
-- + la (5,7) con peso 9, que no forma ciclo
--
-- Después de añadir la arista (5,7) con peso 9
--    fromList [(1,1),(2,1),(3,1),(4,1),(5,1),(6,1),(7,1)]
--
-- No es posible añadir más aristas, pues formarían ciclos.
 
-- Verificación
-- ============
 
verifica :: IO ()
verifica = hspec spec
 
spec :: Spec
spec = do
  it "e1" $
    kruskal g1 `shouldBe` [(55,2,4),(34,1,3),(32,2,5),(12,1,2)]
  it "e2" $
    kruskal g2 `shouldBe` [(32,2,5),(13,1,2),(12,2,4),(11,1,3)]
  it "e3" $
    kruskal g3 `shouldBe` [(9,5,7),(7,2,3),(6,1,6),(5,4,5),(5,1,2),(3,5,6)]
  it "e4" $
    kruskal g4 `shouldBe` [(9,5,7),(6,1,6),(5,4,5),(5,1,2),(3,5,6),(1,3,5)]
 
-- La verificación es
--    λ> verifica
--
--    e1
--    e2
--    e3
--    e4
--
--    Finished in 0.0044 seconds
--    4 examples, 0 failures

module Grafo_Algoritmo_de_Kruskal where import TAD.Grafo (Grafo, Orientacion (ND), aristas, creaGrafo, nodos) import Data.Ix (Ix) import qualified Data.Map as M (Map, (!), fromList, keys, update) import Data.List (sort) import Test.Hspec (Spec, hspec, it, shouldBe) g1, g2, g3, g4 :: Grafo Int Int g1 = 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)] g2 = creaGrafo ND (1,5) [(1,2,13),(1,3,11),(1,5,78), (2,4,12),(2,5,32), (3,4,14),(3,5,44), (4,5,93)] g3 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6), (2,3,7), (3,4,8),(3,5,7), (4,5,5), (5,6,3),(5,7,9), (6,7,11)] g4 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6), (2,3,7), (3,4,8),(3,5,1), (4,5,5), (5,6,3),(5,7,9), (6,7,11)] kruskal :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)] kruskal g = aux (sort [(p,x,y) | ((x,y),p) <- aristas g]) (M.fromList [(x,x) | x <- nodos g]) [] (length (nodos g) - 1) where aux _ _ ae 0 = ae aux [] _ _ _ = error "Imposible" aux ((p,x,y):as) d ae n | actualizado = aux as d' ((p,x,y):ae) (n-1) | otherwise = aux as d ae n where (actualizado,d') = buscaActualiza (x,y) d -- (raiz d n) es la raíz de n en el diccionario. Por ejemplo, -- raiz (M.fromList [(1,1),(3,1),(4,3),(5,4),(2,6),(6,6)]) 5 == 1 -- raiz (M.fromList [(1,1),(3,1),(4,3),(5,4),(2,6),(6,6)]) 2 == 6 raiz :: (Eq n, Ord n) => M.Map n n -> n -> n raiz d x | v == x = v | otherwise = raiz d v where v = d M.! x -- (buscaActualiza a d) es el par formado por False y el diccionario d, -- si los dos vértices de la arista a tienen la misma raíz en d y el par -- formado por True y la tabla obtenida añadiéndole a d la arista -- formada por el vértice de a de mayor raíz y la raíz del vértice de a -- de menor raíz. Y actualizando las raices de todos los elementos -- afectados por la raíz añadida. Por ejemplo, -- λ> d = M.fromList [(1,1),(2,1),(3,3),(4,4),(5,5),(6,5),(7,7)] -- λ> buscaActualiza (5,4) d -- (True,fromList [(1,1),(2,1),(3,3),(4,4),(5,4),(6,4),(7,7)]) -- λ> d' = snd it -- λ> buscaActualiza (6,1) d' -- (True,fromList [(1,1),(2,1),(3,3),(4,1),(5,1),(6,1),(7,7)]) buscaActualiza :: (Eq n, Ord n) => (n,n) -> M.Map n n -> (Bool,M.Map n n) buscaActualiza (x,y) d | x' == y' = (False, d) | y' < x' = (True, modificaR x (d M.! x) y' d) | otherwise = (True, modificaR y (d M.! y) x' d) where x' = raiz d x y' = raiz d y -- (modificaR x y y' d) actualiza d como sigue: -- + el valor de todas las claves z con valor y es y' -- + el valor de todas las claves z con (z > x) con valor x es y' modificaR :: (Eq n, Ord n) => n -> n -> n -> M.Map n n -> M.Map n n modificaR x y y' d = aux2 ds (aux1 cs d) where cs = M.keys d ds = filter (>x) cs aux1 [] tb = tb aux1 (a:as) tb | tb M.! a == y = aux1 as (M.update (\_ -> Just y') a tb) | otherwise = aux1 as tb aux2 [] tb = tb aux2 (b:bs) tb | tb M.! b == x = aux2 bs (M.update (\_ -> Just y') b tb) | otherwise = aux2 bs tb -- Traza del diccionario correspondiente al grafo g3 -- ================================================= -- Lista de aristas, ordenadas según su peso: -- [(3,5,6),(5,1,2),(5,4,5),(6,1,6),(7,2,3),(7,3,5),(8,3,4),(9,1,3),(9,5,7),(11,6,7),(15,1,5)] -- -- Inicial -- fromList [(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(7,7)] -- -- Después de añadir la arista (5,6) de peso 3 -- fromList [(1,1),(2,2),(3,3),(4,4),(5,5),(6,5),(7,7)] -- -- Después de añadir la arista (1,2) de peso 5 -- fromList [(1,1),(2,1),(3,3),(4,4),(5,5),(6,5),(7,7)] -- -- Después de añadir la arista (4,5) de peso 5 -- fromList [(1,1),(2,1),(3,3),(4,4),(5,4),(6,4),(7,7)] -- -- Después de añadir la arista (1,6) de peso 6 -- fromList [(1,1),(2,1),(3,3),(4,1),(5,1),(6,1),(7,7)] -- -- Después de añadir la arista (2,3) de peso 7 -- fromList [(1,1),(2,1),(3,1),(4,1),(5,1),(6,1),(7,7)] -- -- Las posibles aristas a añadir son: -- + la (3,5) con peso 7, que no es posible pues la raíz de 3 -- coincide con la raíz de 5, por lo que formaría un ciclo -- + la (3,4) con peso 8, que no es posible pues la raíz de 3 -- coincide con la raíz de 4, por lo que formaría un ciclo -- + la (1,3) con peso 9, que no es posible pues la raíz de 3 -- coincide con la raíz de 1, por lo que formaría un ciclo -- + la (5,7) con peso 9, que no forma ciclo -- -- Después de añadir la arista (5,7) con peso 9 -- fromList [(1,1),(2,1),(3,1),(4,1),(5,1),(6,1),(7,1)] -- -- No es posible añadir más aristas, pues formarían ciclos. -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ kruskal g1 `shouldBe` [(55,2,4),(34,1,3),(32,2,5),(12,1,2)] it "e2" $ kruskal g2 `shouldBe` [(32,2,5),(13,1,2),(12,2,4),(11,1,3)] it "e3" $ kruskal g3 `shouldBe` [(9,5,7),(7,2,3),(6,1,6),(5,4,5),(5,1,2),(3,5,6)] it "e4" $ kruskal g4 `shouldBe` [(9,5,7),(6,1,6),(5,4,5),(5,1,2),(3,5,6),(1,3,5)] -- La verificación es -- λ> verifica -- -- e1 -- e2 -- e3 -- e4 -- -- Finished in 0.0044 seconds -- 4 examples, 0 failures

Soluciones en Python

from src.TAD.Grafo import (Grafo, Orientacion, Peso, Vertice, aristas,
                           creaGrafo, nodos)
 
g1 = 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)])
g2 = creaGrafo (Orientacion.ND,
                (1,5),
                [((1,2),13),((1,3),11),((1,5),78),
                 ((2,4),12),((2,5),32),
                 ((3,4),14),((3,5),44),
                 ((4,5),93)])
g3 = creaGrafo (Orientacion.ND,
                (1,7),
                [((1,2),5),((1,3),9),((1,5),15),((1,6),6),
                 ((2,3),7),
                 ((3,4),8),((3,5),7),
                 ((4,5),5),
                 ((5,6),3),((5,7),9),
                 ((6,7),11)])
g4 = creaGrafo (Orientacion.ND,
                (1,7),
                [((1,2),5),((1,3),9),((1,5),15),((1,6),6),
                 ((2,3),7),
                 ((3,4),8),((3,5),1),
                 ((4,5),5),
                 ((5,6),3),((5,7),9),
                 ((6,7),11)])
 
# raiz(d, n) es la raíz de n en el diccionario. Por ejemplo,
#    raiz({1:1, 3:1, 4:3, 5:4, 2:6, 6:6}, 5)  == 1
#    raiz({1:1, 3:1, 4:3, 5:4, 2:6, 6:6}, 2)  == 6
def raiz(d: dict[Vertice, Vertice], x: Vertice) -> Vertice:
    v = d[x]
    if v == x:
        return v
    return raiz(d, v)
 
# modificaR(x, y, y_, d) actualiza d como sigue:
# + el valor de todas las claves z con valor y es y_
# + el valor de todas las claves z con (z > x) con valor x es y_
def modificaR(x: Vertice,
              y: Vertice,
              y_: Vertice,
              d: dict[Vertice, Vertice]) -> dict[Vertice, Vertice]:
    def aux1(vs: list[Vertice],
             tb: dict[Vertice, Vertice],
             y: Vertice) -> dict[Vertice, Vertice]:
        for a in vs:
            if tb[a] == y:
                tb[a] = y_
        return tb
 
    def aux2(vs: list[Vertice],
             tb: dict[Vertice, Vertice],
             y_: Vertice) -> dict[Vertice, Vertice]:
        for b in vs:
            if tb[b] == x:
                tb[b] = y_
        return tb
 
    cs = list(d.keys())
    ds = [c for c in cs if c > x]
 
    tb = aux1(cs, d, y)
    tb = aux2(ds, tb, y_)
 
    return tb
 
# buscaActualiza(a, d) es el par formado por False y el diccionario d,
# si los dos vértices de la arista a tienen la misma raíz en d y el par
# formado por True y la tabla obtenida añadiéndole a d la arista
# formada por el vértice de a de mayor raíz y la raíz del vértice de a
# de menor raíz. Y actualizando las raices de todos los elementos
# afectados por la raíz añadida. Por ejemplo,
#    >>> buscaActualiza((5,4), {1:1, 2:1, 3:3, 4:4, 5:5, 6:5, 7:7})
#    (True, {1: 1, 2: 1, 3: 3, 4: 4, 5: 4, 6: 4, 7: 7})
#    >>> buscaActualiza((6,1), {1:1, 2:1, 3:3, 4:4, 5:4, 6:4, 7:7})
#    (True, {1: 1, 2: 1, 3: 3, 4: 1, 5: 1, 6: 1, 7: 7})
#    >>> buscaActualiza((6,2), {1:1, 2:1, 3:3, 4:1, 5:4, 6:5, 7:7})
#    (False, {1: 1, 2: 1, 3: 3, 4: 1, 5: 4, 6: 5, 7: 7})
def buscaActualiza(a: tuple[Vertice, Vertice],
                   d: dict[Vertice, Vertice]) -> tuple[bool,
                                                       dict[Vertice, Vertice]]:
    x, y = a
    x_ = raiz(d, x)
    y_ = raiz(d, y)
 
    if x_ == y_:
        return False, d
    if y_ < x_:
        return True, modificaR(x, d[x], y_, d)
    return True, modificaR(y, d[y], x_, d)
 
def kruskal(g: Grafo) -> list[tuple[Peso, Vertice, Vertice]]:
    def aux(as_: list[tuple[Peso, Vertice, Vertice]],
            d: dict[Vertice, Vertice],
            ae: list[tuple[Peso, Vertice, Vertice]],
            n: int) -> list[tuple[Peso, Vertice, Vertice]]:
        if n == 0:
            return ae
        p, x, y = as_[0]
        actualizado, d = buscaActualiza((x, y), d)
        if actualizado:
            return aux(as_[1:], d, [(p, x, y)] + ae, n - 1)
        return aux(as_[1:], d, ae, n)
    return aux(list(sorted([(p, x, y) for ((x, y), p) in aristas(g)])),
               {x: x for x in nodos(g)},
               [],
               len(nodos(g)) - 1)
 
# Traza del diccionario correspondiente al grafo g3
# =================================================
 
# Lista de aristas, ordenadas según su peso:
# [(3,5,6),(5,1,2),(5,4,5),(6,1,6),(7,2,3),(7,3,5),(8,3,4),(9,1,3),(9,5,7),(11,6,7),(15,1,5)]
#
# Inicial
#   {1:1, 2:2, 3:3, 4:4, 5:5, 6:6, 7:7}
#
# Después de añadir la arista (5,6) de peso 3
#   {1:1, 2:2, 3:3, 4:4, 5:5, 6:5, 7:7}
#
# Después de añadir la arista (1,2) de peso 5
#   {1:1, 2:1, 3:3, 4:4, 5:5, 6:5, 7:7}
#
# Después de añadir la arista (4,5) de peso 5
#   {1:1, 2:1, 3:3, 4:4, 5:4, 6:4, 7:7}
#
# Después de añadir la arista (1,6) de peso 6
#   {1:1, 2:1, 3:3, 4:1, 5:1, 6:1, 7:7}
#
# Después de añadir la arista (2,3) de peso 7
#   {1:1, 2:1, 3:1, 4:1, 5:1, 6:1, 7:7}
#
# Las posibles aristas a añadir son:
# + la (3,5) con peso 7, que no es posible pues la raíz de 3
#   coincide con la raíz de 5, por lo que formaría un ciclo
# + la (3,4) con peso 8, que no es posible pues la raíz de 3
#   coincide con la raíz de 4, por lo que formaría un ciclo
# + la (1,3) con peso 9, que no es posible pues la raíz de 3
#   coincide con la raíz de 1, por lo que formaría un ciclo
# + la (5,7) con peso 9, que no forma ciclo
#
# Después de añadir la arista (5,7) con peso 9
#    {1:1, 2:1, 3:1, 4:1, 5:1, 6:1, 7:1}
#
# No es posible añadir más aristas, pues formarían ciclos.
 
# Verificación
# ============
 
def test_kruskal() -> None:
    assert kruskal(g1) == [(55,2,4),(34,1,3),(32,2,5),(12,1,2)]
    assert kruskal(g2) == [(32,2,5),(13,1,2),(12,2,4),(11,1,3)]
    assert kruskal(g3) == [(9,5,7),(7,2,3),(6,1,6),(5,4,5),(5,1,2),(3,5,6)]
    assert kruskal(g4) == [(9,5,7),(6,1,6),(5,4,5),(5,1,2),(3,5,6),(1,3,5)]
    print("Vefificado")
 
# La verificación es
#    >>> test_kruskal()
#    Vefificado

from src.TAD.Grafo import (Grafo, Orientacion, Peso, Vertice, aristas, creaGrafo, nodos) g1 = 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)]) g2 = creaGrafo (Orientacion.ND, (1,5), [((1,2),13),((1,3),11),((1,5),78), ((2,4),12),((2,5),32), ((3,4),14),((3,5),44), ((4,5),93)]) g3 = creaGrafo (Orientacion.ND, (1,7), [((1,2),5),((1,3),9),((1,5),15),((1,6),6), ((2,3),7), ((3,4),8),((3,5),7), ((4,5),5), ((5,6),3),((5,7),9), ((6,7),11)]) g4 = creaGrafo (Orientacion.ND, (1,7), [((1,2),5),((1,3),9),((1,5),15),((1,6),6), ((2,3),7), ((3,4),8),((3,5),1), ((4,5),5), ((5,6),3),((5,7),9), ((6,7),11)]) # raiz(d, n) es la raíz de n en el diccionario. Por ejemplo, # raiz({1:1, 3:1, 4:3, 5:4, 2:6, 6:6}, 5) == 1 # raiz({1:1, 3:1, 4:3, 5:4, 2:6, 6:6}, 2) == 6 def raiz(d: dict[Vertice, Vertice], x: Vertice) -> Vertice: v = d[x] if v == x: return v return raiz(d, v) # modificaR(x, y, y_, d) actualiza d como sigue: # + el valor de todas las claves z con valor y es y_ # + el valor de todas las claves z con (z > x) con valor x es y_ def modificaR(x: Vertice, y: Vertice, y_: Vertice, d: dict[Vertice, Vertice]) -> dict[Vertice, Vertice]: def aux1(vs: list[Vertice], tb: dict[Vertice, Vertice], y: Vertice) -> dict[Vertice, Vertice]: for a in vs: if tb[a] == y: tb[a] = y_ return tb def aux2(vs: list[Vertice], tb: dict[Vertice, Vertice], y_: Vertice) -> dict[Vertice, Vertice]: for b in vs: if tb[b] == x: tb[b] = y_ return tb cs = list(d.keys()) ds = [c for c in cs if c > x] tb = aux1(cs, d, y) tb = aux2(ds, tb, y_) return tb # buscaActualiza(a, d) es el par formado por False y el diccionario d, # si los dos vértices de la arista a tienen la misma raíz en d y el par # formado por True y la tabla obtenida añadiéndole a d la arista # formada por el vértice de a de mayor raíz y la raíz del vértice de a # de menor raíz. Y actualizando las raices de todos los elementos # afectados por la raíz añadida. Por ejemplo, # >>> buscaActualiza((5,4), {1:1, 2:1, 3:3, 4:4, 5:5, 6:5, 7:7}) # (True, {1: 1, 2: 1, 3: 3, 4: 4, 5: 4, 6: 4, 7: 7}) # >>> buscaActualiza((6,1), {1:1, 2:1, 3:3, 4:4, 5:4, 6:4, 7:7}) # (True, {1: 1, 2: 1, 3: 3, 4: 1, 5: 1, 6: 1, 7: 7}) # >>> buscaActualiza((6,2), {1:1, 2:1, 3:3, 4:1, 5:4, 6:5, 7:7}) # (False, {1: 1, 2: 1, 3: 3, 4: 1, 5: 4, 6: 5, 7: 7}) def buscaActualiza(a: tuple[Vertice, Vertice], d: dict[Vertice, Vertice]) -> tuple[bool, dict[Vertice, Vertice]]: x, y = a x_ = raiz(d, x) y_ = raiz(d, y) if x_ == y_: return False, d if y_ < x_: return True, modificaR(x, d[x], y_, d) return True, modificaR(y, d[y], x_, d) def kruskal(g: Grafo) -> list[tuple[Peso, Vertice, Vertice]]: def aux(as_: list[tuple[Peso, Vertice, Vertice]], d: dict[Vertice, Vertice], ae: list[tuple[Peso, Vertice, Vertice]], n: int) -> list[tuple[Peso, Vertice, Vertice]]: if n == 0: return ae p, x, y = as_[0] actualizado, d = buscaActualiza((x, y), d) if actualizado: return aux(as_[1:], d, [(p, x, y)] + ae, n - 1) return aux(as_[1:], d, ae, n) return aux(list(sorted([(p, x, y) for ((x, y), p) in aristas(g)])), {x: x for x in nodos(g)}, [], len(nodos(g)) - 1) # Traza del diccionario correspondiente al grafo g3 # ================================================= # Lista de aristas, ordenadas según su peso: # [(3,5,6),(5,1,2),(5,4,5),(6,1,6),(7,2,3),(7,3,5),(8,3,4),(9,1,3),(9,5,7),(11,6,7),(15,1,5)] # # Inicial # {1:1, 2:2, 3:3, 4:4, 5:5, 6:6, 7:7} # # Después de añadir la arista (5,6) de peso 3 # {1:1, 2:2, 3:3, 4:4, 5:5, 6:5, 7:7} # # Después de añadir la arista (1,2) de peso 5 # {1:1, 2:1, 3:3, 4:4, 5:5, 6:5, 7:7} # # Después de añadir la arista (4,5) de peso 5 # {1:1, 2:1, 3:3, 4:4, 5:4, 6:4, 7:7} # # Después de añadir la arista (1,6) de peso 6 # {1:1, 2:1, 3:3, 4:1, 5:1, 6:1, 7:7} # # Después de añadir la arista (2,3) de peso 7 # {1:1, 2:1, 3:1, 4:1, 5:1, 6:1, 7:7} # # Las posibles aristas a añadir son: # + la (3,5) con peso 7, que no es posible pues la raíz de 3 # coincide con la raíz de 5, por lo que formaría un ciclo # + la (3,4) con peso 8, que no es posible pues la raíz de 3 # coincide con la raíz de 4, por lo que formaría un ciclo # + la (1,3) con peso 9, que no es posible pues la raíz de 3 # coincide con la raíz de 1, por lo que formaría un ciclo # + la (5,7) con peso 9, que no forma ciclo # # Después de añadir la arista (5,7) con peso 9 # {1:1, 2:1, 3:1, 4:1, 5:1, 6:1, 7:1} # # No es posible añadir más aristas, pues formarían ciclos. # Verificación # ============ def test_kruskal() -> None: assert kruskal(g1) == [(55,2,4),(34,1,3),(32,2,5),(12,1,2)] assert kruskal(g2) == [(32,2,5),(13,1,2),(12,2,4),(11,1,3)] assert kruskal(g3) == [(9,5,7),(7,2,3),(6,1,6),(5,4,5),(5,1,2),(3,5,6)] assert kruskal(g4) == [(9,5,7),(6,1,6),(5,4,5),(5,1,2),(3,5,6),(1,3,5)] print("Vefificado") # La verificación es # >>> test_kruskal() # Vefificado

Leer más →

TAD de los grafos: Nodos conectados en un grafo

José A. Alonso, 21-junio-2023, Haskell y Python

Usando el tipo abstracto de datos de los grafos, definir la función,

   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

   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,

   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.

Soluciones en Haskell

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

Soluciones en Python

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

Leer más →

TAD de los grafos: Nodos aislados de un grafo

José A. Alonso, 20-junio-2023, Haskell y Python

Dado un grafo dirigido G, diremos que un nodo está aislado si o bien de dicho nodo no sale ninguna arista o bien no llega al nodo ninguna arista. Por ejemplo, en el siguiente grafo

   grafo1 :: Grafo Int Int
   grafo1 = creaGrafo' D (1,6) [(1,2),(1,3),(1,4),(3,6),
                                (5,4),(6,2),(6,5)]

podemos ver que del nodo 1 salen 3 aristas pero no llega ninguna, por lo que lo consideramos aislado. Así mismo, a los nodos 2 y 4 llegan aristas pero no sale ninguna, por tanto también estarán aislados.

Usando el tipo abstracto de datos de los grafos, definir la función,

   aislados :: (Ix v, Num p) => Grafo v p -> [v]

tal que aislados g es la lista de nodos aislados del grafo g. Por ejemplo,

   aislados grafo1 == [1,2,4]

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

module Grafo_Nodos_aislados_de_un_grafo where
 
import TAD.Grafo (Grafo, Orientacion (D), adyacentes, nodos, creaGrafo')
import Data.Ix (Ix)
import Grafo_Incidentes_de_un_vertice (incidentes)
import Test.Hspec (Spec, hspec, it, shouldBe)
 
grafo1 :: Grafo Int Int
grafo1 = creaGrafo' D (1,6) [(1,2),(1,3),(1,4),(3,6),
                             (5,4),(6,2),(6,5)]
 
aislados :: (Ix v, Num p) => Grafo v p -> [v]
aislados g =
  [n | n <- nodos g, null (adyacentes g n) || null (incidentes g n)]
 
-- Verificación
-- ============
 
verifica :: IO ()
verifica = hspec spec
 
spec :: Spec
spec = do
  it "e1" $
    aislados grafo1 `shouldBe` [1,2,4]
 
-- La verificación es
--    λ> verifica
--
--    e1
--
--    Finished in 0.0008 seconds
--    1 example, 0 failures

Soluciones en Python

from src.Grafo_Incidentes_de_un_vertice import incidentes
from src.TAD.Grafo import (Grafo, Orientacion, Vertice, adyacentes, creaGrafo_,
                           nodos)
 
grafo1: Grafo = creaGrafo_(Orientacion.D,
                           (1,6),
                           [(1,2),(1,3),(1,4),(3,6),(5,4),(6,2),(6,5)])
 
def aislados(g: Grafo) -> list[Vertice]:
    return [n for n in nodos(g)
            if not adyacentes(g, n) or not incidentes(g, n)]
 
# Verificación
# ============
 
def test_aislados() -> None:
    assert aislados(grafo1) == [1, 2, 4]
    print("Verificado")
 
# La verificación es
#    >>> test_aislados()
#    Verificado

Leer más →

TAD de los grafos: Coloreado correcto de un mapa

José A. Alonso, 19-junio-2023, Haskell y Python

Un mapa se puede representar mediante un grafo donde los vértices son las regiones del mapa y hay una arista entre dos vértices si las correspondientes regiones son vecinas. Por ejemplo, el mapa siguiente

   +----------+----------+
   |    1     |     2    |
   +----+-----+-----+----+
   |    |           |    |
   | 3  |     4     | 5  |
   |    |           |    |
   +----+-----+-----+----+
   |    6     |     7    |
   +----------+----------+

se pueden representar por

   mapa :: Grafo Int Int
   mapa = creaGrafo' ND (1,7)
                     [(1,2),(1,3),(1,4),(2,4),(2,5),(3,4),
                      (3,6),(4,5),(4,6),(4,7),(5,7),(6,7)]

Para colorear el mapa se dispone de 4 colores definidos por

   data Color = A | B | C | D
     deriving (Eq, Show)

Usando el tipo abstracto de datos de los grafos, definir la función,

   correcta :: [(Int,Color)] -> Grafo Int Int -> Bool

tal que correcta ncs m se verifica si ncs es una coloración del mapa m tal que todos las regiones vecinas tienen colores distintos. Por ejemplo,

   correcta [(1,A),(2,B),(3,B),(4,C),(5,A),(6,A),(7,B)] mapa == True
   correcta [(1,A),(2,B),(3,A),(4,C),(5,A),(6,A),(7,B)] mapa == False

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

module Grafo_Coloreado_correcto_de_un_mapa where
 
import TAD.Grafo (Grafo, Orientacion (ND), aristas, creaGrafo')
import Test.Hspec (Spec, hspec, it, shouldBe)
 
mapa :: Grafo Int Int
mapa = creaGrafo' ND (1,7)
                  [(1,2),(1,3),(1,4),(2,4),(2,5),(3,4),
                   (3,6),(4,5),(4,6),(4,7),(5,7),(6,7)]
 
data Color = A | B | C | E
  deriving (Eq, Show)
 
correcta :: [(Int,Color)] -> Grafo Int Int -> Bool
correcta ncs g =
  and [color x /= color y | ((x,y),_) <- aristas g]
  where color x = head [c | (y,c) <- ncs, y == x]
 
-- Verificación
-- ============
 
verifica :: IO ()
verifica = hspec spec
 
spec :: Spec
spec = do
  it "e1" $
    correcta [(1,A),(2,B),(3,B),(4,C),(5,A),(6,A),(7,B)] mapa `shouldBe` True
  it "e2" $
    correcta [(1,A),(2,B),(3,A),(4,C),(5,A),(6,A),(7,B)] mapa `shouldBe` False
 
-- La verificación es
--    λ> verifica
--
--    e1
--    e2
--
--    Finished in 0.0004 seconds
--    2 examples, 0 failures

Soluciones en Python

from enum import Enum
 
from src.TAD.Grafo import Grafo, Orientacion, aristas, creaGrafo_
 
mapa: Grafo = creaGrafo_(Orientacion.ND,
                         (1,7),
                         [(1,2),(1,3),(1,4),(2,4),(2,5),(3,4),
                          (3,6),(4,5),(4,6),(4,7),(5,7),(6,7)])
 
Color = Enum('Color', ['A', 'B', 'C', 'E'])
 
def correcta(ncs: list[tuple[int, Color]], g: Grafo) -> bool:
    def color(x: int) -> Color:
        return [c for (y, c) in ncs if y == x][0]
    return all(color(x) != color(y) for ((x, y), _) in aristas(g))
 
# Verificación
# ============
 
def test_correcta() -> None:
    assert correcta([(1,Color.A),
                     (2,Color.B),
                     (3,Color.B),
                     (4,Color.C),
                     (5,Color.A),
                     (6,Color.A),
                     (7,Color.B)],
                    mapa)
    assert not correcta([(1,Color.A),
                         (2,Color.B),
                         (3,Color.A),
                         (4,Color.C),
                         (5,Color.A),
                         (6,Color.A),
                         (7,Color.B)],
                        mapa)
    print("Verificado")
 
# La verificación es
#    >>> test_correcta()
#    Verificado

Leer más →

Etiqueta: Grafos

TAD de los grafos: Algoritmo de Prim

TAD de los grafos: Algoritmo de Kruskal

TAD de los grafos: Nodos conectados en un grafo

TAD de los grafos: Nodos aislados de un grafo

TAD de los grafos: Coloreado correcto de un mapa

Subscribe to Blog via Email

Entradas recientes

Etiquetas