Complete the unweighted graph implementation provided. You will need to implemen

Question

Complete the unweighted graph implementation provided. You will need to implement the various functions (constructor, addVertex, addEdge, print) and determine the data members. It is an unweighted graph; you can choose a directed/or undirected.

- graph() constructs an empty graph

- addVertex() adds a vertex to your graph and returns its nodeid (an unsigned int). Starts at 0, then 1, etc.

- addEdge(to,from) adds an edge from nodeid to to nodeid from. If your graph is undirected, also adds the other edge.

- print() prints out the structure of the graph (node 0 is connected to nodes i, j, k and etc)

Explanation / Answer

Here is the java code for implementing unweighted graph. In adjacency map, complete information of vertices and edges are stored.

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

/*A simple unweighed graph implementation*/

public class Graph<X>
{
final private HashMap<X, Set<X>> adjacencyList;
  
/*Create new Graph object*/
public Graph() {
this.adjacencyList = new HashMap<>();
}
  
/*Add new vertex to the graph*/
public void ADDVertex(X x)
{
if (this.adjacencyList.containsKey(x))
{
throw new IllegalArgumentException("Vertex already exists");
}
this.adjacencyList.put(x, new HashSet<X>());
}
  
/*Remove the vertex v from the graph*/
public void REMOVEVertex(X x)
{
if (!this.adjacencyList.containsKey(x))
{
throw new IllegalArgumentException("Vertex doesn't exist.");
}
  
this.adjacencyList.remove(x);
  
for (X u: this.getAllVertices())
{
this.adjacencyList.get(u).remove(x);
}
}
  
/*Add new edge between vertex. Adding new edge from u to v will automatically add new edge from v to u since the graph is undirected*/
public void ADDEdge(X x, X u)
{
if (!this.adjacencyList.containsKey(x) || !this.adjacencyList.containsKey(u))
{
throw new IllegalArgumentException();
}
  
this.adjacencyList.get(x).add(u);
this.adjacencyList.get(u).add(x);
}
  
/*Remove the edge between vertex. Removing the edge from u to v will automatically remove the edge from v to u since the graph is undirected*/
public void REMOVEEdge(X x, X u)
{
if (!this.adjacencyList.containsKey(x) || !this.adjacencyList.containsKey(u))
{
throw new IllegalArgumentException();
}
  
this.adjacencyList.get(x).remove(u);
this.adjacencyList.get(u).remove(x);
}
  
/*Check adjacency between 2 vertices in the graph*/
public boolean isAdjacent(X x, X u)
{
return this.adjacencyList.get(x).contains(u);
}
  
/*Get connected vertices of a vertex*/
public Iterable<X> getNeighbors(X x)
{
return this.adjacencyList.get(x);
}
  
/*Get all vertices in the graph*/
public Iterable<X> getAllVertices()
{
return this.adjacencyList.keySet();
}
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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