Grafos

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

Caminos en un grafo

PorJosé A. Alonso 28-mayo-20204-junio-2020

Definir las funciones

   grafo   :: [(Int,Int)] -> Grafo Int Int
   caminos :: Grafo Int Int -> Int -> Int -> [[Int]]

1 2	grafo :: [(Int,Int)] -> Grafo Int Int caminos :: Grafo Int Int -> Int -> Int -> [[Int]]

tales que

(grafo as) es el grafo no dirigido definido cuyas aristas son as. Por ejemplo,

     ghci> grafo [(2,4),(4,5)]
     G ND (array (2,5) [(2,[(4,0)]),(3,[]),(4,[(2,0),(5,0)]),(5,[(4,0)])])

1 2	ghci> grafo [(2,4),(4,5)] G ND (array (2,5) [(2,[(4,0)]),(3,[]),(4,[(2,0),(5,0)]),(5,[(4,0)])])

(caminos g a b) es la lista los caminos en el grafo g desde a hasta b sin pasar dos veces por el mismo nodo. Por ejemplo,

     ghci> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 7)
     [[1,3,5,7],[1,3,7]]
     ghci> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 2 7)
     [[2,5,3,7],[2,5,7]]
     ghci> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 2)
     [[1,3,5,2],[1,3,7,5,2]]
     ghci> caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 4
     []
     ghci> length (caminos (grafo [(i,j) | i <- [1..10], j <- [i..10]]) 1 10)
     109601

ghci> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 7)

[[1,3,5,7],[1,3,7]]

ghci> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 2 7)

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

ghci> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 2)

[[1,3,5,2],[1,3,7,5,2]]

ghci> caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 4

[]

ghci> length (caminos (grafo [(i,j) | i <- [1..10], j <- [i..10]]) 1 10)

109601

Soluciones

import Data.List (sort)
import I1M.Grafo
import I1M.BusquedaEnEspaciosDeEstados

grafo :: [(Int,Int)] -> Grafo Int Int
grafo as = creaGrafo ND (m,n) [(x,y,0) | (x,y) <- as]
  where ns = map fst as ++ map snd as
        m  = minimum ns
        n  = maximum ns

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

caminos :: Grafo Int Int -> Int -> Int -> [[Int]]
caminos g a b = aux [[b]] where 
  aux [] = []
  aux ((x:xs):yss)
    | x == a    = (x:xs) : aux yss
    | otherwise = aux ([z:x:xs | z <- adyacentes g x
                               , z `notElem` (x:xs)] 
                       ++ yss) 

-- 2ª solución (mediante espacio de estados)
-- =========================================

caminos2 :: Grafo Int Int -> Int -> Int -> [[Int]]
caminos2 g a b = buscaEE sucesores esFinal inicial
  where inicial          = [b]
        sucesores (x:xs) = [z:x:xs | z <- adyacentes g x
                                   , z `notElem` (x:xs)] 
        esFinal (x:xs)   = x == a

-- Comparación de eficiencia
-- =========================

--    ghci> length (caminos (grafo [(i,j) | i <- [1..10], j <- [i..10]]) 1 10)
--    109601
--    (3.57 secs, 500533816 bytes)
--    ghci> length (caminos2 (grafo [(i,j) | i <- [1..10], j <- [i..10]]) 1 10)
--    109601
--    (3.53 secs, 470814096 bytes)

import Data.List (sort)

import I1M.Grafo

import I1M.BusquedaEnEspaciosDeEstados

grafo :: [(Int,Int)] -> Grafo Int Int

grafo as = creaGrafo ND (m,n) [(x,y,0) | (x,y) <- as]

where ns = map fst as ++ map snd as

m = minimum ns

n = maximum ns

-- 1ª solución

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

caminos :: Grafo Int Int -> Int -> Int -> [[Int]]

caminos g a b = aux [[b]] where

aux [] = []

aux ((x:xs):yss)

| x == a = (x:xs) : aux yss

| otherwise = aux ([z:x:xs | z <- adyacentes g x

, z `notElem` (x:xs)]

++ yss)

-- 2ª solución (mediante espacio de estados)

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

