In the GraphImplementations project, consider all of the following directed grap
ID: 3876924 • Letter: I
Question
In the GraphImplementations project, consider all of the following directed graph implementations:
AdjListIntVertices
AdjMatrixIntVertices
For each of these classes, add the following methods. You implementation must use the existing graph representations and must use the algorithms described in class.
public void breadthFirstTraversal(int start);
public void depthFirstTraversal(int start);
public class AdjListIntVertices {
private int N;
private HashSet<Integer>[] adjList;
@SuppressWarnings("unchecked")
public AdjListIntVertices(String fname) {
try {
Scanner input = new Scanner(new File(fname));
N = input.nextInt();
adjList = (HashSet<Integer>[]) Array
.newInstance(new HashSet<Integer>().getClass(), N);
for (int r = 0; r < N; r++) {
adjList[r] = new HashSet<Integer>();
for (int c = 0; c < N; c++) {
if (input.nextInt() == 1) {
adjList[r].add(c);
}
}
}
input.close();
} catch (Exception e) {
System.err.println("Problem during file input");
System.exit(0);
}
}
public void breadthFirstTraversal(int start) {
}
public void depthFirstTraversal(int start) {
}
public Set<Integer> canReach(int startVertex) {
HashSet<Integer> reachable = new HashSet<>();
HashSet<Integer> recentAdditions = new HashSet<>();
reachable.add(startVertex);
recentAdditions.add(startVertex);
do {
HashSet<Integer> copyRecentAdditions = new HashSet<Integer>(
recentAdditions);
recentAdditions.clear();
for (int v : copyRecentAdditions) {
for (int i = 0; i < N; i++) {
if (adjList[v].contains(i) && !reachable.contains(i)) {
recentAdditions.add(i);
}
}
}
reachable.addAll(recentAdditions);
} while (recentAdditions.size() != 0);
return reachable;
}
}
public class AdjMatrixIntVertices {
private int N;
private boolean[][] adjMatrix;
public AdjMatrixIntVertices(String fname) {
try {
Scanner input = new Scanner(new File(fname));
N = input.nextInt();
adjMatrix = new boolean[N][];
for (int r = 0; r < N; r++) {
adjMatrix[r] = new boolean[N];
for (int c = 0; c < N; c++) {
adjMatrix[r][c] = input.nextInt() == 1;
}
}
input.close();
} catch (Exception e) {
System.err.println("Problem during file input");
System.exit(0);
}
}
public void breadthFirstTraversal(int start) {
}
public void depthFirstTraversal(int start) {
}
public Set<Integer> canReach(int startVertex) {
HashSet<Integer> reachable = new HashSet<>();
HashSet<Integer> recentAdditions = new HashSet<>();
reachable.add(startVertex);
recentAdditions.add(startVertex);
do {
HashSet<Integer> copyRecentAdditions = new HashSet<Integer>(
recentAdditions);
recentAdditions.clear();
for (int v : copyRecentAdditions) {
for (int i = 0; i < N; i++) {
if (adjMatrix[v][i] && !reachable.contains(i)) {
recentAdditions.add(i);
}
}
}
reachable.addAll(recentAdditions);
} while (recentAdditions.size() != 0);
return reachable;
}
}
Explanation / Answer
Hi.. Please check below java code.
AdjListIntVertices.java
import java.io.File;
import java.lang.reflect.Array;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
public class AdjListIntVertices {
private int N;
private HashSet<Integer>[] adjList;
@SuppressWarnings("unchecked")
public AdjListIntVertices(String fname) {
try {
Scanner input = new Scanner(new File(fname));
N = input.nextInt();
adjList = (HashSet<Integer>[]) Array.newInstance(new HashSet<Integer>().getClass(), N);
for (int r = 0; r < N; r++) {
adjList[r] = new HashSet<Integer>();
for (int c = 0; c < N; c++) {
if (input.nextInt() == 1) {
adjList[r].add(c);
}
}
}
input.close();
} catch (Exception e) {
System.err.println("Problem during file input");
System.exit(0);
}
}
public void breadthFirstTraversal(int start) {
Queue<Integer> queue = new ArrayDeque<>();
HashSet<Integer> seen = new HashSet<>();
queue.add(start);
while(0 != queue.size()){
int vertex = queue.poll();
if(!seen.contains(vertex)){
System.out.print(vertex + " ");
queue.add(vertex); // Add all neighbors of 'vertex' to the queue
seen.add(vertex);
}
}
}
public void depthFirstTraversal(int start) {
Queue<Integer> queue = new ArrayDeque<>();
HashSet<Integer> seen = new HashSet<>();
queue.add(start);
while(0 != queue.size()){
int vertex = queue.peek();
if(!seen.contains(vertex)){
System.out.print(vertex + " ");
queue.add(vertex); // Add all neighbors of 'vertex' to the queue
seen.add(vertex);
}
}
}
public Set<Integer> canReach(int startVertex) {
HashSet<Integer> reachable = new HashSet<>();
HashSet<Integer> recentAdditions = new HashSet<>();
reachable.add(startVertex);
recentAdditions.add(startVertex);
do {
HashSet<Integer> copyRecentAdditions = new HashSet<Integer>(
recentAdditions);
recentAdditions.clear();
for (int v : copyRecentAdditions) {
for (int i = 0; i < N; i++) {
if (adjList[v].contains(i) && !reachable.contains(i)) {
recentAdditions.add(i);
}
}
}
reachable.addAll(recentAdditions);
} while (recentAdditions.size() != 0);
return reachable;
}
}
AdjMatrixIntVertices.java
import java.io.File;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
import java.util.Stack;
public class AdjMatrixIntVertices {
private int N;
private boolean[][] adjMatrix;
private Queue<Integer> queue= new LinkedList<Integer>();
private Stack<Integer> stack = new Stack<Integer>();
public AdjMatrixIntVertices(String fname) {
try {
Scanner input = new Scanner(new File(fname));
N = input.nextInt();
adjMatrix = new boolean[N][];
for (int r = 0; r < N; r++) {
adjMatrix[r] = new boolean[N];
for (int c = 0; c < N; c++) {
adjMatrix[r][c] = input.nextInt() == 1;
}
}
input.close();
} catch (Exception e) {
System.err.println("Problem during file input");
System.exit(0);
}
}
public void breadthFirstTraversal(int start) {
int number_of_nodes = adjMatrix[start].length - 1;
int[] visited = new int[number_of_nodes + 1];
int i, element;
visited[start] = 1;
queue.add(start);
while (!queue.isEmpty())
{
element = queue.remove();
i = element;
System.out.print(i + " ");
while (i <= number_of_nodes)
{
if (adjMatrix[element][i] == true && visited[i] == 0)
{
queue.add(i);
visited[i] = 1;
}
i++;
}
}
}
public void depthFirstTraversal(int start) {
int number_of_nodes = adjMatrix[start].length - 1;
int visited[] = new int[number_of_nodes + 1];
int element = start;
int i = start;
System.out.print(element + " ");
visited[start] = 1;
stack.push(start);
while (!stack.isEmpty())
{
element = stack.peek();
i = element;
while (i <= number_of_nodes)
{
if (adjMatrix[element][i] == true && visited[i] == 0)
{
stack.push(i);
visited[i] = 1;
element = i;
i = 1;
System.out.print(element + " ");
continue;
}
i++;
}
stack.pop();
}
}
public Set<Integer> canReach(int startVertex) {
HashSet<Integer> reachable = new HashSet<>();
HashSet<Integer> recentAdditions = new HashSet<>();
reachable.add(startVertex);
recentAdditions.add(startVertex);
do {
HashSet<Integer> copyRecentAdditions = new HashSet<Integer>(
recentAdditions);
recentAdditions.clear();
for (int v : copyRecentAdditions) {
for (int i = 0; i < N; i++) {
if (adjMatrix[v][i] && !reachable.contains(i)) {
recentAdditions.add(i);
}
}
}
reachable.addAll(recentAdditions);
} while (recentAdditions.size() != 0);
return reachable;
}
}
Please check the above code and let me know any issues. Thank you. All the best.