mayo 2023 – Exercitium

TAD de los grafos: Lazos de un grafo

PorJosé A. Alonso 31-mayo-20233-junio-2023

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

   lazos  :: (Ix v,Num p) => Grafo v p -> [(v,v)]
   nLazos :: (Ix v,Num p) => Grafo v p -> Int

1 2	lazos :: (Ix v,Num p) => Grafo v p -> [(v,v)] nLazos :: (Ix v,Num p) => Grafo v p -> Int

tales que

lazos g es el conjunto de los lazos (es decir, aristas cuyos extremos son iguales) del grafo g. Por ejemplo,

     λ> ej1 = creaGrafo' D (1,3) [(1,1),(2,3),(3,2),(3,3)]
     λ> ej2 = creaGrafo' ND (1,3) [(2,3),(3,1)]
     λ> lazos ej1
     [(1,1),(3,3)]
     λ> lazos ej2
     []

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

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

λ> lazos ej1

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

λ> lazos ej2

[]

nLazos g es el número de lazos del grafo g. Por ejemplo,

     λ> nLazos ej1
     2
     λ> nLazos ej2
     0

λ> nLazos ej1

λ> nLazos ej2

Soluciones

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

Soluciones en Haskell

module Grafo_Lazos_de_un_grafo where

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

lazos :: (Ix v,Num p) => Grafo v p -> [(v,v)]
lazos g = [(x,x) | x <- nodos g, aristaEn g (x,x)]

nLazos :: (Ix v,Num p) => Grafo v p ->  Int
nLazos = length . lazos

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

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "e1" $
    lazos ej1 `shouldBe` [(1,1),(3,3)]
  it "e2" $
    lazos ej2 `shouldBe` []
  it "e3" $
    nLazos ej1 `shouldBe` 2
  it "e4" $
    nLazos ej2 `shouldBe` 0
  where
    ej1, ej2 :: Grafo Int Int
    ej1 = creaGrafo' D (1,3) [(1,1),(2,3),(3,2),(3,3)]
    ej2 = creaGrafo' ND (1,3) [(2,3),(3,1)]

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

module Grafo_Lazos_de_un_grafo where

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

import Data.Ix (Ix)

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

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

lazos g = [(x,x) | x <- nodos g, aristaEn g (x,x)]

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

nLazos = length . lazos

-- Verificación

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

verifica :: IO ()

verifica = hspec spec

spec :: Spec

spec = do

it "e1" $

lazos ej1 `shouldBe` [(1,1),(3,3)]

it "e2" $

lazos ej2 `shouldBe` []

it "e3" $

nLazos ej1 `shouldBe` 2

it "e4" $

nLazos ej2 `shouldBe` 0

where

ej1, ej2 :: Grafo Int Int

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

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

-- La verificación es

-- λ> verifica

-- e1

-- e2

-- e3

-- e4

-- Finished in 0.0005 seconds

-- 4 examples, 0 failures

Soluciones en Python

from src.TAD.Grafo import (Grafo, Orientacion, Vertice, aristaEn, creaGrafo_,
                           nodos)


def lazos(g: Grafo) -> list[tuple[Vertice, Vertice]]:
    return [(x, x) for x in nodos(g) if aristaEn(g, (x, x))]

def nLazos(g: Grafo) -> int:
    return len(lazos(g))

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

def test_lazos() -> None:
    ej1 = creaGrafo_(Orientacion.D, (1,3), [(1,1),(2,3),(3,2),(3,3)])
    ej2 = creaGrafo_(Orientacion.ND, (1,3), [(2,3),(3,1)])
    assert lazos(ej1) == [(1,1),(3,3)]
    assert lazos(ej2) == []
    assert nLazos(ej1) == 2
    assert nLazos(ej2) == 0
    print("Verificado")

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

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

nodos)

def lazos(g: Grafo) -> list[tuple[Vertice, Vertice]]:

return [(x, x) for x in nodos(g) if aristaEn(g, (x, x))]

def nLazos(g: Grafo) -> int:

return len(lazos(g))

# Verificación

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

def test_lazos() -> None:

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

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

assert lazos(ej1) == [(1,1),(3,3)]

assert lazos(ej2) == []

assert nLazos(ej1) == 2

assert nLazos(ej2) == 0

print("Verificado")

# La verificación es

# >>> test_lazos()

# Verificado

TAD de los grafos: Contiguos de un vértice

PorJosé A. Alonso 30-mayo-20233-junio-2023

En un un grafo g, los contiguos de un vértice v es el conjuntos de vértices x de g tales que x es adyacente o incidente con v.

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

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

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

tal que contiguos g v es el conjunto de los vértices de g contiguos con el vértice v. Por ejemplo,

   λ> g1 = creaGrafo' D (1,3) [(1,2),(2,2),(3,1),(3,2)]
   λ> contiguos g1 1
   [2,3]
   λ> contiguos g1 2
   [2,1,3]
   λ> contiguos g1 3
   [1,2]
   λ> g2 = creaGrafo' ND (1,3) [(1,2),(2,2),(3,1),(3,2)]
   λ> contiguos g2 1
   [2,3]
   λ> contiguos g2 2
   [1,2,3]
   λ> contiguos g2 3
   [1,2]

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

λ> contiguos g1 1

[2,3]

λ> contiguos g1 2

[2,1,3]

λ> contiguos g1 3

[1,2]

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

λ> contiguos g2 1

[2,3]

λ> contiguos g2 2

[1,2,3]

λ> contiguos g2 3

[1,2]

Soluciones

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

Soluciones en Haskell

module Grafo_Contiguos_de_un_vertice where

import TAD.Grafo (Grafo, Orientacion (D, ND), adyacentes, creaGrafo')
import Grafo_Incidentes_de_un_vertice (incidentes)
import Data.List (nub)
import Data.Ix
import Test.Hspec

contiguos :: (Ix v,Num p) => Grafo v p -> v -> [v]
contiguos g v = nub (adyacentes g v ++ incidentes g v)

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

verifica :: IO ()
verifica = hspec spec

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

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

module Grafo_Contiguos_de_un_vertice where

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

import Grafo_Incidentes_de_un_vertice (incidentes)

import Data.List (nub)

import Data.Ix

import Test.Hspec

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

contiguos g v = nub (adyacentes g v ++ incidentes g v)

-- Verificación

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

verifica :: IO ()

verifica = hspec spec

spec :: Spec

spec = do

it "e1" $

contiguos g1 1 `shouldBe` [2,3]

it "e2" $

contiguos g1 2 `shouldBe` [2,1,3]

it "e3" $

contiguos g1 3 `shouldBe` [1,2]

it "e4" $

contiguos g2 1 `shouldBe` [2,3]

it "e5" $

contiguos g2 2 `shouldBe` [1,2,3]

it "e6" $

contiguos g2 3 `shouldBe` [1,2]

where

g1, g2 :: Grafo Int Int

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

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

-- La verificación es

-- λ> verifica

-- e1

-- e2

-- e3

-- e4

-- e5

-- e6

-- Finished in 0.0005 seconds

-- 6 examples, 0 failures

Soluciones en Python

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


def contiguos(g: Grafo, v: Vertice) -> list[Vertice]:
    return list(set(adyacentes(g, v) + incidentes(g, v)))

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

def test_contiguos() -> None:
    g1 = creaGrafo_(Orientacion.D, (1,3), [(1,2),(2,2),(3,1),(3,2)])
    g2 = creaGrafo_(Orientacion.ND, (1,3), [(1,2),(2,2),(3,1),(3,2)])
    assert contiguos(g1, 1) == [2, 3]
    assert contiguos(g1, 2) == [1, 2, 3]
    assert contiguos(g1, 3) == [1, 2]
    assert contiguos(g2, 1) == [2, 3]
    assert contiguos(g2, 2) == [1, 2, 3]
    assert contiguos(g2, 3) == [1, 2]
    print("Verificado")

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

from src.Grafo_Incidentes_de_un_vertice import incidentes

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

def contiguos(g: Grafo, v: Vertice) -> list[Vertice]:

return list(set(adyacentes(g, v) + incidentes(g, v)))

# Verificación

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

def test_contiguos() -> None:

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

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

assert contiguos(g1, 1) == [2, 3]

assert contiguos(g1, 2) == [1, 2, 3]

assert contiguos(g1, 3) == [1, 2]

assert contiguos(g2, 1) == [2, 3]

assert contiguos(g2, 2) == [1, 2, 3]

assert contiguos(g2, 3) == [1, 2]

print("Verificado")

# La verificación es

# >>> test_contiguos()

# Verificado

TAD de los grafos: Incidentes de un vértice

PorJosé A. Alonso 29-mayo-20233-junio-2023

En un un grafo g, los incidentes de un vértice v es el conjuntos de vértices x de g para los que hay un arco (o una arista) de x a v; es decir, que v es adyacente a x.

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

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

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

tal que incidentes g v es la lista de los vértices incidentes en el vértice v. Por ejemplo,

   λ> g1 = creaGrafo' D (1,3) [(1,2),(2,2),(3,1),(3,2)]
   λ> incidentes g1 1
   [3]
   λ> incidentes g1 2
   [1,2,3]
   λ> incidentes g1 3
   []
   λ> g2 = creaGrafo' ND (1,3) [(1,2),(2,2),(3,1),(3,2)]
   λ> incidentes g2 1
   [2,3]
   λ> incidentes g2 2
   [1,2,3]
   λ> incidentes g2 3
   [1,2]

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

λ> incidentes g1 1

[3]

λ> incidentes g1 2

[1,2,3]

λ> incidentes g1 3

[]

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

λ> incidentes g2 1

[2,3]

λ> incidentes g2 2

[1,2,3]

λ> incidentes g2 3

[1,2]

Soluciones

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

Soluciones en Haskell

module Grafo_Incidentes_de_un_vertice where

import TAD.Grafo (Grafo, Orientacion (D, ND), nodos,  adyacentes, creaGrafo')
import Data.Ix
import Test.Hspec

incidentes :: (Ix v,Num p) => Grafo v p -> v -> [v]
incidentes g v = [x | x <- nodos g, v `elem` adyacentes g x]

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

verifica :: IO ()
verifica = hspec spec

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

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

module Grafo_Incidentes_de_un_vertice where

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

import Data.Ix

import Test.Hspec

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

incidentes g v = [x | x <- nodos g, v `elem` adyacentes g x]

-- Verificación

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

verifica :: IO ()

verifica = hspec spec

spec :: Spec

spec = do

it "e1" $

incidentes g1 1 `shouldBe` [3]

it "e2" $

incidentes g1 2 `shouldBe` [1,2,3]

it "e3" $

incidentes g1 3 `shouldBe` []

it "e4" $

incidentes g2 1 `shouldBe` [2,3]

it "e5" $

incidentes g2 2 `shouldBe` [1,2,3]

it "e6" $

incidentes g2 3 `shouldBe` [1,2]

where

g1, g2 :: Grafo Int Int

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

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

-- La verificación es

-- λ> verifica

-- e1

-- e2

-- e3

-- e4

-- e5

-- e6

-- Finished in 0.0005 seconds

-- 6 examples, 0 failures

Soluciones en Python

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


def incidentes(g: Grafo, v: Vertice) -> list[Vertice]:
    return [x for x in nodos(g) if v in adyacentes(g, x)]

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

def test_incidentes() -> None:
    g1 = creaGrafo_(Orientacion.D, (1,3), [(1,2),(2,2),(3,1),(3,2)])
    g2 = creaGrafo_(Orientacion.ND, (1,3), [(1,2),(2,2),(3,1),(3,2)])
    assert incidentes(g1,1) == [3]
    assert incidentes(g1,2) == [1, 2, 3]
    assert incidentes(g1,3) == []
    assert incidentes(g2, 1) == [2, 3]
    assert incidentes(g2, 2) == [1, 2, 3]
    assert incidentes(g2, 3) == [1, 2]
    print("Verificado")

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

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

nodos)

def incidentes(g: Grafo, v: Vertice) -> list[Vertice]:

return [x for x in nodos(g) if v in adyacentes(g, x)]

# Verificación

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

def test_incidentes() -> None:

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

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

assert incidentes(g1,1) == [3]

assert incidentes(g1,2) == [1, 2, 3]

assert incidentes(g1,3) == []

assert incidentes(g2, 1) == [2, 3]

assert incidentes(g2, 2) == [1, 2, 3]

assert incidentes(g2, 3) == [1, 2]

print("Verificado")

# La verificación es

# >>> test_incidentes()

# Verificado

TAD de los grafos: Número de vértices

PorJosé A. Alonso 26-mayo-20233-junio-2023

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

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

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

tal que nVertices g es el número de vértices del grafo g. Por ejemplo,

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

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

Soluciones

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

Soluciones en Haskell

module Grafo_Numero_de_vertices where

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

nVertices :: (Ix v, Num p) => Grafo v p ->  Int
nVertices = length . nodos

module Grafo_Numero_de_vertices where

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

import Data.Ix

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

nVertices = length . nodos

Soluciones en Python

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


def nVertices(g: Grafo) -> int:
    return len(nodos(g))

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

def nVertices(g: Grafo) -> int:

return len(nodos(g))

TAD de los grafos: Grafos ciclos

PorJosé A. Alonso 25-mayo-20233-junio-2023

El ciclo de orden n, C(n), es un grafo no dirigido cuyo conjunto de vértices es {1,…,n} y las aristas son

   (1,2), (2,3), ..., (n-1,n), (n,1)

1	(1,2), (2,3), ..., (n-1,n), (n,1)

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

   grafoCiclo :: Int -> Grafo Int Int

1	grafoCiclo :: Int -> Grafo Int Int

tal que (grafoCiclo n) es el grafo ciclo de orden n. Por ejemplo,

   λ> grafoCiclo 3
   G ND ([1,2,3],[(1,2),(1,3),(2,3)])

1 2	λ> grafoCiclo 3 G ND ([1,2,3],[(1,2),(1,3),(2,3)])

Soluciones

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

Soluciones en Haskell

module Grafo_Grafos_ciclos where

import TAD.Grafo (Grafo, Orientacion (ND), creaGrafo')
import Test.Hspec (Spec, hspec, it, shouldBe)

grafoCiclo :: Int -> Grafo Int Int
grafoCiclo n =
  creaGrafo' ND (1,n) ((n,1):[(x,x+1) | x <- [1..n-1]])

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

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "e1" $
    show (grafoCiclo 3) `shouldBe`
    "G ND ([1,2,3],[(1,2),(1,3),(2,3)])"

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

module Grafo_Grafos_ciclos where

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

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

grafoCiclo :: Int -> Grafo Int Int

grafoCiclo n =

creaGrafo' ND (1,n) ((n,1):[(x,x+1) | x <- [1..n-1]])

-- Verificación

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

verifica :: IO ()

verifica = hspec spec

spec :: Spec

spec = do

it "e1" $

show (grafoCiclo 3) `shouldBe`

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

-- La verificación es

-- λ> verifica

-- e1

-- Finished in 0.0006 seconds

-- 1 example, 0 failures

Soluciones en Python

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


def grafoCiclo(n: int) -> Grafo:
    return creaGrafo_(Orientacion.ND,
                      (1, n),
                      [(n,1)] + [(x, x + 1) for x in range(1, n)])

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

def test_grafoCiclo() -> None:
    assert str(grafoCiclo(3)) == \
        "G ND ([1, 2, 3], [(1, 2), (1, 3), (2, 3)])"
    print("Verificado")

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

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

def grafoCiclo(n: int) -> Grafo:

return creaGrafo_(Orientacion.ND,

(1, n),

[(n,1)] + [(x, x + 1) for x in range(1, n)])

# Verificación

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

def test_grafoCiclo() -> None:

assert str(grafoCiclo(3)) == \

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

print("Verificado")

# La verificación es

# >>> test_grafoCiclo()

# Verificado

TAD de los grafos: Grafos completos

PorJosé A. Alonso 24-mayo-20233-junio-2023

El grafo completo de orden n, K(n), es un grafo no dirigido cuyos conjunto de vértices es {1,..n} y tiene una arista entre cada par de vértices distintos.

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

   completo :: Int -> Grafo Int Int

1	completo :: Int -> Grafo Int Int

tal que completo n es el grafo completo de orden n. Por ejemplo,

   λ> completo 4
   G ND ([1,2,3,4],[(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)])

1 2	λ> completo 4 G ND ([1,2,3,4],[(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)])

Soluciones

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

Soluciones en Haskell

module Grafo_Grafos_completos where

import TAD.Grafo (Grafo, Orientacion (ND), creaGrafo')
import Test.Hspec (Spec, hspec, it, shouldBe)

completo :: Int -> Grafo Int Int
completo n =
  creaGrafo' ND (1,n) [(x,y) | x <- [1..n], y <- [x+1..n]]

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

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "e1" $
    show (completo 4) `shouldBe`
    "G ND ([1,2,3,4],[(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)])"

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

module Grafo_Grafos_completos where

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

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

completo :: Int -> Grafo Int Int

completo n =

creaGrafo' ND (1,n) [(x,y) | x <- [1..n], y <- [x+1..n]]

-- Verificación

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

verifica :: IO ()

verifica = hspec spec

spec :: Spec

spec = do

it "e1" $

show (completo 4) `shouldBe`

"G ND ([1,2,3,4],[(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)])"

-- La verificación es

-- λ> verifica

-- e1

-- Finished in 0.0004 seconds

-- 1 example, 0 failures

Soluciones en Python

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

def completo(n: int) -> Grafo:
    return creaGrafo_(Orientacion.ND,
                      (1, n),
                      [(x, y)
                       for x in range(1, n + 1)
                       for y in range(x + 1, n+1)])

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

def test_completo() -> None:
    assert str(completo(4)) == \
        "G ND ([1, 2, 3, 4], [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)])"
    print("Verificado")

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

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

def completo(n: int) -> Grafo:

return creaGrafo_(Orientacion.ND,

(1, n),

[(x, y)

for x in range(1, n + 1)

for y in range(x + 1, n+1)])

# Verificación

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

def test_completo() -> None:

assert str(completo(4)) == \

"G ND ([1, 2, 3, 4], [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)])"

print("Verificado")

# La verificación es

# >>> test_completo()

# Verificado

El tipo abstracto de datos de los grafos

PorJosé A. Alonso 23-mayo-202320-mayo-2023

1. El tipo abstracto de datos de los grafos

Un grafo es una estructura que consta de un conjunto de vértices y un conjunto de aristas que conectan los vértices entre sí. Cada vértice representa una entidad o un elemento, y cada arista representa una relación o conexión entre dos vértices.

Por ejemplo,

         12
    1 -------- 2
    | \78     /|
    |  \   32/ |
    |   \   /  |
  34|     5    |55
    |   /   \  |
    |  /44   \ |
    | /     93\|
    3 -------- 4
         61

1 -------- 2

| \78 /|

| \ 32/ |

| \ / |

34| 5 |55

| / \ |

| /44 \ |

| / 93\|

3 -------- 4

representa un grafo no dirigido, lo que significa que las aristas tienen una dirección específica. Cada arista tiene un peso asociado, que puede representar una medida o una valoración de la relación entre los vértices que conecta.

El grafo consta de cinco vértices numerados del 1 al 5. Las aristas especificadas en la lista indican las conexiones entre los vértices y sus respectivos pesos. Por ejemplo, la arista (1,2,12) indica que existe una conexión entre el vértice 1 y el vértice 2 con un peso de 12.

En el grafo representado, se pueden observar las conexiones entre los vértices de la siguiente manera:

El vértice 1 está conectado con el vértice 2 (peso 12), el vértice 3 (peso 34) y el vértice 5 (peso 78).
El vértice 2 está conectado con el vértice 4 (peso 55) y el vértice 5 (peso 32).
El vértice 3 está conectado con el vértice 4 (peso 61) y el vértice 5 (peso 44).
El vértice 4 está conectado con el vértice 5 (peso 93).

Las operaciones del tipo abstracto de datos (TAD) de los grafos son

   creaGrafo  :: (Ix v, Num p, Ord v, Ord p) =>
                  Orientacion -> (v,v) -> [(v,v,p)] -> Grafo v p
   creaGrafo' :: (Ix v, Num p, Ord v, Ord p) =>
                  Orientacion -> (v,v) -> [(v,v)] -> Grafo v p
   dirigido   :: (Ix v,Num p) => (Grafo v p) -> Bool
   adyacentes :: (Ix v,Num p) => (Grafo v p) -> v -> [v]
   nodos      :: (Ix v,Num p) => (Grafo v p) -> [v]
   aristas    :: (Ix v,Num p) => (Grafo v p) -> [(v,v,p)]
   aristaEn   :: (Ix v,Num p) => (Grafo v p) -> (v,v) -> Bool
   peso       :: (Ix v,Num p) => v -> v -> (Grafo v p) -> p

creaGrafo :: (Ix v, Num p, Ord v, Ord p) =>

Orientacion -> (v,v) -> [(v,v,p)] -> Grafo v p

creaGrafo' :: (Ix v, Num p, Ord v, Ord p) =>

Orientacion -> (v,v) -> [(v,v)] -> Grafo v p

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

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

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

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

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

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

tales que
+ creaGrafo o cs as es un grafo (dirigido o no, según el de o), con el par de cotas cs y listas de aristas as (cada arista es un trío formado por los dos vértices y su peso).
+ creaGrafo' es la versión de creaGrafo para los grafos sin pesos.
+ dirigido g se verifica si g es dirigido.
+ nodos g es la lista de todos los nodos del grafo g.
+ aristas g es la lista de las aristas del grafo g.
+ adyacentes g v es la lista de los vértices adyacentes al nodo v en el grafo g.
+ aristaEn g a se verifica si a es una arista del grafo g.
+ peso v1 v2 g es el peso de la arista que une los vértices v1 y v2 en el grafo g.

Usando el TAD de los grafos, el grafo anterior se puede definir por

   creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78),
                       (2,4,55),(2,5,32),
                       (3,4,61),(3,5,44),
                       (4,5,93)]

creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78),

