-- |
-- Module      : Grafos
-- Description : TAD de los grafos.
-- License     : Creative Commons
-- Maintainer  : José A. Alonso
-- 
-- = El TAD (tipo abstracto de datos) de los grafos
--
-- Este módulo contiene el código del TAD de los grafos
-- estudiado en el <http://bit.ly/1WYZAY3 tema 22> del curso.
-- 
-- En los ejemplos se usarán los siguientes grafos:
-- 
-- >             12
-- >        1 -------- 2
-- >        | \78     /|
-- >        |  \   32/ |
-- >        |   \   /  |
-- >      34|     5    |55
-- >        |   /   \  |
-- >        |  /44   \ |
-- >        | /     93\|
-- >        3 -------- 4
-- >             61
-- definido por
--
-- > ejGrafoND = creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78),
-- >                                 (2,4,55),(2,5,32),
-- >                                 (3,4,61),(3,5,44),
-- >                                 (4,5,93)]
-- y el mismo grafo que ejGrafoND pero orientando las aristas;
-- 
-- > ejGrafoD = creaGrafo D (1,5) [(1,2,12),(1,3,34),(1,5,78),
-- >                               (2,4,55),(2,5,32),
-- >                               (3,4,61),(3,5,44),
-- >                               (4,5,93)]

module I1M.Grafo
  (Orientacion (..),
   Grafo,
   creaGrafo,  -- (Ix v,Num p) => Orientacion -> (v,v) -> [(v,v,p)] -> 
               --                 Grafo v p
   dirigido,   -- (Ix v,Num p) => (Grafo v p) -> Bool
   adyacentes, -- (Ix v,Num p) => (Grafo v p) -> v -> [v]
   nodos,      -- (Ix v,Num p) => (Grafo v p) -> [v]
   aristas,    -- (Ix v,Num p) => (Grafo v p) -> [(v,v,p)]
   aristaEn,   -- (Ix v,Num p) => (Grafo v p) -> (v,v) -> Bool
   peso        -- (Ix v,Num p) => v -> v -> (Grafo v p) -> p
  ) where

-- ---------------------------------------------------------------------
-- Librerías auxiliares                                               --
-- ---------------------------------------------------------------------

import Data.Array

-- | Orientacion es D (dirigida) ó ND (no dirigida).
data Orientacion = D | ND
  deriving (Orientacion -> Orientacion -> Bool
(Orientacion -> Orientacion -> Bool)
-> (Orientacion -> Orientacion -> Bool) -> Eq Orientacion
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: Orientacion -> Orientacion -> Bool
== :: Orientacion -> Orientacion -> Bool
$c/= :: Orientacion -> Orientacion -> Bool
/= :: Orientacion -> Orientacion -> Bool
Eq, Int -> Orientacion -> ShowS
[Orientacion] -> ShowS
Orientacion -> String
(Int -> Orientacion -> ShowS)
-> (Orientacion -> String)
-> ([Orientacion] -> ShowS)
-> Show Orientacion
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> Orientacion -> ShowS
showsPrec :: Int -> Orientacion -> ShowS
$cshow :: Orientacion -> String
show :: Orientacion -> String
$cshowList :: [Orientacion] -> ShowS
showList :: [Orientacion] -> ShowS
Show)

-- | (Grafo v p) es un grafo con vértices de tipo v y pesos de tipo p.
data Grafo v p = G Orientacion (Array v [(v,p)])
  deriving (Grafo v p -> Grafo v p -> Bool
(Grafo v p -> Grafo v p -> Bool)
-> (Grafo v p -> Grafo v p -> Bool) -> Eq (Grafo v p)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall v p. (Ix v, Eq p) => Grafo v p -> Grafo v p -> Bool
$c== :: forall v p. (Ix v, Eq p) => Grafo v p -> Grafo v p -> Bool
== :: Grafo v p -> Grafo v p -> Bool
$c/= :: forall v p. (Ix v, Eq p) => Grafo v p -> Grafo v p -> Bool
/= :: Grafo v p -> Grafo v p -> Bool
Eq, Int -> Grafo v p -> ShowS
[Grafo v p] -> ShowS
Grafo v p -> String
(Int -> Grafo v p -> ShowS)
-> (Grafo v p -> String)
-> ([Grafo v p] -> ShowS)
-> Show (Grafo v p)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall v p. (Ix v, Show v, Show p) => Int -> Grafo v p -> ShowS
forall v p. (Ix v, Show v, Show p) => [Grafo v p] -> ShowS
forall v p. (Ix v, Show v, Show p) => Grafo v p -> String
$cshowsPrec :: forall v p. (Ix v, Show v, Show p) => Int -> Grafo v p -> ShowS
showsPrec :: Int -> Grafo v p -> ShowS
$cshow :: forall v p. (Ix v, Show v, Show p) => Grafo v p -> String
show :: Grafo v p -> String
$cshowList :: forall v p. (Ix v, Show v, Show p) => [Grafo v p] -> ShowS
showList :: [Grafo v p] -> ShowS
Show)

