El tipo abstracto de datos de los grafos en Haskell

Continuando la serie dedicada a los tipos de datos abstractos (TAD) en Haskell, hoy le toca el turno a los grafos. En los próximos, estudiaremos algoritmos sobre grafos basados en este TAD.

Informalmente, un grafo es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos.

El contenido del este artículo es el siguiente:

la signatura del TAD de los grafos;
la implementación de los grafos mediante vectores de adyacencia y
la implementación de los grafos mediante matrices de adyacencia.

La signatura del TAD de los grafos

Las signatura de las operaciones del TAD de los grafos son las siguientes:

creaGrafo  :: (Ix v,Num p) => Bool -> (v,v) -> [(v,v,p)] 
                              -> Grafo v p
adyacentes :: (Ix v,Num p) => (Grafo v p) -> v -> [v]
nodos      :: (Ix v,Num p) => (Grafo v p) -> [v]
aristasND  :: (Ix v,Num p) => (Grafo v p) -> [(v,v,p)]
aristasD   :: (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) => Bool -> (v,v) -> [(v,v,p)]

-> Grafo v p

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

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

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

aristasD :: (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

con el siguiente significado

(creaGrafo d cs as) es un grafo (dirigido si d es True y no dirigido en caso contrario), 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).
(adyacentes g v) es la lista de los vértices adyacentes al nodo v en el grafo g.
(nodos g) es la lista de todos los nodos del grafo g.
(aristasND g) es la lista de las aristas del grafo no dirigido g.
(aristasD g) es la lista de las aristas del grafo dirigido 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.

Por ejemplo,

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

crea el grafo

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

1 -------- 2

| \78 /|

| \ 32/ |

| \ / |

34| 5 |55

| / \ |

| /44 \ |

| / 93\|

3 -------- 4

Implementación de los grafos mediante vectores de adyacencia

module GrafoConVectorDeAdyacencia 
    (Grafo,
     creaGrafo,  -- (Ix v,Num p) => Bool -> (v,v) -> [(v,v,p)] -> Grafo v p
     adyacentes, -- (Ix v,Num p) => (Grafo v p) -> v -> [v]
     nodos,      -- (Ix v,Num p) => (Grafo v p) -> [v]
     aristasND,  -- (Ix v,Num p) => (Grafo v p) -> [(v,v,p)]
     aristasD,   -- (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

-- (Grafo v p) es un grafo con vértices de tipo v y pesos de tipo p.
type Grafo v p = Array v [(v,p)]

-- grafoVA es el grafo
--             12
--        1 -------- 2
--        | \78     /|
--        |  \   32/ |
--        |   \   /  |
--      34|     5    |55
--        |   /   \  |
--        |  /44   \ |
--        | /     93\|
--        3 -------- 4
--             61
-- representado mediante un vector de adyacencia.
grafoVA = 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)])]

-- (creaGrafo d cs as) es un grafo (dirigido si d es True y no dirigido
-- en caso contrario), 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) => Bool -> (v,v) -> [(v,v,p)] -> Grafo v p
creaGrafo d cs vs =
    accumArray 
     (\xs x -> xs++[x]) [] cs 
     ((if d then []
       else [(x2,(x1,p))|(x1,x2,p) <- vs, x1 /= x2]) ++
      [(x1,(x2,p)) | (x1,x2,p) <- vs])

-- grafoVA' es el mismo grafo que grafoVA pero creado con creaGrafo. Por
-- ejemplo, 
--    ghci> grafoVA'
--    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)])]
grafoVA' = creaGrafo False (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)]

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

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