(2,4,55),(2,5,32),

(3,4,61),(3,5,44),

(4,5,93)]

con los siguientes argumentos:

ND: Es un parámetro de tipo Orientacion que indica si el es dirigido o no. En este caso, se utiliza ND, lo que significa «no dirigido». Por lo tanto, el grafo creado será no dirigido, lo que implica que las aristas no tienen una dirección específica.
(1,5): Es el par de cotas que define los vértices del grafo. En este caso, el grafo tiene vértices numerados desde 1 hasta 5.
[(1,2,12),(1,3,34),(1,5,78),(2,4,55),(2,5,32),(3,4,61),(3,5,44),(4,5,93)]: Es una lista de aristas, donde cada arista está representada por un trío de valores. Cada trío contiene los dos vértices que están conectados por la arista y el peso de dicha arista.

Para usar el TAD hay que usar una implementación concreta. En principio, consideraremos las siguientes:
+ mediante lista de adyacencia,
+ mediante vector de adyacencia y
+ mediante matriz de adyacencia.

Hay que elegir la que se desee utilizar, descomentándola y comentando las otras.

2. Los grafos en Haskell

2.1. El tipo abstracto de datos de los grafos en Haskell

El TAD de los grafos se encuentra en el módulo Grafo.hs cuyo contenido es el siguiente:

module TAD.Grafo
  (Orientacion (..),
   Grafo,
   creaGrafo,
   creaGrafo',
   dirigido,
   adyacentes,
   nodos,
   aristas,
   aristaEn,
   peso
  ) where

import TAD.GrafoConListaDeAdyacencia
-- import TAD.GrafoConVectorDeAdyacencia
-- import TAD.GrafoConMatrizDeAdyacencia

module TAD.Grafo

(Orientacion (..),

Grafo,

creaGrafo,

creaGrafo',

dirigido,

adyacentes,

nodos,

aristas,

aristaEn,

peso

) where

import TAD.GrafoConListaDeAdyacencia

-- import TAD.GrafoConVectorDeAdyacencia

-- import TAD.GrafoConMatrizDeAdyacencia

2.2. Implementación de los grafos mediante listas de adyacencia

La implementación se encuentra en el módulo GrafoConListaDeAdyacencia cuyo contenido es el siguiente:

{-# LANGUAGE FlexibleInstances #-}

module TAD.GrafoConListaDeAdyacencia
    (Orientacion (..),
     Grafo,
     creaGrafo,
     creaGrafo',
     dirigido,
     adyacentes,
     nodos,
     aristas,
     aristaEn,
     peso
    ) where

-- Librerías auxiliares                                               --
import Data.Array
import Data.List

-- Orientacion es D (dirigida) ó ND (no dirigida).
data Orientacion = D | ND
  deriving (Eq, Show)

-- (Grafo v p) es un grafo con vértices de tipo v y pesos de tipo p.
data Grafo v p = G Orientacion ([v],[((v,v),p)])
  deriving Eq

-- (escribeGrafo g) es la cadena correspondiente al grafo g. Por
-- ejemplo,
--    λ> escribeGrafo (creaGrafo ND (1,3) [(1,2,0),(2,3,5),(2,2,0)])
--    "G ND ([1,2,3],[((1,2),0),((2,2),0),((2,3),5)])"
--    λ> escribeGrafo (creaGrafo D (1,3) [(1,2,0),(2,3,5),(2,2,0)])
--    "G D ([1,2,3],[((1,2),0),((2,2),0),((2,3),5)])"
--    λ> escribeGrafo (creaGrafo ND (1,3) [(1,2,0),(2,3,0),(2,2,0)])
--    "G ND ([1,2,3],[(1,2),(2,2),(2,3)])"
--    λ> escribeGrafo (creaGrafo D (1,3) [(1,2,0),(2,3,0),(2,2,0)])
--    "G D ([1,2,3],[(1,2),(2,2),(2,3)])"
--    λ> escribeGrafo (creaGrafo D (1,3) [(1,2,0),(3,2,0),(2,2,0)])
--    "G D ([1,2,3],[(1,2),(2,2),(3,2)])"
--    λ> escribeGrafo (creaGrafo ND (1,3) [(1,2,0),(3,2,0),(2,2,0)])
--    "G ND ([1,2,3],[(1,2),(2,2),(2,3)])"
escribeGrafo :: (Ix v,Num p,Eq p,Show v,Show p) => Grafo v p -> String
escribeGrafo (G o (vs,as)) =
  "G " ++ show o ++ " (" ++ show vs ++ "," ++ escribeAristas ++ ")"
  where
    aristasReducidas
      | o == D    = as
      | otherwise = [((x,y),p) | ((x,y),p) <- as, x <= y]
    escribeAristas
      | ponderado = show aristasReducidas
      | otherwise = show [a | (a,_) <- aristasReducidas]
    ponderado = any (\((_,_),p) -> p /= 0) as

-- Procedimiento de escritura de grafos
instance (Ix v,Num p,Eq p,Show v,Show p) => Show (Grafo v p) where
  show = escribeGrafo

-- (creaGrafo o cs as) es un grafo (dirigido o no, según el valor de o),
-- con el par de cotas cs y listas de aristas as (cada arista es un trío
-- formado por los dos vértices y su peso). Por ejemplo,
--    λ> creaGrafo ND (1,3) [(1,2,12),(1,3,34)]
--    G ND ([1,2,3],[((1,2),12),((1,3),34),((2,1),12),((3,1),34)])
--    λ> creaGrafo D (1,3) [(1,2,12),(1,3,34)]
--    G D ([1,2,3],[((1,2),12),((1,3),34)])
--    λ> creaGrafo D (1,4) [(1,2,12),(1,3,34)]
--    G D ([1,2,3,4],[((1,2),12),((1,3),34)])
creaGrafo :: (Ix v, Num p, Ord v, Ord p) =>
             Orientacion -> (v,v) -> [(v,v,p)] -> Grafo v p
creaGrafo o cs as =
  G o (range cs,
       sort ([((x1,x2),p) | (x1,x2,p) <- as] ++
             if o == D then []
             else [((x2,x1),p) | (x1,x2,p) <- as, x1 /= x2]))

-- (creaGrafo' o cs as) es un grafo (dirigido o no, según el valor de o),
-- con el par de cotas cs y listas de aristas as (cada arista es un par
-- de vértices y se supone que su peso es 0). Por ejemplo,
--    λ> creaGrafo' ND (1,3) [(2,1),(1,3)]
--    G ND ([1,2,3],[(1,2),(1,3)])
--    λ> creaGrafo' D (1,3) [(2,1),(1,3)]
--    G D ([1,2,3],[(1,3),(2,1)])
creaGrafo' :: (Ix v, Num p, Ord v, Ord p) =>
              Orientacion -> (v,v) -> [(v,v)] -> Grafo v p
creaGrafo' o cs as =
  creaGrafo o cs [(v1,v2,0) | (v1,v2) <- as]

-- ejGrafoND es el grafo
--             12
--        1 -------- 2
--        | \78     /|
--        |  \   32/ |
--        |   \   /  |
--      34|     5    |55
--        |   /   \  |
--        |  /44   \ |
--        | /     93\|
--        3 -------- 4
--             61
-- Se define por
ejGrafoND :: Grafo Int Int
ejGrafoND = creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78),
                                (2,4,55),(2,5,32),
                                (3,4,61),(3,5,44),
                                (4,5,93)]

ejGrafoD :: Grafo Int Int
ejGrafoD = creaGrafo D (1,5) [(1,2,12),(1,3,34),(1,5,78),
                              (2,4,55),(2,5,32),
                              (3,4,61),(3,5,44),
                              (4,5,93)]

-- (dirigido g) se verifica si g es dirigido. Por ejemplo,
--    dirigido ejGrafoD   ==  True
--    dirigido ejGrafoND  ==  False
dirigido :: (Ix v,Num p) => Grafo v p -> Bool
dirigido (G o _) = o == D

-- (nodos g) es la lista de todos los nodos del grafo g. Por ejemplo,
--    nodos ejGrafoND  ==  [1,2,3,4,5]
--    nodos ejGrafoD   ==  [1,2,3,4,5]
nodos :: (Ix v,Num p) => Grafo v p -> [v]
nodos (G _ (ns,_)) = ns

-- (adyacentes g v) es la lista de los vértices adyacentes al nodo v en
-- el grafo g. Por ejemplo,
--    adyacentes ejGrafoND 4  ==  [2,3,5]
--    adyacentes ejGrafoD  4  ==  [5]
adyacentes :: (Ix v, Num p) => Grafo v p -> v -> [v]
adyacentes (G _ (_,e)) v = nub [u | ((w,u),_) <- e, w == v]