-- | (creaGrafo o cs as) es un grafo (dirigido o no, según el valor de o),
-- con el par de cotas cs y listas de aristas as (cada arista es un trío
-- formado por los dos vértices y su peso). Ver el ejemplo a continuación.
creaGrafo :: (Ix v, Num p) => Orientacion -> (v,v) -> [(v,v,p)] -> Grafo v p
creaGrafo :: forall v p.
(Ix v, Num p) =>
Orientacion -> (v, v) -> [(v, v, p)] -> Grafo v p
creaGrafo Orientacion
o (v, v)
cs [(v, v, p)]
vs =
  Orientacion -> Array v [(v, p)] -> Grafo v p
forall v p. Orientacion -> Array v [(v, p)] -> Grafo v p
G Orientacion
o (([(v, p)] -> (v, p) -> [(v, p)])
-> [(v, p)] -> (v, v) -> [(v, (v, p))] -> Array v [(v, p)]
forall i e a.
Ix i =>
(e -> a -> e) -> e -> (i, i) -> [(i, a)] -> Array i e
accumArray 
       (\[(v, p)]
xs (v, p)
x -> [(v, p)]
xs[(v, p)] -> [(v, p)] -> [(v, p)]
forall a. [a] -> [a] -> [a]
++[(v, p)
x]) [] (v, v)
cs 
       ((if Orientacion
o Orientacion -> Orientacion -> Bool
forall a. Eq a => a -> a -> Bool
== Orientacion
D then []
         else [(v
x2,(v
x1,p
p))|(v
x1,v
x2,p
p) <- [(v, v, p)]
vs, v
x1 v -> v -> Bool
forall a. Eq a => a -> a -> Bool
/= v
x2]) [(v, (v, p))] -> [(v, (v, p))] -> [(v, (v, p))]
forall a. [a] -> [a] -> [a]
++
        [(v
x1,(v
x2,p
p)) | (v
x1,v
x2,p
p) <- [(v, v, p)]
vs]))

-- ejGrafoND es el grafo
--             12
--        1 -------- 2
--        | \78     /|
--        |  \   32/ |
--        |   \   /  |
--      34|     5    |55
--        |   /   \  |
--        |  /44   \ |
--        | /     93\|
--        3 -------- 4
--             61
-- representado mediante un vector de adyacencia; es decir,
--    ghci> ejGrafoND
--    G ND array (1,5) [(1,[(2,12),(3,34),(5,78)]),
--                      (2,[(1,12),(4,55),(5,32)]),
--                      (3,[(1,34),(4,61),(5,44)]),
--                      (4,[(2,55),(3,61),(5,93)]),
--                      (5,[(1,78),(2,32),(3,44),(4,93)])])
-- ejGrafoND = creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78),
--                                 (2,4,55),(2,5,32),
--                                 (3,4,61),(3,5,44),
--                                 (4,5,93)]

-- ejGrafoD es el mismo grafo que ejGrafoND pero orientando las aristas;
-- es decir,
--    ghci> ejGrafoD
--    G D array (1,5) [(1,[(2,12),(3,34),(5,78)]),
--                     (2,[(4,55),(5,32)]),
--                     (3,[(4,61),(5,44)]),
--                     (4,[(5,93)]),
--                     (5,[])])
-- ejGrafoD = creaGrafo D (1,5) [(1,2,12),(1,3,34),(1,5,78),
--                               (2,4,55),(2,5,32),
--                               (3,4,61),(3,5,44),
--                               (4,5,93)]

-- | (dirigido g) se verifica si g es dirigido. Por ejemplo,
-- 
-- > dirigido ejGrafoD   ==  True
-- > dirigido ejGrafoND  ==  False
dirigido :: (Ix v,Num p) => Grafo v p -> Bool
dirigido :: forall v p. (Ix v, Num p) => Grafo v p -> Bool
dirigido (G Orientacion
o Array v [(v, p)]
_) = Orientacion
o Orientacion -> Orientacion -> Bool
forall a. Eq a => a -> a -> Bool
== Orientacion
D

