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