Answer:
Check the explanation
Explanation:
import java.io.File;
import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.Scanner;
import static org.junit.Assert.assertEquals;
/**
* CS146 Assignment 3 Node class This class is used for undirected graphs
* represented as adjacency lists The areFriends() method checks if two people
* are friends by checking if an edge exists between the two
*
*/
public class NetworkAdjList {
// Initialize array with max number of vertices taken from SNAP
static int max_num_vertices = 88234;
static LinkedList<Integer>[] adjacencyList = new LinkedList[max_num_vertices];
public static void createAdjacencyList() {
// Initialize array elements
for (int j = 0; j < max_num_vertices; j++) {
adjacencyList[j] = new LinkedList<Integer>();
}
// Get file path of the 3980.edges file
String filePath = "C:\\Users\\shahd\\Documents\\CS146\\Assignment 3\\Question 3\\Question3\\src\\a3\\3980.edges";
File f = new File(filePath);
// Use Scanner to read edges from the file and put it into adjacency list
int a;
int b;
try {
Scanner fileIn = new Scanner(f);
while (fileIn.hasNext()) {
a = fileIn.nextInt();
b = fileIn.nextInt();
adjacencyList[a].add(b);
adjacencyList[b].add(a); // We need to add the edges both ways
}
} catch (FileNotFoundException e) {
e.printStackTrace();
}
}
public static boolean areFriends(int A, int B) {
// If the adjacency list contains (A, B) edge, then return true, else false
if (adjacencyList[A].contains(B)) {
return true;
} else {
return false;
}
}
private static void bfsHelper(boolean visited[], int currentNode, int dis, int sourceNode) {
dis++;
if(!visited[currentNode]) {
visited[currentNode] = true;
for(int neighbor: adjacencyList[currentNode]) {
System.out.println(neighbor + " is at a distance of " + dis + " from " + sourceNode);
bfsHelper(visited, neighbor, dis++, sourceNode);
}
}
}
public static void BFStraversal(int start) {
boolean visited[] = new boolean[max_num_vertices];
bfsHelper(visited, start, 0, start);
}
public static void main(String[] args) {
/**
* These test cases assume the file 3980.edges was used
*/
createAdjacencyList();
System.out.println("Testing...");
assertEquals(areFriends(4038, 4014), true);
System.out.println("1 of 7");
System.out.println("Testing...");
assertEquals(areFriends(3982, 4037), true);
System.out.println("2 of 7");
System.out.println("Testing...");
assertEquals(areFriends(4030, 4017), true);
System.out.println("3 of 7");
System.out.println("Testing...");
assertEquals(areFriends(4030, 1), false);
System.out.println("4 of 7");
System.out.println("Testing...");
assertEquals(areFriends(1, 4030), false);
System.out.println("5 of 7");
System.out.println("Testing...");
assertEquals(areFriends(4003, 3980), true);
System.out.println("6 of 7");
System.out.println("Testing...");
assertEquals(areFriends(3985, 4038), false);
System.out.println("7 of 7");
System.out.println("Success!");
}
}
**************************************************