Solucion examen febrero 2013

PARTE JAVA

import dataStructures.graph.BreadthFirstTraversal;
import dataStructures.graph.Graph;
import dataStructures.graph.Traversal;

public class GraphUtil {

    /**
     * LENGTH: Calcula el número de elementos que contiene un iterable
     *
     * @param it  El iterador
     * @return   Número de elementos en el iterador
     */
    public static <T> int length(Iterable<T> it) {
        int cont = 0;
      
        for(T aux: it){
            cont++;
        }
        return cont;
    }

    /**
     * ECCENTRICITY: Calcula la excentricidad de un vértice en un grafo El algoritmo toma la
     * longitud del camino máximo en un recorrido en profundidad del grafo
     * comenzando en el vértice dado.
     *
     * @param graph    Grafo
     * @param v        Vértice del grafo
     * @return         Excentricidad del vértice
     */
    public static <T> int eccentricity(Graph<T> graph, T v) {
        // TO DO
        int aux = 0;
        Traversal<T> bfs = new BreadthFirstTraversal<T>(graph, v);
        for(Iterable<T> path: bfs.paths()){
            if((aux == 0) || (aux < length(path))){
                aux = length(path);
            }
          
        }
        if(aux == 0){
            return 0;
        }else{
            return aux - 1;
        }
    }

    /**
     * DIAMETER: Se define como la máxima excentricidad de los vértices del grafo.
     *
     * @param graph
     * @return
     */

    public static <T> int diameter(Graph<T> graph) {
        // TO DO
        int aux = 0;
        for(T vertice: graph.vertices()){
            if((aux == 0) || (aux < eccentricity(graph, vertice))){
                aux = eccentricity(graph, vertice);
            }
        }
        return aux;
    }
   
    /**
     * Estima y justifica la complejidad del metodo diameter
     *
     * La complejidad del metodo es n^2, ya que el metodo consta de un bucle que depende
     * del numero de vertices del grafo, haciendo en su interior una llamada al metodo
     * eccentricity que tambien consta de un bucle que recorre todo el grafo volviendo
     * a depender del numero de vertices que este tenga, haciendo por lo tanto que
     * ambos bucles tengan complejidad n, por lo que convierte la complejidad de
     * diameter en n^2.
     */
}
                   

HASKELL

module Diameter(
    diameter    -- :: Ord v  => Graph v -> Int
  )  where

import DataStructures.Graph.Graph
import DataStructures.Graph.GraphBFT(
     bftPaths    -- :: (Ord a) => Graph a -> a -> [Path a]
  )

---------------
--- APARTADO 1
---------------
-- La excentricidad de un vértice v se define como la distancia máxima
-- entre v y el resto de los vértices.

-- Si el grafo es conexo, la excentricidad coincide con la profundidad
-- del  árbol de  búsqueda  en anchura  (BFST: Breadth-First  Spanning
-- Tree); con raíz el vértice v.

-- Defina la función
eccentricity :: (Ord v) => Graph v -> v -> Int
eccentricity g v0 = (length (maximumBy tam (bftPaths g v0)) - 1)
          where
              maximumBy               :: (a -> a -> Ordering) -> [a] -> a
              maximumBy _ []          =  error "List.maximumBy: empty list"
              maximumBy cmp xs        =  foldl1 maxBy xs
                        where
                           maxBy x y = case cmp x y of
                                       GT -> x
                                       _  -> y
              tam a b = compare (length a) (length b)
---------------
--- APARTADO 2
---------------
-- El  diámetro de  un grafo  conexo se  define como  la excentricidad
-- máxima de sus vértices.

diameter :: Ord v => Graph v -> Int
diameter g = maximum [eccentricity g v | v <- vertices g]

---------------------
--- EXAMPLES --------
---------------------

data MiVertice = A|B|C|D|E|F|G|H deriving (Show,Eq,Enum,Ord)

{-
  A--B--C
   \ |\ |
     D  E--F--G
-}
g1  = mkGraphSuc vertices suc
  where
        vertices = [A .. G]
        suc A = [B,D]
        suc B = [A,C,D,E]
        suc C = [B,E]
    suc D = [A,B]
        suc E = [B,C,F]
        suc F = [E,G]
    suc G = [F]
{-
  A--B--D--F
     |  |
     C--E
-}
g2  = mkGraphEdges vertices edges
  where
        vertices =  [A .. F]
        edges = [(A,B),(B,C),(B,D),(C,E),(D,E),(D,F)]

{-
A--B--D--F
   |  |
   C  E--G
-}
g3  = mkGraphEdges vertices edges
  where
        vertices =  [A .. G]
        edges = [(A,B),(B,C),(B,D),(D,E),(D,F),(E,G)]

{-
1--2--3--4--5--6--7--8
               |     |
               10----9
-}
g4  = mkGraphEdges vertices edges
  where
        vertices =  [1 .. 9]
        edges = [(1,2),(2,3),(3,4),(4,5),(5,6),(6,7),(7,8),(8,9)
                 ,(6,10),(9,10)  ]