Need a simple exercise with a graph based on an adjacency list. provide two meth

Question

Need a simple exercise with a graph based on an adjacency list. provide two method implementations for the following class:

import java . util . Map ;
import java . util . Set ;
import java . util . List ;

public class Graph <T > {
public Graph () {
adjacency = new java . util . HashMap < >();
}
public void addEdge (T start , T end )
{
}
public boolean testPath ( List <T > vertexList )
{
}
private Map <T , Set <T >> adjacency ;
}

the following methods are needed:
1. void addEdge(T start, T end) This code adds the directed edge (start, end) to the graph. In the map adjacency, get or create the Set associated with start, and add end to this Set.
2. boolean testPath(List vertexList) This method should return true if each consecutive pair of vertices in the list exists in the graph, false otherwise. Throw an exception if vertexList doesn’t have at least one edge’s worth of vertices in it!

Here is a SAMPLE TEST CLASS

Heres the desired output

public static void main (String[] args) Graph g - new Graph); g.addEdge ( "A", "?"); 8. addEdge ("B" "C g.addEdge("A" , "B" System.out println("Test results"+ g.testPath (Arrays.asList ("A", "?", "C"))); System.out.println("Test results: "+ g.testPath(Arrays.asList ("B", .C", "A"))); g.addEdge ( "?", "?"); System.out.println ("Test results: "+ g.testPath (Arrays.asList("B", "C", "A"))); try g.testPath (Arrays.asList ("Z")); catch (Exception e) System.out.println("Graph threw an exception (I expected that!)") e.printStackTrace

Explanation / Answer

import java.util.Map;

import java.util.Set;

import java.util.Arrays;

import java.util.HashSet;

import java.util.List;

public class Graph<T> {

public Graph() {

adjacency = new java.util.HashMap<>();

}

public void addEdge(T start, T end) {

Set<T> set = new HashSet<T>();

if (adjacency.get(start) != null) {

set = adjacency.get(start);

set.add(end);

adjacency.put(start, set);

} else {

set.add(end);

adjacency.put(start, set);

}

}

public boolean testPath(List<T> vertexList) throws Exception {

if(vertexList==null || vertexList.size()<=1)

throw new RuntimeException("vertex list must contain at least two vertices");

for (int i = 0; i < vertexList.size() - 1; i = i + 1) {

Set<T> set = adjacency.get(vertexList.get(i));

if (set == null)

return false;

if (i + 1 < vertexList.size() && !set.contains(vertexList.get(i + 1)))

return false;

}

return true;

}

private Map<T, Set<T>> adjacency;

//You can remove the below Lines, But make sure main throws exception
public static void main(String[] args) throws Exception {

//Remove the below closing brace as well
}

}

==========================================
One small change You need to make in the MAIN that You have

NOTE : Add the Line" throws Exception"

public static void main(String[] args) throws Exception {


Thanks, rest all will remain same. Let me know if there is any concern.

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

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