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

here is the output to the sample

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.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) {

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;

}

=========
Run the test and let me know if it doesnt work, I will help and resolve it.. Thanks

I resolved it..Check it out

import java.util.Map;
import java.util.Set;
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;
}

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

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