El problema Clique en Haskel

-- Cliques.hs
-- El problema del clique.
-- José A. Alonso Jiménez
-- Sevilla, 6 de febrero de 2020
-- ---------------------------------------------------------------------

module Cliques where

import Data.List

-- ---------------------------------------------------------------------
-- Un grafo no dirigido se representa por la lista de sus arcos. Por 
-- ejemplo, el grafo
--              1  -- 2 -- 4
--                    | \  |
--                    |  \ |
--                    3 -- 5
-- se representa por [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)].

--
-- Definir el tipo Grafo.
-- ---------------------------------------------------------------------

type Grafo a = [(a,a)]

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

nodos :: Eq a => Grafo a -> [a]
nodos g = nub (concat [[x,y] | (x,y) <- g])

-- ---------------------------------------------------------------------
-- Ejercicio: Definir la función
--    conectados :: Eq a => Grafo a -> a -> a -> Bool
-- tal que (conectados g x y) se verifica si el grafo no dirigido g
-- posee un arco con extremos x e y. Por ejemplo,
--    conectados [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)] 3 2  ==  True
--    conectados [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)] 2 3  ==  True
--    conectados [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)] 3 4  ==  False
-- ---------------------------------------------------------------------

conectados :: Eq a => Grafo a -> a -> a -> Bool
conectados g x y =
  (x,y) `elem` g || (y,x) `elem` g 

-- ---------------------------------------------------------------------
-- Ejercicio: Definir la función
--    parejas :: [a] -> [(a,a)]
-- tal que (parejas xs) es la lista de las parejas formados por los
-- elementos de xs y sus siguientes en xs. Por ejemplo,
--    parejas [1..4] == [(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)]
-- ---------------------------------------------------------------------

parejas :: [a] -> [(a,a)]
parejas xs =
  [(x,y) | (x:ys) <- tails xs
         , y <- ys]

-- ---------------------------------------------------------------------
-- Ejercicio. Un clique (en español, pandilla) de un grafo g es un
-- conjunto de nodos de g tal que todos sus elementos están conectados
-- en g.
--
-- Definir la función
--    esClique :: Eq a => Grafo a -> [a] -> Bool
-- tal que (esClique g xs) se verifica si el conjunto de nodos xs del
-- grafo g es un clique de g.Por ejemplo,
--    esClique [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)] [2,3,5]  ==  True
--    esClique [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)] [2,3,4]  ==  False
-- ---------------------------------------------------------------------

esClique :: Eq a => Grafo a -> [a] -> Bool
esClique g xs =
  and [conectados g x y | (x,y) <- parejas xs]

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

cliques :: Eq a => Grafo a -> [[a]]
cliques g =
  [xs | xs <- subsequences (nodos g)
      , esClique g xs]

-- ---------------------------------------------------------------------
-- Ejercicio. Definir la función 
--    kSubconjuntos :: [a] -> Int -> [[a]]
-- tal que (kSubconjuntos xs k) es la lista de los subconjuntos de xs
-- con k elementos. Por ejemplo,
--    ghci> kSubconjuntos "bcde" 2
--    ["bc","bd","be","cd","ce","de"]
--    ghci> kSubconjuntos "bcde" 3
--    ["bcd","bce","bde","cde"]
--    ghci> kSubconjuntos "abcde" 3
--    ["abc","abd","abe","acd","ace","ade","bcd","bce","bde","cde"]
-- ---------------------------------------------------------------------
 
kSubconjuntos :: [a] -> Int -> [[a]]
kSubconjuntos _ 0      = [[]]
kSubconjuntos [] _     = []
kSubconjuntos (x:xs) k = 
  [x:ys | ys <- kSubconjuntos xs (k-1)] ++ kSubconjuntos xs k  

-- ---------------------------------------------------------------------
-- Ejercicio. Definir la función
--    kCliques :: Eq a => Grafo a -> Int -> [[a]]
-- tal que (cliques g k) es la lista de los cliques del grafo g de
-- tamaño k. Por ejemplo, 
--    λ> kCliques [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)] 3
--    [[2,3,5],[2,4,5]]
--    λ> kCliques [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)] 2
--    [[1,2],[2,3],[2,4],[2,5],[3,5],[4,5]]
-- ---------------------------------------------------------------------

-- 1ª definición
kCliques1 :: Eq a => Grafo a -> Int -> [[a]]
kCliques1 g k =
  [xs | xs <- cliques g
      , length xs == k]

-- 2ª definición
kCliques :: Eq a => Grafo a -> Int -> [[a]]
kCliques g k =
  [xs | xs <- kSubconjuntos (nodos g) k
      , esClique g xs]

-- Comparación de eficiencia
-- =========================

--    λ> kCliques1 [(n,n+1) | n <- [1..20]] 3
--    []
--    (4.28 secs, 3,204,548,608 bytes)
--    λ> kCliques [(n,n+1) | n <- [1..20]] 3
--    []
--    (0.01 secs, 3,075,768 bytes)