Answer Happy

about java
graph
Code shown below.
1.
Comp108A2Graph.java
class COMP108A2Graph {
// input parameter: an integer distance
// output: compute neighbourhood matrix for distance
static COMP108A2Output neighbourhood(int[][] adjMatrix, int
gSize) {
COMP108A2Output output = new COMP108A2Output(1, gSize);
// do not remove this last statement
return output;
}
// DO NOT change this method, you can use it if you
want
static void printSquareArray(int array[][], int size) {
for (int i=0; i<size; i++) {
for (int j=0; j<size; j++) {
System.out.print(array[j] + " ");
}
System.out.println();
}
}
}
2. COMP108A2GraphApp.java(do not
change).
import java.util.*;
import java.io.*;
class COMP108A2GraphApp {
private static final int MaxVertex = 10;
private static final int MinVertex = 2;
private static Scanner keyboardInput = new Scanner
(System.in);
// adjacency matrix, adjMatrix[j] = 1 means i and j are
adjacent, 0 otherwise
private static int[][] adjMatrix = new
int[MaxVertex][MaxVertex];
private static int numVertex; // total number of vertices
// DO NOT change the main method
public static void main(String[] args) throws Exception
{
boolean userContinue=true;
int distance=1;
// int[][] neighbourMatrix = new
int[MaxVertex][MaxVertex];

input();
COMP108A2Output output = new COMP108A2Output(1,
numVertex);
/*
try {
System.out.print("Enter a distance (" + MinVertex +
"--" + numVertex + ", -1 to exit): ");
distance = keyboardInput.nextInt();
}
catch (Exception e) {
keyboardInput.next();
}
if (distance < MinVertex || distance >
numVertex)
System.out.println("incorrect range");
else {
*/
output = COMP108A2Graph.neighbourhood(adjMatrix,
numVertex);
printSquareArray(output.neighbourMatrix, numVertex);
// }

// degreeSeparation();
}
// DO NOT change this method
static void printSquareArray(int array[][], int size) {
for (int i=0; i<size; i++) {
for (int j=0; j<size; j++) {
System.out.print(array[j] + " ");
}
System.out.println();
}
}
// DO NOT change this method
static void input() {
int i, j;
boolean success = false;
try {
success = true;
// System.out.print("How many vertices (" + MinVertex +
"--" + MaxVertex + ")? ");
numVertex = keyboardInput.nextInt();
if (numVertex > MaxVertex || numVertex <
MinVertex) {
success = false;
}
if (success) {
// System.out.println("Enter adjacency matrix:
");
for (i=0; i<numVertex; i++)
for (j=0; j<numVertex; j++)
adjMatrix[j] =
keyboardInput.nextInt();
for (i=0; i<numVertex && success;
i++) {
if (adjMatrix != 0)
success = false;
for (j=0; j<numVertex; j++) {
if (adjMatrix[j] !=
adjMatrix[j])
success = false;
}
}
}
if (!success) {
System.out.print("Incorrect range ");
System.out.print("or adjacency matrix not
symmetric ");
System.out.println("or vertex connected to
itself");
System.exit(0);
}
}
catch (Exception e) {
keyboardInput.next();
}
}
}
3. COMP108Output.java (Don
not change this). class
COMP108A2Output {
public int hitCount;
public int missCount;
public int[] compare;
public String cabFromHead;
public String cabFromTail;
public String cabFromHeadFreq;
public int[][] neighbourMatrix;

// Constructor
// parameter size is used to define the size of the array to
store number of comparisons
public COMP108A2Output(int cabSize, int graphSize) {
hitCount = 0;
missCount = 0;
cabFromHead = "";
cabFromTail = "";
cabFromHeadFreq = "";
compare = new int[cabSize];
for (int i=0; i<cabSize; i++)
compare = 0;
neighbourMatrix = new int[graphSize][graphSize];
for (int i=0; i<graphSize; i++)
for (int j=0; j<graphSize; j++)
neighbourMatrix[j] = 0;

}
// an auxiliary method to print its attributes in a
readable form
public void printCab(boolean freq) {
System.out.println();
for (int i=0; i<compare.length; i++)
System.out.print(compare[i] + ",");
System.out.println();
System.out.println(hitCount + " h " + missCount + "
m");
System.out.println("From head to tail: " +
cabFromHead);
System.out.println("From tail to head: " +
cabFromTail);
if (freq == true)
System.out.println("Frequency from head to tail: " +
cabFromHeadFreq);
}
2 Part 2: Neighbourhood Distance on Graphs (30%) 2.1 Background Suppose we have an undirected graph to model connections on a social network. There are n users, each represented by a vertex. If two users are friends of each other, then there is an edge between the two corresponding vertices. This forms a simple graph (at most one edge between any two vertices) with no self-loop (a vertex has no edge to itself). This friend-relationship can be represented by an adjacency matrix of size n x n. The entry (1,1) is 1 if vertex i and have an edge between them, and 0 otherwise. For any two vertices that are not immediate neighbour (i.e., no edge between them), we want to know if they are "connected" via the same neighbour. In other words, they are distance-2 apart. We can generalise this concept to distance-d for d > 1. For example, in the following graph, 2 is a distance-2 neighbour of 13 and va but not us while vo is a distance-3 neighbour of us. We can represent this neighbourhood relationship using a neighbourhood matrix. An entry between vertex i and j is d(ij) if the closest distance between them is d(1,1). If there is no path between i and j, then the entry (1,7) is 0. We want to compute the neighbourhood matrix to contain this information for all pairs of vertices. With the above graph, the neighbourhood matrix is shown below 011 2 2 3 1 0 2 1 3 2 1 2 0 1 1 2 2110 21 2 3 1 2 0 1 3 2 2 1 10 2.2 The programs 2.2.1 The program COMP108A2Graph.java The task is to implement the class COMP108A2Graph in a java file named COMP108A2 Graph.java. The class contains a method neighbourhood with the following signature: neighbourhood (int[][] adjMatrix, int gSize) The two parameters means the following: • adjMatrix is a 2-dimensional array containing the adjacent matrix. • gSize is the size / number of vertices of the graph, i.e., adj Matrix is gSize by gSize. 8
The result, i.e., the neighbourhood matrix, of the method should be stored in an object of the class COMP108A2Output. The first line of the method has been written as: COMP108A20utput output = new COMP108A20utput (1, gSize); and the last line as: return output; Details of how to use this class can be found in Section 2.2.2 2.2.2 The program COMP108A20utput.java Note: DO NOT change the content of this file. Any changes this file will NOT be used to grade your submission. A class COMP108A2Output has been defined to contain the following attributes: public int[] [] neighbour Matrix; Note that there are other attributes that are for Part 1 and we have discussed them earlier. A constructor has been implemented that takes two integer parameters and the second pa- rameter is used to define the size of the graph and hence neighbourMatrix[] [] while the first parameter is for Part 1 and takes any positive number. 2.2.3 COMP108A2GraphApp.java To assist you testing of your program, an additional file named COMP108A2GraphApp.java is provided. Once again, you should not change this program. Any changes on this file will NOT be used to grade your submission. This program inputs some data so that they can be passed on to the reorganisation algorithms to process. To use this program, you should compile both COMP108A2Graph.java and COMP108A2GraphApp.java. Then you can run with COMP108A2Graph App. See an illustration below. >javac COMP108A2Graph.java >javac COMP108A2 GraphApp.java >java COMP108A2GraphApp < graphSampleInput01.txt Before you implement anything, you will see the output like the left of the following figure. When you complete your work, you will see the output like the right. 0 000 0 0 0 0 2.3 Your tasks • Task 2 (15%) Implement the neighbourhood() method that computes the neighbour Ma- trix for all pairs of vertices. The method should compute the results and stores them at output neighbour Matrix. 9
2.4 Test cases Below are some sample test cases and the expected output so that you can check and debug your program. The input consists of the following: • The size of graph between 2 and 10 inclusively) • The adjacency matrix Your program will be marked by five other test cases that have not be revealed. Test case #1 graphSample01.txt #2 graphSample02.txt Input Output 6 011 2 2 3 0 1 1 0 0 0 1 0 2 1 3 2 1 0 0 1 0 0 1 2 0 1 1 2 1 0 0 1 1 0 2 1 1 0 2 1 0 1 1 0 0 1 2 3 1 2 0 1 0 0 1 0 0 1 3 2 2 1 1 0 000110 6 011 200 0 1 1 0 0 0 1 0 2 1 0 0 1 0 0 1 0 0 1 2 0 3 0 0 100000 2 1 3 0 0 0 01 0000000001 ооооо1 OOOO 10 оооо 0 0 1 2 3 4 01000 1 0 1 2 3 1 0 1 0 0 2 1 0 1 2 0 1 0 1 0 3 2 1 0 1 001 01 4 3 2 1 0 0 0 0 1 0 #3 graphSample03.txt 3 Additional information 3.1 Worst Case Time Complexity analysis in big-O notation (20%) • Task 3 (20%) For each of the algorithms you have implemented, give a worst case time complexity analysis (in big-O notation). Give also a short justifiation of your answer. This should be added to the comment sections at the beginning of COMP108A2Cab.java and COMP108A2Graph.java. No separate file should be submitted. • The time complexity has to match your implementation. Marks will NOT be awarded if the corresponding algorithm has not been implemented. . For COMP108A2Cab.java, you can use any of the following in the formula: f to represent the initial cabinet size, n the number of requests and d the number of distinct requests. • For COMP108A2Graph.java, you can use n to represent the number of vertices in the graph. 10