Programación 3

¿Qué tengo que hacer?

Tu trabajo en esta práctica consiste en pasar un modelo realizado sin genericidad a otro más adecuado que sí la use. También se añadirá código basado en reflexión de Java para realizar unas operaciones que de otra forma no se podrían abordar.

Una vez hayas entendido la construcción orientada a objetos del modelo y los algoritmos que describimos a continuación, debes seguir los pasos descritos en Tareas a realizar.

Modelo

Un grafo (Graph) está compuesto por un conjunto de nodos (Node) y aristas (Edge). Los nodos son objetos que tienen un identificador numérico y contienen algo (en el UML, una cadena) y las aristas conectan nodos entre sí, de manera que podemos ‘recorrer’ los nodos del grafo atravesando aristas. Una arista tiene siempre un nodo de partida y otro de llegada (son unidireccionales). Los nodos pueden o no tener aristas entrantes y/o salientes. Las aristas también tienen un identificador númerico y un contenido (en el UML anterior, una cadena).

La etiqueta {unique} que ves en la relación entre Graph y Node o Edge indica que un grafo sólo puede contener el mismo nodo o arista una vez. Para eso la relación se debe implementar como un conjunto (Set<T>) de nodos/aristas. A diferencia de una lista (List<T>), un conjunto no pueden contener elementos duplicados. Estudia la parte dedicada a los Set en nuestra web, para saber cómo usarlos (son muy parecidos a las listas).

Para poder usar adecuadamente los conjuntos (Set) es necesario poder distinguir de manera unívoca los nodos y las aristas. Para ello se ha añadido un identificador único a cada uno mediante la clase singleton IDGenerator (una clase singleton es aquella de la que sólo tenemos una instancia en toda la aplicación – puedes ver el código fuente para comprobar cómo conseguimos implementar esa restricción). Para unificar la funcionalidad de mantener un identificador único así como una etiqueta, tanto Node como Edge heredan de la clase abstracta GraphObject que implementa la interfaz IIdentifiable. En este diseño de partida, todas las etiquetas son de tipo cadena.

Los nodos no saben con qué aristas se relacionan. El grafo sí dispone de esa información. En cambio las aristas sí conocen sus nodos origen y destino.

En una aplicación que utilice la librería podemos tener instanciados varios grafos. En los métodos de Graph que reciben como parámetro un nodo se comprueba que éste pertenece al grafo al que se invoca, lanzando NodeNotFoundException en caso de que no pertenezca.

Los nombres y signaturas de cada método mostrado en el UML son suficientemente descriptivos como para entender su significado. No los describimos con más detalle porque no es necesario para realizar la práctica. En cualquier caso, la documentación javadoc incluida en el código fuente contiene suficiente información para quien la quiera consultar.

Algoritmos

Se han creado una serie de algoritmos que utilizan el modelo anteriormente expuesto. La clase Algorithms centraliza el acceso a los distintos algoritmos. Por ello, cada algoritmo está definido con visibilidad de paquete. Puedes ver que hay elementos no optimizados en esa clase.

int edgeDistance = Integer.parseInt(edge.getLabel()); 
int newDistance = dist.get(source) + edgeDistance;

Aplicación de la librería: mapa de red

Como aplicación de la librería hemos creado una representación en grafo de un mapa de red muy sencillo con el cálculo simple de latencias de red basado en el camino más corto entre nodos del grafo.

El problema que tenemos con la representación actual del grafo de nuestra librería es que al almacenar sólo cadenas nos es difícil guardar adecuadamente los dispositivos (Device) como nodos del grafo porque perdemos información.

Por ello, deberás añadir genericidad al grafo para que admita cualquier tipo de dato tanto en las etiquetas como en los nodos. La implementación completa (que no debes modificar) de este mapa de red que se proporciona en el proyecto base de Eclipse ya usa el resultado de esa conversión del grafo a tipos genéricos, por lo que no compilará hasta que añadas correctamente la genericidad.

Introducción de genericidad

Para ampliar las posibilidades de esta pequeña librería de grafos, evitar soluciones como la conversión de tipo cadena a entero usada en la clase DijkstraShortestPath que hemos explicado anteriormente, y permitir la aplicación sobre un mapa de red también descrita arriba, se nos pide que modifiquemos el grafo para que pueda contener cualquier tipo de dato como etiqueta, tanto en los nodos como en las aristas, pudiendo ser un tipo para los nodos y otro distinto para las aristas.

No mostramos nuevos diagramas de clases sino que indicamos uno a uno los pasos que debes realizar y que deberás entender para poder acabar de realizar la práctica. Ten en cuenta que si no eres capaz de entender los cambios que tienes que realizar, es posible que la práctica no te compile en absoluto.

Fíjate en el paquete es.ua.dlsi.prog3.p6.network y en el test GraphTests.java. Verás como Graph recibe dos argumentos de tipo, uno para la etiqueta de los nodos y otro para la de las aristas. Parametriza Graph, GraphObject, Node y Edge para convertirlas en clases genéricas donde el tipo de la etiqueta pasa a ser genérico, de manera que el código del paquete network funcione. Usa como nombres para los parámetros de tipo LabelType, o NodeLabelType y EdgeLabelType cuando sea necesario distinguir entre etiquetas de nodo y de arista. Ten en cuenta que, al igual que Graph, Edge tendrá dos parámetros de tipo: uno para la etiqueta de la arista y otro para la etiqueta de los nodos que conecta.

En el código de Graph ya usamos tipos genéricos para declarar referencias a tipos genéricos definidos en java.util, como Map o Set. Deberás parametrizar los nodos y aristas adecuadamente.

class DijkstraShortestPath<NodeLabelType, EdgeLabelType extends Comparable<EdgeLabelType>> { 
    ...
    private ICostOperators<EdgeLabelType> costOperators;
    ...
    public DijkstraShortestPath(Graph<NodeLabelType, EdgeLabelType> graph, ICostOperators<EdgeLabelType> costOperators) {
        this.graph = graph;
        this.costOperators = costOperators;
    }
    ...

// If new distance is cheaper in cost
int edgeDistance = Integer.parseInt(edge.getLabel());
int newDistance = dist.get(source) + edgeDistance;
 
// If new distance is cheaper in cost
if (newDistance < dist.get(target)) {

// If new distance is cheaper in cost
EdgeLabelType edgeDistance = edge.getLabel();
EdgeLabelType newDistance = costOperators.add(dist.get(source), edgeDistance);
 
// If new distance is cheaper in cost
if (newDistance.compareTo(dist.get(target)) < 0) {

public class Network {
    ...
    public void printLatencyMap(List<Device> devices) {
        ...
    }

    ...
    public static final void main(String [] args) {
        Network network = new Network();
        Computer c1 = new Computer(.....);
        ...
        List<Computer> computers = Arrays.asList(c1, c2);
        network.printLatencyMap(computers); // Error de compilación

Uso de la reflexión en Java

La última parte de la práctica consiste en que utilicemos el mecamismo de la reflexión en Java.

Para ello hemos creado una serie de clases descritas en el siguiente UML.

La clase Code2Graph construye un grafo Graph que muestra las dependencias entre clases. Para ello se apoya en una serie de clases que usan reflexión. Aunque en las pruebas unitarias se evalúa si todo funciona, puedes usar el main de esa clase si quieres experimentar con ella.

La tarea que deberás realizar es la de implementar las clases ClassAnalyzer y ReflectionUtils del paquete es.ua.dlsi.prog3.p6.reflection.impl que te damos vacías.

Damos pistas a continuación de cómo implementarlas mediante el uso de la reflexión de Java.