I1M2013: El tipo abstracto de datos de grafos en Haskell

En la clase de hoy de Informática de 1º del Grado en Matemáticas hemos estudiado el tipo abstracto de datos de los grafos y dos de sus implementaciones en Haskell: mediante vectores y matrices de adyacencia.

Además, hemos estudiado los algoritmos de recorrido de los grafos en profundidad y en anchura.

Las transparencias usadas en la clase son las páginas 1-39 del tema 22:

El código de la implementación de grafos mediante vectores de adyacencia es

module GrafoConVectorDeAdyacencia 
    (Orientacion (..),
     Grafo,
     creaGrafo,  -- (Ix v,Num p) => Orientacion -> (v,v) -> [(v,v,p)] -> 
                 --                 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
    ) where

-- ---------------------------------------------------------------------
-- Librerías auxiliares                                               --
-- ---------------------------------------------------------------------

import Data.Array

-- 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, Show)

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

-- 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,
--    ghci> ejGrafoND
--    G ND array (1,5) [(1,[(2,12),(3,34),(5,78)]),
--                      (2,[(1,12),(4,55),(5,32)]),
--                      (3,[(1,34),(4,61),(5,44)]),
--                      (4,[(2,55),(3,61),(5,93)]),
--                      (5,[(1,78),(2,32),(3,44),(4,93)])])
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,
--    ghci> ejGrafoD
--    G D array (1,5) [(1,[(2,12),(3,34),(5,78)]),
--                     (2,[(4,55),(5,32)]),
--                     (3,[(4,61),(5,44)]),
--                     (4,[(5,93)]),
--                     (5,[])])
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, 
--    ghci> 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)] 
--    ghci> 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

module GrafoConVectorDeAdyacencia

(Orientacion (..),

Grafo,

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

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

) where

-- ---------------------------------------------------------------------

-- Librerías auxiliares --

-- ---------------------------------------------------------------------

import Data.Array

-- 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, Show)

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

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

-- ghci> ejGrafoND

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

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

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

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

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

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,

-- ghci> ejGrafoD

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

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

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

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

-- (5,[])])

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,

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

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

El código de la implementación de grafos mediante matrices de adyacencia es

module GrafoConMatrizDeAdyacencia
    (Orientacion (..),
     Grafo,
     creaGrafo,  -- (Ix v,Num p) => Orientacion -> (v,v) -> [(v,v,p)] -> 
                 --                 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
    ) where

-- ---------------------------------------------------------------------
-- Librerías auxiliares                                               --
-- ---------------------------------------------------------------------

import Data.Array

-- 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, Show)

-- (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 o cs@(l,u) as 
    = G o (matrizVacia // 
            ([((x1,x2),Just w) | (x1,x2,w) <- as] ++
             if o == D then []
             else [((x2,x1),Just w) | (x1,x2,w) <- as, x1 /= x2]))
      where
      matrizVacia = array ((l,l),(u,u)) 
                          [((x1,x2),Nothing) | x1 <- range cs, 
                                               x2 <- range cs]

-- ejGrafoND es el grafo
--             12
--        1 -------- 2
--        | \78     /|
--        |  \   32/ |
--        |   \   /  |
--      34|     5    |55
--        |   /   \  |
--        |  /44   \ |
--        | /     93\|
--        3 -------- 4
--             61
-- representado mediante una matriz de adyacencia.
--    ghci> 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 = 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,
--    ghci> 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 = 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) => (Grafo v p) -> v -> [v]
adyacentes (G o g) v = 
    [v' | v' <- nodos (G o g), (g!(v,v')) /= Nothing]

-- (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) => (Grafo v p) -> (v,v) -> Bool
aristaEn (G _o g) (x,y)= (g!(x,y)) /= Nothing

-- (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, 
--    ghci> 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)] 
--    ghci> 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 o e) = [(v1,v2,extrae(e!(v1,v2))) 
                     | v1 <- nodos g, 
                       v2 <- nodos g,
                       aristaEn g (v1,v2)]
    where extrae (Just w) = w

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

module GrafoConMatrizDeAdyacencia

(Orientacion (..),

Grafo,

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

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

) where

-- ---------------------------------------------------------------------

-- Librerías auxiliares --

-- ---------------------------------------------------------------------

import Data.Array

-- 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, Show)