caminos2 :: Grafo Int Int -> Int -> Int -> [[Int]]

caminos2 g a b = buscaEE sucesores esFinal inicial

where inicial = [b]

sucesores (x:xs) = [z:x:xs | z <- adyacentes g x

, z `notElem` (x:xs)]

esFinal (x:xs) = x == a

-- Comparación de eficiencia

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

-- ghci> length (caminos (grafo [(i,j) | i <- [1..10], j <- [i..10]]) 1 10)

-- 109601

-- (3.57 secs, 500533816 bytes)

-- ghci> length (caminos2 (grafo [(i,j) | i <- [1..10], j <- [i..10]]) 1 10)

-- 109601

-- (3.53 secs, 470814096 bytes)

Grafo de divisibilidad

PorJosé A. Alonso 3-junio-201926-marzo-2022

El grafo de divisibilidad de orden n es el grafo cuyos nodos son los números naturales entre 1 y n, cuyas aristas son los pares (x,y) tales que x divide a y o y divide a x. El coste de cada arista es el cociente entre su mayor y menor elemento.

Definir las siguientes funciones:

   grafoDivisibilidad :: Int -> Grafo Int Int
   coste              :: Int -> Int

1 2	grafoDivisibilidad :: Int -> Grafo Int Int coste :: Int -> Int

tales que

(grafoDivisibilidad n) es el grafo de divisibilidad de orden n. Por ejemplo,

      λ> grafoDivisibilidad 12
      G ND (array (1,12)
                  [(1,[(2,2),(3,3),(4,4),(5,5),(6,6),(7,7),
                       (8,8),(9,9),(10,10),(11,11),(12,12)]),
                   (2,[(1,2),(4,2),(6,3),(8,4),(10,5),(12,6)]),
                   (3,[(1,3),(6,2),(9,3),(12,4)]),
                   (4,[(1,4),(2,2),(8,2),(12,3)]),
                   (5,[(1,5),(10,2)]),
                   (6,[(1,6),(2,3),(3,2),(12,2)]),
                   (7,[(1,7)]),
                   (8,[(1,8),(2,4),(4,2)]),
                   (9,[(1,9),(3,3)]),
                   (10,[(1,10),(2,5),(5,2)]),
                   (11,[(1,11)]),
                   (12,[(1,12),(2,6),(3,4),(4,3),(6,2)])])

λ> grafoDivisibilidad 12

G ND (array (1,12)

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

(8,8),(9,9),(10,10),(11,11),(12,12)]),

(2,[(1,2),(4,2),(6,3),(8,4),(10,5),(12,6)]),

(3,[(1,3),(6,2),(9,3),(12,4)]),

(4,[(1,4),(2,2),(8,2),(12,3)]),

(5,[(1,5),(10,2)]),

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

(7,[(1,7)]),

(8,[(1,8),(2,4),(4,2)]),

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

(10,[(1,10),(2,5),(5,2)]),

(11,[(1,11)]),

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

(coste n) es el coste del árbol de expansión mínimo del grafo de divisibilidad de orden n. Por ejemplo,

      coste 12        ==  41
      coste 3000      ==  605305
      coste (2*10^5)  ==  1711798835

coste 12 == 41

coste 3000 == 605305

coste (2*10^5) == 1711798835

Soluciones

[schedule expon=’2019-06-10′ expat=»06:00″]

Las soluciones se pueden escribir en los comentarios hasta el 10 de junio.
El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>

Pensamiento

Malos sueños he.
Me despertaré.

Antonio Machado

[/schedule]

[schedule on=’2019-06-10′ at=»06:00″]

import Data.Ix
import Data.List (delete, sort)
import qualified Data.Set as S
import I1M.Grafo
import I1M.Tabla
import Data.Numbers.Primes (primeFactors)

-- Definición de grafoDivisibilidad
-- ================================

grafoDivisibilidad :: Int -> Grafo Int Int
grafoDivisibilidad n =
  creaGrafo ND (1,n) [(x,y,y `div` x) | y <- [1..n]
                                      , x <- [1..y-1]
                                      , y `mod` x == 0]

