martes, 18 de febrero de 2014

EXAMEN Febrero 2014. Estructuras de Datos. Enunciados

Buenas. Aquí os traigo los enunciados del examen de Estructuras de datos que hemos hecho hoy (día 18/02/2014) en Ingeniería Informática en la UMA.  Tanto la parte de Haskell como la de Java son el mismo programa. La resolución de la de Haskell la subiré el Miércoles y la de Java el viernes.

Aquí los archivos necesarios. (Debeis esperar el tiempo que os dice y arriba a la derecha darle a entrar).
Nota: Los códigos además los pegaré, pero con las librerías no puedo hacerlo. ;)
Plantilla Haskell -> Es sobre lo que deberíais de trabajar.
Librerías que utilizar -> Debeis descomprimir el archivo en el mismo sitio donde tengais la plantilla.
Librerías de Java
Plantilla de Java -> Es un txt. Copiadlo en la class.

Para la de Haskell, en la misma carpeta deberían de estar la plantilla (Es el archivo sobre el que codeareis) y la carpeta DataStructures (Dentro del zip).
Para la de Java. Debeis crear un paquete llamado dataStructures.graph y dentro de él, una clase que se llame SCCDiGraph. Luego importais las librerias (el unit6.jar)

Aquí teneis el enunciado:
Cómputo de las Componentes Fuertemente Conexas de un digrafo.
Dado un digrafo g , se dice que dos vértices v y w están fuertemente conectados (escrito v FC w) si existe un camino desde v hasta w y otro camino desde w hasta v . Por ejemplo, para el grafo de la izquierda de la Figura 1, los vértices A y B están fuertemente conectados, pero los vértices F y B no lo están.
 La relación FC es una relación de equivalencia y sus clases de equivalencia se llaman Componentes Fuertemente Conexas o SCCs (Strongly Connected Components). Por ejemplo, la colección [A,E,B]es una clase de equivalencia, o sea, una componente fuertemente conexa. En la parte derecha de la Figura 1 aparecen del mismo color los vértices de cada una de las tres componentes. Para computar la SCC (Strongly Connected Component) de un vértice v podemos seguir los siguientes pasos: 

1. Exploramos en profundidad el grafo g desde v; sea vs la lista de vértices obtenida. Entre estos vértices estará la componente fuertemente conexa de v ya que la lista vs contiene solo y únicamente los vértices alcanzables desde v.
2. Por ello, nos limitaremos al subgrafo de g con vértices en vs; sea pues el grafo gr, restricción de g al conjunto de vértices de vs. 
3. Ahora computamos g’, el grafo inverso de gr. Entonces, para cada vértice w visitable desde v en el grafo g’, existirá un camino desde w hasta v en el grafo original g. 
4. Si exploramos en profundidad el grafo g’ desde v, la lista de vértices obtenida es la Componente Fuertemente Conexa (SCC) de v.
Por ejemplo, para el grafo de la Figura 1, la exploración en profundidad desde A proporciona la lista de vértices [A,B,F,G,E] = vs coloreados en rojo en la parte izquierda de la Figura 2. La restricción de g sobre esta lista, es decir el subgrafo gr obtenido en el paso 2, aparece en el centro de la Figura 2. Su grafo inverso g’obtenido en el paso 3, aparece en la parte derecha de la Figura 2. Al explorar en profundidad g’ partiendo del vértice A (paso 4) obtenemos la lista [A,E,B], que es la componente fuertemente conexa del vértice A.


Ejercicios a realizar:
(A) Escribe la función que devuelve el grafo inverso de un digrafo:
reverseDiGraph :: Eq a => DiGraph a -> DiGraph a


(B) Escribe la función que toma un grafo g y una lista de vértices vs y devuelve el subgrafo de g con vértices en vs:
restrictDiGraph :: Eq a => DiGraph a -> [a] -> DiGraph a


(C) Con ayuda de las funciones anteriores, siguiendo los pasos 1-4 descritos anteriormente, escribe una función para computar la SCC sobre un grafo de un determinado vértice:
type SCC a = [a]
sccOf :: Ord a => DiGraph a -> a -> SCC a


(D) Aplicando reiteradamente la función anterior, podemos obtener todas las componentes del grafo original
eliminando en cada paso los vértices de la componente computada. Escribe la función correspondiente a este cómputo:
sccs :: Ord a => DiGraph a -> [SCC a]

Ahora en java:

(A) Define un método que tome un digrafo como argumento y devuelve su grafo inverso:
public static <V> DiGraph<V> reverseDiGraph(DiGraph<V> g)


(B) Escribe el método que toma un grafo g y una lista de vértices vs y devuelve el subgrafo de g con vértices en vs:
 public static <V> DiGraph<V> restrictDiGraph(DiGraph<V> g, Set<V> vs)


(C) Con ayuda de los métodos anteriores, siguiendo los pasos 1-4 descritos anteriormente, escribe un método para computar la SCC sobre un grafo g de un determinado vértice src:
public static <V> Set<V> sccOf (DiGraph<V> g, V src)


(D) Aplicando reiteradamente el método anterior, podemos obtener todas las componentes del grafo original
eliminando en cada paso los vértices de la componente computada. Escribe el método correspondiente a este cómputo:
public static <V> Set<Set<V>> stronglyConnectedComponentsDiGraph(DiGraph<V> g)


Aquí os pongo la plantilla de Haskell:


module StronglyConnectedComponents  where

import DataStructures.Graph.DiGraph 

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

import Data.List( (\\) )

-------
-- A --
-------
reverseDiGraph :: Eq a => DiGraph a -> DiGraph a
reverseDiGraph g = undefined

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


deleteVertices :: Eq a => [a] -> DiGraph a -> DiGraph a
deleteVertices xs g = mkDiGraphSuc (vertices g\\xs) suc' 
   where suc' v = (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 = undefined

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

-------
-- D --
-------
-- todas las componentes
sccs :: Ord a => DiGraph a -> [SCC a]
sccs g  = undefined


{-
*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]




Y aquí la de Java ;)
package dataStructures.graph;

import dataStructures.set.Set;
import dataStructures.set.HashSet;

public class SCCDiGraph {

  /* 
   * apartado A
   */
   public static  DiGraph reverseDiGraph(DiGraph g){
   DiGraph reversedDiGraph = new DictionaryDiGraph();
   // Vuestro Resultado aqui
   return reversedDiGraph;
  }

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

   DiGraph restrictedGraph = new DictionaryDiGraph();
   // Vuestro Resultado aqui

   return restrictedGraph;
  }

  /* 
    * apartado C
    */
  public static  Set sccOf (DiGraphg, V src) {
   //Vuestro Resultado aqui

   return null;
  }

  
  /* 
    * apartado D
    */
  public static  Set> stronglyConnectedComponentsDiGraph(DiGraph graph) {
   Set> components  = new HashSet>();
   // Vuestro Resultado aqui

   return components;
  } 

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

Pasadlo bien :p Saludos ;)

No hay comentarios:

Publicar un comentario