Programming 3

University of Alicante, 2023–2024

Sixth Programming Assignment

Relative weight of this assignment in the practice grade: 15%.

Generics and reflection

In this practical assignment we will work on generics in Java through the activities described below. We will also make use of some Java reflection mechanisms.

This link provides an Eclipse project with the implementation of a graph class (Graph), detailed in the attached UML, which is only able to contain strings in both nodes and edges. A number of algorithms are also included, these algorithms use the graph and whose references to the graph should be updated accordingly. The project contains a list of appropriate unit tests to check the operation of each class. The project currently has compilation errors pending your completion of the tasks outlined in this statement.

(If you need to remember what a graph is, here is a mini-introduction (in Spanish)).

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.


Starting UML: 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.


Starting UML: 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.


Within the algorithms, the DotExporter class is able to export the graph in DOT format for GraphViz. There are many viewers of this format on the web, for example this one.

In DotExporter the class File is used as a reference to a file on disk, and the class PrintStream as an abstraction that encapsulates the behaviour of writing different types of data such as char, String, int, etc. into files.

As the export is to file, to better understand the code of this class you can consult this introduction to the Java input/output system (in Spanish), also accessible from the main page of the course.

The DFS class traverses the graph starting from a given node using the DFS algorithm, returning the sequence of nodes visited as a deep copy to respect the composition between Graph and Node.

Finally, the DijkstraShortestPath class performs the computation of the shortest path from a given node to the rest of the nodes in the graph with the compute method, using the Dijkstra algorithm. We can then invoke getComputedDistances by passing that node as a parameter.

DijkstraShortestPath relies on the inner class DijkstraShortestPath.Cost to be able to compare weights in the calculation of the distances between nodes. The problem we have is that these weights are stored in the edges with a string data type. In the implementation we provide, in the method DijkstraShortestPath.processNeighbours(), lines 157-158, a conversion from String to Integer is performed to perform the calculations, which is not the most advisable way to do it and that we will solve it later:

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

Note: we cannot directly compare strings because it would be a lexicographic comparison and “9” would be compared as less than “10”.

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.

Network model

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.

Tasks to perform

You will need to modify the code of the project we provide. This already contains the network map code described above and unit tests that should work once you have performed all the tasks described below.

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 package and the 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.


When implementing this class we run into the problem that, being an exception, it cannot be generic. Therefore, we can only use Node and Node<?>, which allows any type. For the intended use of the class this is more than enough.

After correctly entering the generics, the tests in should compile and run correctly.


DFS and DotExporter

To parameterise the DFS and DotExporter classes we will repeat exactly the same process we have done to introduce generics in the graph. Thus, the classes will be defined as DFS<NodeLabelType, EdgeLabelType> and DotExporter<NodeLabelType, EdgeLabelType>.


The calculation of the shortest path requires the operation of addition and comparison between edge weights. In the string-based implementation this was done by converting the edge label string into a number and using the native comparison and addition operators (<, +, …). However, if we now want to be able to operate on any data type in the label we must provide a way to perform that operations.

We need to perform two actions. The first is to force the type of the edge label to be comparable, i.e. implement the Comparable interface.

The second is to create a mechanism to be able to operate on the weights of the edges, whatever their data type. We achieve this with the introduction of a generic interface ICostOperators that we show in the diagram and that you will have to implement. This interface defines three generic operations on the type T: the sum, the zero value and the maximum value. Notice how in the test this interface is implemented by means of an anonymous class.

In addition, you need to add a reference to this class as a parameter to the constructor of DijkstraShortestPath and store it as an attribute:

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;

Now, the distances from nodes stored in the dist property need not be Integer, but of the parameterised type of the edges, EdgeLabelType, which we know are comparable. The cost attribute of the inner class Cost will now also be of type EdgeLabelType.

Since we no longer know what the zero and maximum values of the cost weight of an edge are, as these depend on the data type, we will use the zero() and maximumValue() methods of ICostOperators. In the compute() method, use these methods where it is necessary to know the maximum value and zero value of the cost of an edge.

In this code we use the PriorityQueue class from the Java Collections Frameworks. A priority queue is a queue in which the items are queued according to a priority, so we need to provide a sorting method. For this we use the Comparator interface. You can see how to use it in our Easy Guide to the Java Collection Framework (in Spanish).