-- (aristaEn g a) se verifica si a es una arista del grafo g. Por
-- ejemplo,
--    aristaEn ejGrafoND (5,1)  ==  True
--    aristaEn ejGrafoND (4,1)  ==  False
--    aristaEn ejGrafoD  (5,1)  ==  False
--    aristaEn ejGrafoD  (1,5)  ==  True
aristaEn :: (Ix v,Num p) => Grafo v p -> (v,v) -> Bool
aristaEn g (x,y) = y `elem` adyacentes g x

-- (peso v1 v2 g) es el peso de la arista que une los vértices v1 y v2
-- en el grafo g. Por ejemplo,
--    peso 1 5 ejGrafoND  ==  78
--    peso 1 5 ejGrafoD   ==  78
peso :: (Ix v,Num p) => v -> v -> Grafo v p -> p
peso x y (G _ (_,gs)) = head [c | ((x',y'),c) <- gs, (x,y) == (x',y')]

-- (aristas g) es la lista de las aristas del grafo g. Por ejemplo,
--    λ> aristas ejGrafoD
--    [((1,2),12),((1,3),34),((1,5),78),
--     ((2,4),55),((2,5),32),
--     ((3,4),61),((3,5),44),
--     ((4,5),93)]
--    λ> aristas ejGrafoND
--    [((1,2),12),((1,3),34),((1,5),78),
--     ((2,1),12),((2,4),55),((2,5),32),
--     ((3,1),34),((3,4),61),((3,5),44),
--     ((4,2),55),((4,3),61),((4,5),93),
--     ((5,1),78),((5,2),32),((5,3),44),((5,4),93)]
aristas :: (Ix v,Num p) => Grafo v p -> [((v,v),p)]
aristas (G _ (_,g)) = [((v1,v2),p) | ((v1,v2),p) <- g]

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

{-# LANGUAGE FlexibleInstances #-}

module TAD.GrafoConListaDeAdyacencia

(Orientacion (..),

Grafo,

creaGrafo,

creaGrafo',

dirigido,

adyacentes,

nodos,

aristas,

aristaEn,

peso

) where

-- Librerías auxiliares --

import Data.Array

import Data.List

-- Orientacion es D (dirigida) ó ND (no dirigida).

data Orientacion = D | ND

deriving (Eq, Show)

-- (Grafo v p) es un grafo con vértices de tipo v y pesos de tipo p.

data Grafo v p = G Orientacion ([v],[((v,v),p)])

deriving Eq

-- (escribeGrafo g) es la cadena correspondiente al grafo g. Por

-- ejemplo,

-- λ> escribeGrafo (creaGrafo ND (1,3) [(1,2,0),(2,3,5),(2,2,0)])

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

-- λ> escribeGrafo (creaGrafo D (1,3) [(1,2,0),(2,3,5),(2,2,0)])

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

-- λ> escribeGrafo (creaGrafo ND (1,3) [(1,2,0),(2,3,0),(2,2,0)])

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

-- λ> escribeGrafo (creaGrafo D (1,3) [(1,2,0),(2,3,0),(2,2,0)])

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

-- λ> escribeGrafo (creaGrafo D (1,3) [(1,2,0),(3,2,0),(2,2,0)])

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

-- λ> escribeGrafo (creaGrafo ND (1,3) [(1,2,0),(3,2,0),(2,2,0)])

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

escribeGrafo :: (Ix v,Num p,Eq p,Show v,Show p) => Grafo v p -> String

escribeGrafo (G o (vs,as)) =

"G " ++ show o ++ " (" ++ show vs ++ "," ++ escribeAristas ++ ")"

where

aristasReducidas

| o == D = as

| otherwise = [((x,y),p) | ((x,y),p) <- as, x <= y]

escribeAristas

| ponderado = show aristasReducidas

| otherwise = show [a | (a,_) <- aristasReducidas]

ponderado = any (\((_,_),p) -> p /= 0) as

-- Procedimiento de escritura de grafos

instance (Ix v,Num p,Eq p,Show v,Show p) => Show (Grafo v p) where

show = escribeGrafo

-- (creaGrafo o cs as) es un grafo (dirigido o no, según el valor de o),

-- con el par de cotas cs y listas de aristas as (cada arista es un trío

-- formado por los dos vértices y su peso). Por ejemplo,

-- λ> creaGrafo ND (1,3) [(1,2,12),(1,3,34)]

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

-- λ> creaGrafo D (1,3) [(1,2,12),(1,3,34)]

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

-- λ> creaGrafo D (1,4) [(1,2,12),(1,3,34)]

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

creaGrafo :: (Ix v, Num p, Ord v, Ord p) =>

Orientacion -> (v,v) -> [(v,v,p)] -> Grafo v p

creaGrafo o cs as =

G o (range cs,

sort ([((x1,x2),p) | (x1,x2,p) <- as] ++

if o == D then []

else [((x2,x1),p) | (x1,x2,p) <- as, x1 /= x2]))

-- (creaGrafo' o cs as) es un grafo (dirigido o no, según el valor de o),

-- con el par de cotas cs y listas de aristas as (cada arista es un par

-- de vértices y se supone que su peso es 0). Por ejemplo,

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

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

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

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

creaGrafo' :: (Ix v, Num p, Ord v, Ord p) =>

Orientacion -> (v,v) -> [(v,v)] -> Grafo v p

creaGrafo' o cs as =

creaGrafo o cs [(v1,v2,0) | (v1,v2) <- as]

-- ejGrafoND es el grafo

-- 12

-- 1 -------- 2

-- | \78 /|

-- | \ 32/ |

-- | \ / |

-- 34| 5 |55

-- | / \ |

-- | /44 \ |

-- | / 93\|

-- 3 -------- 4

-- 61

-- Se define por

ejGrafoND :: Grafo Int Int

ejGrafoND = creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78),

(2,4,55),(2,5,32),

(3,4,61),(3,5,44),

(4,5,93)]

ejGrafoD :: Grafo Int Int

ejGrafoD = creaGrafo D (1,5) [(1,2,12),(1,3,34),(1,5,78),

(2,4,55),(2,5,32),

(3,4,61),(3,5,44),

(4,5,93)]

-- (dirigido g) se verifica si g es dirigido. Por ejemplo,

-- dirigido ejGrafoD == True

-- dirigido ejGrafoND == False

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

dirigido (G o _) = o == D

-- (nodos g) es la lista de todos los nodos del grafo g. Por ejemplo,

-- nodos ejGrafoND == [1,2,3,4,5]

-- nodos ejGrafoD == [1,2,3,4,5]

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

nodos (G _ (ns,_)) = ns

-- (adyacentes g v) es la lista de los vértices adyacentes al nodo v en

-- el grafo g. Por ejemplo,

-- adyacentes ejGrafoND 4 == [2,3,5]

-- adyacentes ejGrafoD 4 == [5]

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

adyacentes (G _ (_,e)) v = nub [u | ((w,u),_) <- e, w == v]

-- (aristaEn g a) se verifica si a es una arista del grafo g. Por

-- ejemplo,

-- aristaEn ejGrafoND (5,1) == True

-- aristaEn ejGrafoND (4,1) == False

-- aristaEn ejGrafoD (5,1) == False

-- aristaEn ejGrafoD (1,5) == True

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

aristaEn g (x,y) = y `elem` adyacentes g x

-- (peso v1 v2 g) es el peso de la arista que une los vértices v1 y v2

-- en el grafo g. Por ejemplo,

-- peso 1 5 ejGrafoND == 78

-- peso 1 5 ejGrafoD == 78

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

peso x y (G _ (_,gs)) = head [c | ((x',y'),c) <- gs, (x,y) == (x',y')]

-- (aristas g) es la lista de las aristas del grafo g. Por ejemplo,

-- λ> aristas ejGrafoD

-- [((1,2),12),((1,3),34),((1,5),78),

-- ((2,4),55),((2,5),32),

-- ((3,4),61),((3,5),44),

-- ((4,5),93)]

-- λ> aristas ejGrafoND

-- [((1,2),12),((1,3),34),((1,5),78),

-- ((2,1),12),((2,4),55),((2,5),32),

-- ((3,1),34),((3,4),61),((3,5),44),

-- ((4,2),55),((4,3),61),((4,5),93),

-- ((5,1),78),((5,2),32),((5,3),44),((5,4),93)]

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

aristas (G _ (_,g)) = [((v1,v2),p) | ((v1,v2),p) <- g]

2.3. Implementación de los grafos mediante vectores de adyacencia

La implementación se encuentra en el módulo GrafoConVectorDeAdyacencia cuyo contenido es el siguiente:

{-# LANGUAGE FlexibleInstances #-}

module TAD.GrafoConVectorDeAdyacencia
  (Orientacion (..),
   Grafo,
   creaGrafo,
   creaGrafo',
   dirigido,
   adyacentes,
   nodos,
   aristas,
   aristaEn,
   peso
  ) where

-- Librerías auxiliares
import Data.Array (Array, Ix, accumArray, indices, (!))
import Data.List (sort)
import Test.QuickCheck

-- Orientacion es D (dirigida) ó ND (no dirigida).
data Orientacion = D | ND
  deriving (Eq, Show)

-- (Grafo v p) es un grafo con vértices de tipo v y pesos de tipo p.
data Grafo v p = G Orientacion (Array v [(v,p)])
  deriving Eq

-- (escribeGrafo g) es la cadena correspondiente al grafo g. Por
-- ejemplo,
--    λ> escribeGrafo (creaGrafo ND (1,3) [(1,2,0),(2,3,5),(2,2,0)])
--    "G ND ([1,2,3],[((1,2),0),((2,2),0),((2,3),5)])"
--    λ> escribeGrafo (creaGrafo D (1,3) [(1,2,0),(2,3,5),(2,2,0)])
--    "G D ([1,2,3],[((1,2),0),((2,2),0),((2,3),5)])"
--    λ> escribeGrafo (creaGrafo ND (1,3) [(1,2,0),(2,3,0),(2,2,0)])
--    "G ND ([1,2,3],[(1,2),(2,2),(2,3)])"
--    λ> escribeGrafo (creaGrafo D (1,3) [(1,2,0),(2,3,0),(2,2,0)])
--    "G D ([1,2,3],[(1,2),(2,2),(2,3)])"
--    λ> escribeGrafo (creaGrafo D (1,3) [(1,2,0),(3,2,0),(2,2,0)])
--    "G D ([1,2,3],[(1,2),(2,2),(3,2)])"
--    λ> escribeGrafo (creaGrafo ND (1,3) [(1,2,0),(3,2,0),(2,2,0)])
--    "G ND ([1,2,3],[(1,2),(2,2),(2,3)])"
escribeGrafo :: (Ix v,Num p,Ord v, Ord p,Show v,Show p) => Grafo v p -> String
escribeGrafo g@(G o _) =
  "G " ++ show o ++ " (" ++ show vs ++ "," ++ escribeAristas ++ ")"
  where
    as = sort (aristas g)
    vs = nodos g
    aristasReducidas
      | o == D    = as
      | otherwise = [((x,y),p) | ((x,y),p) <- as, x <= y]
    escribeAristas
      | ponderado = show aristasReducidas
      | otherwise = show [a | (a,_) <- aristasReducidas]
    ponderado = any (\((_,_),p) -> p /= 0) as

-- Procedimiento de escritura de grafos
instance (Ix v,Num p,Ord v, Ord p,Show v,Show p) => Show (Grafo v p) where
  show = escribeGrafo

-- (creaGrafo o cs as) es un grafo (dirigido o no, según el valor de o),
-- con el par de cotas cs y listas de aristas as (cada arista es un trío
-- formado por los dos vértices y su peso). Ver el ejemplo a continuación.
creaGrafo :: (Ix v, Num p) => Orientacion -> (v,v) -> [(v,v,p)] -> Grafo v p
creaGrafo o cs vs =
  G o (accumArray (\xs x -> xs++[x]) [] cs
                  ((if o == D then []
                    else [(x2,(x1,p))|(x1,x2,p) <- vs, x1 /= x2]) ++
                   [(x1,(x2,p)) | (x1,x2,p) <- vs]))

-- (creaGrafo' o cs as) es un grafo (dirigido o no, según el valor de o),
-- con el par de cotas cs y listas de aristas as (cada arista es un par
-- de vértices y se supone que su peso es 0). Por ejemplo,
--    λ> creaGrafo' ND (1,3) [(2,1),(1,3)]
--    G ND ([1,2,3],[(1,2),(1,3)])
--    λ> creaGrafo' D (1,3) [(2,1),(1,3)]
--    G D ([1,2,3],[(1,3),(2,1)])
creaGrafo' :: (Ix v, Num p, Ord v, Ord p) =>
              Orientacion -> (v,v) -> [(v,v)] -> Grafo v p
creaGrafo' o cs as =
  creaGrafo o cs [(v1,v2,0) | (v1,v2) <- as]

-- ejGrafoND es el grafo
--             12
--        1 -------- 2
--        | \78     /|
--        |  \   32/ |
--        |   \   /  |
--      34|     5    |55
--        |   /   \  |
--        |  /44   \ |
--        | /     93\|
--        3 -------- 4
--             61
-- representado mediante un vector de adyacencia; es decir,
--    λ> ejGrafoND
--    G ND ([1,2,3,4,5],
--          [((1,2),12),((1,3),34),((1,5),78),
--           ((2,4),55),((2,5),32),
--           ((3,4),61),((3,5),44),
--           ((4,5),93)])
ejGrafoND :: Grafo Int Int
ejGrafoND = creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78),
                                (2,4,55),(2,5,32),
                                (3,4,61),(3,5,44),
                                (4,5,93)]

-- ejGrafoD es el mismo grafo que ejGrafoND pero orientando las aristas;
-- es decir,
--    λ> ejGrafoD
--    G D ([1,2,3,4,5],
--         [((1,2),12),((1,3),34),((1,5),78),
--          ((2,4),55),((2,5),32),
--          ((3,4),61),((3,5),44),
--          ((4,5),93)])
ejGrafoD :: Grafo Int Int
ejGrafoD = creaGrafo D (1,5) [(1,2,12),(1,3,34),(1,5,78),
                              (2,4,55),(2,5,32),
                              (3,4,61),(3,5,44),
                              (4,5,93)]

-- (dirigido g) se verifica si g es dirigido. Por ejemplo,
--    dirigido ejGrafoD   ==  True
--    dirigido ejGrafoND  ==  False
dirigido :: (Ix v,Num p) => Grafo v p -> Bool
dirigido (G o _) = o == D

-- (nodos g) es la lista de todos los nodos del grafo g. Por ejemplo,
--    nodos ejGrafoND  ==  [1,2,3,4,5]
--    nodos ejGrafoD   ==  [1,2,3,4,5]
nodos :: (Ix v,Num p) => Grafo v p -> [v]
nodos (G _ g) = indices g

-- (adyacentes g v) es la lista de los vértices adyacentes al nodo v en
-- el grafo g. Por ejemplo,
--    adyacentes ejGrafoND 4  ==  [2,3,5]
--    adyacentes ejGrafoD  4  ==  [5]
adyacentes :: (Ix v,Num p) => Grafo v p -> v -> [v]
adyacentes (G _ g) v = map fst (g!v)

-- (aristaEn g a) se verifica si a es una arista del grafo g. Por
-- ejemplo,
--    aristaEn ejGrafoND (5,1)  ==  True
--    aristaEn ejGrafoND (4,1)  ==  False
--    aristaEn ejGrafoD (5,1)   ==  False
--    aristaEn ejGrafoD (1,5)   ==  True
aristaEn :: (Ix v,Num p) => Grafo v p -> (v,v) -> Bool
aristaEn g (x,y) = y `elem` adyacentes g x

