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));
    
 }