Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

PLEASE I NEED HELP COMPILING THIS CODE. THIS IS FOR A JAVA PROGRAM THAT BUILD A DIRECTED GRAPH. PLEASE PROVIDE SCREENSHOT FOR MORE EXPLANATION. THANKS

PLEASE I NEED HELP COMPILING THIS CODE. THIS IS FOR A JAVA PROGRAM THAT BUILD A DIRECTED GRAPH. PLEASE PROVIDE SCREENSHOT FOR MORE EXPLANATION. THANKS

Here starts the solution :-

GRAPH CLASS

public class Graph {

private HashMap, HashSet>> adjacencyMap;

private int numVertices;

private int numEdges;

private final String type = "directed";

private final boolean weighted = false;

public Graph() {

this.adjacencyMap = new HashMap<>();

}

/**

* Adds a vertex to the graph.

* @param vertex vertex to add.

* @return true if vertex was added successfully, false if otherwise.

* @

*/

public boolean addVertex(GraphNode vertex) {

if(!this.adjacencyMap.containsKey(vertex)) {

this.adjacencyMap.put(vertex, new HashSet<>());

this.numVertices++;

return true;

}

return false;

}

/**

* Removes a specified vertex from the graph.

* @param vertex vertex to remove.

* @return true if vertex was removed successfully, false if otherwise.

* @

*/

public boolean removeVertex(GraphNode vertex) {

if(this.adjacencyMap.containsKey(vertex)) {

this.adjacencyMap.remove(vertex);

for(Map.Entry, HashSet>> entry : this.adjacencyMap.entrySet()) {

if(entry.getValue().contains(vertex)) {

this.adjacencyMap.get(entry.getKey()).remove(vertex);

}

}

this.numVertices--;

return true;

}

return false;

}

/**

* Adds an edge between two vertices to the graph.

* @param x source vertex of edge to add.

* @param y destination vertex of edge to add.

* @return true if the edge was added successfully, false if otherwise.

* @

*/

public boolean addEdge(GraphNode x, GraphNode y) {

if(this.adjacencyMap.containsKey(x)) {

if(!this.adjacencyMap.get(x).contains(y)) {

this.adjacencyMap.get(x).add(y);

this.numEdges++;

return true;

}

}

return false;

}

/**

* Removes a specified edge between two vertices from the graph, if it already exists.

* @param x source vertex of edge to remove.

* @param y destination vertex of edge to remove.

* @return true if the edge was removed successfully, false if otherwise.

* @

*/

public boolean removeEdge(GraphNode x, GraphNode y) {

if(this.adjacencyMap.containsKey(x)) {

if(this.adjacencyMap.get(x).contains(y)) {

this.adjacencyMap.get(x).remove(y);

this.numEdges--;

return true;

}

}

return false;

}

/**

* Determines if two vertices are adjacent (or, if an edge exists between them).

* @param x source vertex.

* @param y destination vertex.

* @return true if both vertices are adjacent, false if otherwise.

* @

*/

public boolean isAdjacent(GraphNode x, GraphNode y) {

HashSet> adjacencySet = this.adjacencyMap.get(x);

if(adjacencySet != null) {

if(adjacencySet.contains(y)) {

return true;

}

}

return false;

}

/**

* Determines if graph contains a given vertex or not.

* @param vertex vertex to search.

* @return true if the graph contains the vertex, false if otherwise.

* @

*/

public boolean containsVertex(GraphNode vertex) {

if(this.adjacencyMap.containsKey(vertex)) {

return true;

}

return false;

}

/**

* Returns a HashSet containing all neighbors of a given vertex (or, all vertices with which the vertex shares an edge).

* @param vertex vertex to search.

* @return a HashSet containing all neighbors of the vertex.

* @

*/

public HashSet> getNeighbors(GraphNode vertex) {

return this.adjacencyMap.get(vertex);

}

/**

* Determines whether or not a path exists between two nodes, using Depth-First Search.

* Uses a wrapper method to initialize objects required for search traversal.

* @param source source node to be used in search.

* @param destination destination node to be used in search.

* @return true if a path exists between source and destination nodes, false if otherwise.

* @

*/

public boolean depthFirstSearch(GraphNode source, GraphNode destination) {

if(!this.adjacencyMap.containsKey(source) || !this.adjacencyMap.containsKey(destination)) {

return false;

}

Stack> stack = new Stack<>();

stack.push(source);

return depthFirstSearch(stack, destination);

}

private boolean depthFirstSearch(Stack> stack, GraphNode destination) {

HashMap, VisitStatus> visited = new HashMap<>();

while(!stack.isEmpty()) {

GraphNode current = stack.pop();

visited.put(current, VisitStatus.VISITING);

if(current.equals(destination)) {

return true;

}

for(GraphNode neighbor : this.adjacencyMap.get(current)) {

if(visited.containsKey(neighbor)) {

if(visited.get(neighbor).equals(VisitStatus.UNVISITED)) {

stack.push(neighbor);

}

} else {

stack.push(neighbor);

}

}

visited.put(current, VisitStatus.VISITED);

}

return false;

}

/**

* Determines whether or not a path exists between two nodes, using Breadth-First Search.

* Uses a wrapper method to initialize objects required for search traversal.

* @param source source node to be used in search.

* @param destination destination node to be used in search.

* @return true if a path exists between source and destination nodes, false if otherwise.

* @

*/

public boolean breadthFirstSearch(GraphNode source, GraphNode destination) {

if(!this.adjacencyMap.containsKey(source) || !this.adjacencyMap.containsKey(destination)) {

return false;

}

LinkedList> queue = new LinkedList<>();

queue.addLast(source);

return breadthFirstSearch(queue, destination);

}

private boolean breadthFirstSearch(LinkedList> queue, GraphNode destination) {

HashMap, VisitStatus> visited = new HashMap<>();

while(!queue.isEmpty()) {

GraphNode current = queue.removeFirst();

visited.put(current, VisitStatus.VISITING);

if(current.equals(destination)) {

return true;

}

for(GraphNode neighbor : this.adjacencyMap.get(current)) {

if(visited.containsKey(neighbor)) {

if(visited.get(neighbor).equals(VisitStatus.UNVISITED)) {

queue.addLast(neighbor);

}

} else {

queue.addLast(neighbor);

}

}

visited.put(current, VisitStatus.VISITED);

}

return false;

}

/**

* Returns the number of vertices within the graph.

* @return an integer representing number of vertices contained within the graph.

* @

*/

public int getNumVertices() {

return this.numVertices;

}

/**

* Returns the number of edges within the graph.

* @return an integer representing number of edges contained within the graph.

* @

*/

public int getNumEdges() {

return this.numEdges;

}

}

GRAPH NODE CLASS

public class GraphNode {

private T data;

public GraphNode() {}

public GraphNode(T data) {

this.data = data;

}

public T getData() {

return data;

}

public void setData(T data) {

this.data = data;

}

}

VISIT ENUM CLASS :-

public enum VisitStatus {

UNVISITED,

VISITING,

VISITED

}

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Databases And Python Programming MySQL MongoDB OOP And Tkinter

Authors: R. PANNEERSELVAM

1st Edition

9357011331, 978-9357011334

More Books

Students also viewed these Databases questions

Question

What do Dimensions represent in OLAP Cubes?

Answered: 1 week ago