I1M2013: Ejercicios con el TAD de grafos en Haskell

En la clase de hoy de Informática de 1º del Grado en Matemáticas hemos comentado las soluciones de los 4 primeros ejercicios sobre grafos de la 28ª relación.

Los ejercicios y su solución se muestran a continuación

-- ---------------------------------------------------------------------
-- Introducción                                                       --
-- ---------------------------------------------------------------------

-- El objetivo de esta relación de ejercicios es definir funciones sobre 
-- el TAD de los grafos, utilizando las implementaciones estudiadas
-- en el tema 22 que se pueden descargar desde 
--    http://www.cs.us.es/~jalonso/cursos/i1m-13/codigos.zip
--
-- Las transparencias del tema 22 se encuentran en
--    http://www.cs.us.es/~jalonso/cursos/i1m-13/temas/tema-22.pdf

-- ---------------------------------------------------------------------
-- Importación de librerías                                           --
-- ---------------------------------------------------------------------

{-# LANGUAGE FlexibleInstances, TypeSynonymInstances #-}

import Data.Array
import Data.List (nub)
import Test.QuickCheck

-- Hay que seleccionar una implementación del TAD de los grafos
import GrafoConVectorDeAdyacencia 
-- import GrafoConMatrizDeAdyacencia 
-- import Rel_29_sol

-- ---------------------------------------------------------------------
-- Ejemplos                                                           --
-- ---------------------------------------------------------------------

-- Para los ejemplos se usarán los siguientes grafos.
g1, g2, g3, g4, g5, g6, g7, g8, g9, g10, g11 :: Grafo Int Int
g1 = 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)]
g2 = creaGrafo D (1,5) [(1,2,12),(1,3,34),(1,5,78),
                        (2,4,55),(2,5,32),
                        (4,3,61),(4,5,93)]
g3 = creaGrafo D (1,3) [(1,2,0),(2,2,0),(3,1,0),(3,2,0)]
g4 = creaGrafo D (1,4) [(1,2,3),(2,1,5)]
g5 = creaGrafo D (1,1) [(1,1,0)]
g6 = creaGrafo D (1,4) [(1,3,0),(3,1,0),(3,3,0),(4,2,0)]
g7 = creaGrafo ND (1,4) [(1,3,0)]
g8 = creaGrafo D (1,5) [(1,1,0),(1,2,0),(1,3,0),(2,4,0),(3,1,0),
                        (4,1,0),(4,2,0),(4,4,0),(4,5,0)]
g9 = creaGrafo D (1,5) [(4,1,1),(4,3,2),(5,1,0)]
g10 = creaGrafo ND (1,3) [(1,2,1),(1,3,1),(2,3,1),(3,3,1)]
g11 = creaGrafo D (1,3) [(1,2,1),(1,3,1),(2,3,1),(3,3,1)]

-- ---------------------------------------------------------------------
-- Ejercicio 1. 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 par de vértices distintos. Definir la función,
--    completo :: Int -> Grafo Int Int
-- tal que (completo n) es el grafo completo de orden n. Por ejemplo,
--    ghci> completo 4
--    G ND (array (1,4) [(1,[(2,0),(3,0),(4,0)]),
--                       (2,[(1,0),(3,0),(4,0)]),
--                       (3,[(1,0),(2,0),(4,0)]),
--                       (4,[(1,0),(2,0),(3,0)])])
-- ---------------------------------------------------------------------

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

completo' :: Int -> Grafo Int Int
completo' n = creaGrafo ND (1,n) [(a,b,0)|a<-[1..n],b<-[1..a-1]]
 
-- ---------------------------------------------------------------------
-- Ejercicio 2. 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)
-- Definir la función
--    grafoCiclo :: Int -> Grafo Int Int
-- tal que (grafoCiclo n) es el grafo ciclo de orden n. Por ejemplo,
--    ghci> grafoCiclo 3
--    G ND (array (1,3) [(1,[(3,0),(2,0)]),(2,[(1,0),(3,0)]),(3,[(2,0),(1,0)])])
-- ---------------------------------------------------------------------

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

-- ---------------------------------------------------------------------
-- Ejercicio 3. Definir la función
--    nVertices :: (Ix v,Num p) => Grafo v p ->  Int
-- tal que (nVertices g) es el número de vértices del grafo g. Por
-- ejemplo, 
--    nVertices (completo 4)  ==  4
--    nVertices (completo 5)  ==  5
-- ---------------------------------------------------------------------

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

