EXAMEN Febrero 2014 Estructuras de datos. Resolución Primera Parte. Haskell.

Pues bueno, aquí va la parte en Haskell del examen. Dadme vuestras opiniones. Al menos lo que tiene que hacer a mi me lo hacía xD. A ver si saco notaza ^^

Si preferís descargarlo (a mi me haceis un favor) podréis hacerlo de aqui.
Los enunciados y bibliotecas se encuentran aqui

Ahí os va el code ;)

module StronglyConnectedComponents  where

import DataStructures.Graph.DiGraph 

import DataStructures.Graph.DiGraphDFT
    ( dft         -- :: (Ord a) => DiGraph a -> a -> [a] 
    )

import Data.List--( (\\), intersect )
import DataStructures.Stack.LinearStack
-------
-- A --
-------
reverseDiGraph :: Eq a => DiGraph a -> DiGraph a
reverseDiGraph g = mkDiGraphEdges (vertices g) (aux (diEdges g) )

aux :: [DiEdge a] -> [DiEdge a] 
aux xs = [(y:->z) | (z:->y) <- xs]


restrictDiGraph :: Eq a => DiGraph a -> [a] -> DiGraph a
-- el subgrafo de g con vértices en vs
restrictDiGraph g vs = deleteVertices' vs g

deleteVertices :: Eq a => [a] -> DiGraph a -> DiGraph a
deleteVertices xs g = mkDiGraphSuc (vertices g\\xs) suc' 
   where suc' v = (successors g v) \\ xs

deleteVertices' :: Eq a => [a] -> DiGraph a -> DiGraph a
deleteVertices' xs g = mkDiGraphSuc (intersect(vertices g) xs) suc' 
   where suc' v = intersect (successors g v)  xs

{-
*StronglyConnectedComponents> restrictDiGraph gExample [A,B,H,I,J]
Graph, Vertices : [A,B,H], DiEdges: [A :-> B]

*StronglyConnectedComponents> reverseDiGraph $ restrictDiGraph gExample [A,B,H] 
Graph, Vertices : [A,B,H], DiEdges: [B :-> A]
-}

type SCC a = [a] 

-------
-- C --
-------
sccOf :: Ord a => DiGraph a -> a -> SCC a
-- la scc (strongly connected component) en el grafo g del vértice v
sccOf g v =  dft (reverseDiGraph (restrictDiGraph g (dft g v))) v

{-
*StronglyConnectedComponents> sccOf  gExample A
[A,E,B]
-}

-------
-- D --
-------
-- todas las componentes
sccs :: Ord a => DiGraph a -> [SCC a]
sccs g  = aux3 g (vertices g) []

aux3 :: Ord a => DiGraph a -> [a] -> [SCC a] -> [SCC a]
aux3 g [] zs     = zs
aux3 g (x:xs) zs = aux3 g (xs\\vs)  (vs:zs)
  where vs = sccOf g x


{-
*StronglyConnectedComponents> sccs gExample
[[A,E,B],[C,D,H],[F,G]]
it :: [SCC Vertice]

-- las componentes son tres ciclos
-}


-------------------------------------
--- El grafo del enunciado del examen 
-------------------------------------

data Vertice = A|B|C|D|E|F|G|H|I|J|K deriving (Eq,Show,Ord,Enum)


gExample = mkDiGraphEdges [A .. H] 
                         [ A :-> B, B:-> F, B:->E, C:->D, C:->G, 
                           D:->C, D:->H, E:->F, E:->A,
                           F:->G, G:->F, H:->D, H:->G]

Como veis. Importé el intersect de Data.List (espero que no me reste xD). Los comentarios que empiezan por "StronglyConnectedComponents" son lo que tendrías que poner y lo que debería salir con el grafo de ejemplo que se crea al final (es el mismo que el del enunciado)