-- (aristaEn g a) se verifica si a es una arista del grafo g. Por
-- ejemplo,
--    aristaEn grafoVA' (5,1)  ==  True
--    aristaEn grafoVA' (4,1)  ==  False
aristaEn :: (Ix v,Num p) => (Grafo v p) -> (v,v) -> Bool
aristaEn g (x,y) = elem y (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 grafoVA'  ==  78
peso :: (Ix v,Num p) => v -> v -> (Grafo v p) -> p
peso x y g = head [c | (a,c) <- g!x , a == y]

-- (aristasD g) es la lista de las aristas del grafo dirigido g. Por
-- ejemplo, 
--    ghci> aristasD grafoVA'
--    [(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)]
aristasD :: (Ix v,Num p) => (Grafo v p) -> [(v,v,p)]
aristasD g = [(v1,v2,w) | v1 <- nodos g , (v2,w) <- g!v1] 

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

100

101

102

103

104

105

106

107

108

109

module GrafoConVectorDeAdyacencia

(Grafo,

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

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

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

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

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

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

type Grafo v p = Array v [(v,p)]

-- grafoVA es el grafo

-- 12

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

-- | \78 /|

-- | \ 32/ |

-- | \ / |

-- 34| 5 |55

-- | / \ |

-- | /44 \ |

-- | / 93\|

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

-- 61

-- representado mediante un vector de adyacencia.

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

-- (creaGrafo d cs as) es un grafo (dirigido si d es True y no dirigido

-- en caso contrario), 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) => Bool -> (v,v) -> [(v,v,p)] -> Grafo v p

creaGrafo d cs vs =

accumArray

(\xs x -> xs++[x]) [] cs

((if d then []

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

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

-- grafoVA' es el mismo grafo que grafoVA pero creado con creaGrafo. Por

-- ejemplo,

-- ghci> grafoVA'

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

grafoVA' = creaGrafo False (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)]

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

-- el grafo g. Por ejemplo,

-- adyacentes grafoVA' 4 == [2,3,5]

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

adyacentes g v = map fst (g!v)

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

-- nodos grafoVA' == [1,2,3,4,5]

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

nodos g = indices g

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

-- ejemplo,

-- aristaEn grafoVA' (5,1) == True

-- aristaEn grafoVA' (4,1) == False

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

aristaEn g (x,y) = elem y (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 grafoVA' == 78

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

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

-- (aristasD g) es la lista de las aristas del grafo dirigido g. Por

-- ejemplo,

-- ghci> aristasD grafoVA'

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

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

aristasD g = [(v1,v2,w) | v1 <- nodos g , (v2,w) <- g!v1]

-- (aristasND g) es la lista de las aristas del grafo no dirigido g. Por

-- ejemplo,

-- ghci> aristasND grafoVA'

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

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

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

-- (4,5,93)]

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

aristasND g =

[(v1,v2,w) | v1 <- nodos g , (v2,w) <- g!v1 , v1 < v2]

Implementación de los grafos mediante matrices de adyacencia

module GrafoConMatrizDeAdyacencia 
    (Grafo,
     creaGrafo,  -- (Ix v,Num p) => Bool -> (v,v) -> [(v,v,p)] -> Grafo v p
     adyacentes, -- (Ix v,Num p) => (Grafo v p) -> v -> [v]
     nodos,      -- (Ix v,Num p) => (Grafo v p) -> [v]
     aristasND,  -- (Ix v,Num p) => (Grafo v p) -> [(v,v,p)]
     aristasD,   -- (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

-- (Grafo v p) es un grafo con vértices de tipo v y pesos de tipo p.
type Grafo v p = Array (v,v) (Maybe p)

-- grafoMA es el grafo
--             12
--        1 -------- 2
--        | \78     /|
--        |  \   32/ |
--        |   \   /  |
--      34|     5    |55
--        |   /   \  |
--        |  /44   \ |
--        | /     93\|
--        3 -------- 4
--             61
-- representado mediante una matriz de adyacencia.
grafoMA = array ((1, 1), (5, 5)) 
                [((1, 1),Nothing), ((1, 2),Just 10), ((1, 3),Just 20), 
                 ((1, 4),Nothing), ((1, 5),Nothing), ((2, 1),Nothing), 
                 ((2, 2),Nothing), ((2, 3),Nothing), ((2, 4),Just 30), 
                 ((2, 5),Nothing), ((3, 1),Nothing), ((3, 2),Nothing), 
                 ((3, 3),Nothing), ((3, 4),Just 40), ((3, 5),Nothing), 
                 ((4, 1),Nothing), ((4, 2),Nothing), ((4, 3),Nothing), 
                 ((4, 4),Nothing), ((4, 5),Just 50), ((5, 1),Nothing), 
                 ((5, 2),Nothing), ((5, 3),Nothing), ((5, 4),Nothing), 
                 ((5, 5),Nothing)]

-- (creaGrafo d cs as) es un grafo (dirigido si de es True y no dirigido
-- en caso contrario), 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) => Bool -> (v,v) -> [(v,v,p)] -> (Grafo v p)
creaGrafo dir cs@(l,u) as 
    = matrizVacia // 
      ([((x1,x2),Just w) | (x1,x2,w) <- as] ++
       if dir 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]

-- grafoMA' es el mismo grafo que grafoMA pero creado con creaGrafo. Por
-- ejemplo, 
--    ghci> grafoMA'
--    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)]
grafoMA' = creaGrafo False (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)]

-- (adyacentes g v) es la lista de los vértices adyacentes al nodo v en
-- el grafo g. Por ejemplo,
--    adyacentes grafoMA' 4  ==  [2,3,5]
adyacentes :: (Ix v,Num p) => (Grafo v p) -> v -> [v]
adyacentes g v1 = 
    [v2 | v2 <- nodos g, (g!(v1,v2)) /= Nothing]

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

-- (aristaEn g a) se verifica si a es una arista del grafo g. Por
-- ejemplo,
--    aristaEn grafoMA' (5,1)  ==  True
--    aristaEn grafoMA' (4,1)  ==  False
aristaEn :: (Ix v,Num p) => (Grafo v p) -> (v,v) -> Bool
aristaEn 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 grafoMA'  ==  78
peso :: (Ix v,Num p) => v -> v -> (Grafo v p) -> p
peso x y g  = w where (Just w) = g!(x,y)

-- (aristasD g) es la lista de las aristas del grafo dirigido g. Por
-- ejemplo, 
--    ghci> aristasD grafoMA'
--    [(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)]
aristasD :: (Ix v,Num p) => (Grafo v p) -> [(v,v,p)]
aristasD g = [(v1,v2,extrae(g!(v1,v2))) 
              | v1 <- nodos g, 
                v2 <- nodos g,
                aristaEn g (v1,v2)]
    where extrae (Just w) = w

-- (aristasND g) es la lista de las aristas del grafo no dirigido g. Por
-- ejemplo, 
--    ghci> aristasND grafoMA'
--    [(1,2,12),(1,3,34),(1,5,78),
--     (2,4,55),(2,5,32),
--     (3,4,61),(3,5,44),
--     (4,5,93)]
aristasND :: (Ix v,Num p) => (Grafo v p) -> [(v,v,p)]
aristasND g = [(v1,v2,extrae(g!(v1,v2)))
               | v1 <- nodos g, 
                 v2 <- range (v1,u),
                 aristaEn g (v1,v2)]
    where (_,(u,_)) = bounds g          
          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

module GrafoConMatrizDeAdyacencia

(Grafo,

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

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

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

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

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

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

type Grafo v p = Array (v,v) (Maybe p)

-- grafoMA es el grafo

-- 12

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

-- | \78 /|

-- | \ 32/ |

-- | \ / |

-- 34| 5 |55

-- | / \ |

-- | /44 \ |

-- | / 93\|

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

-- 61

-- representado mediante una matriz de adyacencia.

grafoMA = array ((1, 1), (5, 5))

[((1, 1),Nothing), ((1, 2),Just 10), ((1, 3),Just 20),

((1, 4),Nothing), ((1, 5),Nothing), ((2, 1),Nothing),

((2, 2),Nothing), ((2, 3),Nothing), ((2, 4),Just 30),

((2, 5),Nothing), ((3, 1),Nothing), ((3, 2),Nothing),

((3, 3),Nothing), ((3, 4),Just 40), ((3, 5),Nothing),

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

((4, 4),Nothing), ((4, 5),Just 50), ((5, 1),Nothing),

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

((5, 5),Nothing)]

-- (creaGrafo d cs as) es un grafo (dirigido si de es True y no dirigido

-- en caso contrario), 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) => Bool -> (v,v) -> [(v,v,p)] -> (Grafo v p)

creaGrafo dir cs@(l,u) as

= matrizVacia //

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

if dir 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]

-- grafoMA' es el mismo grafo que grafoMA pero creado con creaGrafo. Por

-- ejemplo,

-- ghci> grafoMA'

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

grafoMA' = creaGrafo False (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)]

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

-- el grafo g. Por ejemplo,

-- adyacentes grafoMA' 4 == [2,3,5]

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

adyacentes g v1 =

[v2 | v2 <- nodos g, (g!(v1,v2)) /= Nothing]

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

-- nodos grafoMA' == [1,2,3,4,5]

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

nodos g = range (l,u)

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

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

-- ejemplo,

-- aristaEn grafoMA' (5,1) == True

-- aristaEn grafoMA' (4,1) == False

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

aristaEn 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 grafoMA' == 78

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

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

-- (aristasD g) es la lista de las aristas del grafo dirigido g. Por

-- ejemplo,

-- ghci> aristasD grafoMA'

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

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

aristasD g = [(v1,v2,extrae(g!(v1,v2)))

| v1 <- nodos g,

v2 <- nodos g,

aristaEn g (v1,v2)]

where extrae (Just w) = w

-- (aristasND g) es la lista de las aristas del grafo no dirigido g. Por

-- ejemplo,

-- ghci> aristasND grafoMA'

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

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

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

-- (4,5,93)]

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

aristasND g = [(v1,v2,extrae(g!(v1,v2)))

| v1 <- nodos g,

v2 <- range (v1,u),

aristaEn g (v1,v2)]

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

extrae (Just w) = w

El objetivo de la serie es la elaboración de los temas de TAD del curso de Informática del Grado en Matemáticas.

La signatura del TAD de los grafos

Implementación de los grafos mediante vectores de adyacencia

Implementación de los grafos mediante matrices de adyacencia

Se puede imprimir o compartir con