I1M-0.0.1: Code for the Haskell course taught at the University od Seville.

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 
Instances
Eq Orientacion Source # 
Instance details

Defined in I1M.Grafo

Show Orientacion Source # 
Instance details

Defined in I1M.Grafo

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