Finally, in the code of the processNeighbours() method, which adds and compares distances, we must replace the string-to-integer conversion we had, as well as replace the additions and the direct comparisons with the integer operators + and < by the use of ICostOperators.add() and Comparable.compareTo(), respectively. Specifically, you will need to replace:

// 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) {

In the previous code for graphs with strings, the static methods of the Algorithms class used non-parameterised types. However, now all classes in the graph are parametrised, so you must parameterise the static methods of Algorithms so that they compile and work correctly with the generic classes. Note that you don’t have to parameterise the Algorithms class, but its static methods.

Note that to parameterise shortestPathCost() the edge type must implement the Comparable interface. In addition, the signature of the method changes as follows:

  • it returns EdgeLabelType (remember: this is the data type that defines the ‘cost’ of an edge).
  • we must add a fourth argument of type ICostOperators<EdgeLabelType> which we then pass to the constructor of DijkstraShortestPath.

Network map application

In the code we have provided in the Network and NetworkTest classes we see that we cannot make the call to printLatencyMap() because of Java type erasure:

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

To fix this you must use a wildcard for generic types in the printLatencyMap and computeLatencyMap methods. Instead of List<Device>, to support any type that inherits from Device you must use List<? extends Device>.

When ready, run Network.main() or to see that everything works.

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 package that we give you empty.

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

  • findDependantClasses: This method is given already implemented. It can be used as a guide when using reflection. It traverses the constructors (getConstructors()) and methods (getDeclaredMethods()) of the class and returns its parameter classes (getParameterTypes()) and return types (getReturnType()).
  • findParentClass: returns the superclass of the given class, or null if it has no superclass.
  • haveSamePackage: evaluates whether two classes belong to the same package.
  • findAssociatedClasses: returns a set of classes to which the attributes defined in the class belong (getDeclaredFields()). Use the Field.getType() method to get the type of the attributes.
  • instantiate: creates a new instance of the class. Since no parameters are passed to the constructor we can use the newInstance() method of the class. Notice how we have parameterised the method with <T> so that the client code of this method does not need to do any type conversion (instantiate() will need to do type conversion (T)).
  • findClassInPackage: compose the qualified class name by concatenating the package and class name, interposing a dot (“.”), and use the forName() method of Class.
  • isImplementingInterface: to find out if a class implements an interface, the easiest way is to ask if we can assign that class to the interface (see isAssignableFrom() in Class).

You can see how we use these two classes in the code of Code2Graph. For example, it is interesting to check how the IClassAnalyzer classAnalyzer property of this class is not created through a new clause, instead reflection is used to locate the class in a package that we provide as a string (see createGraph method).


It is not necessary to document this practical assignment

You can document the code you write, in fact we recommend it, but it will not be evaluated.

Minimal requirements for grading your assignment

  • Your program must run with no errors.
  • Unless otherwise stated, your program must not emit any kind of message or text through the standard output or standard error streams. Also avoid error output messages.
  • The format of the name of all properties must be strictly respected, both in terms of scope of visibility and in terms of type and way of writing. Make sure that you respect the distinction between class and instance attributes, as well as the uppercase and lowercase letters in the identifiers.

Submission of the assignment

Submit your work to DLSI practice server.

You must upload a compressed file with your source code (only .java files). In a terminal, place yourself in the ‘src’ directory of your Eclipse project and enter the command

tar czvf prog3-p6.tgz *

This will compress all the code in src/, including those classes that were already implemented. This is correct and should be delivered as is.

Upload the file prog3-p6.tgz to the practice server. Follow the instructions on the page to log in and upload your work.


Testing of your assignment will be done automatically. This means that your program must strictly conform to the input and output formats given in this document, as well as to the public interfaces of all the classes: do not change the method signatures (name of the method, number, type and order of arguments, and data type returned) or their behaviour. So, for example, the Clase(int,int) method must have exactly two arguments of type int.

You can find more information about the grading of programming assignments in the subject description sheet.

In addition to the automatic grading, a plagiarism detection application will be used.

The applicable regulations of the University of Alicante Polytechnic School in the event of plagiarism are indicated below:

“Theoretical/practical work must be original. The detection of copy or plagiarism will suppose the qualification of”0” in the corresponding assignment. The corresponding Department and the University of Alicante Polytechnic School will be informed about the incident. Repeated conduct in this or any other subject will result in notification of the offences committed to the pertinent vice canchellor’s office so that they study the case and punish it in accordance with the legislation in force”.