-- (peso v1 v2 g) es el peso de la arista que une los vértices v1 y v2
-- en el grafo g. Por ejemplo,
--    peso 1 5 ejGrafoND  ==  78
--    peso 1 5 ejGrafoD   ==  78
peso :: (Ix v,Num p) => v -> v -> Grafo v p -> p
peso x y (G _ g) = head [c | (a,c) <- g!x , a == y]

-- (aristas g) es la lista de las aristas del grafo g. Por ejemplo,
--    λ> aristas ejGrafoD
--    [((1,2),12),((1,3),34),((1,5),78),
--     ((2,4),55),((2,5),32),
--     ((3,4),61),((3,5),44),
--     ((4,5),93)]
--    λ> aristas ejGrafoND
--    [((1,2),12),((1,3),34),((1,5),78),
--     ((2,1),12),((2,4),55),((2,5),32),
--     ((3,1),34),((3,4),61),((3,5),44),
--     ((4,2),55),((4,3),61),((4,5),93),
--     ((5,1),78),((5,2),32),((5,3),44),((5,4),93)]
aristas :: (Ix v,Num p) => Grafo v p -> [((v,v),p)]
aristas (G o g) = [((v1,v2),w) | v1 <- nodos (G o g) , (v2,w) <- g!v1]

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

{-# LANGUAGE FlexibleInstances #-}

module TAD.GrafoConVectorDeAdyacencia

(Orientacion (..),

Grafo,

creaGrafo,

creaGrafo',

dirigido,

adyacentes,

nodos,

aristas,

aristaEn,

peso

) where

-- Librerías auxiliares

import Data.Array (Array, Ix, accumArray, indices, (!))

import Data.List (sort)

import Test.QuickCheck

-- Orientacion es D (dirigida) ó ND (no dirigida).

data Orientacion = D | ND

deriving (Eq, Show)

-- (Grafo v p) es un grafo con vértices de tipo v y pesos de tipo p.

data Grafo v p = G Orientacion (Array v [(v,p)])

deriving Eq

-- (escribeGrafo g) es la cadena correspondiente al grafo g. Por

-- ejemplo,

-- λ> escribeGrafo (creaGrafo ND (1,3) [(1,2,0),(2,3,5),(2,2,0)])

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

-- λ> escribeGrafo (creaGrafo D (1,3) [(1,2,0),(2,3,5),(2,2,0)])

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

-- λ> escribeGrafo (creaGrafo ND (1,3) [(1,2,0),(2,3,0),(2,2,0)])

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

-- λ> escribeGrafo (creaGrafo D (1,3) [(1,2,0),(2,3,0),(2,2,0)])

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

-- λ> escribeGrafo (creaGrafo D (1,3) [(1,2,0),(3,2,0),(2,2,0)])

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

-- λ> escribeGrafo (creaGrafo ND (1,3) [(1,2,0),(3,2,0),(2,2,0)])

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

escribeGrafo :: (Ix v,Num p,Ord v, Ord p,Show v,Show p) => Grafo v p -> String

escribeGrafo g@(G o _) =

"G " ++ show o ++ " (" ++ show vs ++ "," ++ escribeAristas ++ ")"

where

as = sort (aristas g)

vs = nodos g

aristasReducidas

| o == D = as

| otherwise = [((x,y),p) | ((x,y),p) <- as, x <= y]

escribeAristas

| ponderado = show aristasReducidas

| otherwise = show [a | (a,_) <- aristasReducidas]

ponderado = any (\((_,_),p) -> p /= 0) as

-- Procedimiento de escritura de grafos

instance (Ix v,Num p,Ord v, Ord p,Show v,Show p) => Show (Grafo v p) where

show = escribeGrafo

-- (creaGrafo o cs as) es un grafo (dirigido o no, según el valor de o),

-- con el par de cotas cs y listas de aristas as (cada arista es un trío

-- formado por los dos vértices y su peso). Ver el ejemplo a continuación.

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

creaGrafo o cs vs =

G o (accumArray (\xs x -> xs++[x]) [] cs

((if o == D then []

else [(x2,(x1,p))|(x1,x2,p) <- vs, x1 /= x2]) ++

[(x1,(x2,p)) | (x1,x2,p) <- vs]))

-- (creaGrafo' o cs as) es un grafo (dirigido o no, según el valor de o),

-- con el par de cotas cs y listas de aristas as (cada arista es un par

-- de vértices y se supone que su peso es 0). Por ejemplo,

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

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

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

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

creaGrafo' :: (Ix v, Num p, Ord v, Ord p) =>

Orientacion -> (v,v) -> [(v,v)] -> Grafo v p

creaGrafo' o cs as =

creaGrafo o cs [(v1,v2,0) | (v1,v2) <- as]

-- ejGrafoND es el grafo

-- 12

-- 1 -------- 2

-- | \78 /|

-- | \ 32/ |

-- | \ / |

-- 34| 5 |55

-- | / \ |

-- | /44 \ |

-- | / 93\|

-- 3 -------- 4

-- 61

-- representado mediante un vector de adyacencia; es decir,

-- λ> ejGrafoND

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

-- [((1,2),12),((1,3),34),((1,5),78),

-- ((2,4),55),((2,5),32),

-- ((3,4),61),((3,5),44),

-- ((4,5),93)])

ejGrafoND :: Grafo Int Int

ejGrafoND = creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78),

(2,4,55),(2,5,32),

(3,4,61),(3,5,44),

(4,5,93)]

-- ejGrafoD es el mismo grafo que ejGrafoND pero orientando las aristas;

-- es decir,

-- λ> ejGrafoD

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

-- [((1,2),12),((1,3),34),((1,5),78),

-- ((2,4),55),((2,5),32),

-- ((3,4),61),((3,5),44),

-- ((4,5),93)])

ejGrafoD :: Grafo Int Int

ejGrafoD = creaGrafo D (1,5) [(1,2,12),(1,3,34),(1,5,78),

(2,4,55),(2,5,32),

(3,4,61),(3,5,44),

(4,5,93)]

-- (dirigido g) se verifica si g es dirigido. Por ejemplo,

-- dirigido ejGrafoD == True

-- dirigido ejGrafoND == False

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

dirigido (G o _) = o == D

-- (nodos g) es la lista de todos los nodos del grafo g. Por ejemplo,

-- nodos ejGrafoND == [1,2,3,4,5]

-- nodos ejGrafoD == [1,2,3,4,5]

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

nodos (G _ g) = indices g

-- (adyacentes g v) es la lista de los vértices adyacentes al nodo v en

-- el grafo g. Por ejemplo,

-- adyacentes ejGrafoND 4 == [2,3,5]

-- adyacentes ejGrafoD 4 == [5]

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

adyacentes (G _ g) v = map fst (g!v)

-- (aristaEn g a) se verifica si a es una arista del grafo g. Por

-- ejemplo,

-- aristaEn ejGrafoND (5,1) == True

-- aristaEn ejGrafoND (4,1) == False

-- aristaEn ejGrafoD (5,1) == False

-- aristaEn ejGrafoD (1,5) == True

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

aristaEn g (x,y) = y `elem` adyacentes g x

-- (peso v1 v2 g) es el peso de la arista que une los vértices v1 y v2

-- en el grafo g. Por ejemplo,

-- peso 1 5 ejGrafoND == 78

-- peso 1 5 ejGrafoD == 78

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

peso x y (G _ g) = head [c | (a,c) <- g!x , a == y]

-- (aristas g) es la lista de las aristas del grafo g. Por ejemplo,

-- λ> aristas ejGrafoD

-- [((1,2),12),((1,3),34),((1,5),78),

-- ((2,4),55),((2,5),32),

-- ((3,4),61),((3,5),44),

-- ((4,5),93)]

-- λ> aristas ejGrafoND

-- [((1,2),12),((1,3),34),((1,5),78),

-- ((2,1),12),((2,4),55),((2,5),32),

-- ((3,1),34),((3,4),61),((3,5),44),

-- ((4,2),55),((4,3),61),((4,5),93),

-- ((5,1),78),((5,2),32),((5,3),44),((5,4),93)]

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

aristas (G o g) = [((v1,v2),w) | v1 <- nodos (G o g) , (v2,w) <- g!v1]

2.3. Implementación de los grafos mediante vectores de adyacencia

La implementación se encuentra en el módulo GrafoConMatrizDeAdyacencia cuyo contenido es el siguiente:

{-# LANGUAGE FlexibleInstances #-}

module TAD.GrafoConMatrizDeAdyacencia
  (Orientacion (..),
   Grafo,
   creaGrafo,
   creaGrafo',
   dirigido,
   adyacentes,
   nodos,
   aristas,
   aristaEn,
   peso
  ) where

-- Librerías auxiliares                                               --
import Data.Array
import Data.Maybe (isJust)
import Data.List (sort)
import Test.QuickCheck

-- Orientacion es D (dirigida) ó ND (no dirigida).
data Orientacion = D | ND
  deriving (Eq, Show)

-- (Grafo v p) es un grafo con vértices de tipo v y pesos de tipo p.
data Grafo v p = G Orientacion (Array (v,v) (Maybe p))
  deriving Eq

-- (escribeGrafo g) es la cadena correspondiente al grafo g. Por
-- ejemplo,
--    λ> escribeGrafo (creaGrafo ND (1,3) [(1,2,0),(2,3,5),(2,2,0)])
--    "G ND ([1,2,3],[((1,2),0),((2,2),0),((2,3),5)])"
--    λ> escribeGrafo (creaGrafo D (1,3) [(1,2,0),(2,3,5),(2,2,0)])
--    "G D ([1,2,3],[((1,2),0),((2,2),0),((2,3),5)])"
--    λ> escribeGrafo (creaGrafo ND (1,3) [(1,2,0),(2,3,0),(2,2,0)])
--    "G ND ([1,2,3],[(1,2),(2,2),(2,3)])"
--    λ> escribeGrafo (creaGrafo D (1,3) [(1,2,0),(2,3,0),(2,2,0)])
--    "G D ([1,2,3],[(1,2),(2,2),(2,3)])"
--    λ> escribeGrafo (creaGrafo D (1,3) [(1,2,0),(3,2,0),(2,2,0)])
--    "G D ([1,2,3],[(1,2),(2,2),(3,2)])"
--    λ> escribeGrafo (creaGrafo ND (1,3) [(1,2,0),(3,2,0),(2,2,0)])
--    "G ND ([1,2,3],[(1,2),(2,2),(2,3)])"
escribeGrafo :: (Ix v,Num p,Ord v, Ord p,Show v,Show p) => Grafo v p -> String
escribeGrafo g@(G o _) =
  "G " ++ show o ++ " (" ++ show vs ++ "," ++ escribeAristas ++ ")"
  where
    as = sort (aristas g)
    vs = nodos g
    aristasReducidas
      | o == D    = as
      | otherwise = [((x,y),p) | ((x,y),p) <- as, x <= y]
    escribeAristas
      | ponderado = show aristasReducidas
      | otherwise = show [a | (a,_) <- aristasReducidas]
    ponderado = any (\((_,_),p) -> p /= 0) as

-- Procedimiento de escritura de grafos
instance (Ix v,Num p,Ord v, Ord p,Show v,Show p) => Show (Grafo v p) where
  show = escribeGrafo

-- (creaGrafo d cs as) es un grafo (dirigido o no, según el valor de o),
-- con el par de cotas cs y listas de aristas as (cada arista es un trío
-- formado por los dos vértices y su peso). Ver el ejemplo a continuación.
creaGrafo :: (Ix v,Num p) => Orientacion -> (v,v) -> [(v,v,p)] -> Grafo v p
creaGrafo D cs as =
  G D (matrizVacia cs // [((v1,v2),Just c) | (v1,v2,c) <- as])
creaGrafo ND cs as =
  G ND (matrizVacia cs // ([((v1,v2),Just c) | (v1,v2,c) <- as] ++
                           [((v2,v1),Just c) | (v1,v2,c) <- as, v1 /= v2]))

matrizVacia :: Ix v => (v,v) -> Array (v,v) (Maybe p)
matrizVacia (l,u) =
  listArray ((l,l),(u,u)) (repeat Nothing)

-- (creaGrafo' o cs as) es un grafo (dirigido o no, según el valor de o),
-- con el par de cotas cs y listas de aristas as (cada arista es un par
-- de vértices y se supone que su peso es 0). Por ejemplo,
--    λ> creaGrafo' ND (1,3) [(2,1),(1,3)]
--    G ND ([1,2,3],[(1,2),(1,3)])
--    λ> creaGrafo' D (1,3) [(2,1),(1,3)]
--    G D ([1,2,3],[(1,3),(2,1)])
creaGrafo' :: (Ix v, Num p, Ord v, Ord p) =>
              Orientacion -> (v,v) -> [(v,v)] -> Grafo v p
creaGrafo' o cs as =
  creaGrafo o cs [(v1,v2,0) | (v1,v2) <- as]

-- ejGrafoND es el grafo
--             12
--        1 -------- 2
--        | \78     /|
--        |  \   32/ |
--        |   \   /  |
--      34|     5    |55
--        |   /   \  |
--        |  /44   \ |
--        | /     93\|
--        3 -------- 4
--             61
-- representado mediante una matriz de adyacencia.
--    λ> ejGrafoND
--    G ND array ((1,1),(5,5))
--               [((1,1),Nothing),((1,2),Just 12),((1,3),Just 34),
--                ((1,4),Nothing),((1,5),Just 78),((2,1),Just 12),
--                ((2,2),Nothing),((2,3),Nothing),((2,4),Just 55),
--                ((2,5),Just 32),((3,1),Just 34),((3,2),Nothing),
--                ((3,3),Nothing),((3,4),Just 61),((3,5),Just 44),
--                ((4,1),Nothing),((4,2),Just 55),((4,3),Just 61),
--                ((4,4),Nothing),((4,5),Just 93),((5,1),Just 78),
--                ((5,2),Just 32),((5,3),Just 44),((5,4),Just 93),
--                ((5,5),Nothing)]
ejGrafoND :: Grafo Int Int
ejGrafoND = creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78),
                                (2,4,55),(2,5,32),
                                (3,4,61),(3,5,44),
                                (4,5,93)]

-- ejGrafoD es el mismo grafo que ejGrafoND pero orientando las aristas;
-- es decir,
--    λ> ejGrafoD
--    G D (array ((1,1),(5,5))
--               [((1,1),Nothing),((1,2),Just 12),((1,3),Just 34),
--                ((1,4),Nothing),((1,5),Just 78),((2,1),Nothing),
--                ((2,2),Nothing),((2,3),Nothing),((2,4),Just 55),
--                ((2,5),Just 32),((3,1),Nothing),((3,2),Nothing),
--                ((3,3),Nothing),((3,4),Just 61),((3,5),Just 44),
--                ((4,1),Nothing),((4,2),Nothing),((4,3),Nothing),
--                ((4,4),Nothing),((4,5),Just 93),((5,1),Nothing),
--                ((5,2),Nothing),((5,3),Nothing),((5,4),Nothing),
--                ((5,5),Nothing)])
ejGrafoD :: Grafo Int Int
ejGrafoD = creaGrafo D (1,5) [(1,2,12),(1,3,34),(1,5,78),
                              (2,4,55),(2,5,32),
                              (3,4,61),(3,5,44),
                              (4,5,93)]

