Project 1: JavaIntroductionThis project will introduce you to programming in Java by asking you to develop anabstract data type for graphs, and then adapt it for a slightly different interface.A graph (https://en.wikipedia.org/wiki/Graph_(abstract_data_type)) consists of aset of nodes (or vertices) N and a set of edges E ⊆ N × N. For this project, graphsare directed, meaning there could be an edge from a to b without there being anedge from b to a.We will define graphs as an abstract data type that implements the followinginterface:public interface Graph { boolean addNode(String n); boolean addEdge(String n1, String n2); boolean hasNode(String n); boolean hasEdge(String n1, String n2); boolean removeNode(String n); boolean removeEdge(String n1, String n2); List<String> nodes(); List<String> succ(String n); List<String> pred(String n); Graph union(Graph g); Graph subGraph(Set<String> nodes); boolean connected(String n1, String n2);}Here, nodes are labeled by strings, and if two strings are equals then they alwaysrefer to the same node. The methods do the following:boolean addNode(String n) adds the node n to the graph. It returns true if thenode was not previously in the graph (i.e., it was added by the call), and false ifthe node was already present.boolean addEdge(String n1, String n2) adds an edge from the node n1 to the noden2 . It returns true if the edge was not previously in the graph, and false2023/9/26 18:20 Project 1: Javahttps://canvas.tufts.edu/courses/48667/assignments/364521 3/9otherwise. This method should throw NoSuchElementException if n1 or n2 were notpreviously added as nodes.boolean hasNode(String n) returns true if the node n was added to the graphpreviously (and not removed), and false if not.boolean hasEdge(String n1, String n2) returns true if the edge from n1 to n2 wasadded to the graph previously (and not removed), and false if not.boolean removeNode(String n) removes node n from the graph and all edges to orfrom n . It returns true if n was previously in the graph and false otherwise.boolean removeEdge(String n1, String n2) removes the edge from n1 to n2 fromthe graph, returning true if the edge was previously in the graph and falseotherwise. This method should throw NoSuchElementException if n1 or n2 were notpreviously added as nodes.List<String> nodes() returns a list containing all the nodes in the current graph, insome unspecified order.List <String> succ(String n) returns a list of all nodes n2 such that there is anedge from n to n2 in the graph, i.e., it returns the successors of n . Thismethod type uses the List(https://docs.oracle.com/en/java/javase/18/docs/api/java.base/java/util/List.html)interface. This is in a generic type, meaning you can have lists of strings, lists ofintegers, lists of lists of strings, etc. We'll go into detail about how this workslater, but for now, all you need to know is that List<String> is a list of strings, andin the documentation, anywhere you see the type parameter E you can mentallysubstitute String . This method should throw NoSuchElementException if n was notpreviously added as a node.List <String> pred(String n) returns a list (a List<String> ) of all nodes n2 suchthat there is an edge from n2 to n in the graph, i.e., it returns the predecessorsof n . This method should throw NoSuchElementException if n was not previouslyadded as a node.Graph union(Graph g) returns a new graph that includes all the nodes and edgesof the current graph and all the nodes and edges of g . Nodes identified by thesame string in both graphs are coalesced to be the same node in the returnedgraph. Note: You may not assume that g is implemented by an ListGraph , i.e.,2023/9/26 18:20 Project 1: Javahttps://canvas.tufts.edu/courses/48667/assignments/364521 4/9code that casts g to an ListGraph will receive no credit. This requirement meansthis method will be extremely annoying to write, which sometimes happens wheninterfaces and APIs are not ideal.Graph subGraph(Set<String> nodes) returns a new graph containing the nodes of thecurrent graph that are included in nodes and the current graph's edges amongthem. For example, if the current graph has nodes [A,B,C,D] and edges A→B ,A→C , C→D and the nodes argument to subGraph is [A, B, C, E] , then the resultinggraph would contain edges A→B and A→C , and nodes A , B , and C .boolean connected(String n1, String n2) returns true if and only if there is a pathfrom n1 to n2 , meaning there is a sequence of edges from n1 to some na tosome nb etc to n2 . If n1.equals(n2) , this method should return true, i.e., a pathof length 0 counts. To implement this method, you'll probably want to use eitherbreadth-first search (https://en.wikipedia.org/wiki/Breadth-first_search) ordepth-first search (https://en.wikipedia.org/wiki/Depth-first_search) (either willwork). For this method to work correctly in the presence of cycles in the graph(i.e., the case when one node is connected to itself), you might want to use aHashSet<String>(https://docs.oracle.com/en/java/javase/20/docs/api/java.base/java/util/HashSet.html). This method should throw NoSuchElementException if n1 or n2 were notpreviously added as nodes.Part 1: Graphs with Adjacency ListsA key algorithmic design choice in implementing graphs is how to represent edgesin the graph. For the first part of the project, you will implement the Graph interfaceusing adjacency lists. More specifically, write an implementation of Graph in the fileListGraph.java in which the nodes and edges of the graph are represented usingthe following field: private HashMap<String, LinkedList<String>> nodes;Here, the graph is represented as a mapping from nodes to lists of their successorsin the graph. The map itself is a hash table (a HashMap(https://docs.oracle.com/en/java/javase/20/docs/api/java.base/java/util/HashMap.html)2023/9/26 18:20 Project 1: Javahttps://canvas.tufts.edu/courses/48667/assignments/364521 5/9), and the lists are LinkedList(https://docs.oracle.com/en/java/javase/20/docs/api/java.base/java/util/LinkedList.html)s, which are just like linked lists in C.For example, here is some code that creates a few nodes and edges in the graphand does some tests to see what the graph contains.nodes.put("a", new LinkedList<String>()); // add node "a" to the graphnodes.put("b", new LinkedList<String>()); // add node "b"nodes.put("c", new LinkedList<String>()); // add node "c"nodes.containsKey("a"); // returns true, "a" is a graph nodenodes.containsKey("d"); // returns false, "d" is not a graph nodenodes.get("a").add("b"); // add edge from "a" to "b"nodes.get("c").add("a"); // add edge from "c" to "a"nodes.containsKey("c") && nodes.get("c").contains("a") && nodes.containsKey("a") && nodes.get("a").contains("b") // returns true, there's a path from "c" to "b"Hint: If you want to iterate through a LinkedList in Java, you can use a while loop,or you can use the following syntactic sugar; we'll explain why this works later.for (String n : nodes.get("a")) { // iterate through elements of nodes.get("a") // code that uses n}If you want to iterate over a HashMap , you can do the following:for (String n : nodes.keySet()) { // iterate over key of HashMap LinkedList<String> s = nodes.get(n); // get corresponding successor lists}It is also possible to avoid the call to get by iterating over the entrySet of theHashMap . If you're interested, you can find out how to use that approach bysearching online.Part 2: A Different Graph APIThe Graph interface we gave you above is just one possible interface for graphs.For example, here is a class that implements an immutable representation of graphedges:2023/9/26 18:20 Project 1: Javahttps://canvas.tufts.edu/courses/48667/assignments/364521 6/9public class Edge { private String src, dst; // source, destination Edge(String src, String dst) {this.src = src; this.dst = dst; } String getSrc() { return src; } String getDst() { return dst; }}We can then use this class to define a different interface for graphs:public interface EdgeGraph { boolean addEdge(Edge e); boolean hasNode(String n); boolean hasEdge(Edge e); boolean removeEdge(Edge e); List<Edge> outEdges(String n); List<Edge> inEdges(String n); List<Edge> edges(); EdgeGraph union(EdgeGraph g); boolean hasPath(List<Edge> l);}with the following methods:boolean addEdge(Edge e) adds an edge to the graph, returning true if the edgewas not already in the graph or false if not. Note that, in this API, nodes are notadded separately from edges. Node n is automatically added to the graph if anedge containing n is added.boolean hasNode(String n) returns true if and only if some edge has been added tothe graph (and not removed) with n as either the source or destination fo theedge.boolean hasEdge(Edge e) returns true if edge e has been added to the graph (andnot removed).boolean removeEdge(Edge e) removes edge e from the graph, returning true if itwas previously in the graph and false otherwise. If this method removes the lastedge to or from a given node in the graph, that node should also be removed.Note: This method does not throw an exception even if one or the other end ofthe Edge is not in the graph.List<Edge> outEdges(String n) returns a list of all edges that start at node n .List<Edge> inEdges(String n) returns a list of all edges that end at node n .2023/9/26 18:20 Project 1: Javahttps://canvas.tufts.edu/courses/48667/assignments/364521 7/9List<Edge> edges() returns a list of all the edges in this graph, in someunspecified order.EdgeGraph union(EdgeGraph g) returns a new graph that includes all the nodes andedges of the current graph and all the nodes and edges of g . Nodes identifiedby the same string in both graphs are coalesced to be the same node in thereturned graph. Note: You may not assume that g is implemented by anEdgeGraphAdapter , i.e., code that casts g to an EdgeGraphAdapter will receive nocredit.boolean hasPath(List<Edge> l) returns true if the path l (a List<Edge> ) is in thegraph. Suppose l = e1, e2, ..., en . The method first checks if all edges ei arein the graph; if any are not, the method should return false . The method thenchecks if the argument is a path, i.e., if ei.getDst() == e(i+1).getSrc() for everyedge in the middle of the list. If this is not the case, this code should raise theexception BadPath , which is defined in file BadPath.java . Note that every graphincludes the empty path (since if a graph contains a path, it should contain everysub-path).Your task for the second part of the project is to implement an EdgeGraph . But, likeany good software engineer, you don't want to start from scratch. You already haveperfectly good Graph implementation. So, for this part of the project, you will writean adapter (https://en.wikipedia.org/wiki/Adapter_pattern) that, given a Graph , willadapt it to be an EdgeGraph . More specifically, implement EdgeGraphAdapter , whichlooks like the following:public class EdgeGraphAdapter implements EdgeGraph { private Graph g; EdgeGraphAdapter(Graph g) { this.g = g; } // methods of EdgeGraph}So, to implement the methods of EdgeGraphAdapter , you will write code thatdelegates graph operations to g . You can assume that when this constructor iscalled, the argument g will be an empty graph. You'll notice that for some methodsof EdgeGraph , you can call corresponding methods of g with no change. With other2023/9/26 18:20 Project 1: Javahttps://canvas.tufts.edu/courses/48667/assignments/364521 8/9methods, you'll need to change the arguments a bit. And with still other methods,you'll need to implement new functionality that's not part of Graph .Notice also that your code will work with any implementation of Graph , not justListGraph . Cool!Part 3: Write and Share a Test CaseTo help you test your code, we've created a simple method main in class Main soyou can run some test cases. The body of main looks like this: public static void main(String[] args) {test1();test2(); }It just calls a couple of simple tests we wrote. Though it won't count in the gradingof your project, you should right a bunch more tests ( test3 , test4 , etc., or callthem whatever you want since we won't evaluate these methods) and add calls tothem in main .Here is the definition of test1 : public static void test1() {Graph g = new ListGraph();assert g.addNode("a");assert g.hasNode("a"); }There are a bunch of ways to write and design tests, which we'll talk about later inthe semester, but this method just creates a new graph, adds a node to it, andchecks that the node is in the graph. To check that methods are returning thecorrect values, it uses Java's assert statement, which takes a boolean argumentand raises an exception if the argument doesn't evaluate to true .Important: To run the code with assertions enabled, you need to invoke java -eaMain , i.e., you need to pass the -ea (or -enableassertions ) argument to the JVM.Otherwise, by default, the JVM will ignore the assertion statements completely andnot run them.2023/9/26 18:20 Project 1: Javahttps://canvas.tufts.edu/courses/48667/assignments/364521 9/9Although you can't generally share code for this class, we will make one exceptionfor this project: You must write one test case, in the style of test1 above, and postit publicly to Piazza to share with the class. Your test case must be for Part 1only. You may not share test cases for Part 2. Your test case can test anyfunctionality of Part 1, as much or as little as you like. It need not be substantivelydifferent than others' test cases, but you must come up with it on your own. In fact,you should come up with a test case (or many test cases) right now, before you'veeven started implementing the project. This is called Test-driven development(https://en.wikipedia.org/wiki/Test-driven_development) , which is a popular softwareengineering approach.What to turn inPut all your code in the code skeleton we have supplied, and upload your solutionusing Gradescope. Important: Be sure all of your .java files are at the top level inyour submission. If you submit them inside of a directory, the autograder won't findyour code and compilation will fail. For this and all future projects, you may notchange any public API we specify, including changing the list of exceptions thatmay be thrown by a method. Also for this and all future projects, unless otherwisespecified, your code may only use standard Java libraries; it may not use anylibraries that require changing the CLASSPATH or compilation options.