-- | (nodos g) es la lista de todos los nodos del grafo g. Por ejemplo,
-- 
-- > nodos ejGrafoND  ==  [1,2,3,4,5]
-- > nodos ejGrafoD   ==  [1,2,3,4,5]
nodos :: (Ix v,Num p) => Grafo v p -> [v]
nodos :: forall v p. (Ix v, Num p) => Grafo v p -> [v]
nodos (G Orientacion
_ Array v [(v, p)]
g) = Array v [(v, p)] -> [v]
forall i e. Ix i => Array i e -> [i]
indices Array v [(v, p)]
g

-- | (adyacentes g v) es la lista de los vértices adyacentes al nodo v en
-- el grafo g. Por ejemplo,
-- 
-- > adyacentes ejGrafoND 4  ==  [2,3,5]
-- > adyacentes ejGrafoD  4  ==  [5]
adyacentes :: (Ix v,Num p) => Grafo v p -> v -> [v]
adyacentes :: forall v p. (Ix v, Num p) => Grafo v p -> v -> [v]
adyacentes (G Orientacion
_ Array v [(v, p)]
g) v
v = ((v, p) -> v) -> [(v, p)] -> [v]
forall a b. (a -> b) -> [a] -> [b]
map (v, p) -> v
forall a b. (a, b) -> a
fst (Array v [(v, p)]
gArray v [(v, p)] -> v -> [(v, p)]
forall i e. Ix i => Array i e -> i -> e
!v
v)

-- | (aristaEn g a) se verifica si a es una arista del grafo g. Por
-- ejemplo,
-- 
-- > aristaEn ejGrafoND (5,1)  ==  True
-- > aristaEn ejGrafoND (4,1)  ==  False
-- > aristaEn ejGrafoD (5,1)   ==  False
-- > aristaEn ejGrafoD (1,5)   ==  True
aristaEn :: (Ix v,Num p) => Grafo v p -> (v,v) -> Bool
aristaEn :: forall v p. (Ix v, Num p) => Grafo v p -> (v, v) -> Bool
aristaEn Grafo v p
g (v
x,v
y) = v
y v -> [v] -> Bool
forall a. Eq a => a -> [a] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`elem` Grafo v p -> v -> [v]
forall v p. (Ix v, Num p) => Grafo v p -> v -> [v]
adyacentes Grafo v p
g v
x

-- | (peso v1 v2 g) es el peso de la arista que une los vértices v1 y v2
-- en el grafo g. Por ejemplo,
-- 
-- > peso 1 5 ejGrafoND  ==  78
-- > peso 1 5 ejGrafoD   ==  78
peso :: (Ix v,Num p) => v -> v -> Grafo v p -> p
peso :: forall v p. (Ix v, Num p) => v -> v -> Grafo v p -> p
peso v
x v
y (G Orientacion
_ Array v [(v, p)]
g) = [p] -> p
forall a. HasCallStack => [a] -> a
head [p
c | (v
a,p
c) <- Array v [(v, p)]
gArray v [(v, p)] -> v -> [(v, p)]
forall i e. Ix i => Array i e -> i -> e
!v
x , v
a v -> v -> Bool
forall a. Eq a => a -> a -> Bool
== v
y]

-- | (aristas g) es la lista de las aristas del grafo g. Por ejemplo, 
-- 
-- > ghci> aristas ejGrafoD
-- > [(1,2,12),(1,3,34),(1,5,78),(2,4,55),(2,5,32),(3,4,61),
-- >  (3,5,44),(4,5,93)] 
-- > ghci> aristas ejGrafoND
-- > [(1,2,12),(1,3,34),(1,5,78),(2,1,12),(2,4,55),(2,5,32),
-- >  (3,1,34),(3,4,61),(3,5,44),(4,2,55),(4,3,61),(4,5,93),
-- >  (5,1,78),(5,2,32),(5,3,44),(5,4,93)]
aristas :: (Ix v,Num p) => Grafo v p -> [(v,v,p)]
aristas :: forall v p. (Ix v, Num p) => Grafo v p -> [(v, v, p)]
aristas (G Orientacion
o Array v [(v, p)]
g) = [(v
v1,v
v2,p
w) | v
v1 <- Grafo v p -> [v]
forall v p. (Ix v, Num p) => Grafo v p -> [v]
nodos (Orientacion -> Array v [(v, p)] -> Grafo v p
forall v p. Orientacion -> Array v [(v, p)] -> Grafo v p
G Orientacion
o Array v [(v, p)]
g) , (v
v2,p
w) <- Array v [(v, p)]
gArray v [(v, p)] -> v -> [(v, p)]
forall i e. Ix i => Array i e -> i -> e
!v
v1]