-- (dirigido g) se verifica si g es dirigido. Por ejemplo,
--    dirigido ejGrafoD   ==  True
--    dirigido ejGrafoND  ==  False
dirigido :: (Ix v,Num p) => Grafo v p -> Bool
dirigido (G o _) = o == D

-- (nodos g) es la lista de todos los nodos del grafo g. Por ejemplo,
--    nodos ejGrafoND  ==  [1,2,3,4,5]
--    nodos ejGrafoD   ==  [1,2,3,4,5]
nodos :: (Ix v,Num p) => Grafo v p -> [v]
nodos (G _ g) = range (l,u)
  where ((l,_),(u,_)) = bounds g

-- (adyacentes g v) es la lista de los vértices adyacentes al nodo v en
-- el grafo g. Por ejemplo,
--    adyacentes ejGrafoND 4  ==  [2,3,5]
--    adyacentes ejGrafoD  4  ==  [5]
adyacentes :: (Ix v,Num p,Eq p) => Grafo v p -> v -> [v]
adyacentes (G o g) v =
  [v' | v' <- nodos (G o g), isJust (g!(v,v'))]

-- (aristaEn g a) se verifica si a es una arista del grafo g. Por
-- ejemplo,
--    aristaEn ejGrafoND (5,1)  ==  True
--    aristaEn ejGrafoND (4,1)  ==  False
aristaEn :: (Ix v,Num p,Eq p) => Grafo v p -> (v,v) -> Bool
aristaEn (G _o g) (x,y) = isJust (g!(x,y))

-- (peso v1 v2 g) es el peso de la arista que une los vértices v1 y v2
-- en el grafo g. Por ejemplo,
--    peso 1 5 ejGrafoND  ==  78
--    peso 1 5 ejGrafoD   ==  78
peso :: (Ix v,Num p) => v -> v -> Grafo v p -> p
peso x y (G _ g)  = w where (Just w) = g!(x,y)

-- (aristas g) es la lista de las aristas del grafo g. Por ejemplo,
--    λ> aristas ejGrafoD
--    [(1,2,12),(1,3,34),(1,5,78),(2,4,55),(2,5,32),(3,4,61),
--     (3,5,44),(4,5,93)]
--    λ> aristas ejGrafoND
--    [(1,2,12),(1,3,34),(1,5,78),(2,1,12),(2,4,55),(2,5,32),
--     (3,1,34),(3,4,61),(3,5,44),(4,2,55),(4,3,61),(4,5,93),
--     (5,1,78),(5,2,32),(5,3,44),(5,4,93)]
aristas :: (Ix v,Num p, Eq p) => Grafo v p -> [((v,v),p)]
aristas g@(G _ e) = [((v1,v2),extrae(e!(v1,v2)))
                     | v1 <- nodos g,
                       v2 <- nodos g,
                       aristaEn g (v1,v2)]
  where extrae (Just w) = w
        extrae _        = error "Imposible"

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

{-# LANGUAGE FlexibleInstances #-}

module TAD.GrafoConMatrizDeAdyacencia

(Orientacion (..),

Grafo,

creaGrafo,

creaGrafo',

dirigido,

adyacentes,

nodos,

aristas,

aristaEn,

peso

) where

-- Librerías auxiliares --

import Data.Array

import Data.Maybe (isJust)

import Data.List (sort)

import Test.QuickCheck

-- Orientacion es D (dirigida) ó ND (no dirigida).

data Orientacion = D | ND

deriving (Eq, Show)

-- (Grafo v p) es un grafo con vértices de tipo v y pesos de tipo p.

data Grafo v p = G Orientacion (Array (v,v) (Maybe p))

deriving Eq

-- (escribeGrafo g) es la cadena correspondiente al grafo g. Por

-- ejemplo,

-- λ> escribeGrafo (creaGrafo ND (1,3) [(1,2,0),(2,3,5),(2,2,0)])

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

-- λ> escribeGrafo (creaGrafo D (1,3) [(1,2,0),(2,3,5),(2,2,0)])

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

-- λ> escribeGrafo (creaGrafo ND (1,3) [(1,2,0),(2,3,0),(2,2,0)])

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

-- λ> escribeGrafo (creaGrafo D (1,3) [(1,2,0),(2,3,0),(2,2,0)])

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

-- λ> escribeGrafo (creaGrafo D (1,3) [(1,2,0),(3,2,0),(2,2,0)])

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

-- λ> escribeGrafo (creaGrafo ND (1,3) [(1,2,0),(3,2,0),(2,2,0)])

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

escribeGrafo :: (Ix v,Num p,Ord v, Ord p,Show v,Show p) => Grafo v p -> String

escribeGrafo g@(G o _) =

"G " ++ show o ++ " (" ++ show vs ++ "," ++ escribeAristas ++ ")"

where

as = sort (aristas g)

vs = nodos g

aristasReducidas

| o == D = as

| otherwise = [((x,y),p) | ((x,y),p) <- as, x <= y]

escribeAristas

| ponderado = show aristasReducidas

| otherwise = show [a | (a,_) <- aristasReducidas]

ponderado = any (\((_,_),p) -> p /= 0) as

-- Procedimiento de escritura de grafos

instance (Ix v,Num p,Ord v, Ord p,Show v,Show p) => Show (Grafo v p) where

show = escribeGrafo

-- (creaGrafo d cs as) es un grafo (dirigido o no, según el valor de o),

-- con el par de cotas cs y listas de aristas as (cada arista es un trío

-- formado por los dos vértices y su peso). Ver el ejemplo a continuación.

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

creaGrafo D cs as =

G D (matrizVacia cs // [((v1,v2),Just c) | (v1,v2,c) <- as])

creaGrafo ND cs as =

G ND (matrizVacia cs // ([((v1,v2),Just c) | (v1,v2,c) <- as] ++

[((v2,v1),Just c) | (v1,v2,c) <- as, v1 /= v2]))

matrizVacia :: Ix v => (v,v) -> Array (v,v) (Maybe p)

matrizVacia (l,u) =

listArray ((l,l),(u,u)) (repeat Nothing)

-- (creaGrafo' o cs as) es un grafo (dirigido o no, según el valor de o),

-- con el par de cotas cs y listas de aristas as (cada arista es un par

-- de vértices y se supone que su peso es 0). Por ejemplo,

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

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

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

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

creaGrafo' :: (Ix v, Num p, Ord v, Ord p) =>

Orientacion -> (v,v) -> [(v,v)] -> Grafo v p

creaGrafo' o cs as =

creaGrafo o cs [(v1,v2,0) | (v1,v2) <- as]

-- ejGrafoND es el grafo

-- 12

-- 1 -------- 2

-- | \78 /|

-- | \ 32/ |

-- | \ / |

-- 34| 5 |55

-- | / \ |

-- | /44 \ |

-- | / 93\|

-- 3 -------- 4

-- 61

-- representado mediante una matriz de adyacencia.

-- λ> ejGrafoND

-- G ND array ((1,1),(5,5))

-- [((1,1),Nothing),((1,2),Just 12),((1,3),Just 34),

-- ((1,4),Nothing),((1,5),Just 78),((2,1),Just 12),

-- ((2,2),Nothing),((2,3),Nothing),((2,4),Just 55),

-- ((2,5),Just 32),((3,1),Just 34),((3,2),Nothing),

-- ((3,3),Nothing),((3,4),Just 61),((3,5),Just 44),

-- ((4,1),Nothing),((4,2),Just 55),((4,3),Just 61),

-- ((4,4),Nothing),((4,5),Just 93),((5,1),Just 78),

-- ((5,2),Just 32),((5,3),Just 44),((5,4),Just 93),

-- ((5,5),Nothing)]

ejGrafoND :: Grafo Int Int

ejGrafoND = creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78),

(2,4,55),(2,5,32),

(3,4,61),(3,5,44),

(4,5,93)]

-- ejGrafoD es el mismo grafo que ejGrafoND pero orientando las aristas;

-- es decir,

-- λ> ejGrafoD

-- G D (array ((1,1),(5,5))

-- [((1,1),Nothing),((1,2),Just 12),((1,3),Just 34),

-- ((1,4),Nothing),((1,5),Just 78),((2,1),Nothing),

-- ((2,2),Nothing),((2,3),Nothing),((2,4),Just 55),

-- ((2,5),Just 32),((3,1),Nothing),((3,2),Nothing),

-- ((3,3),Nothing),((3,4),Just 61),((3,5),Just 44),

-- ((4,1),Nothing),((4,2),Nothing),((4,3),Nothing),

-- ((4,4),Nothing),((4,5),Just 93),((5,1),Nothing),

-- ((5,2),Nothing),((5,3),Nothing),((5,4),Nothing),

-- ((5,5),Nothing)])

ejGrafoD :: Grafo Int Int

ejGrafoD = creaGrafo D (1,5) [(1,2,12),(1,3,34),(1,5,78),

(2,4,55),(2,5,32),

(3,4,61),(3,5,44),

(4,5,93)]

-- (dirigido g) se verifica si g es dirigido. Por ejemplo,

-- dirigido ejGrafoD == True

-- dirigido ejGrafoND == False

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

dirigido (G o _) = o == D

-- (nodos g) es la lista de todos los nodos del grafo g. Por ejemplo,

-- nodos ejGrafoND == [1,2,3,4,5]

-- nodos ejGrafoD == [1,2,3,4,5]

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

nodos (G _ g) = range (l,u)

where ((l,_),(u,_)) = bounds g

-- (adyacentes g v) es la lista de los vértices adyacentes al nodo v en

-- el grafo g. Por ejemplo,

-- adyacentes ejGrafoND 4 == [2,3,5]

-- adyacentes ejGrafoD 4 == [5]

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

adyacentes (G o g) v =

[v' | v' <- nodos (G o g), isJust (g!(v,v'))]

-- (aristaEn g a) se verifica si a es una arista del grafo g. Por

-- ejemplo,

-- aristaEn ejGrafoND (5,1) == True

-- aristaEn ejGrafoND (4,1) == False

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

aristaEn (G _o g) (x,y) = isJust (g!(x,y))

-- (peso v1 v2 g) es el peso de la arista que une los vértices v1 y v2

-- en el grafo g. Por ejemplo,

-- peso 1 5 ejGrafoND == 78

-- peso 1 5 ejGrafoD == 78

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

peso x y (G _ g) = w where (Just w) = g!(x,y)

-- (aristas g) es la lista de las aristas del grafo g. Por ejemplo,

-- λ> aristas ejGrafoD

-- [(1,2,12),(1,3,34),(1,5,78),(2,4,55),(2,5,32),(3,4,61),

-- (3,5,44),(4,5,93)]

-- λ> aristas ejGrafoND

-- [(1,2,12),(1,3,34),(1,5,78),(2,1,12),(2,4,55),(2,5,32),

-- (3,1,34),(3,4,61),(3,5,44),(4,2,55),(4,3,61),(4,5,93),

-- (5,1,78),(5,2,32),(5,3,44),(5,4,93)]

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

aristas g@(G _ e) = [((v1,v2),extrae(e!(v1,v2)))

| v1 <- nodos g,

v2 <- nodos g,

aristaEn g (v1,v2)]

where extrae (Just w) = w

extrae _ = error "Imposible"

3. Los grafos en Python

3.1. El tipo abstracto de los grafos en Python

La implementación se encuentra en el módulo Grafo.py cuyo contenido es el siguiente:

__all__ = [
    'Orientacion',
    'Grafo',
    'creaGrafo',
    'creaGrafo_',
    'dirigido',
    'adyacentes',
    'nodos',
    'aristas',
    'aristaEn',
    'peso'
    ]

from src.TAD.GrafoConListaDeAdyacencia import (Grafo, Orientacion, adyacentes,
                                               aristaEn, aristas, creaGrafo,
                                               creaGrafo_, dirigido, nodos, peso)

__all__ = [

'Orientacion',

'Grafo',

'creaGrafo',

'creaGrafo_',

'dirigido',

'adyacentes',

'nodos',

'aristas',

'aristaEn',

'peso'

]

from src.TAD.GrafoConListaDeAdyacencia import (Grafo, Orientacion, adyacentes,

aristaEn, aristas, creaGrafo,

creaGrafo_, dirigido, nodos, peso)

3.2. Implementación de los grafos mediante listas

Se define la clase Grafo con los siguientes métodos:

dirigido() se verifica si el grafo es dirigido.
nodos() es la lista de todos los nodos del grafo.
aristas() es la lista de las aristas del grafo.
adyacentes(v) es la lista de los vértices adyacentes al vértice v en el grafo.
aristaEn(a) se verifica si a es una arista del grafo.
peso(v1, v2) es el peso de la arista que une los vértices v1 y v2 en el grafo.

Por ejemplo,

>>> Grafo(Orientacion.D, (1,3), [((1,2),0),((3,2),0),((2,2),0)])
G D ([1, 2, 3], [(1, 2), (2, 2), (3, 2)])
>>> Grafo(Orientacion.ND, (1,3), [((1,2),0),((3,2),0),((2,2),0)])
G ND ([1, 2, 3], [(1, 2), (2, 2), (2, 3)])
>>> Grafo(Orientacion.ND, (1,3), [((1,2),0),((3,2),5),((2,2),0)])
G ND ([1, 2, 3], [((1, 2), 0), ((2, 2), 0), ((2, 3), 5)])
>>> Grafo(Orientacion.D, (1,3), [((1,2),0),((3,2),5),((2,2),0)])
G D ([1, 2, 3], [((1, 2), 0), ((2, 2), 0), ((3, 2), 5)])
>>> ejGrafoND: Grafo = Grafo(Orientacion.ND,
                             (1, 5),
                             [((1, 2), 12), ((1, 3), 34), ((1, 5), 78),
                              ((2, 4), 55), ((2, 5), 32),
                              ((3, 4), 61), ((3, 5), 44),
                              ((4, 5), 93)])
>>> ejGrafoND
G ND ([1, 2, 3, 4, 5],
      [((1, 2), 12), ((1, 3), 34), ((1, 5), 78),
       ((2, 4), 55), ((2, 5), 32),
       ((3, 4), 61), ((3, 5), 44),
       ((4, 5), 93)])
>> ejGrafoD: Grafo = Grafo(Orientacion.D,
                           (1,5),
                           [((1, 2), 12), ((1, 3), 34), ((1, 5), 78),
                            ((2, 4), 55), ((2, 5), 32),
                            ((3, 4), 61), ((3, 5), 44),
                            ((4, 5), 93)])
>>> ejGrafoD
G D ([1, 2, 3, 4, 5],
     [((1, 2), 12), ((1, 3), 34), ((1, 5), 78),
      ((2, 4), 55), ((2, 5), 32),
      ((3, 4), 61), ((3, 5), 44),
      ((4, 5), 93)])
>>> ejGrafoD.dirigido()
True
>>> ejGrafoND.dirigido()
False
>>> ejGrafoND.nodos()
[1, 2, 3, 4, 5]
>>> ejGrafoD.nodos()
[1, 2, 3, 4, 5]
>>> ejGrafoND.adyacentes(4)
[2, 3, 5]
>>> ejGrafoD.adyacentes(4)
[5]
>>> ejGrafoND.aristaEn((5, 1))
True
>>> ejGrafoND.aristaEn((4, 1))
False
>>> ejGrafoD.aristaEn((5, 1))
False
>>> ejGrafoD.aristaEn((1, 5))
True
>>> ejGrafoND.peso(1, 5)
78
>>> ejGrafoD.peso(1, 5)
78
>>> ejGrafoD._aristas
[((1, 2), 12), ((1, 3), 34), ((1, 5), 78),
 ((2, 4), 55), ((2, 5), 32),
 ((3, 4), 61), ((3, 5), 44),
 ((4, 5), 93)]
>>> ejGrafoND._aristas
[((1, 2), 12), ((1, 3), 34), ((1, 5), 78),
 ((2, 1), 12), ((2, 4), 55), ((2, 5), 32),
 ((3, 1), 34), ((3, 4), 61), ((3, 5), 44),
 ((4, 2), 55), ((4, 3), 61), ((4, 5), 93),
 ((5, 1), 78), ((5, 2), 32), ((5, 3), 44),
 ((5, 4), 93)]

>>> Grafo(Orientacion.D, (1,3), [((1,2),0),((3,2),0),((2,2),0)])

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

>>> Grafo(Orientacion.ND, (1,3), [((1,2),0),((3,2),0),((2,2),0)])

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

>>> Grafo(Orientacion.ND, (1,3), [((1,2),0),((3,2),5),((2,2),0)])

G ND ([1, 2, 3], [((1, 2), 0), ((2, 2), 0), ((2, 3), 5)])

>>> Grafo(Orientacion.D, (1,3), [((1,2),0),((3,2),5),((2,2),0)])

G D ([1, 2, 3], [((1, 2), 0), ((2, 2), 0), ((3, 2), 5)])

>>> ejGrafoND: Grafo = Grafo(Orientacion.ND,

(1, 5),

[((1, 2), 12), ((1, 3), 34), ((1, 5), 78),

((2, 4), 55), ((2, 5), 32),

((3, 4), 61), ((3, 5), 44),

((4, 5), 93)])

>>> ejGrafoND

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

[((1, 2), 12), ((1, 3), 34), ((1, 5), 78),

((2, 4), 55), ((2, 5), 32),

((3, 4), 61), ((3, 5), 44),

((4, 5), 93)])

>> ejGrafoD: Grafo = Grafo(Orientacion.D,

(1,5),

[((1, 2), 12), ((1, 3), 34), ((1, 5), 78),

((2, 4), 55), ((2, 5), 32),

((3, 4), 61), ((3, 5), 44),

((4, 5), 93)])

>>> ejGrafoD

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

[((1, 2), 12), ((1, 3), 34), ((1, 5), 78),

((2, 4), 55), ((2, 5), 32),

((3, 4), 61), ((3, 5), 44),

((4, 5), 93)])

>>> ejGrafoD.dirigido()

True

>>> ejGrafoND.dirigido()

False

>>> ejGrafoND.nodos()

[1, 2, 3, 4, 5]

>>> ejGrafoD.nodos()

[1, 2, 3, 4, 5]

>>> ejGrafoND.adyacentes(4)

[2, 3, 5]

>>> ejGrafoD.adyacentes(4)

[5]

>>> ejGrafoND.aristaEn((5, 1))

True

>>> ejGrafoND.aristaEn((4, 1))

False

>>> ejGrafoD.aristaEn((5, 1))

False

>>> ejGrafoD.aristaEn((1, 5))

True

>>> ejGrafoND.peso(1, 5)

>>> ejGrafoD.peso(1, 5)

>>> ejGrafoD._aristas

[((1, 2), 12), ((1, 3), 34), ((1, 5), 78),

((2, 4), 55), ((2, 5), 32),

((3, 4), 61), ((3, 5), 44),

((4, 5), 93)]

>>> ejGrafoND._aristas

[((1, 2), 12), ((1, 3), 34), ((1, 5), 78),

((2, 1), 12), ((2, 4), 55), ((2, 5), 32),

((3, 1), 34), ((3, 4), 61), ((3, 5), 44),

((4, 2), 55), ((4, 3), 61), ((4, 5), 93),

((5, 1), 78), ((5, 2), 32), ((5, 3), 44),

((5, 4), 93)]

Además se definen las correspondientes funciones. Por ejemplo,

>>> creaGrafo(Orientacion.ND, (1,3), [((1,2),12),((1,3),34)])
G ND ([1, 2, 3], [((1, 2), 12), ((1, 3), 34), ((2, 1), 12), ((3, 1), 34)])
>>> creaGrafo(Orientacion.D, (1,3), [((1,2),12),((1,3),34)])
G D ([1, 2, 3], [((1, 2), 12), ((1, 3), 34)])
>>> creaGrafo(Orientacion.D, (1,4), [((1,2),12),((1,3),34)])
G D ([1, 2, 3, 4], [((1, 2), 12), ((1, 3), 34)])
>>> ejGrafoND2: Grafo = creaGrafo(Orientacion.ND,
                                  (1,5),
                                  [((1,2),12),((1,3),34),((1,5),78),
                                   ((2,4),55),((2,5),32),
                                   ((3,4),61),((3,5),44),
                                   ((4,5),93)])
>>> ejGrafoND2
G ND ([1, 2, 3, 4, 5],
      [((1, 2), 12), ((1, 3), 34), ((1, 5), 78),
       ((2, 4), 55), ((2, 5), 32),
       ((3, 4), 61), ((3, 5), 44),
       ((4, 5), 93)])
>>> ejGrafoD2: Grafo = creaGrafo(Orientacion.D,
                                 (1,5),
                                 [((1,2),12),((1,3),34),((1,5),78),
                                  ((2,4),55),((2,5),32),
                                  ((3,4),61),((3,5),44),
                                  ((4,5),93)])
>>> ejGrafoD2
G D ([1, 2, 3, 4, 5],
     [((1, 2), 12), ((1, 3), 34), ((1, 5), 78),
      ((2, 4), 55), ((2, 5), 32),
      ((3, 4), 61), ((3, 5), 44),
      ((4, 5), 93)])
>>> creaGrafo_(Orientacion.D, (1,3), [(2, 1), (1, 3)])
G D ([1, 2, 3], [(1, 3), (2, 1)])
>>> creaGrafo_(Orientacion.ND, (1,3), [(2, 1), (1, 3)])
G ND ([1, 2, 3], [(1, 2), (1, 3)])
>>> dirigido(ejGrafoD2)
True
>>> dirigido(ejGrafoND2)
False
>>> nodos(ejGrafoND2)
[1, 2, 3, 4, 5]
>>> nodos(ejGrafoD2)
[1, 2, 3, 4, 5]
>>> adyacentes(ejGrafoND2, 4)
[2, 3, 5]
>>> adyacentes(ejGrafoD2, 4)
[5]
>>> aristaEn(ejGrafoND2, (5,1))
True
>>> aristaEn(ejGrafoND2, (4,1))
False
>>> aristaEn(ejGrafoD2, (5,1))
False
>>> aristaEn(ejGrafoD2, (1,5))
True
>>> peso(1, 5, ejGrafoND2)
78
>>> peso(1, 5, ejGrafoD2)
78
>>> aristas(ejGrafoD2)
[((1, 2), 12), ((1, 3), 34), ((1, 5), 78),
 ((2, 4), 55), ((2, 5), 32),
 ((3, 4), 61), ((3, 5), 44),
 ((4, 5), 93)]
>>> aristas(ejGrafoND2)
[((1, 2), 12), ((1, 3), 34), ((1, 5), 78),
 ((2, 1), 12), ((2, 4), 55), ((2, 5), 32),
 ((3, 1), 34), ((3, 4), 61), ((3, 5), 44),
 ((4, 2), 55), ((4, 3), 61), ((4, 5), 93),
 ((5, 1), 78), ((5, 2), 32), ((5, 3), 44), ((5, 4), 93)]

>>> creaGrafo(Orientacion.ND, (1,3), [((1,2),12),((1,3),34)])

G ND ([1, 2, 3], [((1, 2), 12), ((1, 3), 34), ((2, 1), 12), ((3, 1), 34)])

>>> creaGrafo(Orientacion.D, (1,3), [((1,2),12),((1,3),34)])

G D ([1, 2, 3], [((1, 2), 12), ((1, 3), 34)])

>>> creaGrafo(Orientacion.D, (1,4), [((1,2),12),((1,3),34)])

G D ([1, 2, 3, 4], [((1, 2), 12), ((1, 3), 34)])

>>> ejGrafoND2: Grafo = creaGrafo(Orientacion.ND,

(1,5),

[((1,2),12),((1,3),34),((1,5),78),

((2,4),55),((2,5),32),

((3,4),61),((3,5),44),

((4,5),93)])

>>> ejGrafoND2

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

[((1, 2), 12), ((1, 3), 34), ((1, 5), 78),

((2, 4), 55), ((2, 5), 32),

((3, 4), 61), ((3, 5), 44),

((4, 5), 93)])

>>> ejGrafoD2: Grafo = creaGrafo(Orientacion.D,

(1,5),

[((1,2),12),((1,3),34),((1,5),78),

((2,4),55),((2,5),32),

((3,4),61),((3,5),44),

((4,5),93)])

>>> ejGrafoD2

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

[((1, 2), 12), ((1, 3), 34), ((1, 5), 78),

((2, 4), 55), ((2, 5), 32),

((3, 4), 61), ((3, 5), 44),

((4, 5), 93)])

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

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

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

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

>>> dirigido(ejGrafoD2)

True

>>> dirigido(ejGrafoND2)

False

>>> nodos(ejGrafoND2)

[1, 2, 3, 4, 5]

>>> nodos(ejGrafoD2)

[1, 2, 3, 4, 5]

>>> adyacentes(ejGrafoND2, 4)

[2, 3, 5]

>>> adyacentes(ejGrafoD2, 4)

[5]

>>> aristaEn(ejGrafoND2, (5,1))

True

>>> aristaEn(ejGrafoND2, (4,1))

False

>>> aristaEn(ejGrafoD2, (5,1))

False

>>> aristaEn(ejGrafoD2, (1,5))

True

>>> peso(1, 5, ejGrafoND2)

>>> peso(1, 5, ejGrafoD2)

>>> aristas(ejGrafoD2)

[((1, 2), 12), ((1, 3), 34), ((1, 5), 78),

((2, 4), 55), ((2, 5), 32),

((3, 4), 61), ((3, 5), 44),

((4, 5), 93)]

>>> aristas(ejGrafoND2)

[((1, 2), 12), ((1, 3), 34), ((1, 5), 78),

((2, 1), 12), ((2, 4), 55), ((2, 5), 32),

((3, 1), 34), ((3, 4), 61), ((3, 5), 44),

((4, 2), 55), ((4, 3), 61), ((4, 5), 93),

((5, 1), 78), ((5, 2), 32), ((5, 3), 44), ((5, 4), 93)]

La implementación se encuentra en el módulo GrafoConListaDeAdyacencia cuyo contenido es el siguiente:

from enum import Enum

Orientacion = Enum('Orientacion', ['D', 'ND'])

Vertice = int
Cotas = tuple[Vertice, Vertice]
Peso = float
Arista = tuple[tuple[Vertice, Vertice], Peso]

class Grafo:
    def __init__(self,
                 _orientacion: Orientacion,
                 _cotas: Cotas,
                 _aristas: list[Arista]):
        self._orientacion = _orientacion
        self._cotas = _cotas
        if _orientacion == Orientacion.ND:
            simetricas = [((v2, v1), p) for ((v1, v2), p)
                          in _aristas
                          if v1 != v2]
            self._aristas = sorted(_aristas + simetricas)
        else:
            self._aristas = sorted(_aristas)

    def nodos(self) -> list[Vertice]:
        (x, y) = self._cotas
        return list(range(x, 1 + y))

    def __repr__(self) -> str:
        o = self._orientacion
        vs = nodos(self)
        ns = self._aristas
        escribeOrientacion = "D" if o == Orientacion.D else "ND"
        ponderado = {p for ((_, _), p) in ns} != {0}
        aristasReducidas = ns if o == Orientacion.D \
            else [((x, y), p)
                  for ((x, y), p) in ns
                  if x <= y]
        escribeAristas = str(aristasReducidas) if ponderado \
            else str([a for (a, _) in aristasReducidas])
        return f"G {escribeOrientacion} ({vs}, {escribeAristas})"

    def dirigido(self) -> bool:
        return self._orientacion == Orientacion.D

    def adyacentes(self, v: int) -> list[int]:
        return list(set(u for ((w, u), _)
                        in self._aristas
                        if w == v))

    def aristaEn(self, a: tuple[Vertice, Vertice]) -> bool:
        (x, y) = a
        return y in self.adyacentes(x)

    def peso(self, v1: Vertice, v2: Vertice) -> Peso:
        return [p for ((x1, x2), p)
                in self._aristas
                if (x1, x2) == (v1, v2)][0]

def creaGrafo(o: Orientacion,
              cs: Cotas,
              as_: list[Arista]) -> Grafo:
    return Grafo(o, cs, as_)

def creaGrafo_(o: Orientacion,
              cs: Cotas,
              as_: list[tuple[Vertice, Vertice]]) -> Grafo:
    return Grafo(o, cs, [((v1, v2), 0) for (v1, v2) in as_])

def dirigido(g: Grafo) -> bool:
    return g.dirigido()

def nodos(g: Grafo) -> list[Vertice]:
    return g.nodos()

def adyacentes(g: Grafo, v: Vertice) -> list[Vertice]:
    return g.adyacentes(v)

def aristaEn(g: Grafo, a: tuple[Vertice, Vertice]) -> bool:
    return g.aristaEn(a)

def peso(v1: Vertice, v2: Vertice, g: Grafo) -> Peso:
    return g.peso(v1, v2)

def aristas(g: Grafo) -> list[Arista]:
    return g._aristas

# En los ejemplos se usarán los grafos (no dirigido y dirigido)
# correspondientes a
#             12
#        1 -------- 2
#        | \78     /|
#        |  \   32/ |
#        |   \   /  |
#      34|     5    |55
#        |   /   \  |
#        |  /44   \ |
#        | /     93\|
#        3 -------- 4
#             61
# definidos por
ejGrafoND: Grafo = Grafo(Orientacion.ND,
                         (1, 5),
                         [((1, 2), 12), ((1, 3), 34), ((1, 5), 78),
                          ((2, 4), 55), ((2, 5), 32),
                          ((3, 4), 61), ((3, 5), 44),
                          ((4, 5), 93)])
ejGrafoD: Grafo = Grafo(Orientacion.D,
                        (1,5),
                        [((1, 2), 12), ((1, 3), 34), ((1, 5), 78),
                         ((2, 4), 55), ((2, 5), 32),
                         ((3, 4), 61), ((3, 5), 44),
                         ((4, 5), 93)])

ejGrafoND2: Grafo = creaGrafo(Orientacion.ND,
                              (1,5),
                              [((1,2),12),((1,3),34),((1,5),78),
                               ((2,4),55),((2,5),32),
                               ((3,4),61),((3,5),44),
                               ((4,5),93)])

ejGrafoD2: Grafo = creaGrafo(Orientacion.D,
                             (1,5),
                             [((1,2),12),((1,3),34),((1,5),78),
                              ((2,4),55),((2,5),32),
                              ((3,4),61),((3,5),44),
                              ((4,5),93)])

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

from enum import Enum

Orientacion = Enum('Orientacion', ['D', 'ND'])

Vertice = int

Cotas = tuple[Vertice, Vertice]

Peso = float

Arista = tuple[tuple[Vertice, Vertice], Peso]

class Grafo:

def __init__(self,

_orientacion: Orientacion,

_cotas: Cotas,

_aristas: list[Arista]):

self._orientacion = _orientacion

self._cotas = _cotas

if _orientacion == Orientacion.ND:

simetricas = [((v2, v1), p) for ((v1, v2), p)

in _aristas

if v1 != v2]

self._aristas = sorted(_aristas + simetricas)

else:

self._aristas = sorted(_aristas)

def nodos(self) -> list[Vertice]:

(x, y) = self._cotas

return list(range(x, 1 + y))

def __repr__(self) -> str:

o = self._orientacion

vs = nodos(self)

ns = self._aristas

escribeOrientacion = "D" if o == Orientacion.D else "ND"

ponderado = {p for ((_, _), p) in ns} != {0}

aristasReducidas = ns if o == Orientacion.D \

else [((x, y), p)

for ((x, y), p) in ns

if x <= y]

escribeAristas = str(aristasReducidas) if ponderado \

else str([a for (a, _) in aristasReducidas])

return f"G {escribeOrientacion} ({vs}, {escribeAristas})"

def dirigido(self) -> bool:

return self._orientacion == Orientacion.D

def adyacentes(self, v: int) -> list[int]:

return list(set(u for ((w, u), _)

in self._aristas

if w == v))

def aristaEn(self, a: tuple[Vertice, Vertice]) -> bool:

(x, y) = a

return y in self.adyacentes(x)

def peso(self, v1: Vertice, v2: Vertice) -> Peso:

return [p for ((x1, x2), p)

in self._aristas

if (x1, x2) == (v1, v2)][0]

def creaGrafo(o: Orientacion,

cs: Cotas,

as_: list[Arista]) -> Grafo:

return Grafo(o, cs, as_)

def creaGrafo_(o: Orientacion,

cs: Cotas,

as_: list[tuple[Vertice, Vertice]]) -> Grafo:

return Grafo(o, cs, [((v1, v2), 0) for (v1, v2) in as_])

def dirigido(g: Grafo) -> bool:

return g.dirigido()

def nodos(g: Grafo) -> list[Vertice]:

return g.nodos()

def adyacentes(g: Grafo, v: Vertice) -> list[Vertice]:

return g.adyacentes(v)

def aristaEn(g: Grafo, a: tuple[Vertice, Vertice]) -> bool:

return g.aristaEn(a)

def peso(v1: Vertice, v2: Vertice, g: Grafo) -> Peso:

return g.peso(v1, v2)

def aristas(g: Grafo) -> list[Arista]:

return g._aristas

# En los ejemplos se usarán los grafos (no dirigido y dirigido)

# correspondientes a

# 12

# 1 -------- 2

# | \78 /|

# | \ 32/ |

# | \ / |

# 34| 5 |55

# | / \ |

# | /44 \ |

# | / 93\|

# 3 -------- 4

# 61

# definidos por

ejGrafoND: Grafo = Grafo(Orientacion.ND,

(1, 5),

[((1, 2), 12), ((1, 3), 34), ((1, 5), 78),

((2, 4), 55), ((2, 5), 32),

((3, 4), 61), ((3, 5), 44),

((4, 5), 93)])

ejGrafoD: Grafo = Grafo(Orientacion.D,

(1,5),

[((1, 2), 12), ((1, 3), 34), ((1, 5), 78),

((2, 4), 55), ((2, 5), 32),

((3, 4), 61), ((3, 5), 44),

((4, 5), 93)])

ejGrafoND2: Grafo = creaGrafo(Orientacion.ND,

(1,5),

[((1,2),12),((1,3),34),((1,5),78),

((2,4),55),((2,5),32),

((3,4),61),((3,5),44),

((4,5),93)])

ejGrafoD2: Grafo = creaGrafo(Orientacion.D,

(1,5),

[((1,2),12),((1,3),34),((1,5),78),

((2,4),55),((2,5),32),

((3,4),61),((3,5),44),

((4,5),93)])

TAD de los polinomios: Factorización de un polinomio

PorJosé A. Alonso 22-mayo-202322-mayo-2023

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

   factorizacion :: Polinomio Int -> [Polinomio Int]

1	factorizacion :: Polinomio Int -> [Polinomio Int]

tal que factorizacion p es la lista de la descomposición del polinomio p en factores obtenida mediante el regla de Ruffini. Por ejemplo,

   λ> ejPol1 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
   λ> ejPol1
   x^5 + 5*x^2 + 4*x
   λ> factorizacion ejPol1
   [1*x,1*x + 1,x^3 + -1*x^2 + 1*x + 4]
   λ> ejPol2 = consPol 3 1 (consPol 2 2 (consPol 1 (-1) (consPol 0 (-2) polCero)))
   λ> ejPol2
   x^3 + 2*x^2 + -1*x + -2
   λ> factorizacion ejPol2
   [1*x + -1,1*x + 1,1*x + 2,1]

λ> ejPol1 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))

λ> ejPol1

x^5 + 5*x^2 + 4*x

λ> factorizacion ejPol1

[1*x,1*x + 1,x^3 + -1*x^2 + 1*x + 4]

λ> ejPol2 = consPol 3 1 (consPol 2 2 (consPol 1 (-1) (consPol 0 (-2) polCero)))

λ> ejPol2

x^3 + 2*x^2 + -1*x + -2

λ> factorizacion ejPol2

[1*x + -1,1*x + 1,1*x + 2,1]

Soluciones

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

Soluciones en Haskell

module Pol_Factorizacion_de_un_polinomio where

import TAD.Polinomio (Polinomio, consPol, polCero, esPolCero)
import Pol_Termino_independiente_de_un_polinomio (terminoIndep)
import Pol_Raices_enteras_de_un_polinomio (divisores)
import Pol_Regla_de_Ruffini (cocienteRuffini)
import Pol_Reconocimiento_de_raices_por_la_regla_de_Ruffini (esRaizRuffini)
import Pol_Transformaciones_polinomios_densas (densaApolinomio)
import Test.Hspec (Spec, hspec, it, shouldBe)

factorizacion :: Polinomio Int -> [Polinomio Int]
factorizacion p
  | esPolCero p = [p]
  | otherwise   = aux (0 : divisores (terminoIndep p))
  where
    aux [] = [p]
    aux (r:rs)
        | esRaizRuffini r p =
            densaApolinomio [1,-r] : factorizacion (cocienteRuffini r p)
        | otherwise = aux rs

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

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "e1" $
    map show (factorizacion ejPol1)
      `shouldBe` ["1*x","1*x + 1","x^3 + -1*x^2 + 1*x + 4"]
  it "e2" $
    map show (factorizacion ejPol2)
      `shouldBe` ["1*x + -1","1*x + 1","1*x + 2","1"]
  where
    ejPol1 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
    ejPol2 = consPol 3 1 (consPol 2 2 (consPol 1 (-1) (consPol 0 (-2) polCero)))

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

