License	Creative Commons
Maintainer	José A. Alonso
Safe Haskell	Safe
Language	Haskell2010

I1M.Grafo

Description

El TAD (tipo abstracto de datos) de los grafos

Este módulo contiene el código del TAD de los grafos estudiado en el 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)]

Synopsis

data Orientacion
- = D
- | ND
data Grafo v p
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

Documentation

data Orientacion Source #

Orientacion es D (dirigida) ó ND (no dirigida).

Constructors

D
ND

Instances

Eq Orientacion Source #
Instance details Defined in I1M.Grafo Methods (==) :: Orientacion -> Orientacion -> Bool # (/=) :: Orientacion -> Orientacion -> Bool #
Show Orientacion Source #
Instance details Defined in I1M.Grafo Methods showsPrec :: Int -> Orientacion -> ShowS # show :: Orientacion -> String # showList :: [Orientacion] -> ShowS #

data Grafo v p Source #

(Grafo v p) es un grafo con vértices de tipo v y pesos de tipo p.

Instances

(Ix v, Eq p) => Eq (Grafo v p) Source #
Instance details Defined in I1M.Grafo Methods (==) :: Grafo v p -> Grafo v p -> Bool # (/=) :: Grafo v p -> Grafo v p -> Bool #
(Ix v, Show v, Show p) => Show (Grafo v p) Source #
Instance details Defined in I1M.Grafo Methods showsPrec :: Int -> Grafo v p -> ShowS # show :: Grafo v p -> String # showList :: [Grafo v p] -> ShowS #

creaGrafo :: (Ix v, Num p) => Orientacion -> (v, v) -> [(v, v, p)] -> Grafo v p Source #

(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.

dirigido :: (Ix v, Num p) => Grafo v p -> Bool Source #

(dirigido g) se verifica si g es dirigido. Por ejemplo,

dirigido ejGrafoD   ==  True
dirigido ejGrafoND  ==  False

adyacentes :: (Ix v, Num p) => Grafo v p -> v -> [v] Source #

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

nodos :: (Ix v, Num p) => Grafo v p -> [v] Source #

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

aristas :: (Ix v, Num p) => Grafo v p -> [(v, v, p)] Source #

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

aristaEn :: (Ix v, Num p) => Grafo v p -> (v, v) -> Bool Source #

(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

peso :: (Ix v, Num p) => v -> v -> Grafo v p -> p Source #

(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