Examen febrero 2013

Dado un grafo g se denomina distancia entre dos vértices distintos a la longitud del camino mínimo
que los une. Por ejemplo, para el grafo de la figura:

 

las distancias desde los vértices A y E con el resto de los vértices son las siguientes:
                            
La excentricidad de un vértice se define como la máxima distancia medida desde ese vértice; es
decir, como la longitud del camino mínimo más largo que parte desde ese vértice. Para los vértices A y E tenemos:
                                        excentricidad(A) = 4 excentricidad(E) = 2
Finalmente, eldiámetro de un grafo g se define como la distancia que separa a sus dos vértices más
alejados; es decir, como la máxima excentricidad de sus vértices, o la longitud del camino mínimo más largo que hay en el grafo. Para el grafo de la figura tenemos:
                                                      diámetro(g) = 4
Para calcular las distancias y excentricidades de un vértice, y el diámetro de un grafo es conveniente
recorrer el grafo en anchura (BFT), ya que este recorrido devuelve los caminos mínimos desde un
vértice dado a todos los demás. Por ejemplo, para el grafo de la figura tenemos los siguientes caminos
mínimos calculados por el recorrido en anchura desde el vértice A:
                             {(A), (A,D), (A,B), (A,B,E), (A,B,C), (A,B,E,F), (A,B,E,F,G)}
y desde el vértice E:
                             {(E), (E,F), (E,C), (E,B), (E,F,G), (E,B,D), (E,B,A)}

Haskell

UsandolafunciónbftPathsdelatransparencia162,implementalassiguientesfuncionesparacalcular
la excentricidad de un vértice y el diámetro de un grafo:
             eccentricity :: Ord v => Graph v -> v -> Int
             diameter :: Ord v => Graph v -> Int

Java

Usando el métodopaths de la claseBreadthFirstTraversal de la transparencia 227, implementa
la clase JavaGraphUtil para calcular la excentricidad de un vértice y el diámetro de un grafo:
             public class GraphUtil {
                      // length calcula el número de elementos que contiene un iterable
                      public static <T> int length(Iterable<T> it);
                      public static <T> int eccentricity(Graph<T> graph, T v);
                      public static <T> int diameter(Graph<T> graph);
             }
Observa que la claseGraphUtil también implementa el métodolength, que calcula el número de elementos
que contiene unIterable; es decir, el número de elementos que visita un iterador. Tendrás que
utilizar este método para implementareccentricity.
Estimalaclasedecomplejidadalaqueperteneceelalgoritmoimplementadoporelmétododiameter.
Escribe tu resultado y el razonamiento que has seguido en el comentario correspondiente de la plantilla.