Representaciones de grafos
Los grafos no dirigidos puede representarse mediante matrices de adyacencia y también mediante listas de adyacencia. Por ejemplo, el grafo
1 ----- 2 | \ | | 3 | | / | 4 ----- 5
se puede representar por la matriz de adyacencia
|0 1 1 1 0| |1 0 0 0 1| |1 0 0 1 0| |1 0 1 0 1| |0 1 0 1 0|
donde el elemento (i,j) es 1 si hay una arista entre los vértices i y j y es 0 si no la hay. También se puede representar por la lista de adyacencia
[(1,[2,3,4]),(2,[1,5]),(3,[1,4]),(4,[1,3,5]),(5,[2,4])]
donde las primeras componentes son los vértices y las segundas la lista de los vértices conectados.
Definir las funciones
matrizAlista :: Matrix Int -> [(Int,[Int])] listaAmatriz :: [(Int,[Int])] -> Matrix Int
tales que
- (matrizAlista a) es la lista de adyacencia correspondiente a la matriz de adyacencia a. Por ejemplo, definiendo la matriz anterior por
ejMatriz :: Matrix Int ejMatriz = fromLists [[0,1,1,1,0], [1,0,0,0,1], [1,0,0,1,0], [1,0,1,0,1], [0,1,0,1,0]]
se tiene que
λ> matrizAlista ejMatriz [(1,[2,3,4]),(2,[1,5]),(3,[1,4]),(4,[1,3,5]),(5,[2,4])]
- (listaAmatriz ps) es la matriz de adyacencia correspondiente a la lista de adyacencia ps. Por ejemplo,
λ> listaAmatriz [(1,[2,3,4]),(2,[1,5]),(3,[1,4]),(4,[1,3,5]),(5,[2,4])] ( 0 1 1 1 0 ) ( 1 0 0 0 1 ) ( 1 0 0 1 0 ) ( 1 0 1 0 1 ) ( 0 1 0 1 0 ) λ> matrizAlista it [(1,[2,3,4]),(2,[1,5]),(3,[1,4]),(4,[1,3,5]),(5,[2,4])]
Soluciones
import Data.List (sort) import Data.Matrix ejMatriz :: Matrix Int ejMatriz = fromLists [[0,1,1,1,0], [1,0,0,0,1], [1,0,0,1,0], [1,0,1,0,1], [0,1,0,1,0]] matrizAlista :: Matrix Int -> [(Int,[Int])] matrizAlista a = [(i,[j | j <- [1..n], a!(i,j) == 1]) | i <- [1..n]] where n = nrows a listaAmatriz :: [(Int,[Int])] -> Matrix Int listaAmatriz ps = fromLists [fila n xs | (_,xs) <- sort ps] where n = length ps fila n xs = [f i | i <- [1..n]] where f i | i `elem` xs = 1 | otherwise = 0