EXAMEN Febrero 2014 Estructuras de datos. Resolución Segunda Parte. Java

¿Al fin viernes no? Primer fin de semana del segundo cuatrimestre para los de Ingeniería Informática. ¿Sabeis ya todas las notas? Espero que todo bien ;)

Bueno, aquí os traigo la segunda parte del examen de ED de este año. La parte de Java. El enunciado lo teneis aquí.

El archivo resultado .java lo teneis aqui para descargar, si no quereis andar copiando y pegando.

Aquí os dejo el code ;)

package dataStructures.graph;

import java.util.Iterator;

import dataStructures.list.List;
import dataStructures.set.Set;
import dataStructures.set.HashSet;

public class SCCDiGraph {

  /* 
   * apartado A
   */
   public static  DiGraph reverseDiGraph(DiGraph g){
   DiGraph reversedDiGraph = new DictionaryDiGraph();
   for(V v : g.vertices()){ //Introduce los vértices
    reversedDiGraph.addVertex(v);
   }
   
   for(V v : g.vertices()){ //Introduce las aristas
    for(V w : g.vertices()) {
     if(g.successors(v).isElem(w)) {
      reversedDiGraph.addDiEdge(w, v);
     }
    }
   }
   
   return reversedDiGraph;
  }

   /* 
    * apartado B
    */
  public static  DiGraph restrictDiGraph(DiGraph g, Set vs){

   DiGraph restrictedGraph = new DictionaryDiGraph();
   for(V v : vs) {
    restrictedGraph.addVertex(v);
   }
   
   
   for(V v : vs) {
    for(V w : vs) {
     if(g.successors(v).isElem(w)) {
      restrictedGraph.addDiEdge(v, w);
     }
    }
   }
   
   return restrictedGraph;
  }

  /* 
    * apartado C
    */
  public static  Set sccOf (DiGraphg, V src) {
   Set vertices = new HashSet<>();
   
   DepthFirstTraversal busqueda = new DepthFirstTraversal(g, src); //1)
   vertices =  iterableToSet(busqueda.vertices());
   
   DiGraph  restricted = restrictDiGraph(g, vertices); //2)
   DiGraph  inversed = reverseDiGraph(restricted); //3)
   
   DepthFirstTraversal acabada = new DepthFirstTraversal(inversed, src); //4)
   
   Set vertices2 = iterableToSet(acabada.vertices());
   
   return vertices2;
  }

  
  /* 
    * apartado D
    */
  public static <V> Set<Set<V>> stronglyConnectedComponentsDiGraph(DiGraph<V> graph) {
   Set<Set<V>> components  = new HashSet<Set<V>>();
   Set<V> auxiliar = graph.vertices();
   for(V v : graph.vertices()) {
    if(auxiliar.isElem(v)) {
     Set<V> aux2 = sccOf(graph, v);
     components.insert(aux2);
     for(V w : aux2) {
      auxiliar.delete(w);
     }
     
    }
    
   }
   return components;
  }

 static  Set iterableToSet(Iterable it) {
  Set set = new HashSet();
  for(V v : it)
   set.insert(v);
  return set;  
 }
 
 

}

De todos modos aquí os dejo un main de testeo para que veais si el vuestro está bien.

public static void main(String[] args) {
 // TODO Auto-generated method stub
  DiGraph graph = new DictionaryDiGraph<>();
    graph.addVertex('A');
    graph.addVertex('B');
    graph.addVertex('C');
    graph.addVertex('D');
    graph.addVertex('E');
    graph.addVertex('F');
    graph.addVertex('G');
    graph.addVertex('H');

    graph.addDiEdge('A', 'B');
    graph.addDiEdge('B', 'E');
    graph.addDiEdge('E', 'A');
    graph.addDiEdge('B', 'F');
    graph.addDiEdge('E', 'F');
    graph.addDiEdge('F', 'G');
    graph.addDiEdge('G', 'F');
    graph.addDiEdge('C', 'G');
    graph.addDiEdge('H', 'G');
    graph.addDiEdge('C', 'D');
    graph.addDiEdge('D', 'C');
    graph.addDiEdge('D', 'H');
    graph.addDiEdge('H', 'D');
    
    
    System.out.println(graph);
    System.out.println(reverseDiGraph(graph));
    Set vertices = new HashSet<>();
    vertices.insert('A');
    vertices.insert('B');
    vertices.insert('E');
    vertices.insert('F');
    vertices.insert('G');
    System.out.println(restrictDiGraph(graph, vertices));
    
    System.out.println(stronglyConnectedComponentsDiGraph(graph));
    
 }

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)