Haskell y Python

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: Recorridos en un grafo completo

PorJosé A. Alonso 12-junio-20231-junio-2023

Definir la función

   recorridos :: [a] -> [[a]]

1	recorridos :: [a] -> [[a]]

tal que recorridos xs es la lista de todos los posibles por el grafo cuyo conjunto de vértices es xs y cada vértice se encuentra conectado con todos los otros y los recorridos pasan por todos los vértices una vez y terminan en el vértice inicial. Por ejemplo,

   λ> recorridos [2,5,3]
   [[2,5,3,2],[5,2,3,5],[3,5,2,3],[5,3,2,5],[3,2,5,3],[2,3,5,2]]

1 2	λ> recorridos [2,5,3] [[2,5,3,2],[5,2,3,5],[3,5,2,3],[5,3,2,5],[3,2,5,3],[2,3,5,2]]

Soluciones

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

Soluciones en Haskell

module Grafo_Recorridos_en_un_grafo_completo where

import Data.List (permutations)
import Test.Hspec (Spec, hspec, it, shouldBe)

recorridos :: [a] -> [[a]]
recorridos xs = [(y:ys) ++ [y] | y:ys <- permutations xs]

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

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "e1" $
    recorridos [2 :: Int,5,3] `shouldBe`
    [[2,5,3,2],[5,2,3,5],[3,5,2,3],[5,3,2,5],[3,2,5,3],[2,3,5,2]]

-- La verificación es
--    λ> verifica
--
--    e1
--
--    Finished in 0.0007 seconds
--    1 example, 0 failures

module Grafo_Recorridos_en_un_grafo_completo where

import Data.List (permutations)

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

recorridos :: [a] -> [[a]]

recorridos xs = [(y:ys) ++ [y] | y:ys <- permutations xs]

-- Verificación

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

verifica :: IO ()

verifica = hspec spec

spec :: Spec

spec = do

it "e1" $

recorridos [2 :: Int,5,3] `shouldBe`

[[2,5,3,2],[5,2,3,5],[3,5,2,3],[5,3,2,5],[3,2,5,3],[2,3,5,2]]

-- La verificación es

-- λ> verifica

-- e1

-- Finished in 0.0007 seconds

-- 1 example, 0 failures

Soluciones en Python

from itertools import permutations
from typing import TypeVar

A = TypeVar('A')

def recorridos(xs: list[A]) -> list[list[A]]:
    return [(list(y) + [y[0]]) for y in permutations(xs)]

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

def test_recorridos() -> None:
    assert recorridos([2, 5, 3]) \
        == [[2, 5, 3, 2], [2, 3, 5, 2], [5, 2, 3, 5], [5, 3, 2, 5],
            [3, 2, 5, 3], [3, 5, 2, 3]]
    print("Verificado")

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

from itertools import permutations

from typing import TypeVar

A = TypeVar('A')

def recorridos(xs: list[A]) -> list[list[A]]:

return [(list(y) + [y[0]]) for y in permutations(xs)]

# Verificación

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

def test_recorridos() -> None:

assert recorridos([2, 5, 3]) \

== [[2, 5, 3, 2], [2, 3, 5, 2], [5, 2, 3, 5], [5, 3, 2, 5],

[3, 2, 5, 3], [3, 5, 2, 3]]

print("Verificado")

# La verificación es

# >>> test_recorridos()

# Verificado

TAD de los grafos: Grafos k-regulares

PorJosé A. Alonso 9-junio-20233-junio-2023

Un grafo k-regular es un grafo con todos sus vértices son de grado k.

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

   regularidad :: (Ix v,Num p) => Grafo v p -> Maybe Int

1	regularidad :: (Ix v,Num p) => Grafo v p -> Maybe Int

