License | Creative Commons |
---|---|
Maintainer | José A. Alonso |
Safe Haskell | Safe-Inferred |
Language | Haskell2010 |
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
- 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).
Instances
Eq Orientacion Source # | |
Defined in I1M.Grafo (==) :: Orientacion -> Orientacion -> Bool # (/=) :: Orientacion -> Orientacion -> Bool # | |
Show Orientacion Source # | |
Defined in I1M.Grafo showsPrec :: Int -> Orientacion -> ShowS # show :: Orientacion -> String # showList :: [Orientacion] -> ShowS # |
(Grafo v p) es un grafo con vértices de tipo v y pesos de tipo p.
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)]