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:
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.)