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

Documentation

data Orientacion Source

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

Constructors

D
ND

Instances

Eq Orientacion Source
Show Orientacion Source

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