tal que (regularidad g) es la regularidad de g. Por ejemplo,

   regularidad (creaGrafo' ND (1,2) [(1,2),(2,3)]) == Just 1
   regularidad (creaGrafo' D (1,2) [(1,2),(2,3)])  == Nothing
   regularidad (completo 4)                        == Just 3
   regularidad (completo 5)                        == Just 4
   regularidad (grafoCiclo 4)                      == Just 2
   regularidad (grafoCiclo 5)                      == Just 2

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

regularidad (creaGrafo' D (1,2) [(1,2),(2,3)]) == Nothing

regularidad (completo 4) == Just 3

regularidad (completo 5) == Just 4

regularidad (grafoCiclo 4) == Just 2

regularidad (grafoCiclo 5) == Just 2

Comprobar que el grafo completo de orden n es (n-1)-regular (para n de 1 a 20) y el grafo ciclo de orden n es 2-regular (para n de 3 a 20).

Soluciones

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

Soluciones en Haskell

module Grafo_Grafos_k_regulares where

import TAD.Grafo (Grafo, Orientacion (D, ND), nodos, creaGrafo')
import Data.Ix (Ix)
import Grafo_Grado_de_un_vertice (grado)
import Grafo_Grafos_regulares (regular)
import Grafo_Grafos_completos (completo)
import Grafo_Grafos_ciclos (grafoCiclo)
import Test.Hspec (Spec, hspec, it, shouldBe)

regularidad :: (Ix v,Num p) => Grafo v p -> Maybe Int
regularidad g
  | regular g = Just (grado g (head (nodos g)))
  | otherwise = Nothing

-- La propiedad de k-regularidad de los grafos completos es
prop_completoRegular :: Int -> Bool
prop_completoRegular n =
  regularidad (completo n) == Just (n-1)

-- La comprobación es
--    λ> and [prop_completoRegular n | n <- [1..20]]
--    True

-- La propiedad de k-regularidad de los grafos ciclos es
prop_cicloRegular :: Int -> Bool
prop_cicloRegular n =
  regularidad (grafoCiclo n) == Just 2

-- La comprobación es
--    λ> and [prop_cicloRegular n | n <- [3..20]]
--    True

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

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "e1" $
    regularidad g1             `shouldBe` Just 1
  it "e2" $
    regularidad g2             `shouldBe` Nothing
  it "e3" $
    regularidad (completo 4)   `shouldBe` Just 3
  it "e4" $
    regularidad (completo 5)   `shouldBe` Just 4
  it "e5" $
    regularidad (grafoCiclo 4) `shouldBe` Just 2
  it "e6" $
    regularidad (grafoCiclo 5) `shouldBe` Just 2
  where
    g1, g2 :: Grafo Int Int
    g1 = creaGrafo' ND (1,2) [(1,2),(2,3)]
    g2 = creaGrafo' D (1,2) [(1,2),(2,3)]

-- La verificación es
--    λ> verifica
--
--    e1
--    e2
--    e3
--    e4
--    e5
--    e6
--
--    Finished in 0.0027 seconds
--    6 examples, 0 failures

module Grafo_Grafos_k_regulares where

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

import Data.Ix (Ix)

import Grafo_Grado_de_un_vertice (grado)

import Grafo_Grafos_regulares (regular)

import Grafo_Grafos_completos (completo)

import Grafo_Grafos_ciclos (grafoCiclo)

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

regularidad :: (Ix v,Num p) => Grafo v p -> Maybe Int

regularidad g

| regular g = Just (grado g (head (nodos g)))

| otherwise = Nothing

-- La propiedad de k-regularidad de los grafos completos es

prop_completoRegular :: Int -> Bool

prop_completoRegular n =

regularidad (completo n) == Just (n-1)

-- La comprobación es

-- λ> and [prop_completoRegular n | n <- [1..20]]

-- True

-- La propiedad de k-regularidad de los grafos ciclos es

prop_cicloRegular :: Int -> Bool

prop_cicloRegular n =

regularidad (grafoCiclo n) == Just 2

-- La comprobación es

-- λ> and [prop_cicloRegular n | n <- [3..20]]

-- True

-- Verificación

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

verifica :: IO ()

verifica = hspec spec

spec :: Spec

spec = do

it "e1" $

regularidad g1 `shouldBe` Just 1

it "e2" $

regularidad g2 `shouldBe` Nothing

it "e3" $

regularidad (completo 4) `shouldBe` Just 3

it "e4" $

regularidad (completo 5) `shouldBe` Just 4

it "e5" $

regularidad (grafoCiclo 4) `shouldBe` Just 2

it "e6" $

regularidad (grafoCiclo 5) `shouldBe` Just 2

where

g1, g2 :: Grafo Int Int

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

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

-- La verificación es

-- λ> verifica

-- e1

-- e2

-- e3

-- e4

-- e5

-- e6

-- Finished in 0.0027 seconds

-- 6 examples, 0 failures

Soluciones en Python

from typing import Optional

from src.Grafo_Grado_de_un_vertice import grado
from src.Grafo_Grafos_ciclos import grafoCiclo
from src.Grafo_Grafos_completos import completo
from src.Grafo_Grafos_regulares import regular
from src.TAD.Grafo import Grafo, Orientacion, creaGrafo_, nodos


def regularidad(g: Grafo) -> Optional[int]:
    if regular(g):
        return grado(g, nodos(g)[0])
    return None

# La propiedad de k-regularidad de los grafos completos es
def prop_completoRegular(n: int) -> bool:
    return regularidad(completo(n)) == n - 1

# La comprobación es
#    >>> all(prop_completoRegular(n) for n in range(1, 21))
#    True

# La propiedad de k-regularidad de los grafos ciclos es
def prop_cicloRegular(n: int) -> bool:
    return regularidad(grafoCiclo(n)) == 2

# La comprobación es
#    >>> all(prop_cicloRegular(n) for n in range(3, 21))
#    True

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

def test_k_regularidad() -> None:
    g1 = creaGrafo_(Orientacion.ND, (1,2), [(1,2),(2,3)])
    g2 = creaGrafo_(Orientacion.D, (1,2), [(1,2),(2,3)])
    assert regularidad(g1) == 1
    assert regularidad(g2) is None
    assert regularidad(completo(4)) == 3
    assert regularidad(completo(5)) == 4
    assert regularidad(grafoCiclo(4)) == 2
    assert regularidad(grafoCiclo(5)) == 2
    print("Verificado")

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

from typing import Optional

from src.Grafo_Grado_de_un_vertice import grado

from src.Grafo_Grafos_ciclos import grafoCiclo

from src.Grafo_Grafos_completos import completo

from src.Grafo_Grafos_regulares import regular

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

def regularidad(g: Grafo) -> Optional[int]:

if regular(g):

return grado(g, nodos(g)[0])

return None

# La propiedad de k-regularidad de los grafos completos es

def prop_completoRegular(n: int) -> bool:

return regularidad(completo(n)) == n - 1

# La comprobación es

# >>> all(prop_completoRegular(n) for n in range(1, 21))

# True

# La propiedad de k-regularidad de los grafos ciclos es

def prop_cicloRegular(n: int) -> bool:

return regularidad(grafoCiclo(n)) == 2

# La comprobación es

# >>> all(prop_cicloRegular(n) for n in range(3, 21))

# True

# Verificación

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

def test_k_regularidad() -> None:

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

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

assert regularidad(g1) == 1

assert regularidad(g2) is None

assert regularidad(completo(4)) == 3

assert regularidad(completo(5)) == 4

assert regularidad(grafoCiclo(4)) == 2

assert regularidad(grafoCiclo(5)) == 2

print("Verificado")

# La verificación es

# >>> test_k_regularidad()

# Verificado

TAD de los grafos: Grafos regulares

PorJosé A. Alonso 8-junio-20233-junio-2023

Un grafo regular es un grafo en el que todos sus vértices tienen el mismo grado.

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

   regular :: (Ix v,Num p) => Grafo v p -> Bool

1	regular :: (Ix v,Num p) => Grafo v p -> Bool

tal que (regular g) se verifica si el grafo g es regular. Por ejemplo,

   λ> regular (creaGrafo' D (1,3) [(1,2),(2,3),(3,1)])
   True
   λ> regular (creaGrafo' ND (1,3) [(1,2),(2,3)])
   False
   λ> regular (completo 4)
   True

λ> regular (creaGrafo' D (1,3) [(1,2),(2,3),(3,1)])

True

λ> regular (creaGrafo' ND (1,3) [(1,2),(2,3)])

False

λ> regular (completo 4)

True

Comprobar que los grafos completos son regulares.

Soluciones

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

Soluciones en Haskell

module Grafo_Grafos_regulares where

import TAD.Grafo (Grafo, Orientacion (D, ND), nodos, creaGrafo')
import Data.Ix (Ix)
import Grafo_Grado_de_un_vertice (grado)
import Grafo_Grafos_completos (completo)
import Test.Hspec (Spec, hspec, it, shouldBe)

regular :: (Ix v,Num p) => Grafo v p -> Bool
regular g = and [grado g v == k | v <- vs]
  where vs = nodos g
        k  = grado g (head vs)

-- La propiedad de la regularidad de todos los grafos completos de orden
-- entre m y n es
prop_CompletoRegular :: Int -> Int -> Bool
prop_CompletoRegular m n =
  and [regular (completo x) | x <- [m..n]]

-- La comprobación es
--    λ> prop_CompletoRegular 1 30
--    True

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

verifica :: IO ()
verifica = hspec spec

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

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

module Grafo_Grafos_regulares where

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

import Data.Ix (Ix)

import Grafo_Grado_de_un_vertice (grado)

import Grafo_Grafos_completos (completo)

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

regular :: (Ix v,Num p) => Grafo v p -> Bool

regular g = and [grado g v == k | v <- vs]

where vs = nodos g

k = grado g (head vs)

-- La propiedad de la regularidad de todos los grafos completos de orden

-- entre m y n es

prop_CompletoRegular :: Int -> Int -> Bool

prop_CompletoRegular m n =

and [regular (completo x) | x <- [m..n]]

-- La comprobación es

-- λ> prop_CompletoRegular 1 30

-- True

-- Verificación

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

verifica :: IO ()

verifica = hspec spec

spec :: Spec

spec = do

it "e1" $

regular g1 `shouldBe` True

it "e2" $

regular g2 `shouldBe` False

it "e3" $

regular (completo 4) `shouldBe` True

where

g1, g2 :: Grafo Int Int

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

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

-- La verificación es

-- λ> verifica

-- e1

-- e2

-- e3

-- Finished in 0.0006 seconds

-- 3 examples, 0 failures

Soluciones en Python

from src.Grafo_Grado_de_un_vertice import grado
from src.Grafo_Grafos_completos import completo
from src.TAD.Grafo import Grafo, Orientacion, creaGrafo_, nodos


def regular(g: Grafo) -> bool:
    vs = nodos(g)
    k = grado(g, vs[0])
    return all(grado(g, v) == k for v in vs)

# La propiedad de la regularidad de todos los grafos completos de orden
# entre m y n es
def prop_CompletoRegular(m: int, n: int) -> bool:
    return all(regular(completo(x)) for x in range(m, n + 1))

# La comprobación es
#    >>> prop_CompletoRegular(1, 30)
#    True

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

def test_regular() -> None:
    g1 = creaGrafo_(Orientacion.D, (1,3), [(1,2),(2,3),(3,1)])
    g2 = creaGrafo_(Orientacion.ND, (1,3), [(1,2),(2,3)])
    assert regular(g1)
    assert not regular(g2)
    assert regular(completo(4))
    print("Verificado")

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

from src.Grafo_Grado_de_un_vertice import grado

from src.Grafo_Grafos_completos import completo

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

def regular(g: Grafo) -> bool:

vs = nodos(g)

k = grado(g, vs[0])

return all(grado(g, v) == k for v in vs)

# La propiedad de la regularidad de todos los grafos completos de orden

# entre m y n es

def prop_CompletoRegular(m: int, n: int) -> bool:

return all(regular(completo(x)) for x in range(m, n + 1))

# La comprobación es

# >>> prop_CompletoRegular(1, 30)

# True

# Verificación

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

def test_regular() -> None:

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

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

assert regular(g1)

assert not regular(g2)

assert regular(completo(4))

print("Verificado")

# La verificación es

# >>> test_regular()

# Verificado

TAD de los grafos: Lema del apretón de manos

PorJosé A. Alonso 7-junio-202328-mayo-2023

En la teoría de grafos, se conoce como «Lema del apretón de manos» la siguiente propiedad: la suma de los grados de los vértices de g es el doble del número de aristas de g.

Comprobar con QuickCheck que para cualquier grafo g, se verifica dicha propiedad.

Soluciones

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

Soluciones en Haskell

import TAD.Grafo (Grafo, nodos)
import TAD.GrafoGenerador
import Grafo_Grado_de_un_vertice (grado)
import Grafo_Numero_de_aristas_de_un_grafo (nAristas)
import Test.QuickCheck

prop_apretonManos :: Grafo Int Int -> Bool
prop_apretonManos g =
  sum [grado g v | v <- nodos g] == 2 * nAristas g

-- La comprobación es
--    λ> quickCheck prop_apretonManos
--    +++ OK, passed 100 tests.

import TAD.Grafo (Grafo, nodos)

import TAD.GrafoGenerador

import Grafo_Grado_de_un_vertice (grado)

import Grafo_Numero_de_aristas_de_un_grafo (nAristas)

import Test.QuickCheck

prop_apretonManos :: Grafo Int Int -> Bool

prop_apretonManos g =

sum [grado g v | v <- nodos g] == 2 * nAristas g

-- La comprobación es

-- λ> quickCheck prop_apretonManos

-- +++ OK, passed 100 tests.

Soluciones en Python

from hypothesis import given

from src.Grafo_Grado_de_un_vertice import grado
from src.Grafo_Numero_de_aristas_de_un_grafo import nAristas
from src.TAD.Grafo import nodos
from src.TAD.GrafoGenerador import gen_grafo


# La propiedad es
@given(gen_grafo())
def test_apreton(g):
    assert sum((grado(g, v) for v in nodos(g))) == 2 * nAristas(g)

# La comprobación es
#    src> poetry run pytest -q Grafo_Lema_del_apreton_de_manos.py
#    1 passed in 0.32s

from hypothesis import given

from src.Grafo_Grado_de_un_vertice import grado

from src.Grafo_Numero_de_aristas_de_un_grafo import nAristas

from src.TAD.Grafo import nodos

from src.TAD.GrafoGenerador import gen_grafo

# La propiedad es

@given(gen_grafo())

def test_apreton(g):

assert sum((grado(g, v) for v in nodos(g))) == 2 * nAristas(g)

# La comprobación es

# src> poetry run pytest -q Grafo_Lema_del_apreton_de_manos.py

# 1 passed in 0.32s

TAD de los grafos: Grado de un vértice

PorJosé A. Alonso 6-junio-20233-junio-2023

El grado de un vértice v de un grafo dirigido g, es el número aristas de g que contiene a v. Si g es no dirigido, el grado de un vértice v es el número de aristas incidentes en v, teniendo en cuenta que los lazos se cuentan dos veces.

Usando el tipo abstracto de datos de los grafos, definir las funciones,

   grado :: (Ix v,Num p) => Grafo v p -> v -> Int

1	grado :: (Ix v,Num p) => Grafo v p -> v -> Int

tal que grado g v es el grado del vértice v en el grafo g. Por ejemplo,

   g1 = creaGrafo' ND (1,5) [(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)]
   g2 = creaGrafo' D  (1,5) [(1,2),(1,3),(1,5),(2,4),(2,5),(4,3),(4,5)]
   g3 = creaGrafo' D  (1,3) [(1,2),(2,2),(3,1),(3,2)]
   g4 = creaGrafo' D  (1,1) [(1,1)]
   g5 = creaGrafo' ND (1,3) [(1,2),(1,3),(2,3),(3,3)]
   g6 = creaGrafo' D  (1,3) [(1,2),(1,3),(2,3),(3,3)]
   grado g1 5 ==  4
   grado g2 5 ==  3
   grado g2 1 ==  3
   grado g3 2 ==  4
   grado g3 1 ==  2
   grado g3 3 ==  2
   grado g4 1 ==  2
   grado g6 3 ==  4
   grado g6 3 ==  4

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

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

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

g4 = creaGrafo' D (1,1) [(1,1)]

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

g6 = creaGrafo' D (1,3) [(1,2),(1,3),(2,3),(3,3)]

grado g1 5 == 4

grado g2 5 == 3

grado g2 1 == 3

grado g3 2 == 4

grado g3 1 == 2

grado g3 3 == 2

grado g4 1 == 2

grado g6 3 == 4

Comprobar con QuickCheck que en todo grafo, el número de nodos de grado impar es par.

Soluciones

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

Soluciones en Haskell

module Grafo_Grado_de_un_vertice where

import TAD.Grafo (Grafo, Orientacion (D, ND), dirigido, nodos, creaGrafo')
import Data.Ix (Ix)
import Grafo_Lazos_de_un_grafo (lazos)
import Grafo_Incidentes_de_un_vertice (incidentes)
import Grafo_Grados_positivos_y_negativos (gradoPos, gradoNeg)
import Test.Hspec (Spec, hspec, it, shouldBe)

grado :: (Ix v,Num p) => Grafo v p -> v -> Int
grado g v | dirigido g           = gradoNeg g v + gradoPos g v
          | (v,v) `elem` lazos g = length (incidentes g v) + 1
          | otherwise            = length (incidentes g v)

-- La propiedad es
prop_numNodosGradoImpar :: Grafo Int Int -> Bool
prop_numNodosGradoImpar g =
  even (length [v | v <- nodos g, odd (grado g v)])

-- La comprobación es
--    λ> quickCheck prop_numNodosGradoImpar
--    +++ OK, passed 100 tests.

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

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "e1" $
    grado g1 5 `shouldBe`  4
  it "e2" $
    grado g2 5 `shouldBe`  3
  it "e3" $
    grado g2 1 `shouldBe`  3
  it "e4" $
    grado g3 2 `shouldBe`  4
  it "e5" $
    grado g3 1 `shouldBe`  2
  it "e6" $
    grado g3 3 `shouldBe`  2
  it "e7" $
    grado g4 1 `shouldBe`  2
  it "e8" $
    grado g5 3 `shouldBe`  4
  it "e9" $
    grado g6 3 `shouldBe`  4
  where
    g1, g2, g3, g4, g5, g6 :: Grafo Int Int
    g1 = creaGrafo' ND (1,5) [(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)]
    g2 = creaGrafo' D  (1,5) [(1,2),(1,3),(1,5),(2,4),(2,5),(4,3),(4,5)]
    g3 = creaGrafo' D  (1,3) [(1,2),(2,2),(3,1),(3,2)]
    g4 = creaGrafo' D  (1,1) [(1,1)]
    g5 = creaGrafo' ND (1,3) [(1,2),(1,3),(2,3),(3,3)]
    g6 = creaGrafo' D  (1,3) [(1,2),(1,3),(2,3),(3,3)]

-- La verificación es
--    λ> verifica
--
--    e1
--    e2
--    e3
--    e4
--    e5
--    e6
--    e7
--    e8
--    e9
--
--    Finished in 0.0015 seconds
--    9 examples, 0 failures

module Grafo_Grado_de_un_vertice where

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

import Data.Ix (Ix)

import Grafo_Lazos_de_un_grafo (lazos)

import Grafo_Incidentes_de_un_vertice (incidentes)

import Grafo_Grados_positivos_y_negativos (gradoPos, gradoNeg)

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

grado :: (Ix v,Num p) => Grafo v p -> v -> Int

grado g v | dirigido g = gradoNeg g v + gradoPos g v

| (v,v) `elem` lazos g = length (incidentes g v) + 1

| otherwise = length (incidentes g v)

-- La propiedad es

prop_numNodosGradoImpar :: Grafo Int Int -> Bool

prop_numNodosGradoImpar g =

even (length [v | v <- nodos g, odd (grado g v)])

-- La comprobación es

-- λ> quickCheck prop_numNodosGradoImpar

-- +++ OK, passed 100 tests.

-- Verificación

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

verifica :: IO ()

verifica = hspec spec

spec :: Spec

spec = do

it "e1" $

grado g1 5 `shouldBe` 4

it "e2" $

grado g2 5 `shouldBe` 3

it "e3" $

grado g2 1 `shouldBe` 3

it "e4" $

grado g3 2 `shouldBe` 4

it "e5" $

grado g3 1 `shouldBe` 2

it "e6" $

grado g3 3 `shouldBe` 2

it "e7" $

grado g4 1 `shouldBe` 2

it "e8" $

grado g5 3 `shouldBe` 4

it "e9" $

grado g6 3 `shouldBe` 4

where

g1, g2, g3, g4, g5, g6 :: Grafo Int Int

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

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

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

g4 = creaGrafo' D (1,1) [(1,1)]

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

g6 = creaGrafo' D (1,3) [(1,2),(1,3),(2,3),(3,3)]

-- La verificación es

-- λ> verifica

-- e1

-- e2

-- e3

-- e4

-- e5

-- e6

-- e7

-- e8

-- e9

-- Finished in 0.0015 seconds

-- 9 examples, 0 failures

Soluciones en Python

from hypothesis import given

from src.Grafo_Grados_positivos_y_negativos import gradoNeg, gradoPos
from src.Grafo_Incidentes_de_un_vertice import incidentes
from src.Grafo_Lazos_de_un_grafo import lazos
from src.TAD.Grafo import (Grafo, Orientacion, Vertice, creaGrafo_, dirigido,
                           nodos)
from src.TAD.GrafoGenerador import gen_grafo


def grado(g: Grafo, v: Vertice) -> int:
    if dirigido(g):
        return gradoNeg(g, v) + gradoPos(g, v)
    if (v, v) in lazos(g):
        return len(incidentes(g, v)) + 1
    return len(incidentes(g, v))

# La propiedad esp
@given(gen_grafo())
def test_grado1(g):
    assert len([v for v in nodos(g) if grado(g, v) % 2 == 1]) % 2 == 0

# La comprobación es
#    src> poetry run pytest -q Grafo_Grado_de_un_vertice.py
#    1 passed in 0.36s

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

def test_grado() -> None:
    g1 = creaGrafo_(Orientacion.ND, (1,5),
                    [(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)])
    g2 = creaGrafo_(Orientacion.D, (1,5),
                    [(1,2),(1,3),(1,5),(2,4),(2,5),(4,3),(4,5)])
    g3 = creaGrafo_(Orientacion.D, (1,3),
                    [(1,2),(2,2),(3,1),(3,2)])
    g4 = creaGrafo_(Orientacion.D, (1,1),
                    [(1,1)])
    g5 = creaGrafo_(Orientacion.ND, (1,3),
                    [(1,2),(1,3),(2,3),(3,3)])
    g6 = creaGrafo_(Orientacion.D, (1,3),
                    [(1,2),(1,3),(2,3),(3,3)])
    assert grado(g1, 5) == 4
    assert grado(g2, 5) == 3
    assert grado(g2, 1) == 3
    assert grado(g3, 2) == 4
    assert grado(g3, 1) == 2
    assert grado(g3, 3) == 2
    assert grado(g4, 1) == 2
    assert grado(g5, 3) == 4
    assert grado(g6, 3) == 4
    print("Verificado")

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

from hypothesis import given

from src.Grafo_Grados_positivos_y_negativos import gradoNeg, gradoPos

from src.Grafo_Incidentes_de_un_vertice import incidentes

from src.Grafo_Lazos_de_un_grafo import lazos

from src.TAD.Grafo import (Grafo, Orientacion, Vertice, creaGrafo_, dirigido,

nodos)

from src.TAD.GrafoGenerador import gen_grafo

def grado(g: Grafo, v: Vertice) -> int:

if dirigido(g):

return gradoNeg(g, v) + gradoPos(g, v)

if (v, v) in lazos(g):

return len(incidentes(g, v)) + 1

return len(incidentes(g, v))

# La propiedad esp

@given(gen_grafo())

def test_grado1(g):

assert len([v for v in nodos(g) if grado(g, v) % 2 == 1]) % 2 == 0

# La comprobación es

# src> poetry run pytest -q Grafo_Grado_de_un_vertice.py

# 1 passed in 0.36s

# Verificación

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

def test_grado() -> None:

g1 = creaGrafo_(Orientacion.ND, (1,5),

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

g2 = creaGrafo_(Orientacion.D, (1,5),

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

g3 = creaGrafo_(Orientacion.D, (1,3),

[(1,2),(2,2),(3,1),(3,2)])

g4 = creaGrafo_(Orientacion.D, (1,1),

[(1,1)])

g5 = creaGrafo_(Orientacion.ND, (1,3),

[(1,2),(1,3),(2,3),(3,3)])

g6 = creaGrafo_(Orientacion.D, (1,3),

[(1,2),(1,3),(2,3),(3,3)])

assert grado(g1, 5) == 4

assert grado(g2, 5) == 3

assert grado(g2, 1) == 3

assert grado(g3, 2) == 4

assert grado(g3, 1) == 2

assert grado(g3, 3) == 2

assert grado(g4, 1) == 2

assert grado(g5, 3) == 4

assert grado(g6, 3) == 4

print("Verificado")

# La verificación es

# >>> test_grado()

# Verificado

TAD de los grafos: Generadores de grafos

PorJosé A. Alonso 5-junio-20233-junio-2023

Definir un generador de grafos para comprobar propiedades de grafos con QuickCheck y hacer el tipo de los Grafos un subtipo de Arbitrary.

Usando el generador, con QuickCheck que para cualquier grafo g, las sumas de los grados positivos y la de los grados negativos de los vértices de g son iguales.

Soluciones

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

Soluciones en Haskell

La definición del generador es

{-# LANGUAGE FlexibleInstances #-}
{-# OPTIONS_GHC -fno-warn-orphans #-}

module TAD.GrafoGenerador where

import TAD.Grafo (Grafo, Orientacion (D, ND), creaGrafo)
import Test.QuickCheck (Arbitrary, Gen, arbitrary, choose, vectorOf)

-- (generaGND n ps) es el grafo completo de orden n tal que los pesos
-- están determinados por ps. Por ejemplo,
--    λ> generaGND 3 [4,2,5]
--    G ND ([1,2,3],[((1,2),4),((1,3),2),((2,3),5)])
--    λ> generaGND 3 [4,-2,5]
--    G ND ([1,2,3],[((1,2),4),((2,3),5)])
generaGND :: Int -> [Int] -> Grafo Int Int
generaGND n ps  = creaGrafo ND (1,n) l3
  where l1 = [(x,y) | x <- [1..n], y <- [1..n], x < y]
        l2 = zip l1 ps
        l3 = [(x,y,z) | ((x,y),z) <- l2, z > 0]

-- (generaGD n ps) es el grafo completo de orden n tal que los pesos
-- están determinados por ps. Por ejemplo,
--    λ> generaGD 3 [4,2,5]
--    G D ([1,2,3],[((1,1),4),((1,2),2),((1,3),5)])
--    λ> generaGD 3 [4,2,5,3,7,9,8,6]
--    G D ([1,2,3],[((1,1),4),((1,2),2),((1,3),5),
--                  ((2,1),3),((2,2),7),((2,3),9),
--                  ((3,1),8),((3,2),6)])
generaGD :: Int -> [Int] -> Grafo Int Int
generaGD n ps = creaGrafo D (1,n) l3
  where l1 = [(x,y) | x <- [1..n], y <- [1..n]]
        l2 = zip l1 ps
        l3 = [(x,y,z) | ((x,y),z) <- l2, z > 0]

-- genGD es un generador de grafos dirigidos. Por ejemplo,
--    λ> sample genGD
--    G D ([1],[])
--    G D ([1,2],[((1,1),5),((2,1),4)])
--    G D ([1,2],[((1,1),3),((1,2),3)])
--    G D ([1,2,3,4,5,6],[])
--    G D ([1,2],[((2,2),16)])
--    ...
genGD :: Gen (Grafo Int Int)
genGD = do
  n <- choose (1,10)
  xs <- vectorOf (n*n) arbitrary
  return (generaGD n xs)

-- genGND es un generador de grafos dirigidos. Por ejemplo,
--    λ> sample genGND
--    G ND ([1,2,3,4,5,6,7,8],[])
--    G ND ([1],[])
--    G ND ([1,2,3,4,5],[((1,2),2),((2,3),5),((3,4),5),((3,5),5)])
--    G ND ([1,2,3,4,5],[((1,2),6),((1,3),5),((1,5),1),((3,5),9),((4,5),6)])
--    G ND ([1,2,3,4],[((1,2),5),((3,4),2)])
--    G ND ([1,2,3],[])
--    G ND ([1,2,3,4],[((1,2),5),((1,4),14),((2,4),10)])
--    G ND ([1,2,3,4,5],[((1,5),8),((4,5),5)])
--    G ND ([1,2,3,4],[((1,2),1),((1,4),4),((2,3),4),((3,4),5)])
--    G ND ([1,2,3],[((1,2),8),((1,3),8),((2,3),3)])
--    ...
genGND :: Gen (Grafo Int Int)
genGND = do
  n <- choose (1,10)
  xs <- vectorOf (n*n) arbitrary
  return (generaGND n xs)

-- genG es un generador de grafos. Por ejemplo,
--    λ> sample genG
--    G ND ([1,2,3,4,5,6],[])
--    G D ([1],[((1,1),2)])
--    G D ([1,2],[((1,1),9)])
--    ...
genG :: Gen (Grafo Int Int)
genG = do
  d <- choose (True,False)
  n <- choose (1,10)
  xs <- vectorOf (n*n) arbitrary
  if d then return (generaGD n xs)
       else return (generaGND n xs)

-- Los grafos está contenido en la clase de los objetos generables
-- aleatoriamente.
instance Arbitrary (Grafo Int Int) where
  arbitrary = genG

{-# LANGUAGE FlexibleInstances #-}

{-# OPTIONS_GHC -fno-warn-orphans #-}

module TAD.GrafoGenerador where

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

import Test.QuickCheck (Arbitrary, Gen, arbitrary, choose, vectorOf)

-- (generaGND n ps) es el grafo completo de orden n tal que los pesos

-- están determinados por ps. Por ejemplo,

-- λ> generaGND 3 [4,2,5]

-- G ND ([1,2,3],[((1,2),4),((1,3),2),((2,3),5)])

-- λ> generaGND 3 [4,-2,5]

-- G ND ([1,2,3],[((1,2),4),((2,3),5)])

generaGND :: Int -> [Int] -> Grafo Int Int

generaGND n ps = creaGrafo ND (1,n) l3

where l1 = [(x,y) | x <- [1..n], y <- [1..n], x < y]

l2 = zip l1 ps

l3 = [(x,y,z) | ((x,y),z) <- l2, z > 0]

-- (generaGD n ps) es el grafo completo de orden n tal que los pesos

-- están determinados por ps. Por ejemplo,

-- λ> generaGD 3 [4,2,5]

-- G D ([1,2,3],[((1,1),4),((1,2),2),((1,3),5)])

-- λ> generaGD 3 [4,2,5,3,7,9,8,6]

-- G D ([1,2,3],[((1,1),4),((1,2),2),((1,3),5),

-- ((2,1),3),((2,2),7),((2,3),9),

-- ((3,1),8),((3,2),6)])

generaGD :: Int -> [Int] -> Grafo Int Int

generaGD n ps = creaGrafo D (1,n) l3

where l1 = [(x,y) | x <- [1..n], y <- [1..n]]

l2 = zip l1 ps

l3 = [(x,y,z) | ((x,y),z) <- l2, z > 0]

-- genGD es un generador de grafos dirigidos. Por ejemplo,

-- λ> sample genGD

-- G D ([1],[])

-- G D ([1,2],[((1,1),5),((2,1),4)])

-- G D ([1,2],[((1,1),3),((1,2),3)])

-- G D ([1,2,3,4,5,6],[])

-- G D ([1,2],[((2,2),16)])

-- ...

genGD :: Gen (Grafo Int Int)

genGD = do

n <- choose (1,10)

xs <- vectorOf (n*n) arbitrary

return (generaGD n xs)

-- genGND es un generador de grafos dirigidos. Por ejemplo,

-- λ> sample genGND

-- G ND ([1,2,3,4,5,6,7,8],[])

-- G ND ([1],[])

-- G ND ([1,2,3,4,5],[((1,2),2),((2,3),5),((3,4),5),((3,5),5)])

-- G ND ([1,2,3,4,5],[((1,2),6),((1,3),5),((1,5),1),((3,5),9),((4,5),6)])

-- G ND ([1,2,3,4],[((1,2),5),((3,4),2)])

-- G ND ([1,2,3],[])

-- G ND ([1,2,3,4],[((1,2),5),((1,4),14),((2,4),10)])

-- G ND ([1,2,3,4,5],[((1,5),8),((4,5),5)])

-- G ND ([1,2,3,4],[((1,2),1),((1,4),4),((2,3),4),((3,4),5)])

-- G ND ([1,2,3],[((1,2),8),((1,3),8),((2,3),3)])

-- ...

genGND :: Gen (Grafo Int Int)

genGND = do

n <- choose (1,10)

xs <- vectorOf (n*n) arbitrary

return (generaGND n xs)

-- genG es un generador de grafos. Por ejemplo,

-- λ> sample genG

-- G ND ([1,2,3,4,5,6],[])

-- G D ([1],[((1,1),2)])

-- G D ([1,2],[((1,1),9)])

-- ...

genG :: Gen (Grafo Int Int)

genG = do

d <- choose (True,False)

n <- choose (1,10)

xs <- vectorOf (n*n) arbitrary

if d then return (generaGD n xs)

else return (generaGND n xs)

-- Los grafos está contenido en la clase de los objetos generables

-- aleatoriamente.

instance Arbitrary (Grafo Int Int) where

arbitrary = genG

La comprobación de la propiedad es

module Grafo_Propiedades_de_grados_positivos_y_negativos where

import TAD.Grafo (Grafo, nodos)
import TAD.GrafoGenerador
import Grafo_Grados_positivos_y_negativos (gradoPos, gradoNeg)
import Test.QuickCheck

-- La propiedad es
prop_sumaGrados :: Grafo Int Int -> Bool
prop_sumaGrados g =
  sum [gradoPos g v | v <- vs] == sum [gradoNeg g v | v <- vs]
  where vs = nodos g

-- La comprobación es
--    λ> quickCheck prop_sumaGrados
--    +++ OK, passed 100 tests.

module Grafo_Propiedades_de_grados_positivos_y_negativos where

import TAD.Grafo (Grafo, nodos)

import TAD.GrafoGenerador

import Grafo_Grados_positivos_y_negativos (gradoPos, gradoNeg)

import Test.QuickCheck

-- La propiedad es

prop_sumaGrados :: Grafo Int Int -> Bool

prop_sumaGrados g =

sum [gradoPos g v | v <- vs] == sum [gradoNeg g v | v <- vs]

where vs = nodos g

-- La comprobación es

-- λ> quickCheck prop_sumaGrados

-- +++ OK, passed 100 tests.

Soluciones en Python

La definición del generador es

from hypothesis import strategies as st
from hypothesis.strategies import composite

from src.TAD.Grafo import Orientacion, creaGrafo_


# Generador de aristas. Por ejemplo,
#    >>> gen_aristas(5).example()
#    [(2, 5), (4, 5), (1, 2), (2, 3), (4, 1)]
#    >>> gen_aristas(5).example()
#    [(3, 4)]
#    >>> gen_aristas(5).example()
#    [(5, 3), (3, 2), (1, 3), (5, 2)]
@composite
def gen_aristas(draw, n):
    as_ = draw(st.lists(st.tuples(st.integers(1,n),
                                  st.integers(1,n)),
                        unique=True))
    return as_

# Generador de grafos no dirigidos. Por ejemplo,
#    >>> gen_grafoND().example()
#    G ND ([1, 2, 3, 4, 5], [(1, 4), (5, 5)])
#    >>> gen_grafoND().example()
#    G ND ([1], [])
#    >>> gen_grafoND().example()
#    G ND ([1, 2, 3, 4, 5, 6, 7, 8], [(7, 7)])
#    >>> gen_grafoND().example()
#    G ND ([1, 2, 3, 4, 5, 6], [(1, 3), (2, 4), (3, 3), (3, 5)])
@composite
def gen_grafoND(draw):
    n = draw(st.integers(1,10))
    as_ = [(x, y) for (x, y ) in draw(gen_aristas(n)) if x <= y]
    return creaGrafo_(Orientacion.ND, (1,n), as_)

# Generador de grafos dirigidos. Por ejemplo,
#    >>> gen_grafoD().example()
#    G D ([1, 2, 3, 4], [(3, 3), (4, 1)])
#    >>> gen_grafoD().example()
#    G D ([1, 2], [(1, 1), (2, 1), (2, 2)])
#    >>> gen_grafoD().example()
#    G D ([1, 2], [])
@composite
def gen_grafoD(draw):
    n = draw(st.integers(1,10))
    as_ = draw(gen_aristas(n))
    return creaGrafo_(Orientacion.D, (1,n), as_)

# Generador de grafos. Por ejemplo,
#    >>> gen_grafo().example()
#    G ND ([1, 2, 3, 4, 5, 6, 7], [(1, 3)])
#    >>> gen_grafo().example()
#    G D ([1], [])
#    >>> gen_grafo().example()
#    G D ([1, 2, 3, 4, 5, 6, 7], [(1, 3), (3, 4), (5, 5)])
@composite
def gen_grafo(draw):
    o = draw(st.sampled_from([Orientacion.D, Orientacion.ND]))
    if o == Orientacion.ND:
        return draw(gen_grafoND())
    return draw(gen_grafoD())

from hypothesis import strategies as st

from hypothesis.strategies import composite

from src.TAD.Grafo import Orientacion, creaGrafo_

# Generador de aristas. Por ejemplo,

# >>> gen_aristas(5).example()

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

# >>> gen_aristas(5).example()

# [(3, 4)]

# >>> gen_aristas(5).example()

# [(5, 3), (3, 2), (1, 3), (5, 2)]

@composite

def gen_aristas(draw, n):

as_ = draw(st.lists(st.tuples(st.integers(1,n),

st.integers(1,n)),

unique=True))

return as_

# Generador de grafos no dirigidos. Por ejemplo,

# >>> gen_grafoND().example()

# G ND ([1, 2, 3, 4, 5], [(1, 4), (5, 5)])

# >>> gen_grafoND().example()

# G ND ([1], [])

# >>> gen_grafoND().example()

# G ND ([1, 2, 3, 4, 5, 6, 7, 8], [(7, 7)])

# >>> gen_grafoND().example()

# G ND ([1, 2, 3, 4, 5, 6], [(1, 3), (2, 4), (3, 3), (3, 5)])

@composite

def gen_grafoND(draw):

n = draw(st.integers(1,10))

as_ = [(x, y) for (x, y ) in draw(gen_aristas(n)) if x <= y]

return creaGrafo_(Orientacion.ND, (1,n), as_)

# Generador de grafos dirigidos. Por ejemplo,

# >>> gen_grafoD().example()

# G D ([1, 2, 3, 4], [(3, 3), (4, 1)])

# >>> gen_grafoD().example()

# G D ([1, 2], [(1, 1), (2, 1), (2, 2)])

# >>> gen_grafoD().example()

# G D ([1, 2], [])

@composite

def gen_grafoD(draw):

n = draw(st.integers(1,10))

as_ = draw(gen_aristas(n))

return creaGrafo_(Orientacion.D, (1,n), as_)

# Generador de grafos. Por ejemplo,

# >>> gen_grafo().example()

# G ND ([1, 2, 3, 4, 5, 6, 7], [(1, 3)])

# >>> gen_grafo().example()

# G D ([1], [])

# >>> gen_grafo().example()

# G D ([1, 2, 3, 4, 5, 6, 7], [(1, 3), (3, 4), (5, 5)])

@composite

def gen_grafo(draw):

o = draw(st.sampled_from([Orientacion.D, Orientacion.ND]))

if o == Orientacion.ND:

return draw(gen_grafoND())

return draw(gen_grafoD())

La comprobación de la propiedad es

from hypothesis import given

from src.Grafo_Grados_positivos_y_negativos import gradoNeg, gradoPos
from src.TAD.Grafo import nodos
from src.TAD.GrafoGenerador import gen_grafo


# La propiedad es
@given(gen_grafo())
def test_sumaGrados(g):
    vs = nodos(g)
    assert sum((gradoPos(g, v) for v in vs)) == sum((gradoNeg(g, v) for v in vs))

# La comprobación es
#    src> poetry run pytest -q Grafo_Propiedades_de_grados_positivos_y_negativos.py
#    1 passed in 0.31s

from hypothesis import given

from src.Grafo_Grados_positivos_y_negativos import gradoNeg, gradoPos

from src.TAD.Grafo import nodos

from src.TAD.GrafoGenerador import gen_grafo

# La propiedad es

@given(gen_grafo())

def test_sumaGrados(g):

vs = nodos(g)

assert sum((gradoPos(g, v) for v in vs)) == sum((gradoNeg(g, v) for v in vs))

# La comprobación es

# src> poetry run pytest -q Grafo_Propiedades_de_grados_positivos_y_negativos.py

# 1 passed in 0.31s

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

TAD de los grafos: Recorridos en un grafo completo

TAD de los grafos: Grafos k-regulares

TAD de los grafos: Grafos regulares

TAD de los grafos: Lema del apretón de manos

TAD de los grafos: Grado de un vértice

TAD de los grafos: Generadores de grafos

Entradas recientes

Buscar

Correo electrónico