-- (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 o cs@(l,u) as

= G o (matrizVacia //

([((x1,x2),Just w) | (x1,x2,w) <- as] ++

if o == D then []

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

where

matrizVacia = array ((l,l),(u,u))

[((x1,x2),Nothing) | x1 <- range cs,

x2 <- range cs]

-- ejGrafoND es el grafo

-- 12

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

-- | \78 /|

-- | \ 32/ |

-- | \ / |

-- 34| 5 |55

-- | / \ |

-- | /44 \ |

-- | / 93\|

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

-- 61

-- representado mediante una matriz de adyacencia.

-- ghci> 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 = 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,

-- ghci> 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 = 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) => (Grafo v p) -> v -> [v]

adyacentes (G o g) v =

[v' | v' <- nodos (G o g), (g!(v,v')) /= Nothing]

-- (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) => (Grafo v p) -> (v,v) -> Bool

aristaEn (G _o g) (x,y)= (g!(x,y)) /= Nothing

-- (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,

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

-- ghci> 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 o e) = [(v1,v2,extrae(e!(v1,v2)))

| v1 <- nodos g,

v2 <- nodos g,

aristaEn g (v1,v2)]

where extrae (Just w) = w

El código del recorridos de grafos en profundidad es

module RecorridoEnProfundidad where

-- ---------------------------------------------------------------------
-- Librerías auxiliares                                               --
-- ---------------------------------------------------------------------

-- Nota: Elegir una implementación de los grafos.
import GrafoConVectorDeAdyacencia
-- import GrafoConMatrizDeAdyacencia

-- ---------------------------------------------------------------------
-- Ejemplo de grafo                                                   --
-- ---------------------------------------------------------------------

-- g es el grafo
--    +---> 2 <---+
--    |           |
--    |           |
--    1 --> 3 --> 6 --> 5
--    |                 |
--    |                 |
--    +---> 4 <---------+

g = creaGrafo D (1,6) 
              [(1,2,0),(1,3,0),(1,4,0),(3,6,0),(5,4,0),(6,2,0),(6,5,0)]

-- ---------------------------------------------------------------------
-- Recorrido en profundidad                                            --
-- ---------------------------------------------------------------------

-- (recorridoEnProfundidad i g) es el recorrido en profundidad del grafo g
-- desde el vértice i. Por ejemplo,
--    recorridoEnProfundidad 1 g  ==  [1,2,3,6,5,4]
recorridoEnProfundidad i g = rp [i] []
    where 
      rp [] vis    = vis
      rp (c:cs) vis 
          | c `elem` vis = rp cs vis
          | otherwise    = rp ((adyacentes g c)++cs) (vis++[c])

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

-- ---------------------------------------------------------------------
-- Recorrido en profundidad con acumuladores                           --
-- ---------------------------------------------------------------------

-- (recorridoEnProfundidad' i g) es el recorrido en profundidad del
-- grafo g desde el vértice i, usando la lista de los visitados como
-- acumulador. Por ejemplo, 
--    recorridoEnProfundidad' 1 g  ==  [1,2,3,6,5,4]
recorridoEnProfundidad' i g = reverse (rp [i] [])
    where
      rp [] vis     = vis
      rp (c:cs) vis 
          | c `elem` vis = rp cs vis
          | otherwise    = rp ((adyacentes g c)++cs) (c:vis)

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

module RecorridoEnProfundidad where

-- ---------------------------------------------------------------------

-- Librerías auxiliares --

-- ---------------------------------------------------------------------

-- Nota: Elegir una implementación de los grafos.

import GrafoConVectorDeAdyacencia

-- import GrafoConMatrizDeAdyacencia

-- ---------------------------------------------------------------------

-- Ejemplo de grafo --

-- ---------------------------------------------------------------------

-- g es el grafo

-- +---> 2 <---+

-- | |

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

-- | |

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

g = creaGrafo D (1,6)

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

-- ---------------------------------------------------------------------

-- Recorrido en profundidad --

-- ---------------------------------------------------------------------

-- (recorridoEnProfundidad i g) es el recorrido en profundidad del grafo g

-- desde el vértice i. Por ejemplo,

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

recorridoEnProfundidad i g = rp [i] []

where

rp [] vis = vis

rp (c:cs) vis

| c `elem` vis = rp cs vis

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

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

-- recorridoEnProfundidad 1 g

-- = rp [1] []

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

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

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

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

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

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

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

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

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

-- ---------------------------------------------------------------------

-- Recorrido en profundidad con acumuladores --

-- ---------------------------------------------------------------------

-- (recorridoEnProfundidad' i g) es el recorrido en profundidad del

-- grafo g desde el vértice i, usando la lista de los visitados como

-- acumulador. Por ejemplo,

-- recorridoEnProfundidad' 1 g == [1,2,3,6,5,4]

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

where

rp [] vis = vis

rp (c:cs) vis

| c `elem` vis = rp cs vis

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

-- Traza del cálculo de (recorridoEnProfundidad' 1 g)

-- RecorridoEnProfundidad' 1 g

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

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

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

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

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

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

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

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

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

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

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

El código del recorridos de grafos en anchura es

module RecorridoEnAnchura where

-- ---------------------------------------------------------------------
-- Librerías auxiliares                                               --
-- ---------------------------------------------------------------------

-- Nota: Elegir una implementación de los grafos.
import GrafoConVectorDeAdyacencia
-- import GrafoConMatrizDeAdyacencia

-- ---------------------------------------------------------------------
-- Ejemplo de grafo                                                   --
-- ---------------------------------------------------------------------

-- g es el grafo
--    +---> 2 <---+
--    |           |
--    |           |
--    1 --> 3 --> 6 --> 5
--    |                 |
--    |                 |
--    +---> 4 <---------+
g = creaGrafo D (1,6) 
              [(1,2,0),(1,3,0),(1,4,0),(3,6,0),(5,4,0),(6,2,0),(6,5,0)]

-- ---------------------------------------------------------------------
-- Recorrido en anchura con colas                                      --
-- ---------------------------------------------------------------------

-- (recorridoEnAnchura i g) es el recorrido en anchura del grafo g
-- desde el vértice i, usando colas. Por ejemplo, 
--    recorridoEnAnchura 1 g  ==  [1,4,3,2,6,5]
recorridoEnAnchura i g = reverse (ra [i] [])
    where 
      ra [] vis    = vis
      ra (c:cs) vis 
          | c `elem` vis = ra cs vis
          | otherwise    = ra (cs ++ adyacentes g c) (c:vis)

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

module RecorridoEnAnchura where

-- ---------------------------------------------------------------------

-- Librerías auxiliares --

-- ---------------------------------------------------------------------

-- Nota: Elegir una implementación de los grafos.

import GrafoConVectorDeAdyacencia

-- import GrafoConMatrizDeAdyacencia

-- ---------------------------------------------------------------------

-- Ejemplo de grafo --

-- ---------------------------------------------------------------------

-- g es el grafo

-- +---> 2 <---+

-- | |

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

-- | |

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

g = creaGrafo D (1,6)

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

-- ---------------------------------------------------------------------

-- Recorrido en anchura con colas --

-- ---------------------------------------------------------------------

-- (recorridoEnAnchura i g) es el recorrido en anchura del grafo g

-- desde el vértice i, usando colas. Por ejemplo,

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

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

where

ra [] vis = vis

ra (c:cs) vis

| c `elem` vis = ra cs vis

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

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

-- RecorridoEnAnchura 1 g

-- = ra [1] []

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

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

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

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

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

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

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

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

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

Se puede imprimir o compartir con