-- ---------------------------------------------------------------------
-- Ejercicio 4. Definir la función
--    noDirigido :: (Ix v,Num p) => Grafo v p ->  Bool
-- tal que (noDirigido g) se verifica si el grafo g es no dirigido. Por
-- ejemplo, 
--    noDirigido g1            ==  True
--    noDirigido g2            ==  False
--    noDirigido (completo 4)  ==  True
-- ---------------------------------------------------------------------

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

100

101

102

103

104

105

106

107

108

109

110

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

-- Introducción --

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

-- El objetivo de esta relación de ejercicios es definir funciones sobre

-- el TAD de los grafos, utilizando las implementaciones estudiadas

-- en el tema 22 que se pueden descargar desde

-- http://www.cs.us.es/~jalonso/cursos/i1m-13/codigos.zip

-- Las transparencias del tema 22 se encuentran en

-- http://www.cs.us.es/~jalonso/cursos/i1m-13/temas/tema-22.pdf

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

-- Importación de librerías --

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

{-# LANGUAGE FlexibleInstances, TypeSynonymInstances #-}

import Data.Array

import Data.List (nub)

import Test.QuickCheck

-- Hay que seleccionar una implementación del TAD de los grafos

import GrafoConVectorDeAdyacencia

-- import GrafoConMatrizDeAdyacencia

-- import Rel_29_sol

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

-- Ejemplos --

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

-- Para los ejemplos se usarán los siguientes grafos.

g1, g2, g3, g4, g5, g6, g7, g8, g9, g10, g11 :: Grafo Int Int

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

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

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

(4,3,61),(4,5,93)]

g3 = creaGrafo D (1,3) [(1,2,0),(2,2,0),(3,1,0),(3,2,0)]

g4 = creaGrafo D (1,4) [(1,2,3),(2,1,5)]

g5 = creaGrafo D (1,1) [(1,1,0)]

g6 = creaGrafo D (1,4) [(1,3,0),(3,1,0),(3,3,0),(4,2,0)]

g7 = creaGrafo ND (1,4) [(1,3,0)]

g8 = creaGrafo D (1,5) [(1,1,0),(1,2,0),(1,3,0),(2,4,0),(3,1,0),

(4,1,0),(4,2,0),(4,4,0),(4,5,0)]

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

g10 = creaGrafo ND (1,3) [(1,2,1),(1,3,1),(2,3,1),(3,3,1)]

g11 = creaGrafo D (1,3) [(1,2,1),(1,3,1),(2,3,1),(3,3,1)]

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

-- Ejercicio 1. 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 par de vértices distintos. Definir la función,

-- completo :: Int -> Grafo Int Int

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

-- ghci> completo 4

-- G ND (array (1,4) [(1,[(2,0),(3,0),(4,0)]),

-- (2,[(1,0),(3,0),(4,0)]),

-- (3,[(1,0),(2,0),(4,0)]),

-- (4,[(1,0),(2,0),(3,0)])])

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

completo :: Int -> Grafo Int Int

completo n = creaGrafo ND (1,n) xs

where xs = [(x,y,0) | x <- [1..n], y <- [1..n], x < y]

completo' :: Int -> Grafo Int Int

completo' n = creaGrafo ND (1,n) [(a,b,0)|a<-[1..n],b<-[1..a-1]]

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

-- Ejercicio 2. 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)

-- Definir la función

-- grafoCiclo :: Int -> Grafo Int Int

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

-- ghci> grafoCiclo 3

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

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

grafoCiclo :: Int -> Grafo Int Int

grafoCiclo n = creaGrafo ND (1,n) xs

where xs = [(x,x+1,0) | x <- [1..n-1]] ++ [(n,1,0)]

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

-- Ejercicio 3. Definir la función

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

-- tal que (nVertices g) es el número de vértices del grafo g. Por

-- ejemplo,

-- nVertices (completo 4) == 4

-- nVertices (completo 5) == 5

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

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

nVertices = length . nodos

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

-- Ejercicio 4. Definir la función

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

-- tal que (noDirigido g) se verifica si el grafo g es no dirigido. Por

-- ejemplo,

-- noDirigido g1 == True

-- noDirigido g2 == False

-- noDirigido (completo 4) == True

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

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

noDirigido = not . dirigido

Se puede imprimir o compartir con