module Pol_Factorizacion_de_un_polinomio where

import TAD.Polinomio (Polinomio, consPol, polCero, esPolCero)

import Pol_Termino_independiente_de_un_polinomio (terminoIndep)

import Pol_Raices_enteras_de_un_polinomio (divisores)

import Pol_Regla_de_Ruffini (cocienteRuffini)

import Pol_Reconocimiento_de_raices_por_la_regla_de_Ruffini (esRaizRuffini)

import Pol_Transformaciones_polinomios_densas (densaApolinomio)

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

factorizacion :: Polinomio Int -> [Polinomio Int]

factorizacion p

| esPolCero p = [p]

| otherwise = aux (0 : divisores (terminoIndep p))

where

aux [] = [p]

aux (r:rs)

| esRaizRuffini r p =

densaApolinomio [1,-r] : factorizacion (cocienteRuffini r p)

| otherwise = aux rs

-- Verificación

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

verifica :: IO ()

verifica = hspec spec

spec :: Spec

spec = do

it "e1" $

map show (factorizacion ejPol1)

`shouldBe` ["1*x","1*x + 1","x^3 + -1*x^2 + 1*x + 4"]

it "e2" $

map show (factorizacion ejPol2)

`shouldBe` ["1*x + -1","1*x + 1","1*x + 2","1"]

where

ejPol1 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))

ejPol2 = consPol 3 1 (consPol 2 2 (consPol 1 (-1) (consPol 0 (-2) polCero)))

-- La verificación es

-- λ> verifica

-- e1

-- e2

-- Finished in 0.0015 seconds

-- 2 examples, 0 failures

Soluciones en Python

from src.Pol_Raices_enteras_de_un_polinomio import divisores
from src.Pol_Reconocimiento_de_raices_por_la_regla_de_Ruffini import \
    esRaizRuffini
from src.Pol_Regla_de_Ruffini import cocienteRuffini
from src.Pol_Termino_independiente_de_un_polinomio import terminoIndep
from src.Pol_Transformaciones_polinomios_densas import densaApolinomio
from src.TAD.Polinomio import Polinomio, consPol, esPolCero, polCero


def factorizacion(p: Polinomio[int]) -> list[Polinomio[int]]:
    def aux(xs: list[int]) -> list[Polinomio[int]]:
        if not xs:
            return [p]
        r, *rs = xs
        if esRaizRuffini(r, p):
            return [densaApolinomio([1, -r])] + factorizacion(cocienteRuffini(r, p))
        return aux(rs)

    if esPolCero(p):
        return [p]
    return aux([0] + divisores(terminoIndep(p)))

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

def test_factorizacion() -> None:
    ejPol1 = consPol(5, 1, consPol(2, 5, consPol(1, 4, polCero())))
    assert list(map(str, factorizacion(ejPol1))) \
        == ["1*x", "1*x + 1", "x^3 + -1*x^2 + 1*x + 4"]
    ejPol2 = consPol(3, 1, consPol(2, 2, consPol(1, -1, consPol(0, -2, polCero()))))
    assert list(map(str, factorizacion(ejPol2))) \
        == ["1*x + -1", "1*x + 1", "1*x + 2", "1"]
    print("Verificado")

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

from src.Pol_Raices_enteras_de_un_polinomio import divisores

from src.Pol_Reconocimiento_de_raices_por_la_regla_de_Ruffini import \

esRaizRuffini

from src.Pol_Regla_de_Ruffini import cocienteRuffini

from src.Pol_Termino_independiente_de_un_polinomio import terminoIndep

from src.Pol_Transformaciones_polinomios_densas import densaApolinomio

from src.TAD.Polinomio import Polinomio, consPol, esPolCero, polCero

def factorizacion(p: Polinomio[int]) -> list[Polinomio[int]]:

def aux(xs: list[int]) -> list[Polinomio[int]]:

if not xs:

return [p]

r, *rs = xs

if esRaizRuffini(r, p):

return [densaApolinomio([1, -r])] + factorizacion(cocienteRuffini(r, p))

return aux(rs)

if esPolCero(p):

return [p]

return aux([0] + divisores(terminoIndep(p)))

# Verificación

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

def test_factorizacion() -> None:

ejPol1 = consPol(5, 1, consPol(2, 5, consPol(1, 4, polCero())))

assert list(map(str, factorizacion(ejPol1))) \

== ["1*x", "1*x + 1", "x^3 + -1*x^2 + 1*x + 4"]

ejPol2 = consPol(3, 1, consPol(2, 2, consPol(1, -1, consPol(0, -2, polCero()))))

assert list(map(str, factorizacion(ejPol2))) \

== ["1*x + -1", "1*x + 1", "1*x + 2", "1"]

print("Verificado")

# La verificación es

# >>> test_factorizacion()

# Verificado

TAD de los polinomios: Raíces enteras de un polinomio

PorJosé A. Alonso 19-mayo-202322-mayo-2023

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

    raicesRuffini :: Polinomio Int -> [Int]

1	raicesRuffini :: Polinomio Int -> [Int]

tal que raicesRuffini p es la lista de las raices enteras de p, calculadas usando el regla de Ruffini. Por ejemplo,

    λ> ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))
    λ> ejPol1
    3*x^4 + -5*x^2 + 3
    λ> raicesRuffini ejPol1
    []
    λ> ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
    λ> ejPol2
    x^5 + 5*x^2 + 4*x
    λ> raicesRuffini ejPol2
    [0,-1]
    λ> ejPol3 = consPol 4 6 (consPol 1 2 polCero)
    λ> ejPol3
    6*x^4 + 2*x
    λ> raicesRuffini ejPol3
    [0]
    λ> ejPol4 = consPol 3 1 (consPol 2 2 (consPol 1 (-1) (consPol 0 (-2) polCero)))
    λ> ejPol4
    x^3 + 2*x^2 + -1*x + -2
    λ> raicesRuffini ejPol4
    [1,-1,-2]

λ> ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))

λ> ejPol1

3*x^4 + -5*x^2 + 3

λ> raicesRuffini ejPol1

[]

λ> ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))

λ> ejPol2

x^5 + 5*x^2 + 4*x

λ> raicesRuffini ejPol2

[0,-1]

λ> ejPol3 = consPol 4 6 (consPol 1 2 polCero)

λ> ejPol3

6*x^4 + 2*x

λ> raicesRuffini ejPol3

[0]

λ> ejPol4 = consPol 3 1 (consPol 2 2 (consPol 1 (-1) (consPol 0 (-2) polCero)))

λ> ejPol4

x^3 + 2*x^2 + -1*x + -2

λ> raicesRuffini ejPol4

[1,-1,-2]

Soluciones

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

Soluciones en Haskell

module Pol_Raices_enteras_de_un_polinomio where

import TAD.Polinomio (Polinomio, consPol, polCero, esPolCero)
import Pol_Termino_independiente_de_un_polinomio (terminoIndep)
import Pol_Regla_de_Ruffini (cocienteRuffini)
import Pol_Reconocimiento_de_raices_por_la_regla_de_Ruffini (esRaizRuffini)
import Test.Hspec (Spec, hspec, it, shouldBe)

raicesRuffini :: Polinomio Int -> [Int]
raicesRuffini p
  | esPolCero p = []
  | otherwise   = aux (0 : divisores (terminoIndep p))
  where aux [] = []
        aux (r:rs)
          | esRaizRuffini r p = r : raicesRuffini (cocienteRuffini r p)
          | otherwise         = aux rs

-- (divisores n) es la lista de todos los divisores enteros de n. Por
-- ejemplo,
--    divisores 4     ==  [1,-1,2,-2,4,-4]
--    divisores (-6)  ==  [1,-1,2,-2,3,-3,6,-6]
divisores :: Int -> [Int]
divisores n = concat [[x,-x] | x <- [1..abs n], rem n x == 0]

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

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "e1" $
    raicesRuffini ejPol1 `shouldBe` []
  it "e2" $
    raicesRuffini ejPol2 `shouldBe` [0,-1]
  it "e3" $
    raicesRuffini ejPol3 `shouldBe` [0]
  it "e4" $
    raicesRuffini ejPol4 `shouldBe` [1,-1,-2]
  where
    ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))
    ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
    ejPol3 = consPol 4 6 (consPol 1 2 polCero)
    ejPol4 = consPol 3 1 (consPol 2 2 (consPol 1 (-1) (consPol 0 (-2) polCero)))

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

module Pol_Raices_enteras_de_un_polinomio where

import TAD.Polinomio (Polinomio, consPol, polCero, esPolCero)

import Pol_Termino_independiente_de_un_polinomio (terminoIndep)

