I1M.Grafo

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

Documentation

data Orientacion

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

Constructors

D

ND

Instances

Eq Orientacion

Defined in I1M.Grafo

Methods

(==) :: Orientacion -> Orientacion -> Bool

(/=) :: Orientacion -> Orientacion -> Bool

Show Orientacion

Defined in I1M.Grafo

Methods

showsPrec :: Int -> Orientacion -> ShowS

show :: Orientacion -> String

showList :: [Orientacion] -> ShowS

data Grafo v p

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

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)

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

(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

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

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

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

(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

(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

(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