JAVA Homework Graph Objective: Create a class which constructs a graph and perfo

ID: 3683560 • Letter: J

Question

JAVA Homework

Graph

Objective:

Create a class which constructs a graph and performs a few graph operations. Test out your code with the Driver.

public class GraphTester {
public static void main(String[] args)
{
  Graph g = new Graph(25);
  System.out.println("Adding verticies");
  g.addVertex("v1");
  g.addVertex("v2");
  g.addVertex("v3");
  g.addVertex("v4");
  g.addVertex("v5");
  g.addVertex("v6");
  g.addVertex("v7");
  g.addVertex("v8");
  System.out.println("Adding edges");
  g.addEdge("v1", "v2", 10);
  g.addEdge("v1", "v4", 20);
  g.addEdge("v1", "v6", 50);

  g.addEdge("v2", "v4", 21);
  g.addEdge("v2", "v5", 25);

  g.addEdge("v3", "v8", 50);

  g.addEdge("v4", "v7", 7);
  g.addEdge("v4", "v8", 40);

  g.addEdge("v5", "v3", 23);

  g.addEdge("v6", "v4", 31);

  g.addEdge("v7", "v6", 10);

  System.out.println("Printing DFS");
  g.printDFS();
  System.out.println("Printing BFS");
  g.printBFS();
  System.out.println("Printing Lazy DFS");
  g.printLazyDFS();
}
}

Download the class called Graph

import java.util.*;
public class Graph {
private class Vertex
{
  String name;
  ArrayList<Edge> neighbors;
  public Vertex(String aName)
  {
   this.name = aName;
   this.neighbors = new ArrayList<Edge>();
  }
}
private class Edge
{
  Vertex nextVert;
  double weight;
  public Edge(Vertex aV1, double aWeight)
  {
   nextVert = aV1;
   weight = aWeight;
  }
}

private Vertex origin;
private ArrayList<Vertex> verticies;
private ArrayList<Vertex> markedVerts;
private ArrayList<Vertex> visitedVerts;
private double maxLength;
public Graph(double aLength)
{
  origin = null;
  verticies = new ArrayList<Vertex>();
  markedVerts = new ArrayList<Vertex>();
  visitedVerts = new ArrayList<Vertex>();
  maxLength = aLength;
}

}

. It already has some instance variables and constructors. It is up to you to finish it by adding the following methods.

addVertex: this method which returns nothing and takes in a string parameter corresponding to the name of the new vertex. It will only add a new vertex if that name is not already in the list of vertices.

vertexIsContained: this method returns a true or false if there exists a vertex in the graph that matches the name passed in via the parameter.

addEdge: this method returns nothing and takes in two string parameters and a weight. The two string parameters correspond to the names of vertices and the weight is the weight of the newly created edge. The newly created edge is then placed in the neighbors edge list inside the first vertex. If either the first or second vertex doesnt exist the method should not continue.

getVertex: this method returns an instance of a vertex if the name (passed in via a parameter) is found in the vertex list.

printDFS: This prints out the vertices names in depth first order. You can find the algorithm the presentation provided.

printBFS: This prints out the vertices names in breadth first order. Like above you can find the algorithm in the presentation.

printLazyDFS: In the class there is an instance variable called maxDist which corresponds to the maximum distance that is allowed to travel. Write another DFS but make sure it doesnt traverse edges that are greater than the max distance.

Heres the graph the driver is based on

Addition help with this assignment can be found here.

Example Print Out:

Adding verticies

Adding edges

Printing DFS

Printing BFS

Printing Lazy DFS

Finally:

Explanation / Answer

void addVertex(String v)
{
   if(!vertexIsContained(v))
   {
       verticies.add(v);
   }
   else
       System.out.println("vertex is already present in the graph");
}

boolean vertexIsContained(String v)
{
if(verticies.contains(v))
return true;
return false;
}

void addEdge(String x, String y, int w)
{
   if((!vertexIsContained(x)) || (!vertexIsContained(y))
       System.out.println("vertex is not present in the graph");
   else
   {
       edges.add(new Edge(toVertex, weight));
       neighbours.add(new Edge(toVertex, weight));
   }
}

Vertex getVerrtex(String v)
{
   if((!vertexIsContained(v))
       System.out.println("vertex is not present in the graph");
   else
       {
           Vertex r = new Vertex(v);
       }
   return r;
}

public static void printDFS(){
boolean[] visited = new boolean[verticies.size()];
Stack<Integer> st = new Stack<Integer>();
st.push(s);
while(!st.isEmpty()){
int v = st.pop();
if(!visited[v]){
visited[v] = true;
System.out.print(v + " ");
Stack<Integer> auxStack = new Stack<Integer>();
for(int w : verticies.get(v)){
if(!visited[w]){
auxStack.push(w);
}
}
while(!auxStack.isEmpty()){
st.push(auxStack.pop());
}
}
}
System.out.println();
}

public static void printDFS(){

boolean visited[] = new boolean[V];

// Create a queue for BFS
LinkedList<Integer> queue = new LinkedList<Integer>();

// Mark the current node as visited and enqueue it
visited[s]=true;
queue.add(s);

while (queue.size() != 0)
{
// Dequeue a vertex from queue and print it
s = queue.poll();
System.out.print(s+" ");

// Get all adjacent vertices of the dequeued vertex s
// If a adjacent has not been visited, then mark it
// visited and enqueue it
Iterator<Integer> i = adj[s].listIterator();
while (i.hasNext())
{
int n = i.next();
if (!visited[n])
{
visited[n] = true;
queue.add(n);
}
}
}
}

Navigate

JAVA Homework 1) Create a die class. This is similar to the coin class , but ins

JAVA Homework Help THANK YOU Question 1: Writing Exception Code A Write a method

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

JAVA Homework Graph Objective: Create a class which constructs a graph and perfo

Question

Explanation / Answer

Related Questions

Navigate