import Pol_Regla_de_Ruffini (cocienteRuffini)

import Pol_Reconocimiento_de_raices_por_la_regla_de_Ruffini (esRaizRuffini)

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

raicesRuffini :: Polinomio Int -> [Int]

raicesRuffini p

| esPolCero p = []

| otherwise = aux (0 : divisores (terminoIndep p))

where aux [] = []

aux (r:rs)

| esRaizRuffini r p = r : raicesRuffini (cocienteRuffini r p)

| otherwise = aux rs

-- (divisores n) es la lista de todos los divisores enteros de n. Por

-- ejemplo,

-- divisores 4 == [1,-1,2,-2,4,-4]

-- divisores (-6) == [1,-1,2,-2,3,-3,6,-6]

divisores :: Int -> [Int]

divisores n = concat [[x,-x] | x <- [1..abs n], rem n x == 0]

-- Verificación

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

verifica :: IO ()

verifica = hspec spec

spec :: Spec

spec = do

it "e1" $

raicesRuffini ejPol1 `shouldBe` []

it "e2" $

raicesRuffini ejPol2 `shouldBe` [0,-1]

it "e3" $

raicesRuffini ejPol3 `shouldBe` [0]

it "e4" $

raicesRuffini ejPol4 `shouldBe` [1,-1,-2]

where

ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))

ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))

ejPol3 = consPol 4 6 (consPol 1 2 polCero)

ejPol4 = consPol 3 1 (consPol 2 2 (consPol 1 (-1) (consPol 0 (-2) polCero)))

-- La verificación es

-- λ> verifica

-- e1

-- e2

-- e3

-- e4

-- Finished in 0.0013 seconds

-- 4 examples, 0 failures

Soluciones en Python

from src.Pol_Reconocimiento_de_raices_por_la_regla_de_Ruffini import \
    esRaizRuffini
from src.Pol_Regla_de_Ruffini import cocienteRuffini
from src.Pol_Termino_independiente_de_un_polinomio import terminoIndep
from src.TAD.Polinomio import Polinomio, consPol, esPolCero, polCero


# (divisores n) es la lista de todos los divisores enteros de n. Por
# ejemplo,
#    divisores(4)  == [1, 2, 4, -1, -2, -4]
#    divisores(-6) == [1, 2, 3, 6, -1, -2, -3, -6]
def divisores(n: int) -> list[int]:
    xs = [x for x in range(1, abs(n)+1) if n % x == 0]
    return xs + [-x for x in xs]

def raicesRuffini(p: Polinomio[int]) -> list[int]:
    if esPolCero(p):
        return []
    def aux(rs: list[int]) -> list[int]:
        if not rs:
            return []
        x, *xs = rs
        if esRaizRuffini(x, p):
            return [x] + raicesRuffini(cocienteRuffini(x, p))
        return aux(xs)

    return aux([0] + divisores(terminoIndep(p)))

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

def test_raicesRuffini() -> None:
    ejPol1 = consPol(4, 3, consPol(2, -5, consPol(0, 3, polCero())))
    assert raicesRuffini(ejPol1) == []
    ejPol2 = consPol(5, 1, consPol(2, 5, consPol(1, 4, polCero())))
    assert raicesRuffini(ejPol2) == [0, -1]
    ejPol3 = consPol(4, 6, consPol(1, 2, polCero()))
    assert raicesRuffini(ejPol3) == [0]
    ejPol4 = consPol(3, 1, consPol(2, 2, consPol(1, -1, consPol(0, -2, polCero()))))
    assert raicesRuffini(ejPol4) == [1, -1, -2]
    print("Verificado")

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

from src.Pol_Reconocimiento_de_raices_por_la_regla_de_Ruffini import \

esRaizRuffini

from src.Pol_Regla_de_Ruffini import cocienteRuffini

from src.Pol_Termino_independiente_de_un_polinomio import terminoIndep

from src.TAD.Polinomio import Polinomio, consPol, esPolCero, polCero

# (divisores n) es la lista de todos los divisores enteros de n. Por

# ejemplo,

# divisores(4) == [1, 2, 4, -1, -2, -4]

# divisores(-6) == [1, 2, 3, 6, -1, -2, -3, -6]

def divisores(n: int) -> list[int]:

xs = [x for x in range(1, abs(n)+1) if n % x == 0]

return xs + [-x for x in xs]

def raicesRuffini(p: Polinomio[int]) -> list[int]:

if esPolCero(p):

return []

def aux(rs: list[int]) -> list[int]:

if not rs:

return []

x, *xs = rs

if esRaizRuffini(x, p):

return [x] + raicesRuffini(cocienteRuffini(x, p))

return aux(xs)

return aux([0] + divisores(terminoIndep(p)))

# Verificación

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

def test_raicesRuffini() -> None:

ejPol1 = consPol(4, 3, consPol(2, -5, consPol(0, 3, polCero())))

assert raicesRuffini(ejPol1) == []

ejPol2 = consPol(5, 1, consPol(2, 5, consPol(1, 4, polCero())))

assert raicesRuffini(ejPol2) == [0, -1]

ejPol3 = consPol(4, 6, consPol(1, 2, polCero()))

assert raicesRuffini(ejPol3) == [0]

ejPol4 = consPol(3, 1, consPol(2, 2, consPol(1, -1, consPol(0, -2, polCero()))))

assert raicesRuffini(ejPol4) == [1, -1, -2]

print("Verificado")

# La verificación es

# >>> test_raicesRuffini()

# Verificado

TAD de los polinomios: Reconocimiento de raíces por la regla de Ruffini

PorJosé A. Alonso 18-mayo-202310-mayo-2023

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

   esRaizRuffini :: Int -> Polinomio Int -> Bool

1	esRaizRuffini :: Int -> Polinomio Int -> Bool

tal que esRaizRuffini r p se verifica si r es una raiz de p, usando para ello el regla de Ruffini. Por ejemplo,

   λ> ejPol = consPol 4 6 (consPol 1 2 polCero)
   λ> ejPol
   6*x^4 + 2*x
   λ> esRaizRuffini 0 ejPol
   True
   λ> esRaizRuffini 1 ejPol
   False

λ> ejPol = consPol 4 6 (consPol 1 2 polCero)

λ> ejPol

6*x^4 + 2*x

λ> esRaizRuffini 0 ejPol

True

λ> esRaizRuffini 1 ejPol

False

Soluciones

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

Soluciones en Haskell

module Pol_Reconocimiento_de_raices_por_la_regla_de_Ruffini where

import TAD.Polinomio (Polinomio, consPol, polCero)
import Pol_Regla_de_Ruffini (restoRuffini)

esRaizRuffini :: Int -> Polinomio Int -> Bool
esRaizRuffini r p = restoRuffini r p == 0

module Pol_Reconocimiento_de_raices_por_la_regla_de_Ruffini where

import TAD.Polinomio (Polinomio, consPol, polCero)

import Pol_Regla_de_Ruffini (restoRuffini)

esRaizRuffini :: Int -> Polinomio Int -> Bool

esRaizRuffini r p = restoRuffini r p == 0

Soluciones en Python

from src.Pol_Regla_de_Ruffini import restoRuffini
from src.TAD.Polinomio import Polinomio, consPol, polCero


def esRaizRuffini(r: int, p: Polinomio[int]) -> bool:
    return restoRuffini(r, p) == 0

from src.Pol_Regla_de_Ruffini import restoRuffini

from src.TAD.Polinomio import Polinomio, consPol, polCero

def esRaizRuffini(r: int, p: Polinomio[int]) -> bool:

return restoRuffini(r, p) == 0

TAD de los polinomios: Regla de Ruffini

PorJosé A. Alonso 17-mayo-20239-mayo-2023

Usando el tipo abstracto de los polinomios, definir las funciones

   cocienteRuffini :: Int -> Polinomio Int -> Polinomio Int
   restoRuffini    :: Int -> Polinomio Int -> Int

1 2	cocienteRuffini :: Int -> Polinomio Int -> Polinomio Int restoRuffini :: Int -> Polinomio Int -> Int

tales que

cocienteRuffini r p es el cociente de dividir el polinomio p por el polinomio x-r. Por ejemplo:

     λ> ejPol = consPol 3 1 (consPol 2 2 (consPol 1 (-1) (consPol 0 (-2) polCero)))
     λ> ejPol
     x^3 + 2*x^2 + -1*x + -2
     λ> cocienteRuffini 2 ejPol
     x^2 + 4*x + 7
     λ> cocienteRuffini (-2) ejPol
     x^2 + -1
     λ> cocienteRuffini 3 ejPol
     x^2 + 5*x + 14

λ> ejPol = consPol 3 1 (consPol 2 2 (consPol 1 (-1) (consPol 0 (-2) polCero)))

λ> ejPol

x^3 + 2*x^2 + -1*x + -2

λ> cocienteRuffini 2 ejPol

x^2 + 4*x + 7

λ> cocienteRuffini (-2) ejPol

x^2 + -1

λ> cocienteRuffini 3 ejPol

x^2 + 5*x + 14

restoRuffini r p es el resto de dividir el polinomio p por el polinomio x-r. Por ejemplo,

     λ> restoRuffini 2 ejPol
     12
     λ> restoRuffini (-2) ejPol
     0
     λ> restoRuffini 3 ejPol
     40

λ> restoRuffini 2 ejPol

λ> restoRuffini (-2) ejPol

λ> restoRuffini 3 ejPol

Comprobar con QuickCheck que, dado un polinomio p y un número entero r, las funciones anteriores verifican la propiedad de la división euclídea.

Soluciones

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

Soluciones en Haskell

import TAD.Polinomio (Polinomio, consPol, polCero)
import Pol_Transformaciones_polinomios_densas (densaApolinomio,
                                               polinomioAdensa)
import Pol_Division_de_Ruffini_con_representacion_densa (ruffiniDensa)
import Pol_Producto_polinomios (multPol)
import Pol_Suma_de_polinomios (sumaPol)
import Pol_Crea_termino (creaTermino)
import Test.QuickCheck

-- 1ª definición de cocienteRuffini
-- ================================

cocienteRuffini :: Int -> Polinomio Int -> Polinomio Int
cocienteRuffini r p = densaApolinomio (init (ruffiniDensa r (polinomioAdensa p)))

-- 2ª definición de cocienteRuffini
-- ================================

cocienteRuffini2 :: Int -> Polinomio Int -> Polinomio Int
cocienteRuffini2 r = densaApolinomio . ruffiniDensa r . init . polinomioAdensa

-- 1ª definición de restoRuffini
-- =============================

restoRuffini :: Int -> Polinomio Int -> Int
restoRuffini r p = last (ruffiniDensa r (polinomioAdensa p))

-- 2ª definición de restoRuffini
-- =============================

restoRuffini2 :: Int -> Polinomio Int -> Int
restoRuffini2 r = last . ruffiniDensa r . polinomioAdensa

-- Comprobación de la propiedad
-- ============================

-- La propiedad es
prop_diviEuclidea :: Int -> Polinomio Int -> Bool
prop_diviEuclidea r p =
  p == sumaPol (multPol coci divi) rest
  where coci = cocienteRuffini r p
        divi = densaApolinomio [1,-r]
        rest = creaTermino 0 (restoRuffini r p)

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

import TAD.Polinomio (Polinomio, consPol, polCero)

import Pol_Transformaciones_polinomios_densas (densaApolinomio,

polinomioAdensa)

import Pol_Division_de_Ruffini_con_representacion_densa (ruffiniDensa)

import Pol_Producto_polinomios (multPol)

import Pol_Suma_de_polinomios (sumaPol)

import Pol_Crea_termino (creaTermino)

import Test.QuickCheck

-- 1ª definición de cocienteRuffini

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

cocienteRuffini :: Int -> Polinomio Int -> Polinomio Int

cocienteRuffini r p = densaApolinomio (init (ruffiniDensa r (polinomioAdensa p)))

-- 2ª definición de cocienteRuffini

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

cocienteRuffini2 :: Int -> Polinomio Int -> Polinomio Int

cocienteRuffini2 r = densaApolinomio . ruffiniDensa r . init . polinomioAdensa

-- 1ª definición de restoRuffini

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

restoRuffini :: Int -> Polinomio Int -> Int

restoRuffini r p = last (ruffiniDensa r (polinomioAdensa p))

-- 2ª definición de restoRuffini

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

restoRuffini2 :: Int -> Polinomio Int -> Int

restoRuffini2 r = last . ruffiniDensa r . polinomioAdensa

-- Comprobación de la propiedad

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

-- La propiedad es

prop_diviEuclidea :: Int -> Polinomio Int -> Bool

prop_diviEuclidea r p =

p == sumaPol (multPol coci divi) rest

where coci = cocienteRuffini r p

divi = densaApolinomio [1,-r]

rest = creaTermino 0 (restoRuffini r p)

-- La comprobación es

-- λ> quickCheck prop_diviEuclidea

-- +++ OK, passed 100 tests.

Soluciones en Python

from hypothesis import given
from hypothesis import strategies as st

from src.Pol_Crea_termino import creaTermino
from src.Pol_Division_de_Ruffini_con_representacion_densa import ruffiniDensa
from src.Pol_Producto_polinomios import multPol
from src.Pol_Suma_de_polinomios import sumaPol
from src.Pol_Transformaciones_polinomios_densas import (densaApolinomio,
                                                        polinomioAdensa)
from src.TAD.Polinomio import (Polinomio, consPol, esPolCero, polCero,
                               polinomioAleatorio)


def cocienteRuffini(r: int, p: Polinomio[int]) -> Polinomio[int]:
    if esPolCero(p):
        return polCero()
    return densaApolinomio(ruffiniDensa(r, polinomioAdensa(p))[:-1])

def restoRuffini(r: int, p: Polinomio[int]) -> int:
    if esPolCero(p):
        return 0
    return ruffiniDensa(r, polinomioAdensa(p))[-1]

# Comprobación de la propiedad
# ============================

# La propiedad es
@given(r=st.integers(), p=polinomioAleatorio())
def test_diviEuclidea (r: int, p: Polinomio[int]) -> None:
    coci = cocienteRuffini(r, p)
    divi = densaApolinomio([1, -r])
    rest = creaTermino(0, restoRuffini(r, p))
    assert p == sumaPol(multPol(coci, divi), rest)

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

from hypothesis import given

from hypothesis import strategies as st

from src.Pol_Crea_termino import creaTermino

from src.Pol_Division_de_Ruffini_con_representacion_densa import ruffiniDensa

from src.Pol_Producto_polinomios import multPol

from src.Pol_Suma_de_polinomios import sumaPol

from src.Pol_Transformaciones_polinomios_densas import (densaApolinomio,

polinomioAdensa)

from src.TAD.Polinomio import (Polinomio, consPol, esPolCero, polCero,

polinomioAleatorio)

def cocienteRuffini(r: int, p: Polinomio[int]) -> Polinomio[int]:

if esPolCero(p):

return polCero()

return densaApolinomio(ruffiniDensa(r, polinomioAdensa(p))[:-1])

def restoRuffini(r: int, p: Polinomio[int]) -> int:

if esPolCero(p):

return 0

return ruffiniDensa(r, polinomioAdensa(p))[-1]

# Comprobación de la propiedad

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

# La propiedad es

@given(r=st.integers(), p=polinomioAleatorio())

def test_diviEuclidea (r: int, p: Polinomio[int]) -> None:

coci = cocienteRuffini(r