Menu Close

Día: 23 de mayo de 2023

El tipo abstracto de datos de los grafos

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

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

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

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

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]

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]

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"

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)

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

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

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