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

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|

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

1	[(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

1 2	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]]

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

1 2	λ> 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])]

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

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

3 Comentarios

import Data.Vector as V
import Data.Matrix as M

matrizAlista :: Matrix Int -> [(Int,[Int])]
matrizAlista m = [(i, aux 0 (V.toList(M.getRow i m))) | i <- [1.. M.nrows m]]
  where aux _ [] = []
        aux n (x:xs) | x == 1 = [n+1] ++ aux (n+1) xs
                     | otherwise = aux (n+1) xs

listaAmatriz :: [(Int,[Int])] -> Matrix Int
listaAmatriz xs = M.fromLists [[f n x | n <- cs] | x <- cs]
  where cs = map fst xs
        f x y |elem x (fromJust(lookup y xs)) = 1
              |otherwise                      = 0

import Data.Vector as V

import Data.Matrix as M

matrizAlista :: Matrix Int -> [(Int,[Int])]

matrizAlista m = [(i, aux 0 (V.toList(M.getRow i m))) | i <- [1.. M.nrows m]]

where aux _ [] = []

aux n (x:xs) | x == 1 = [n+1] ++ aux (n+1) xs

| otherwise = aux (n+1) xs

listaAmatriz :: [(Int,[Int])] -> Matrix Int

listaAmatriz xs = M.fromLists [[f n x | n <- cs] | x <- cs]

where cs = map fst xs

f x y |elem x (fromJust(lookup y xs)) = 1

|otherwise = 0

Responder

import Data.Matrix
matrizAlista :: Matrix Int -> [(Int,[Int])]
matrizAlista m = [(x,[j | j<-[1..ncols m],m!(x,j)/=0]) | x<-[1..nrows m]]

listaAmatriz :: [(Int,[Int])] -> Matrix Int
listaAmatriz xs = fromLists (map f  xs)
  where f  (x,ys) = filaAmpliada (maximum (concatMap snd xs))  ((g) ys)
        g ys = [(y,1)|y<-ys]
        
filaAmpliada :: Num a => Int -> [(Int,a)] -> [a]
filaAmpliada n xs =
  [f (lookup i xs) | i <- [1..n]]
  where f Nothing  = 0
        f (Just x) = x

import Data.Matrix

matrizAlista :: Matrix Int -> [(Int,[Int])]

matrizAlista m = [(x,[j | j<-[1..ncols m],m!(x,j)/=0]) | x<-[1..nrows m]]

listaAmatriz :: [(Int,[Int])] -> Matrix Int

listaAmatriz xs = fromLists (map f xs)

where f (x,ys) = filaAmpliada (maximum (concatMap snd xs)) ((g) ys)

g ys = [(y,1)|y<-ys]

filaAmpliada :: Num a => Int -> [(Int,a)] -> [a]

filaAmpliada n xs =

[f (lookup i xs) | i <- [1..n]]

where f Nothing = 0

f (Just x) = x

Responder

import Data.List
import Data.Matrix as M

matrizAlista :: Matrix Int -> [(Int,[Int])]
matrizAlista q = aux [(i,[j]) | i <- [1..m], j <- [1..n], q M.! (i,j) == 1]
  where m = M.nrows q
        n = M.ncols q
        aux [] = []
        aux [(x,y)] = [(x,y)]
        aux ((x,y):(x2,z):ps) | x == x2 = aux ((x,y++z) : ps)
                              | otherwise = (x,y) : aux ((x2,z):ps)
        
listaAmatriz :: [(Int,[Int])] -> Matrix Int
listaAmatriz ps = aux xs
  where xs = concatMap parea ps
        parea (x,[]) = []
        parea (x,(y:ys)) = (x,y) : parea (x,ys)
        m = maximum (map fst ps)
        n = maximum (concatMap snd ps)
        aux xs = matrix m n (\(i,j) -> f(i,j))  
        f (i,j) | (i,j) `elem`xs = 1
                | otherwise = 0

import Data.List

import Data.Matrix as M

matrizAlista :: Matrix Int -> [(Int,[Int])]

matrizAlista q = aux [(i,[j]) | i <- [1..m], j <- [1..n], q M.! (i,j) == 1]

where m = M.nrows q

n = M.ncols q

aux [] = []

aux [(x,y)] = [(x,y)]

aux ((x,y):(x2,z):ps) | x == x2 = aux ((x,y++z) : ps)

| otherwise = (x,y) : aux ((x2,z):ps)

listaAmatriz :: [(Int,[Int])] -> Matrix Int

listaAmatriz ps = aux xs

where xs = concatMap parea ps

parea (x,[]) = []

parea (x,(y:ys)) = (x,y) : parea (x,ys)

m = maximum (map fst ps)

n = maximum (concatMap snd ps)

aux xs = matrix m n (\(i,j) -> f(i,j))

f (i,j) | (i,j) `elem`xs = 1

| otherwise = 0

Responder

Representaciones de grafos

Soluciones

3 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

3 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico