I have a Graph.java which I need to complete four methods in the java file: completeGraph(),...
I have a Graph.java which I need to complete four methods in the java file: completeGraph(), valence(int vid), DFS(int start), and findPathBFS(int start, int end).
I also have a JUnit test file GraphTest.java for you to check your code.
Here is Graph.java:
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
/* Generic vertex class */
class Vertex<T> {
public T data;
public boolean visited;
public Vertex() {
data = null; visited = false;
}
public Vertex(T _data) {
data = _data; visited = false;
}
public String toString() {
return data.toString();
}
/* Declare any additional vertex attribute you may need */
}
public class Graph<T> {
// array of vertices
protected ArrayList<Vertex<T>> verts;
/* 2D array representing adjacency matrix of an unweighted graph.
* If adjMat[i][j] is true, there is an edge from vertex i to j;
* otherwise the element adjMat[i][j] is false.
*/
protected boolean[][] adjMat;
public Graph(ArrayList<Vertex<T>> _verts, boolean[][] _mat) {
/* check the validity of input parameters */
int nverts = _verts.size();
// adjacency matrix must be square matrix of NxN
if(_mat.length != nverts) return;
for(int i=0;i<nverts;i++) {
if(_mat[i].length != nverts) return;
}
verts = _verts;
adjMat = _mat;
}
public int numVerts() { return verts.size(); }
// Return the next unvisited neighbor of a given vertex
protected int getNextUnvisitedNeighbor (int vid) {
for (int j=0; j<numVerts(); j++) {
if(adjMat[vid][j] && verts.get(j).visited == false) return j;
}
return -1; // return index -1 if none found
}
// Print out the graph, including vertex list and adjacency matrix
public void print() {
int nverts = numVerts();
System.out.println("Vertex List:");
for(int i=0;i<nverts;i++) {
System.out.println(i+": "+verts.get(i)+" (valence: "+valence(i)+")");
}
System.out.println("Adjacency Matrix:");
for(int i=0;i<nverts;i++) {
for(int j=0;j<nverts;j++) {
System.out.print(adjMat[i][j]?"1 ":"0 ");
}
System.out.println("");
}
}
/* TODO: Make this a complete graph. All you need to do is to
* modify the adjMat according to the definition of a complete
* graph, that is, there is an edge between every two vertices,
* but there is no self-loop (no vertex is connected to itself).
*/
public void completeGraph() {
// TODO
}
/* TODO: Return the number of neighbors (i.e. valence) of a given vertex */
public int valence(int vid) {
// TODO
return 0;
}
/* TODO: Perform DFS from start vertex, and print out all vertices visited.
* When printing vertices, use System.out.print(verts.get(index).data+" ");
* to create a space between every two vertices.
*/
public void DFS(int start) {
for(int i=0;i<numVerts();i++) verts.get(i).visited=false; // clears flags
Stack<Integer> stack = new Stack<Integer>(); // create stack
// TODO
}
/* TODO: find the path from start vertex to end vertex using BFS.
* If the path exists, return the path in an Arraylist, where the
* first element must be start, and the last element must be end,
* and the intermediate vertices must be the indices of vertices
* that are on the path from start to end.
* If the path doesn't exist, return null.
*/
public ArrayList<Integer> findPathBFS(int start, int end) {
for(int i=0;i<numVerts();i++) verts.get(i).visited=false; // clear flags
Queue<Integer> queue = new LinkedList<Integer>(); // create queue
// TODO
return null;
}
}
Here is GraphTest.java:
import java.util.ArrayList;
public class GraphTest {
private static Graph<String> graphS;
private final static int nverts = 8; // number of vertices in the graph
private static void testCompleteGraph() {
ArrayList<Vertex<Character>> verts = new ArrayList<Vertex<Character>>();
// create vertices
for(int i=0;i<nverts;i++) {
verts.add(new Vertex<Character>((char)('A'+i)));
}
boolean[][] mat = new boolean[nverts][nverts];
for(int i=0;i<nverts;i++) {
for(int j=0;j<nverts;j++) {
mat[i][j] = false;
}
}
Graph<Character> graphC = new Graph<Character>(verts, mat);
graphC.completeGraph();
graphC.print();
}
private static void makeCycleGraph(boolean reverse, boolean double_edges) {
ArrayList<Vertex<String>> verts = new ArrayList<Vertex<String>>();
// create vertices
for(int i=0;i<nverts;i++) {
verts.add(new Vertex<String>("V"+(char)('a'+i)));
}
boolean[][] mat = new boolean[nverts][nverts];
for(int i=0;i<nverts;i++) {
for(int j=0;j<nverts;j++) {
mat[i][j] = false;
}
if(!reverse) {
mat[i][(i+2)%nverts] = true;
if(double_edges) mat[i][(i+3)%nverts] = true;
}
else {
mat[i][(i-2+nverts)%nverts] = true;
if(double_edges) mat[i][(i-3+nverts)%nverts] = true;
}
}
graphS = new Graph<String>(verts, mat);
}
public static void testDFS() {
makeCycleGraph(false, true);
System.out.print("DFS in a cycle graph: ");
graphS.DFS(0);
System.out.println("\n(correct answer is: Va Vc Ve Vg Vb Vd Vf Vh)");
System.out.print("DFS in a reverse cycle graph: ");
makeCycleGraph(true, true);
graphS.DFS(1);
System.out.println("\n(correct answer is: Vb Vg Vd Va Vf Vc Vh Ve)");
}
public static void testBFS() {
System.out.print("BFS path finding in a cycle graph: ");
makeCycleGraph(false, true);
ArrayList<Integer> path = graphS.findPathBFS(0, 1);
if(path != null) {
for(Integer x:path) {
System.out.print(x+" ");
}
} else System.out.print("doesn't exist");
System.out.println("\n(correct answer is: 0 3 6 1)");
System.out.print("BFS path finding in a reverse cycle graph: ");
makeCycleGraph(true, false);
path = graphS.findPathBFS(0, 1);
if(path != null) {
for(Integer x:path) {
System.out.print(x+" ");
}
} else System.out.print("doesn't exist");
System.out.println("\n(correct answer is: doesn't exist)");
}
public static void main(String[] args) {
// TODO Auto-generated method stub
testCompleteGraph();
testDFS();
testBFS();
}
}
Homework Answers
GraphTest.java
import java.util.ArrayList;
public class GraphTest {
private static Graph<String> graphS;
private final static int nverts = 8; //
number of vertices in the graph
private static void testCompleteGraph() {
ArrayList<Vertex<Character>> verts = new
ArrayList<Vertex<Character>>();
// create vertices
for(int i=0;i<nverts;i++)
{
verts.add(new
Vertex<Character>((char)('A'+i)));
}
boolean[][] mat = new
boolean[nverts][nverts];
for(int i=0;i<nverts;i++)
{
for(int
j=0;j<nverts;j++) {
mat[i][j] = false;
}
}
Graph<Character> graphC = new
Graph<Character>(verts, mat);
graphC.completeGraph();
graphC.print();
}
private static void makeCycleGraph(boolean reverse,
boolean double_edges) {
ArrayList<Vertex<String>> verts = new
ArrayList<Vertex<String>>();
// create vertices
for(int i=0;i<nverts;i++)
{
verts.add(new
Vertex<String>("V"+(char)('a'+i)));
}
boolean[][] mat = new
boolean[nverts][nverts];
for(int i=0;i<nverts;i++)
{
for(int
j=0;j<nverts;j++) {
mat[i][j] = false;
}
if(!reverse)
{
mat[i][(i+2)%nverts] = true;
if(double_edges) mat[i][(i+3)%nverts] =
true;
}
else {
mat[i][(i-2+nverts)%nverts] = true;
if(double_edges) mat[i][(i-3+nverts)%nverts] =
true;
}
}
graphS = new
Graph<String>(verts, mat);
}
public static void testDFS() {
makeCycleGraph(false, true);
System.out.print("DFS in a cycle
graph: ");
graphS.DFS(0);
System.out.println("\n(correct
answer is: Va Vc Ve Vg Vb Vd Vf Vh)");
System.out.print("DFS in a reverse
cycle graph: ");
makeCycleGraph(true, true);
graphS.DFS(1);
System.out.println("\n(correct
answer
is: Vb
Vg Vd Va Vf Vc Vh Ve)");
}
public static void testBFS() {
System.out.print("BFS path finding
in a cycle graph: ");
makeCycleGraph(false, true);
ArrayList<Integer> path =
graphS.findPathBFS(0, 1);
if(path != null) {
for(Integer
x:path) {
System.out.print(x+" ");
}
} else System.out.print("doesn't
exist");
System.out.println("\n(correct
answer is: 0 3 6 1)");
System.out.print("BFS path finding
in a reverse cycle graph: ");
makeCycleGraph(true, false);
path = graphS.findPathBFS(0,
1);
if(path != null) {
for(Integer
x:path) {
System.out.print(x+" ");
}
} else System.out.print("doesn't
exist");
System.out.println("\n(correct
answer is: doesn't exist)");
}
public static void main(String[] args) {
// TODO Auto-generated method
stub
testCompleteGraph();
testDFS();
testBFS();
}
}
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
/* Generic vertex class */
class Vertex<T> {
public T data;
public boolean visited;
public int a;
public Vertex() {
data = null; visited = false; a =
-1;
}
public Vertex(T _data) {
data = _data; visited = false; a =
-1;
}
public String toString() {
return data.toString();
}
/* Declare any additional vertex attribute you may
need */
}
public class Graph<T> {
// array of vertices
protected ArrayList<Vertex<T>>
verts;
protected boolean[][] adjMat;
public Graph(ArrayList<Vertex<T>> _verts,
boolean[][] _mat) {
/* check the validity of input
parameters */
int nverts = _verts.size();
// adjacency matrix must be square
matrix of NxN
if(_mat.length != nverts)
return;
for(int i=0;i<nverts;i++)
{
if(_mat[i].length != nverts) return;
}
verts = _verts;
adjMat = _mat;
}
public int numVerts() { return verts.size(); }
// Return the next unvisited neighbor of a given
vertex
protected int getNextUnvisitedNeighbor (int vid)
{
for (int j=0; j<numVerts(); j++)
{
if(adjMat[vid][j] && verts.get(j).visited == false) return
j;
}
return -1;
// return index -1 if none found
}
// Print out the graph, including vertex list and
adjacency matrix
public void print() {
int nverts = numVerts();
System.out.println("Vertex
List:");
for(int i=0;i<nverts;i++)
{
System.out.println(i+": "+verts.get(i)+" (valence:
"+valence(i)+")");
}
System.out.println("Adjacency
Matrix:");
for(int i=0;i<nverts;i++)
{
for(int
j=0;j<nverts;j++) {
System.out.print(adjMat[i][j]?"1 ":"0 ");
}
System.out.println("");
}
}
public void completeGraph() {
for(int i=0;i<numVerts();i++)
{
for(int
j=0;j<numVerts();j++) {
if (i!=j) { adjMat[i][j] = true; }
}
}
}
/* TODO: Return the number of neighbors (i.e. valence)
of a given vertex */
public int valence(int vid) {
int count = 0;
for (int i = 0; i < numVerts();
i++) {
if
(adjMat[vid][i] == true) count++;
}
return count;
}
public void DFS(int start) {
for(int i=0;i<numVerts();i++)
verts.get(i).visited=false; // clears flags
Stack<Integer> stack = new
Stack<Integer>(); // create stack
stack.push(start);
while(!stack.isEmpty()) {
int index =
stack.pop();
if
(verts.get(index).visited==true) continue;
System.out.print(verts.get(index).data + " ");
verts.get(index).visited=true;
for (int i =
numVerts()-1; i >= 0; i--) {
if (adjMat[index][i] == true &&
verts.get(i).visited==false) {
stack.push(i);
}
}
}
}
public ArrayList<Integer> findPathBFS(int start,
int end) {
for(int i=0;i<numVerts();i++)
verts.get(i).visited=false; // clear flags
Queue<Integer> queue = new
LinkedList<Integer>(); // create queue
queue.add(start);
verts.get(start).visited=true;
boolean found = false;
while(!queue.isEmpty()) {
int index =
queue.remove();
if (index ==
end) {
found = true;
break;
}
for (int i =
numVerts()-1; i >= 0; i--) {
if (adjMat[index][i] == true &&
verts.get(i).visited==false) {
queue.add(i);
verts.get(i).visited=true;
verts.get(i).a = index;
}
}
}
if (found == false) return
null;
ArrayList<Integer> pathBack =
new ArrayList<Integer>();
pathBack.add(end);
while(verts.get(end).a != -1)
{
pathBack.add(verts.get(end).a);
end =
verts.get(end).a;
}
ArrayList<Integer> path = new
ArrayList<Integer>();
for(int i = pathBack.size()-1; i
>= 0; i--) {
path.add(pathBack.get(i));
}
return path;
}
}
Add Answer to:
I have a Graph.java which I need to complete
four methods in the java file:
completeGraph(),...
Please follow all the instructions and do all the parts (a-d)! Create a Java program which implem...
Please follow all the instructions and do all the parts
(a-d)!
Create a Java program which implements Dijkstra’s shortest path
algorithm according to the psueudocode below. Base the design on
the weighted graph implementation used in Problem3.java (provided
at the bottom). Your program should include the following
features:
a. A new method receives a starting vertex index and a target
vertex index (e.g. 0 and 4). It computes the shortest distances to
all vertexes using Dijkstra’s algorithm. The pseudocode is...
Why am I getting compile errors. rowPuzzle.java:9: error: class, interface, or enum expected public static boolean...
Why am I getting compile errors. rowPuzzle.java:9: error: class, interface, or enum expected public static boolean rowPuzzle(ArrayList<Integer> squares, int index, ArrayList<Boolean> visited) ^ rowPuzzle.java:16: error: class, interface, or enum expected } //Java Program import java.util.*; // rowPuzzle helper function implementation // File: rowPuzzle.cpp // Header files section // function prototypes public static boolean rowPuzzle(ArrayList<Integer> squares, int index, ArrayList<Boolean> visited) { // base case // return true if the puzzle is solvable if (index == squares.size() - 1) { return...
Please try your best to complete this 11 methods under. I have provided the UndirectedGraph class...
Please try your best to complete this 11 methods under. I have provided the UndirectedGraph class with the single instance data variable. Do not add any additional instance data variables. Do not modify any other classes provided. In addition to writing the 8 required methods of the interface and the constructor, you will also write methods for the two traversals and an isConnected method. import java.util.Queue; public class UndirectedGraph<T> implements BasicGraphInterface <T> { private DirectedGraph digraph; ...
I am currently using eclipse to write in java. A snapshot of the output would be...
I am currently using eclipse to write in java.
A snapshot of the output would be greatly appreciated to verify
that the program is indeed working. Thanks in advance for both your
time and effort.
Here is the previous exercise code:
/////////////////////////////////////////////////////Main
/*******************************************
* Week 5 lab - exercise 1 and exercise 2: *
* ArrayList class with search algorithms *
********************************************/
import java.util.*;
/**
* Class to test sequential search, sorted search, and binary search
algorithms
* implemented in...
Hello, I've been working on this for a while and I can't figure the rest out....
Hello, I've been working on this for a while and I can't figure the rest out. Need asap if anyone can help. maxBSt,minBST,isBST, and inOrder package lab7; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; public class TreeExercise { /* * Construct BST from preorder traversal */ public static Node<Integer> consBSTfromPreOrder(int[] arr, int start, int end) { if(start > end) return null; Node<Integer> root = new Node<Integer>(arr[start],...
import java.io.FileNotFoundException; import java.util.ArrayList; import java.util.Collections; import java.util.HashSet; public class FindWordInMaze { private char grid[][]; private...
import java.io.FileNotFoundException; import java.util.ArrayList; import java.util.Collections; import java.util.HashSet; public class FindWordInMaze { private char grid[][]; private ArrayList<String> words; private HashSet<String> foundWords = new HashSet<String>(); public FindWordInMaze(char[][] grid) { this.grid = grid; this.words = new ArrayList<>(); // add dictionary words words.add("START"); words.add("NOTE"); words.add("SAND"); words.add("STONED"); Collections.sort(words); } public void findWords() { for(int i=0; i<grid.length; i++) { for(int j=0; j<grid[i].length; j++) { findWordsFromLocation(i, j); } } for(String w: foundWords) { System.out.println(w); } } private boolean isValidIndex(int i, int j, boolean visited[][]) { return...
This is my code for my game called Reversi, I need to you to make the...
This is my code for my game called Reversi, I need to you to make the Tester program that will run and complete the game. Below is my code, please add comments and Javadoc. Thank you. public class Cell { // Displays 'B' for the black disk player. public static final char BLACK = 'B'; // Displays 'W' for the white disk player. public static final char WHITE = 'W'; // Displays '*' for the possible moves available. public static...
Preliminaries Download the template class and the driver file. Objective Learn how to traverse a binary...
Preliminaries Download the template class and the driver file. Objective Learn how to traverse a binary search tree in order. Description For the template class BinarySearchTree, fill in the following methods: insert - Inserts values greater than the parent to the right, and values lesser than the parent to the left.parameters elem - The new element to be inserted into the tree. printInOrder - Prints the values stored in the tree in ascending order. Hint: Use a recursive method to...
Hi I need help with a java program that I need to create a Airline Reservation...
Hi I need help with a java program that I need to create a Airline Reservation System I already finish it but it doesnt work can someone please help me I would be delighted it doesnt show the available seats when running the program and I need it to run until someone says no for booking a seat and if they want to cancel a seat it should ask the user to cancel a seat or continue booking also it...
I have a below codes with all details and need to answer this below question ONLY!...
I have a below codes with all details and need to answer this below question ONLY! How to explain below codes with the two properties of a Greedy algorithm - Optimal Substructure and the Greedy Property line by line? ====================== public class TeamFormation { private static ArrayList buildTeam(ArrayList team, int skill) { ArrayList newTeam = new ArrayList(); newTeam.add(skill); for (int player : team) { if (skill == (player + 1)) { newTeam.add(player); } } return newTeam; } private static boolean...
Please follow all the instructions and do all the parts
(a-d)!
Create a Java program which implements Dijkstra’s shortest path
algorithm according to the psueudocode below. Base the design on
the weighted graph implementation used in Problem3.java (provided
at the bottom). Your program should include the following
features:
a. A new method receives a starting vertex index and a target
vertex index (e.g. 0 and 4). It computes the shortest distances to
all vertexes using Dijkstra’s algorithm. The pseudocode is...
I am currently using eclipse to write in java.
A snapshot of the output would be greatly appreciated to verify
that the program is indeed working. Thanks in advance for both your
time and effort.
Here is the previous exercise code:
/////////////////////////////////////////////////////Main
/*******************************************
* Week 5 lab - exercise 1 and exercise 2: *
* ArrayList class with search algorithms *
********************************************/
import java.util.*;
/**
* Class to test sequential search, sorted search, and binary search
algorithms
* implemented in...
Most questions answered within 3 hours.
-
The probability that a randomly selected teenager studied at
least once during a week was only...
asked 1 minute ago -
At 20.0°C, the vapor pressure of ethanol is 45.0 torr, and the
vapor pressure of methanol...
asked 3 minutes ago -
13.
Given the following definitions:
U = {1, 2, 3, 4, 5, 6, 7}
A =...
asked 11 minutes ago -
1. Let us again continue with analyses of data from the study of
M Daviglus et...
asked 11 minutes ago -
Consider the following data for a dependent variable y and two
independent variables, x1 and x2....
asked 10 minutes ago -
Research paper on a Sex Crime and Policy Topic
Including all 3 origins “sex crime and...
asked 13 minutes ago -
6. What volume will 40.0mL of nitrogen, measured at 15.0°C and
780.0torr, occupy at STP?
7....
asked 12 minutes ago -
Scientists have meaured that at a distance of 1 AU from star X
energy of radiation...
asked 24 minutes ago -
Q4 #4
How far apart are an object and an image formed by a
89-cm-focal-length converging...
asked 29 minutes ago -
What function do boron esters serve in polymers?
asked 30 minutes ago -
In a survey of 1147 small-business owners, the following
question was posed: Would you recommend working...
asked 57 minutes ago -
The value of the equilibrium constant Kc for the reaction
N2(g)+3H2(g)⇌2NH3(g) changes in the following manner...
asked 1 hour ago