-- I1M 2009-10: Relación 27 (3 de mayo de 2010)
-- Departamento de Ciencias de la Computación e I.A.
-- Universidad de Sevilla
-- =====================================================================

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

import Test.QuickCheck
import Data.List

-- ---------------------------------------------------------------------
-- Nota: Los grafos se pueden representar mediante la lista de sus
-- arcos. Por ejemplo, el grafo 
--                          2
--                        / | \
--                       /  |  \
--                      1   |   3
--                          |  /
--                          | /
--                          |/
--                          4
-- puede representarse mediante la lista [(1,2),(2,3),(2,4),(3,4)]. En
-- los siguientes ejercicios se usará dicha representación. 
-- ---------------------------------------------------------------------

type Grafo a = [(a,a)]

ejGrafo1 :: Grafo Int
ejGrafo1 = [(1,2),(2,3),(2,4),(3,4)]

-- ---------------------------------------------------------------------
-- Ejercicio 1: Definir la función 
--    adyacentes :: Grafo a -> a -> [a]
-- tal que (adyacentes g x) es la lista de los nodos adyacentes al nodo
-- x en el grafo g. Por ejemplo,
--    adyacentes [(1,2),(2,3),(2,4),(3,4)] 3  ==  [4,2]
-- ---------------------------------------------------------------------

adyacentes :: Eq a => Grafo a -> a -> [a]
adyacentes g x = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 2: Definir la función
--    nodos :: Grafo a -> [a]
-- tal que (nodos g) es el conjunto de los nodos del grafo g. Por
-- ejemplo,
--    nodos [(1,2),(2,3),(2,4),(3,4)]  ==  [2,3,4,1]
-- ---------------------------------------------------------------------

nodos :: Eq a => Grafo a -> [a]
nodos g = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 4: Definir la función 
--    caminos :: Eq a => Grafo a -> a -> a -> [Camino a]
-- tal que (caminos g x y ) es la lista de los caminos en el grafo g
-- desde el nodo x al nodo y. Por ejemplo,
--    caminos [(1,2),(2,3),(2,4),(3,4)] 1 4  ==  [[1,2,4],[1,2,3,4]] 
-- El tipo Camino es una lista de nodos.
-- ---------------------------------------------------------------------

type Camino a = [a]

caminos :: Eq a => Grafo a -> a -> a -> [Camino a]
caminos g x y = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 5: Definir la función
--    Eq a => Grafo a -> Bool
-- tal que (conectado g) se verifica si el grafo g está conectado; es
-- decir, existe un camino entre cada par de vértices. Por ejemplo, 
--    conectado [(1,2),(2,3),(2,4),(3,4)]  ==  True
--    conectado [(1,2),(3,4)]              ==  False
-- ---------------------------------------------------------------------

conectado :: Eq a => Grafo a -> Bool
conectado g = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 6: Definir la función
--    tieneCiclos :: Eq a => Grafo a -> Bool
-- tal que (tieneCiclos g) se verifica si en el grafo g hay ciclos. Por
-- ejemplo,
--    tieneCiclos [(1,2),(2,3),(2,4),(3,4)]  ==  True
--    tieneCiclos [(1,2),(2,3),(2,4)]        ==  False
-- ---------------------------------------------------------------------

tieneCiclos :: Eq a => Grafo a -> Bool
tieneCiclos g = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 7: Definir la función 
--    esArbol :: Eq a => Grafo a -> Bool
-- tal que (esArbol g) se verifica si g es  un árbol; es decir, g es un
-- grafo conectado sin ciclos. Por ejemplo, 
--    esArbol [(1,2),(2,3),(2,4),(3,4)]  ==  False
--    esArbol [(1,2),(2,3),(2,4)]        ==  True
-- ---------------------------------------------------------------------

esArbol :: Eq a => Grafo a -> Bool
esArbol g = undefined

-- ---------------------------------------------------------------------
-- Ejercicio 8. Definir la función
--    caminosHamiltonianos :: Eq a => Grafo a -> [Camino a]
-- tal que (caminosHamiltonianos g) es la lista de los caminos
-- hamiltoniano en el grafo g (es decir, es la lista de los caminos en g
-- que pasa por todos sus nodos). Por ejemplo,  
--    *Main> caminosHamiltonianos [(1,2),(2,3),(2,4),(3,4)]
--    [[3,4,2,1],[4,3,2,1],[1,2,4,3],[1,2,3,4]]
-- ---------------------------------------------------------------------

caminosHamiltonianos :: Eq a => Grafo a -> [Camino a]
caminosHamiltonianos g = undefined