-- 1ª definición de coste (con el algoritmo de Kruskal)
-- ====================================================

coste1 :: Int -> Int
coste1 n = sum [p | (p,x,y) <- kruskal (grafoDivisibilidad n)]

-- (kruskal g) es el árbol de expansión mínimo del grafo g calculado
-- mediante el algoritmo de Kruskal. Por ejemplo,
--    λ> kruskal (grafoDivisibilidad 12)
--    [(11,1,11),(7,1,7),(5,1,5),(3,3,9),(3,1,3),(2,6,12),(2,5,10),
--     (2,4,8),(2,3,6),(2,2,4),(2,1,2)]
kruskal :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)]
kruskal g = kruskal' cola                           -- Cola ordenada
                     (tabla [(x,x) | x <- nodos g]) -- Tabla de raices
                     []                             -- Árbol de expansión
                     (length (nodos g) - 1)         -- Aristas por
                                                    -- colocar
    where cola = sort [(p,x,y) | (x,y,p) <- aristas g]

kruskal' ((p,x,y):as) t ae n 
  | n == 0      = ae
  | actualizado = kruskal' as t' ((p,x,y):ae) (n-1)
  | otherwise   = kruskal' as t  ae           n
  where (actualizado,t') = buscaActualiza (x,y) t

-- (raiz t n) es la raíz de n en la tabla t. Por ejemplo,
--    raiz (crea [(1,1),(3,1),(4,3),(5,4),(2,6),(6,6)]) 5  == 1
--    raiz (crea [(1,1),(3,1),(4,3),(5,4),(2,6),(6,6)]) 2  == 6
raiz:: Eq n => Tabla n n -> n -> n
raiz t x | v == x    = v
         | otherwise = raiz t v
         where v = valor t x

-- (buscaActualiza a t) es el par formado por False y la tabla t, si los
-- dos vértices de la arista a tienen la misma raíz en t y el par
-- formado por True y la tabla obtenida añadiéndole a t la arista
-- formada por el vértice de a de mayor raíz y la raíz del vértice de
-- a de menor raíz. Por ejemplo,
--    ghci> let t = crea [(1,1),(2,2),(3,1),(4,1)]
--    ghci> buscaActualiza (2,3) t
--    (True,Tbl [(1,1),(2,1),(3,1),(4,1)])
--    ghci> buscaActualiza (3,4) t
--    (False,Tbl [(1,1),(2,2),(3,1),(4,1)])
buscaActualiza :: (Eq n, Ord n) => (n,n) -> Tabla n n -> (Bool,Tabla n n)
buscaActualiza (x,y) t 
  | x' == y'  = (False, t) 
  | y' <  x'  = (True, modifica (x,y') t)
  | otherwise = (True, modifica (y,x') t)
  where x' = raiz t x 
        y' = raiz t y

-- 2ª definición de coste (con el algoritmo de Prim)
-- =================================================

coste2 :: Int -> Int
coste2 n = sum [p | (p,x,y) <- prim (grafoDivisibilidad n)]

-- (prim g) es el árbol de expansión mínimo del grafo g calculado
-- mediante el algoritmo de Prim. Por ejemplo,
--    λ> prim (grafoDivisibilidad 12)
--    [(11,1,11),(7,1,7),(2,5,10),(5,1,5),(3,3,9),(2,6,12),(2,3,6),
--     (3,1,3),(2,4,8),(2,2,4),(2,1,2)]
prim :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)]
prim g = prim' [n]              -- Nodos colocados
               ns               -- Nodos por colocar 
               []               -- Árbol de expansión
               (aristas g)      -- Aristas del grafo
         where (n:ns) = nodos g

prim' t [] ae as = ae
prim' t r  ae as = prim' (v':t) (delete v' r) (e:ae) as
  where e@(c,u', v') = minimum [(c,u,v)| (u,v,c) <- as,
                                         u `elem` t, 
                                         v `elem` r]

-- 3ª definición de coste (con el algoritmo de Prim con conjuntos)
-- ===============================================================

coste3 :: Int -> Int
coste3 n = sum [p | (p,x,y) <- prim2 (grafoDivisibilidad n)]

-- (prim2 g) es el árbol de expansión mínimo del grafo g calculado
-- mediante el algoritmo de Prim. Por ejemplo,
--    λ> prim2 (grafoDivisibilidad 12)
--    [(11,1,11),(7,1,7),(2,5,10),(5,1,5),(3,3,9),(2,6,12),(2,3,6),
--     (3,1,3),(2,4,8),(2,2,4),(2,1,2)]
prim2 :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)]
prim2 g = prim2' (S.singleton n)  -- Nodos colocados
                 (S.fromList ns)  -- Nodos por colocar 
                 []               -- Árbol de expansión
                 (aristas g)      -- Aristas del grafo
  where (n:ns) = nodos g

prim2' t r ae as
  | S.null r  = ae
  | otherwise = prim2' (S.insert v' t)
                       (S.delete v' r)
                       (e:ae)
                       as
  where e@(c,u', v') = minimum [(c,u,v)| (u,v,c) <- as,
                                         S.member u t, 
                                         S.member v r]

-- 4ª definición de coste
-- ======================

coste4 :: Int -> Int
coste4 n = sum [head (primeFactors x) | x <- [2..n]]

-- Comparación de eficiencia
-- =========================

--    λ> coste1 400
--    14923
--    (0.08 secs, 31,336,440 bytes)
--    λ> coste2 400
--    14923
--    (4.54 secs, 220,745,608 bytes)
--    λ> coste3 400
--    14923
--    (0.69 secs, 217,031,144 bytes)
--    λ> coste4 400
--    14923
--    (0.01 secs, 2,192,336 bytes)
--    
--    λ> coste1 2000
--    284105
--    (2.09 secs, 842,601,904 bytes)
--    λ> coste4 2000
--    284105
--    (0.02 secs, 14,586,888 bytes)

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

import Data.Ix

import Data.List (delete, sort)

import qualified Data.Set as S

import I1M.Grafo

import I1M.Tabla

import Data.Numbers.Primes (primeFactors)

-- Definición de grafoDivisibilidad

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

grafoDivisibilidad :: Int -> Grafo Int Int

grafoDivisibilidad n =

creaGrafo ND (1,n) [(x,y,y `div` x) | y <- [1..n]

, x <- [1..y-1]

, y `mod` x == 0]

-- 1ª definición de coste (con el algoritmo de Kruskal)

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

coste1 :: Int -> Int

coste1 n = sum [p | (p,x,y) <- kruskal (grafoDivisibilidad n)]

-- (kruskal g) es el árbol de expansión mínimo del grafo g calculado

-- mediante el algoritmo de Kruskal. Por ejemplo,

-- λ> kruskal (grafoDivisibilidad 12)

-- [(11,1,11),(7,1,7),(5,1,5),(3,3,9),(3,1,3),(2,6,12),(2,5,10),

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

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

kruskal g = kruskal' cola -- Cola ordenada

(tabla [(x,x) | x <- nodos g]) -- Tabla de raices

[] -- Árbol de expansión

(length (nodos g) - 1) -- Aristas por

-- colocar

where cola = sort [(p,x,y) | (x,y,p) <- aristas g]

kruskal' ((p,x,y):as) t ae n

| n == 0 = ae

| actualizado = kruskal' as t' ((p,x,y):ae) (n-1)

| otherwise = kruskal' as t ae n

where (actualizado,t') = buscaActualiza (x,y) t

-- (raiz t n) es la raíz de n en la tabla t. Por ejemplo,

-- raiz (crea [(1,1),(3,1),(4,3),(5,4),(2,6),(6,6)]) 5 == 1

-- raiz (crea [(1,1),(3,1),(4,3),(5,4),(2,6),(6,6)]) 2 == 6

raiz:: Eq n => Tabla n n -> n -> n

raiz t x | v == x = v

| otherwise = raiz t v

where v = valor t x

-- (buscaActualiza a t) es el par formado por False y la tabla t, si los

-- dos vértices de la arista a tienen la misma raíz en t y el par

-- formado por True y la tabla obtenida añadiéndole a t la arista

-- formada por el vértice de a de mayor raíz y la raíz del vértice de

-- a de menor raíz. Por ejemplo,

-- ghci> let t = crea [(1,1),(2,2),(3,1),(4,1)]

-- ghci> buscaActualiza (2,3) t

-- (True,Tbl [(1,1),(2,1),(3,1),(4,1)])

-- ghci> buscaActualiza (3,4) t

-- (False,Tbl [(1,1),(2,2),(3,1),(4,1)])

buscaActualiza :: (Eq n, Ord n) => (n,n) -> Tabla n n -> (Bool,Tabla n n)

buscaActualiza (x,y) t

| x' == y' = (False, t)

| y' < x' = (True, modifica (x,y') t)

| otherwise = (True, modifica (y,x') t)

where x' = raiz t x

y' = raiz t y

-- 2ª definición de coste (con el algoritmo de Prim)

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

coste2 :: Int -> Int

coste2 n = sum [p | (p,x,y) <- prim (grafoDivisibilidad n)]

-- (prim g) es el árbol de expansión mínimo del grafo g calculado

-- mediante el algoritmo de Prim. Por ejemplo,

-- λ> prim (grafoDivisibilidad 12)

-- [(11,1,11),(7,1,7),(2,5,10),(5,1,5),(3,3,9),(2,6,12),(2,3,6),

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

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

prim g = prim' [n] -- Nodos colocados

ns -- Nodos por colocar

[] -- Árbol de expansión

(aristas g) -- Aristas del grafo

where (n:ns) = nodos g

prim' t [] ae as = ae

prim' t r ae as = prim' (v':t) (delete v' r) (e:ae) as

where e@(c,u', v') = minimum [(c,u,v)| (u,v,c) <- as,

u `elem` t,

v `elem` r]

-- 3ª definición de coste (con el algoritmo de Prim con conjuntos)

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

coste3 :: Int -> Int

coste3 n = sum [p | (p,x,y) <- prim2 (grafoDivisibilidad n)]

-- (prim2 g) es el árbol de expansión mínimo del grafo g calculado

-- mediante el algoritmo de Prim. Por ejemplo,

-- λ> prim2 (grafoDivisibilidad 12)

-- [(11,1,11),(7,1,7),(2,5,10),(5,1,5),(3,3,9),(2,6,12),(2,3,6),

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

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

prim2 g = prim2' (S.singleton n) -- Nodos colocados

(S.fromList ns) -- Nodos por colocar

[] -- Árbol de expansión

(aristas g) -- Aristas del grafo

where (n:ns) = nodos g

prim2' t r ae as

| S.null r = ae

| otherwise = prim2' (S.insert v' t)

(S.delete v' r)

(e:ae)

where e@(c,u', v') = minimum [(c,u,v)| (u,v,c) <- as,

S.member u t,

S.member v r]

-- 4ª definición de coste

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

coste4 :: Int -> Int

coste4 n = sum [head (primeFactors x) | x <- [2..n]]

-- Comparación de eficiencia

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

-- λ> coste1 400

-- 14923

-- (0.08 secs, 31,336,440 bytes)

-- λ> coste2 400

-- 14923

-- (4.54 secs, 220,745,608 bytes)

-- λ> coste3 400

-- 14923

-- (0.69 secs, 217,031,144 bytes)

-- λ> coste4 400

-- 14923

-- (0.01 secs, 2,192,336 bytes)

-- λ> coste1 2000

-- 284105

-- (2.09 secs, 842,601,904 bytes)

-- λ> coste4 2000

-- 284105

-- (0.02 secs, 14,586,888 bytes)

[/schedule]

TAD de los grafos: Grafos ciclos

TAD de los grafos: Grafos completos

El tipo abstracto de datos de los grafos

1. El tipo abstracto de datos de los grafos

2. Los grafos en Haskell

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

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

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

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

3. Los grafos en Python

3.1. El tipo abstracto de los grafos en Python

3.2. Implementación de los grafos mediante listas

Caminos en un grafo

Soluciones

Grafo de divisibilidad

Soluciones

Pensamiento

Entradas recientes

Buscar

Correo electrónico