Exercitium

TAD de los grafos: Coloreado correcto de un mapa

PorJosé A. Alonso 19-junio-202312-junio-2023

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    |
   +----------+----------+

+----------+----------+

| 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)]

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)

1 2	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

1	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

1 2	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

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

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

TAD de los grafos: Grafos conexos

PorJosé A. Alonso 16-junio-202310-junio-2023

Un grafo no dirigido G se dice conexo, si para cualquier par de vértices u y v en G, existe al menos una trayectoria (una sucesión de vértices adyacentes) de u a v.

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

   conexo :: (Ix a, Num p, Eq p) => Grafo a p -> Bool

1	conexo :: (Ix a, Num p, Eq p) => Grafo a p -> Bool

tal que conexo g se verifica si el grafo g es conexo. Por ejemplo,

   conexo (creaGrafo' ND (1,3) [(1,2),(3,2)])        ==  True
   conexo (creaGrafo' ND (1,4) [(1,2),(3,2),(4,1)])  ==  True
   conexo (creaGrafo' ND (1,4) [(1,2),(3,4)])        ==  False

conexo (creaGrafo' ND (1,3) [(1,2),(3,2)]) == True

conexo (creaGrafo' ND (1,4) [(1,2),(3,2),(4,1)]) == True

conexo (creaGrafo' ND (1,4) [(1,2),(3,4)]) == False

Soluciones

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

Soluciones en Haskell

module Grafo_Grafos_conexos where

import TAD.Grafo (Grafo, Orientacion (ND), nodos, creaGrafo')
import Data.Ix (Ix)
import Grafo_Recorrido_en_anchura (recorridoEnAnchura)
import Test.Hspec (Spec, hspec, it, shouldBe)

conexo :: (Ix a, Num p, Eq p) => Grafo a p -> Bool
conexo g = length (recorridoEnAnchura i g) == n
  where xs = nodos g
        i  = head xs
        n  = length xs

-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "e1" $
    conexo g1 `shouldBe` True
  it "e2" $
    conexo g2 `shouldBe` True
  it "e3" $
    conexo g3 `shouldBe` False
  where
    g1, g2, g3 :: Grafo Int Int
    g1 = creaGrafo' ND (1,3) [(1,2),(3,2)]
    g2 = creaGrafo' ND (1,4) [(1,2),(3,2),(4,1)]
    g3 = creaGrafo' ND (1,4) [(1,2),(3,4)]

-- La verificación es
--    λ> verifica
--
--    e1
--    e2
--    e3
--
--    Finished in 0.0003 seconds
--    3 examples, 0 failures

module Grafo_Grafos_conexos where

import TAD.Grafo (Grafo, Orientacion (ND), nodos, creaGrafo')

import Data.Ix (Ix)

import Grafo_Recorrido_en_anchura (recorridoEnAnchura)

import Test.Hspec (Spec, hspec, it, shouldBe)

conexo :: (Ix a, Num p, Eq p) => Grafo a p -> Bool

conexo g = length (recorridoEnAnchura i g) == n

where xs = nodos g

i = head xs

n = length xs

-- Verificación

-- ============

verifica :: IO ()

verifica = hspec spec

spec :: Spec

spec = do

it "e1" $

conexo g1 `shouldBe` True

it "e2" $

conexo g2 `shouldBe` True

it "e3" $

conexo g3 `shouldBe` False

where

g1, g2, g3 :: Grafo Int Int

g1 = creaGrafo' ND (1,3) [(1,2),(3,2)]

g2 = creaGrafo' ND (1,4) [(1,2),(3,2),(4,1)]

g3 = creaGrafo' ND (1,4) [(1,2),(3,4)]

-- La verificación es

-- λ> verifica

-- e1

-- e2

-- e3

-- Finished in 0.0003 seconds

-- 3 examples, 0 failures

Soluciones en Python

from src.Grafo_Recorrido_en_anchura import recorridoEnAnchura
from src.TAD.Grafo import Grafo, Orientacion, creaGrafo_, nodos


def conexo(g: Grafo) -> bool:
    xs = nodos(g)
    i = xs[0]
    n = len(xs)
    return len(recorridoEnAnchura(i, g)) == n

# Verificación
# ============

def test_conexo() -> None:
    g1 = creaGrafo_(Orientacion.ND, (1,3), [(1,2),(3,2)])
    g2 = creaGrafo_(Orientacion.ND, (1,4), [(1,2),(3,2),(4,1)])
    g3 = creaGrafo_(Orientacion.ND, (1,4), [(1,2),(3,4)])
    assert conexo(g1)
    assert conexo(g2)
    assert not conexo(g3)
    print("Verificado")

# La verificación es
#    >>> test_conexo()
#    Verificado

from src.Grafo_Recorrido_en_anchura import recorridoEnAnchura

from src.TAD.Grafo import Grafo, Orientacion, creaGrafo_, nodos

def conexo(g: Grafo) -> bool:

xs = nodos(g)

i = xs[0]

n = len(xs)

return len(recorridoEnAnchura(i, g)) == n

# Verificación

# ============

def test_conexo() -> None:

g1 = creaGrafo_(Orientacion.ND, (1,3), [(1,2),(3,2)])

g2 = creaGrafo_(Orientacion.ND, (1,4), [(1,2),(3,2),(4,1)])

g3 = creaGrafo_(Orientacion.ND, (1,4), [(1,2),(3,4)])

assert conexo(g1)

assert conexo(g2)

assert not conexo(g3)

print("Verificado")

# La verificación es

# >>> test_conexo()

# Verificado

TAD de los grafos: Recorrido en anchura

PorJosé A. Alonso 15-junio-20237-junio-2023

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

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

1	recorridoEnAnchura :: (Num p, Eq p, Ix v) => v -> Grafo v p -> [v]

tal que recorridoEnAnchura i g es el recorrido en anchura del grafo g desde el vértice i. Por ejemplo, en el grafo

   +---> 2 <---+
   |           |
   |           |
   1 --> 3 --> 6 --> 5
   |                 |
   |                 |
   +---> 4 <---------+

+---> 2 <---+

| |

1 --> 3 --> 6 --> 5

| |

+---> 4 <---------+

definido por

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

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

entonces

   recorridoEnAnchura 1 grafo1  ==  [1,2,3,4,6,5]

1	recorridoEnAnchura 1 grafo1 == [1,2,3,4,6,5]

Soluciones

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

Soluciones en Haskell

module Grafo_Recorrido_en_anchura where
import TAD.Grafo (Grafo, Orientacion (D, ND), adyacentes,
                  creaGrafo')
import Data.Ix (Ix)
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)]

recorridoEnAnchura :: (Num p, Eq p, Ix v) => v -> Grafo v p -> [v]
recorridoEnAnchura i g = reverse (ra [i] [])
  where
    ra [] vis    = vis
    ra (c:cs) vis
        | c `elem` vis = ra cs vis
        | otherwise    = ra (cs ++ adyacentes g c) (c:vis)

-- Traza del cálculo de (recorridoEnAnchura1 1 grafo1)
--    recorridoEnAnchura1 1 grafo1
--    = ra [1]     []
--    = ra [2,3,4] [1]
--    = ra [3,4]   [2,1]
--    = ra [4,6]   [3,2,1]
--    = ra [6]     [4,3,2,1]
--    = ra [2,5]   [6,4,3,2,1]
--    = ra [5]     [6,4,3,2,1]
--    = ra [4]     [5,6,4,3,2,1]
--    = ra []      [5,6,4,3,2,1]
--    = [1,2,3,4,6,5]

-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "e1" $
    recorridoEnAnchura 1 grafo1 `shouldBe` [1,2,3,4,6,5]
  it "e2" $
    recorridoEnAnchura 1 grafo2 `shouldBe` [1,2,3,4,6,5]
  where
    grafo2 :: Grafo Int Int
    grafo2 = creaGrafo' ND (1,6) [(1,2),(1,3),(1,4),(3,6),(5,4),(6,2),(6,5)]

-- La verificación es
--    λ> verifica
--
--    e1
--    e2
--
--    Finished in 0.0010 seconds
--    2 examples, 0 failures

module Grafo_Recorrido_en_anchura where

import TAD.Grafo (Grafo, Orientacion (D, ND), adyacentes,

creaGrafo')

import Data.Ix (Ix)

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)]

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

recorridoEnAnchura i g = reverse (ra [i] [])

where

ra [] vis = vis

ra (c:cs) vis

| c `elem` vis = ra cs vis

| otherwise = ra (cs ++ adyacentes g c) (c:vis)

-- Traza del cálculo de (recorridoEnAnchura1 1 grafo1)

-- recorridoEnAnchura1 1 grafo1

-- = ra [1] []

-- = ra [2,3,4] [1]

-- = ra [3,4] [2,1]

-- = ra [4,6] [3,2,1]

-- = ra [6] [4,3,2,1]

-- = ra [2,5] [6,4,3,2,1]

-- = ra [5] [6,4,3,2,1]

-- = ra [4] [5,6,4,3,2,1]

-- = ra [] [5,6,4,3,2,1]

-- = [1,2,3,4,6,5]

-- Verificación

-- ============

verifica :: IO ()

verifica = hspec spec

spec :: Spec

spec = do

it "e1" $

recorridoEnAnchura 1 grafo1 `shouldBe` [1,2,3,4,6,5]

it "e2" $

recorridoEnAnchura 1 grafo2 `shouldBe` [1,2,3,4,6,5]

where

grafo2 :: Grafo Int Int

grafo2 = creaGrafo' ND (1,6) [(1,2),(1,3),(1,4),(3,6),(5,4),(6,2),(6,5)]

-- La verificación es

-- λ> verifica

-- e1

-- e2

-- Finished in 0.0010 seconds

-- 2 examples, 0 failures

Soluciones en Python

from src.TAD.Grafo import Grafo, Orientacion, Vertice, adyacentes, creaGrafo_

grafo1: Grafo = creaGrafo_(Orientacion.D,
                           (1,6),
                           [(1,2),(1,3),(1,4),(3,6),(5,4),(6,2),(6,5)])

def recorridoEnAnchura(i: Vertice, g: Grafo) -> list[Vertice]:
    def ra(cs: list[Vertice], vis: list[Vertice]) -> list[Vertice]:
        if not cs:
            return vis
        d, *ds = cs
        if d in vis:
            return ra(ds, vis)
        return ra(ds + adyacentes(g, d), [d] + vis)
    return list(reversed(ra([i], [])))

# Traza del cálculo de recorridoEnAnchura(1, grafo1)
#    recorridoEnAnchura(1, grafo1
#    = ra([1],     [])
#    = ra([2,3,4], [1])
#    = ra([3,4],   [2,1])
#    = ra([4,6],   [3,2,1])
#    = ra([6],     [4,3,2,1])
#    = ra([2,5],   [6,4,3,2,1])
#    = ra([5],     [6,4,3,2,1])
#    = ra([4],     [5,6,4,3,2,1])
#    = ra([],      [5,6,4,3,2,1])
#    = [1,2,3,4,6,5]

# Verificación
# ============

def test_recorridoEnAnchura() -> None:
    grafo2 = creaGrafo_(Orientacion.ND,
                        (1,6),
                        [(1,2),(1,3),(1,4),(3,6),(5,4),(6,2),(6,5)])
    assert recorridoEnAnchura(1, grafo1) == [1,2,3,4,6,5]
    assert recorridoEnAnchura(1, grafo2) == [1,2,3,4,6,5]
    print("Verificado")

# La verificación es
#    >>> test_recorridoEnAnchura()
#    Verificado

from src.TAD.Grafo import Grafo, Orientacion, Vertice, adyacentes, creaGrafo_

grafo1: Grafo = creaGrafo_(Orientacion.D,

(1,6),

[(1,2),(1,3),(1,4),(3,6),(5,4),(6,2),(6,5)])

def recorridoEnAnchura(i: Vertice, g: Grafo) -> list[Vertice]:

def ra(cs: list[Vertice], vis: list[Vertice]) -> list[Vertice]:

if not cs:

return vis

d, *ds = cs

if d in vis:

return ra(ds, vis)

return ra(ds + adyacentes(g, d), [d] + vis)

return list(reversed(ra([i], [])))

# Traza del cálculo de recorridoEnAnchura(1, grafo1)

# recorridoEnAnchura(1, grafo1

# = ra([1], [])

# = ra([2,3,4], [1])

# = ra([3,4], [2,1])

# = ra([4,6], [3,2,1])

# = ra([6], [4,3,2,1])

# = ra([2,5], [6,4,3,2,1])

# = ra([5], [6,4,3,2,1])

# = ra([4], [5,6,4,3,2,1])

# = ra([], [5,6,4,3,2,1])

# = [1,2,3,4,6,5]

# Verificación

# ============

def test_recorridoEnAnchura() -> None:

grafo2 = creaGrafo_(Orientacion.ND,

(1,6),

[(1,2),(1,3),(1,4),(3,6),(5,4),(6,2),(6,5)])

assert recorridoEnAnchura(1, grafo1) == [1,2,3,4,6,5]

assert recorridoEnAnchura(1, grafo2) == [1,2,3,4,6,5]

print("Verificado")

# La verificación es

# >>> test_recorridoEnAnchura()

# Verificado

TAD de los grafos: Recorrido en profundidad

PorJosé A. Alonso 14-junio-20235-junio-2023

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

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

1	recorridoEnProfundidad :: (Num p, Eq p, Ix v) => v -> Grafo v p -> [v]

tal que recorridoEnProfundidad i g es el recorrido en profundidad del grafo g desde el vértice i. Por ejemplo, en el grafo

   +---> 2 <---+
   |           |
   |           |
   1 --> 3 --> 6 --> 5
   |                 |
   |                 |
   +---> 4 <---------+

+---> 2 <---+

| |

1 --> 3 --> 6 --> 5

| |

+---> 4 <---------+

definido por

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

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

entonces

   recorridoEnProfundidad 1 grafo1  ==  [1,2,3,6,5,4]

1	recorridoEnProfundidad 1 grafo1 == [1,2,3,6,5,4]

Soluciones

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

Soluciones en Haskell

module Grafo_Recorrido_en_profundidad where
import TAD.Grafo (Grafo, Orientacion (D, ND), adyacentes,
                  creaGrafo')
import Data.Ix (Ix)
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)]

-- 1ª solución
-- ===========

recorridoEnProfundidad1 :: (Num p, Eq p, Ix v) => v -> Grafo v p -> [v]
recorridoEnProfundidad1 i g = rp [i] []
  where
    rp [] vis    = vis
    rp (c:cs) vis
        | c `elem` vis = rp cs vis
        | otherwise    = rp (adyacentes g c ++ cs) (vis ++ [c])

-- Traza del cálculo de (recorridoEnProfundidad1 1 grafo1)
--    recorridoEnProfundidad1 1 grafo1
--    = rp [1]     []
--    = rp [2,3,4] [1]
--    = rp [3,4]   [1,2]
--    = rp [6,4]   [1,2,3]
--    = rp [2,5,4] [1,2,3,6]
--    = rp [5,4]   [1,2,3,6]
--    = rp [4,4]   [1,2,3,6,5]
--    = rp [4]     [1,2,3,6,5,4]
--    = rp []      [1,2,3,6,5,4]
--    = [1,2,3,6,5,4]

-- 2ª solución
-- ===========

recorridoEnProfundidad :: (Num p, Eq p, Ix v) => v -> Grafo v p -> [v]
recorridoEnProfundidad i g = reverse (rp [i] [])
  where
    rp [] vis     = vis
    rp (c:cs) vis
        | c `elem` vis = rp cs vis
        | otherwise    = rp (adyacentes g c ++ cs) (c:vis)

-- Traza del cálculo de (recorridoEnProfundidad 1 grafo1)
--    RecorridoEnProfundidad 1 grafo1
--    = reverse (rp [1]     [])
--    = reverse (rp [2,3,4] [1])
--    = reverse (rp [3,4]   [2,1])
--    = reverse (rp [6,4]   [3,2,1])
--    = reverse (rp [2,5,4] [6,3,2,1])
--    = reverse (rp [5,4]   [6,3,2,1])
--    = reverse (rp [4,4]   [5,6,3,2,1])
--    = reverse (rp [4]     [4,5,6,3,2,1])
--    = reverse (rp []      [4,5,6,3,2,1])
--    = reverse [4,5,6,3,2,1]
--    = [1,2,3,6,5,4]

-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "e1" $
    recorridoEnProfundidad1 1 grafo1 `shouldBe` [1,2,3,6,5,4]
  it "e2" $
    recorridoEnProfundidad 1 grafo1 `shouldBe` [1,2,3,6,5,4]
  it "e3" $
    recorridoEnProfundidad1 1 grafo2 `shouldBe` [1,2,6,3,5,4]
  it "e4" $
    recorridoEnProfundidad 1 grafo2 `shouldBe` [1,2,6,3,5,4]
  where
    grafo2 :: Grafo Int Int
    grafo2 = creaGrafo' ND (1,6) [(1,2),(1,3),(1,4),(3,6),(5,4),(6,2),(6,5)]

-- La verificación es
--    λ> verifica
--
--    e1
--    e2
--    e3
--    e4
--
--    Finished in 0.0022 seconds
--    4 examples, 0 failures

module Grafo_Recorrido_en_profundidad where

import TAD.Grafo (Grafo, Orientacion (D, ND), adyacentes,

creaGrafo')

import Data.Ix (Ix)

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)]

-- 1ª solución

-- ===========

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

recorridoEnProfundidad1 i g = rp [i] []

where

rp [] vis = vis

rp (c:cs) vis

| c `elem` vis = rp cs vis

| otherwise = rp (adyacentes g c ++ cs) (vis ++ [c])

-- Traza del cálculo de (recorridoEnProfundidad1 1 grafo1)

-- recorridoEnProfundidad1 1 grafo1

-- = rp [1] []

-- = rp [2,3,4] [1]

-- = rp [3,4] [1,2]

-- = rp [6,4] [1,2,3]

-- = rp [2,5,4] [1,2,3,6]

-- = rp [5,4] [1,2,3,6]

-- = rp [4,4] [1,2,3,6,5]

-- = rp [4] [1,2,3,6,5,4]

-- = rp [] [1,2,3,6,5,4]

-- = [1,2,3,6,5,4]

-- 2ª solución

-- ===========

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

recorridoEnProfundidad i g = reverse (rp [i] [])

where

rp [] vis = vis

rp (c:cs) vis

| c `elem` vis = rp cs vis

| otherwise = rp (adyacentes g c ++ cs) (c:vis)

-- Traza del cálculo de (recorridoEnProfundidad 1 grafo1)

-- RecorridoEnProfundidad 1 grafo1

-- = reverse (rp [1] [])

-- = reverse (rp [2,3,4] [1])

-- = reverse (rp [3,4] [2,1])

-- = reverse (rp [6,4] [3,2,1])

-- = reverse (rp [2,5,4] [6,3,2,1])

-- = reverse (rp [5,4] [6,3,2,1])

-- = reverse (rp [4,4] [5,6,3,2,1])

-- = reverse (rp [4] [4,5,6,3,2,1])

-- = reverse (rp [] [4,5,6,3,2,1])

-- = reverse [4,5,6,3,2,1]

-- = [1,2,3,6,5,4]

-- Verificación

-- ============

verifica :: IO ()

verifica = hspec spec

spec :: Spec

spec = do

it "e1" $

recorridoEnProfundidad1 1 grafo1 `shouldBe` [1,2,3,6,5,4]

it "e2" $

recorridoEnProfundidad 1 grafo1 `shouldBe` [1,2,3,6,5,4]

it "e3" $

recorridoEnProfundidad1 1 grafo2 `shouldBe` [1,2,6,3,5,4]

it "e4" $

recorridoEnProfundidad 1 grafo2 `shouldBe` [1,2,6,3,5,4]

where

grafo2 :: Grafo Int Int

grafo2 = creaGrafo' ND (1,6) [(1,2),(1,3),(1,4),(3,6),(5,4),(6,2),(6,5)]

-- La verificación es

-- λ> verifica

-- e1

-- e2

-- e3

-- e4

-- Finished in 0.0022 seconds

-- 4 examples, 0 failures

Soluciones en Python

from src.TAD.Grafo import Grafo, Orientacion, Vertice, adyacentes, creaGrafo_

grafo1: Grafo = creaGrafo_(Orientacion.D,
                           (1,6),
                           [(1,2),(1,3),(1,4),(3,6),(5,4),(6,2),(6,5)])

# 1ª solución
# ===========

def recorridoEnProfundidad1(i: Vertice, g: Grafo) -> list[Vertice]:
    def rp(cs: list[Vertice], vis: list[Vertice]) -> list[Vertice]:
        if not cs:
            return vis
        d, *ds = cs
        if d in vis:
            return rp(ds, vis)
        return rp(adyacentes(g, d) + ds, vis + [d])
    return rp([i], [])

# Traza del cálculo de recorridoEnProfundidad1(1, grafo1)
#    recorridoEnProfundidad1(1, grafo1)
#    = rp([1],     [])
#    = rp([2,3,4], [1])
#    = rp([3,4],   [1,2])
#    = rp([6,4],   [1,2,3])
#    = rp([2,5,4], [1,2,3,6])
#    = rp([5,4],   [1,2,3,6])
#    = rp([4,4],   [1,2,3,6,5])
#    = rp([4],     [1,2,3,6,5,4])
#    = rp([],      [1,2,3,6,5,4])
#    = [1,2,3,6,5,4]

# 2ª solución
# ===========

def recorridoEnProfundidad(i: Vertice, g: Grafo) -> list[Vertice]:
    def rp(cs: list[Vertice], vis: list[Vertice]) -> list[Vertice]:
        if not cs:
            return vis
        d, *ds = cs
        if d in vis:
            return rp(ds, vis)
        return rp(adyacentes(g, d) + ds, [d] + vis)
    return list(reversed(rp([i], [])))

# Traza del cálculo de (recorridoEnProfundidad(1, grafo1)
#    recorridoEnProfundidad(1, grafo1)
#    = reverse(rp([1],     []))
#    = reverse(rp([2,3,4], [1]))
#    = reverse(rp([3,4],   [2,1]))
#    = reverse(rp([6,4],   [3,2,1]))
#    = reverse(rp([2,5,4], [6,3,2,1]))
#    = reverse(rp([5,4],   [6,3,2,1]))
#    = reverse(rp([4,4],   [5,6,3,2,1]))
#    = reverse(rp([4],     [4,5,6,3,2,1]))
#    = reverse(rp([],      [4,5,6,3,2,1]))
#    = reverse([4,5,6,3,2,1])
#    = [1,2,3,6,5,4]

# Verificación
# ============

def test_recorridoEnProfundidad() -> None:
    grafo2 = creaGrafo_(Orientacion.ND,
                        (1,6),
                        [(1,2),(1,3),(1,4),(3,6),(5,4),(6,2),(6,5)])
    assert recorridoEnProfundidad1(1, grafo1) == [1,2,3,6,5,4]
    assert recorridoEnProfundidad1(1, grafo2) == [1,2,6,3,5,4]
    assert recorridoEnProfundidad(1, grafo1) == [1,2,3,6,5,4]
    assert recorridoEnProfundidad(1, grafo2) == [1,2,6,3,5,4]
    print("Verificado")

# La verificación es
#    >>> test_recorridoEnProfundidad()
#    Verificado

from src.TAD.Grafo import Grafo, Orientacion, Vertice, adyacentes, creaGrafo_

grafo1: Grafo = creaGrafo_(Orientacion.D,

(1,6),

[(1,2),(1,3),(1,4),(3,6),(5,4),(6,2),(6,5)])

# 1ª solución

# ===========

def recorridoEnProfundidad1(i: Vertice, g: Grafo) -> list[Vertice]:

def rp(cs: list[Vertice], vis: list[Vertice]) -> list[Vertice]:

if not cs:

return vis

d, *ds = cs

if d in vis:

return rp(ds, vis)

return rp(adyacentes(g, d) + ds, vis + [d])

return rp([i], [])

# Traza del cálculo de recorridoEnProfundidad1(1, grafo1)

# recorridoEnProfundidad1(1, grafo1)

# = rp([1], [])

# = rp([2,3,4], [1])

# = rp([3,4], [1,2])

# = rp([6,4], [1,2,3])

# = rp([2,5,4], [1,2,3,6])

# = rp([5,4], [1,2,3,6])

# = rp([4,4], [1,2,3,6,5])

# = rp([4], [1,2,3,6,5,4])

# = rp([], [1,2,3,6,5,4])

# = [1,2,3,6,5,4]

# 2ª solución

# ===========

def recorridoEnProfundidad(i: Vertice, g: Grafo) -> list[Vertice]:

def rp(cs: list[Vertice], vis: list[Vertice]) -> list[Vertice]:

if not cs:

return vis

d, *ds = cs

if d in vis:

return rp(ds, vis)

return rp(adyacentes(g, d) + ds, [d] + vis)

return list(reversed(rp([i], [])))

# Traza del cálculo de (recorridoEnProfundidad(1, grafo1)

# recorridoEnProfundidad(1, grafo1)

# = reverse(rp([1], []))

# = reverse(rp([2,3,4], [1]))

# = reverse(rp([3,4], [2,1]))

# = reverse(rp([6,4], [3,2,1]))

# = reverse(rp([2,5,4], [6,3,2,1]))

# = reverse(rp([5,4], [6,3,2,1]))

# = reverse(rp([4,4], [5,6,3,2,1]))

# = reverse(rp([4], [4,5,6,3,2,1]))

# = reverse(rp([], [4,5,6,3,2,1]))

# = reverse([4,5,6,3,2,1])

# = [1,2,3,6,5,4]

# Verificación

# ============

def test_recorridoEnProfundidad() -> None:

grafo2 = creaGrafo_(Orientacion.ND,

(1,6),

[(1,2),(1,3),(1,4),(3,6),(5,4),(6,2),(6,5)])

assert recorridoEnProfundidad1(1, grafo1) == [1,2,3,6,5,4]

assert recorridoEnProfundidad1(1, grafo2) == [1,2,6,3,5,4]

assert recorridoEnProfundidad(1, grafo1) == [1,2,3,6,5,4]

assert recorridoEnProfundidad(1, grafo2) == [1,2,6,3,5,4]

print("Verificado")

# La verificación es

# >>> test_recorridoEnProfundidad()

# Verificado

TAD de los grafos: Anchura de un grafo

PorJosé A. Alonso 13-junio-20234-junio-2023

En un grafo, la anchura de un nodo es el máximo de los absolutos de la diferencia entre el valor del nodo y los de sus adyacentes; y la anchura del grafo es la máxima anchura de sus nodos. Por ejemplo, en el grafo

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

grafo1 :: Grafo Int Int

grafo1 = creaGrafo' D (1,5) [(1,2),(1,3),(1,5),

(2,4),(2,5),

(3,4),(3,5),

(4,5)]

su anchura es 4 y el nodo de máxima anchura es el 5.

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

   anchura :: Grafo Int Int -> Int

1	anchura :: Grafo Int Int -> Int

tal que (anchuraG g) es la anchura del grafo g. Por ejemplo,

   anchura grafo1  ==  4

1	anchura grafo1 == 4

Comprobar experimentalmente que la anchura del grafo ciclo de orden n es n-1.

Soluciones

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

Soluciones en Haskell

module Grafo_Anchura_de_un_grafo where

import TAD.Grafo (Grafo, Orientacion (D, ND), adyacentes, aristas,
                  creaGrafo', nodos)
import Grafo_Grafos_ciclos (grafoCiclo)
import Test.Hspec (Spec, hspec, it, shouldBe)

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

-- 1ª solución
-- ===========

anchura :: Grafo Int Int -> Int
anchura g = maximum [anchuraN g x | x <- nodos g]

-- (anchuraN g x) es la anchura del nodo x en el grafo g. Por ejemplo,
--    anchuraN g 1  ==  4
--    anchuraN g 2  ==  3
--    anchuraN g 4  ==  2
--    anchuraN g 5  ==  4
anchuraN :: Grafo Int Int -> Int -> Int
anchuraN g x = maximum (0 : [abs (x-v) | v <- adyacentes g x])

-- 2ª solución
-- ===========

anchura2 :: Grafo Int Int -> Int
anchura2 g = maximum [abs (x-y) | ((x,y),_) <- aristas g]

-- La conjetura
conjetura :: Int -> Bool
conjetura n = anchura (grafoCiclo n) == n-1

-- La comprobación es
--    λ> and [conjetura n | n <- [2..10]]
--    True

-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "e1" $
    anchura grafo1 `shouldBe` 4
  it "e2" $
    anchura g2 `shouldBe` 2
  where
    g2 :: Grafo Int Int
    g2 = creaGrafo' ND (1,3) [(1,2),(1,3),(2,3),(3,3)]

-- La verificación es
--    λ> verifica
--
--    e1
--    e2
--
--    Finished in 0.0004 seconds
--    2 examples, 0 failures

module Grafo_Anchura_de_un_grafo where

import TAD.Grafo (Grafo, Orientacion (D, ND), adyacentes, aristas,

creaGrafo', nodos)

import Grafo_Grafos_ciclos (grafoCiclo)

import Test.Hspec (Spec, hspec, it, shouldBe)

grafo1 :: Grafo Int Int

grafo1 = creaGrafo' D (1,5) [(1,2),(1,3),(1,5),

(2,4),(2,5),

(3,4),(3,5),

(4,5)]

-- 1ª solución

-- ===========

anchura :: Grafo Int Int -> Int

anchura g = maximum [anchuraN g x | x <- nodos g]

-- (anchuraN g x) es la anchura del nodo x en el grafo g. Por ejemplo,

-- anchuraN g 1 == 4

-- anchuraN g 2 == 3

-- anchuraN g 4 == 2

-- anchuraN g 5 == 4

anchuraN :: Grafo Int Int -> Int -> Int

anchuraN g x = maximum (0 : [abs (x-v) | v <- adyacentes g x])

-- 2ª solución

-- ===========

anchura2 :: Grafo Int Int -> Int

anchura2 g = maximum [abs (x-y) | ((x,y),_) <- aristas g]

-- La conjetura

conjetura :: Int -> Bool

conjetura n = anchura (grafoCiclo n) == n-1

-- La comprobación es

-- λ> and [conjetura n | n <- [2..10]]

-- True

-- Verificación

-- ============

verifica :: IO ()

verifica = hspec spec

spec :: Spec

spec = do

it "e1" $

anchura grafo1 `shouldBe` 4

it "e2" $

anchura g2 `shouldBe` 2

where

g2 :: Grafo Int Int

g2 = creaGrafo' ND (1,3) [(1,2),(1,3),(2,3),(3,3)]

-- La verificación es

-- λ> verifica

-- e1

-- e2

-- Finished in 0.0004 seconds

-- 2 examples, 0 failures

Soluciones en Python

from src.Grafo_Grafos_ciclos import grafoCiclo
from src.TAD.Grafo import (Grafo, Orientacion, Vertice, adyacentes, aristas,
                           creaGrafo_, nodos)

grafo1: Grafo = creaGrafo_(Orientacion.D, (1,5), [(1,2),(1,3),(1,5),
                                                  (2,4),(2,5),
                                                  (3,4),(3,5),
                                                  (4,5)])

# 1ª solución
# ===========

def anchura(g: Grafo) -> int:
    return max(anchuraN(g, x) for x in nodos(g))

# (anchuraN g x) es la anchura del nodo x en el grafo g. Por ejemplo,
#    anchuraN g 1  ==  4
#    anchuraN g 2  ==  3
#    anchuraN g 4  ==  2
#    anchuraN g 5  ==  4
def anchuraN(g: Grafo, x: Vertice) -> int:
    return max([0] + [abs (x - v) for v in adyacentes(g, x)])

# 2ª solución
# ===========

def anchura2(g: Grafo) -> int:
    return max(abs (x-y) for ((x,y),_) in aristas(g))

# La conjetura
def conjetura(n: int) -> bool:
    return anchura(grafoCiclo(n)) == n - 1

# La comprobación es
#    >>> all(conjetura(n) for n in range(2, 11))
#    True

# Verificación
# ============

def test_anchura() -> None:
    g2 = creaGrafo_(Orientacion.ND, (1,3), [(1,2),(1,3),(2,3),(3,3)])
    assert anchura(grafo1) == 4
    assert anchura(g2) == 2
    print("Verificado")

# La verificación es
#    >>> test_anchura()
#    Verificado

from src.Grafo_Grafos_ciclos import grafoCiclo

from src.TAD.Grafo import (Grafo, Orientacion, Vertice, adyacentes, aristas,

creaGrafo_, nodos)

grafo1: Grafo = creaGrafo_(Orientacion.D, (1,5), [(1,2),(1,3),(1,5),

(2,4),(2,5),

(3,4),(3,5),

(4,5)])

# 1ª solución

# ===========

def anchura(g: Grafo) -> int:

return max(anchuraN(g, x) for x in nodos(g))

# (anchuraN g x) es la anchura del nodo x en el grafo g. Por ejemplo,

# anchuraN g 1 == 4

# anchuraN g 2 == 3

# anchuraN g 4 == 2

# anchuraN g 5 == 4

def anchuraN(g: Grafo, x: Vertice) -> int:

return max([0] + [abs (x - v) for v in adyacentes(g, x)])

# 2ª solución

# ===========

def anchura2(g: Grafo) -> int:

return max(abs (x-y) for ((x,y),_) in aristas(g))

# La conjetura

def conjetura(n: int) -> bool:

return anchura(grafoCiclo(n)) == n - 1

# La comprobación es

# >>> all(conjetura(n) for n in range(2, 11))

# True

# Verificación

# ============

def test_anchura() -> None:

g2 = creaGrafo_(Orientacion.ND, (1,3), [(1,2),(1,3),(2,3),(3,3)])

assert anchura(grafo1) == 4

assert anchura(g2) == 2

print("Verificado")

# La verificación es

# >>> test_anchura()

# Verificado

TAD de los grafos: Coloreado correcto de un mapa

TAD de los grafos: Grafos conexos

TAD de los grafos: Recorrido en anchura

TAD de los grafos: Recorrido en profundidad

TAD de los grafos: Anchura de un grafo

Entradas recientes

Buscar

Correo electrónico