I1M-0.1.0.0: Código de I1M.

LicenseCreative Commons
MaintainerJosé A. Alonso
Safe HaskellSafe
LanguageHaskell2010

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

Documentation

data Orientacion Source

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

Constructors

D 
ND 

data Grafo v p Source

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

Instances

(Eq p, Ix v) => Eq (Grafo v p) Source 
(Show v, Show p, Ix v) => Show (Grafo v p) Source 

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