Programming 3

What do I have to do?

Your job in this assignment is to convert a model made without generics into a more suitable model that does use generics. You will also add Java reflection-based code to perform operations that otherwise could not be performed.

Once you understand the object-oriented construction of the model and the algorithms described below, you should follow the steps described in Tasks to do.

Model

A graph (Graph) is composed of a set of nodes (Node) and edges (Edge). Nodes are objects that have a numeric identifier and contain something (in the UML, a string) and edges connect nodes together, so we can ‘traverse’ the nodes of the graph by traversing edges. An edge always has a starting and an ending node (they are unidirectional). Nodes may or may not have incoming and/or outgoing edges. Edges also have a numeric identifier and a content (in the UML above, a string).

The {unique} tag you see in the relationship between Graph and Node or Edge indicates that a graph can only contain the same node or edge once. For that, the relation must be implemented as a set (Set<T>) of nodes/edges. Unlike a list (List<T>), a set cannot contain duplicate elements. Study the part dedicated to Sets on our website, to know how to use them (they are very similar to lists).

In order to properly use sets (Set), it is necessary to be able to distinguish nodes and edges univocally. To do this, a unique identifier has been added to each one using the singleton IDGenerator class (a singleton class is one of which we only have one instance in the whole application – you can see the source code to check how we managed to implement this restriction). To unify the functionality of maintaining a unique identifier as well as a label, both Node and Edge inherit from the abstract GraphObject class that implements the IIdentifiable interface. In this starting design, all labels are of type string.

The nodes do not know which edges they are related to. The network does have that information. The edges do know their source and destination nodes.

In an application that uses the library, we can have several graphs instantiated. In the methods of Graph that receive a node as a parameter, it is checked that it belongs to the invoked graph, throwing NodeNotFoundException in case it does not belong to it.

The names and symbols of each method shown in the UML are descriptive enough to understand their meaning. We do not describe them in more detail because it is not necessary to do the task of this practical assignment. In any case, the javadoc documentation included in the source code contains enough information for anyone who wants to consult it.

Algorithms

<!–> Note: In this UML, notation using generic types (Graph<NodeType, LabelType>, etc.) has not been indicated in order to simplify the diagram. –>

A number of algorithms have been created using the above model. The Algorithms class centralises the access to the different algorithms. As such, each algorithm is defined with package visibility. You can see that there are non-optimised elements in that class.

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

Library application: network map

As an application of the library we have created a graph representation of a very simple network map with the simple calculation of network latencies based on the shortest path between nodes in the network.

The problem we have with the current graph representation of our library is that storing only strings makes it difficult to properly store devices (Device) as graph nodes because we lose information.

Therefore, you will have to add generics to the graph so that it supports any type of data in both labels and nodes. The full implementation (which you should not modify) of this network map provided in the Eclipse base project already uses the result of that conversion of the graph to generic types, so it will not compile until you correctly add generics.

Introduction of generics

To extend the possibilities of this small graph library, to avoid solutions like the string-to-integer conversion used in the DijkstraShortestPath class explained above, and to allow the application on a network map also described above, we are asked to modify the graph so that it can contain any type of data as label, both in the nodes and in the edges, being one type for the nodes and a different one for the edges.

We do not show new class diagrams but we indicate one by one the steps that you must follow and that you will have to understand in order to finish the assignments. Please note that if you are not able to understand the changes you need to make, it is possible that your implementation does not compile at all..

Have a look at the es.ua.dlsi.prog3.p6.network package and the GraphTests.java test. You will see how Graph receives two type arguments, one for the node label and one for the edge label. Parameterize Graph, GraphObject, Node and Edge to turn them into generic classes where the type of the label becomes generic, so that the code in the network package works. Use LabelType, or NodeLabelType and EdgeLabelType as type parameter names when it is necessary to distinguish between node and edge labels. Note that, like Graph, Edge will have two type parameters: one for the edge label and one for the label of the nodes it connects.

In the Graph code we already use generic types to declare references to generic types defined in java.util, such as Map or Set. You will need to parameterise the nodes and edges appropriately.

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); // Compilation error

Using reflection in Java

The last part of this assignment consists of the use of the reflection mechanism in Java.

For this we have created a series of classes described in the following UML.

The class Code2Graph constructs a graph Graph that shows the dependencies between classes. To do so, it relies on a number of classes that use reflection. Although unit tests evaluate whether everything works, you can use the main of that class if you want to experiment with it.

The task you’ll need to do is to implement the ClassAnalyzer and ReflectionUtils classes from the es.ua.dlsi.prog3.p6.reflection.impl package that we give you empty.

We give hints below on how to implement them by using Java reflection.