Triangular Graph

In some applications we want something like 2-dimensional arrays but we will always have that a[i][j] and a[j][i] are (or should be) the same. In particular this is the case when we have the adjacency matrix for a non-directed graph. Often, people will use 2-dimensional arrays anyway, but that leaves half the memory wasted. We can do better than that by creating a bespoke class that realises arrays of this kind.

The task for this assessment is to complete the Triangular project (zip file for download). This involves the following:

• Complete the class design for class Triangular, i.e. add the fields you need to store the data, complete the constructor, and also the copy method (which is needed for cloning objects). The generic type parameter A of the class is the "component type" of our triangular array.
• Write the set/get methods for the class. These are indexed with two integers, and it should make no difference whether you index with (i,j) or (j,i). The call get(i,j) should return null if and only if the matrix has a null entry at (i,j); for an adjacency matrix we interpret that as "there is no edge between i and j". If either of the two indices is out of the index range the method should throw an IndexOutOfBoundsException.
• In class Graph complete the methods degree and centre.
  • The degree of a node is the number of edges adjacent to it.
  • The centre of a graph is a node with the lowest average shortest distance to the other nodes, provided the graph is connected. Otherwise, we require (in addition) that the centre is connected to at least as many nodes as any other. Both connectedness and shortest distances you can find out through the shortest-path graph of a graph - there is already a method provided that computes that graph, but it requires that the Triangular class works.

Hints and notes: the project also contains a RandomGraph class. You do not have to do anything with it, but you can use it to generate some random graphs to test your code. Similarly, there is a printEdges method provided to aid testing.

If you have never thrown yourself exceptions in Java then it's high time that you learn how to do it. Just look it up in a textbook and try it out!

How can one realise a triangular array? Well, you can simply use a one-dimensional array that holds all the data, and compute from the indices i and j a new index for the one-dimensional array. In a triangular array with index range n, the "first row" will contain n entries, the second n-1, the third n-2, etc. In the corresponding one-dimensional array these rows are simply concatenated into a single sequence. The smaller of the two indices (of (i,j)) we can read as giving us "the row" in which we find the data, and then the difference between the larger and the smaller index gives us the place within that row. For example, if we index a triangular array (with index range n) at (5,2) we would have to skip the first 2 rows (with n and n-1 entries), and then the first 3 (as 5-2=3) entries of the third row, giving us an overall index of (n+n-1+3)=(2n+2) which we can use to index our one-dimensional realisation of this structure. More generally, you would have to come up with a formula that turns two indices (i,j) (both between 0 and n-1) into the triangular array into a single index (between 0 and n*(n+1)/2-1) into the underlying one-dimensional array that realises the triangular structure. If you struggle with that then first implement the class with rectangular (or even 2D) arrays; this should give you a working implementation with which you can implement the required methods of the Graph class.

The Triangular class has a generic type parameter A which is supposed to be the component type of the array. Problem is: you cannot use generic types as component type for an array in Java. What you can do instead is this: use an array of objects, i.e. use type Object[]. This causes no issues withwriting to the array, but when you read from it you need to cast the type, like so: A content = (A)array[index]; The compiler will accept that but will complain about unsafe coercions in your program. If you want those warnings to go away, precede that statement with@SuppressWarnings("unchecked"). (As an aside: the ArrayList class is actually implemented in this way.)