Java程序设计代做、代写data编程

项目预算：开发周期：发布时间：要求地区：

Project 1: Java
Introduction
This project will introduce you to programming in Java by asking you to develop an
abstract 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 a
set of nodes (or vertices) N and a set of edges E ⊆ N × N. For this project, graphs
are directed, meaning there could be an edge from a to b without there being an
edge from b to a.
We will define graphs as an abstract data type that implements the following
interface:
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 nodes();
List succ(String n);
List pred(String n);
Graph union(Graph g);
Graph subGraph(Set nodes);
boolean connected(String n1, String n2);
}
Here, nodes are labeled by strings, and if two strings are equals then they always
refer to the same node. The methods do the following:
boolean addNode(String n) adds the node n to the graph. It returns true if the
node was not previously in the graph (i.e., it was added by the call), and false if
the node was already present.
boolean addEdge(String n1, String n2) adds an edge from the node n1 to the node
n2 . It returns true if the edge was not previously in the graph, and false
2023/9/26 18:20 Project 1: Java
https://canvas.tufts.edu/courses/48667/assignments/364521 3/9
otherwise. This method should throw NoSuchElementException if n1 or n2 were not
previously added as nodes.
boolean hasNode(String n) returns true if the node n was added to the graph
previously (and not removed), and false if not.
boolean hasEdge(String n1, String n2) returns true if the edge from n1 to n2 was
added 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 or
from 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 from
the graph, returning true if the edge was previously in the graph and false
otherwise. This method should throw NoSuchElementException if n1 or n2 were not
previously added as nodes.
List nodes() returns a list containing all the nodes in the current graph, in
some unspecified order.
List succ(String n) returns a list of all nodes n2 such that there is an
edge from n to n2 in the graph, i.e., it returns the successors of n . This
method 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 of
integers, lists of lists of strings, etc. We'll go into detail about how this works
later, but for now, all you need to know is that List is a list of strings, and
in the documentation, anywhere you see the type parameter E you can mentally
substitute String . This method should throw NoSuchElementException if n was not
previously added as a node.
List pred(String n) returns a list (a List ) of all nodes n2 such
that there is an edge from n2 to n in the graph, i.e., it returns the predecessors
of n . This method should throw NoSuchElementException if n was not previously
added as a node.
Graph union(Graph g) returns a new graph that includes all the nodes and edges
of the current graph and all the nodes and edges of g . Nodes identified by the
same string in both graphs are coalesced to be the same node in the returned
graph. Note: You may not assume that g is implemented by an ListGraph , i.e.,
2023/9/26 18:20 Project 1: Java
https://canvas.tufts.edu/courses/48667/assignments/364521 4/9
code that casts g to an ListGraph will receive no credit. This requirement means
this method will be extremely annoying to write, which sometimes happens when
interfaces and APIs are not ideal.
Graph subGraph(Set nodes) returns a new graph containing the nodes of the
current graph that are included in nodes and the current graph's edges among
them. 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 resulting
graph 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 path
from n1 to n2 , meaning there is a sequence of edges from n1 to some na to
some nb etc to n2 . If n1.equals(n2) , this method should return true, i.e., a path
of length 0 counts. To implement this method, you'll probably want to use either
breadth-first search (https://en.wikipedia.org/wiki/Breadth-first_search) or
depth-first search (https://en.wikipedia.org/wiki/Depth-first_search) (either will
work). 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 a
HashSet
(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 not
previously added as nodes.
Part 1: Graphs with Adjacency Lists
A key algorithmic design choice in implementing graphs is how to represent edges
in the graph. For the first part of the project, you will implement the Graph interface
using adjacency lists. More specifically, write an implementation of Graph in the file
ListGraph.java in which the nodes and edges of the graph are represented using
the following field:
private HashMap> nodes;
Here, the graph is represented as a mapping from nodes to lists of their successors
in 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: Java
https://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 graph
and does some tests to see what the graph contains.
nodes.put("a", new LinkedList()); // add node "a" to the graph
nodes.put("b", new LinkedList()); // add node "b"
nodes.put("c", new LinkedList()); // add node "c"
nodes.containsKey("a"); // returns true, "a" is a graph node
nodes.containsKey("d"); // returns false, "d" is not a graph node
nodes.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 s = nodes.get(n); // get corresponding successor lists
}
It is also possible to avoid the call to get by iterating over the entrySet of the
HashMap . If you're interested, you can find out how to use that approach by
searching online.
Part 2: A Different Graph API
The 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 graph
edges:
2023/9/26 18:20 Project 1: Java
https://canvas.tufts.edu/courses/48667/assignments/364521 6/9
public 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 outEdges(String n);
List inEdges(String n);
List edges();
EdgeGraph union(EdgeGraph g);
boolean hasPath(List l);
}
with the following methods:
boolean addEdge(Edge e) adds an edge to the graph, returning true if the edge
was not already in the graph or false if not. Note that, in this API, nodes are not
added separately from edges. Node n is automatically added to the graph if an
edge containing n is added.
boolean hasNode(String n) returns true if and only if some edge has been added to
the graph (and not removed) with n as either the source or destination fo the
edge.
boolean hasEdge(Edge e) returns true if edge e has been added to the graph (and
not removed).
boolean removeEdge(Edge e) removes edge e from the graph, returning true if it
was previously in the graph and false otherwise. If this method removes the last
edge 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 of
the Edge is not in the graph.
List outEdges(String n) returns a list of all edges that start at node n .
List inEdges(String n) returns a list of all edges that end at node n .
2023/9/26 18:20 Project 1: Java
https://canvas.tufts.edu/courses/48667/assignments/364521 7/9
List edges() returns a list of all the edges in this graph, in some
unspecified order.
EdgeGraph union(EdgeGraph g) returns a new graph that includes all the nodes and
edges of the current graph and all the nodes and edges of g . Nodes identified
by the same string in both graphs are coalesced to be the same node in the
returned graph. Note: You may not assume that g is implemented by an
EdgeGraphAdapter , i.e., code that casts g to an EdgeGraphAdapter will receive no
credit.
boolean hasPath(List l) returns true if the path l (a List ) is in the
graph. Suppose l = e1, e2, ..., en . The method first checks if all edges ei are
in the graph; if any are not, the method should return false . The method then
checks if the argument is a path, i.e., if ei.getDst() == e(i+1).getSrc() for every
edge in the middle of the list. If this is not the case, this code should raise the
exception BadPath , which is defined in file BadPath.java . Note that every graph
includes the empty path (since if a graph contains a path, it should contain every
sub-path).
Your task for the second part of the project is to implement an EdgeGraph . But, like
any good software engineer, you don't want to start from scratch. You already have
perfectly good Graph implementation. So, for this part of the project, you will write
an adapter (https://en.wikipedia.org/wiki/Adapter_pattern) that, given a Graph , will
adapt it to be an EdgeGraph . More specifically, implement EdgeGraphAdapter , which
looks 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 that
delegates graph operations to g . You can assume that when this constructor is
called, the argument g will be an empty graph. You'll notice that for some methods
of EdgeGraph , you can call corresponding methods of g with no change. With other
2023/9/26 18:20 Project 1: Java
https://canvas.tufts.edu/courses/48667/assignments/364521 8/9
methods, 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 just
ListGraph . Cool!
Part 3: Write and Share a Test Case
To help you test your code, we've created a simple method main in class Main so
you 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 grading
of your project, you should right a bunch more tests ( test3 , test4 , etc., or call
them whatever you want since we won't evaluate these methods) and add calls to
them 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 in
the semester, but this method just creates a new graph, adds a node to it, and
checks that the node is in the graph. To check that methods are returning the
correct values, it uses Java's assert statement, which takes a boolean argument
and raises an exception if the argument doesn't evaluate to true .
Important: To run the code with assertions enabled, you need to invoke java -ea
Main , 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 and
not run them.
2023/9/26 18:20 Project 1: Java
https://canvas.tufts.edu/courses/48667/assignments/364521 9/9
Although you can't generally share code for this class, we will make one exception
for this project: You must write one test case, in the style of test1 above, and post
it publicly to Piazza to share with the class. Your test case must be for Part 1
only. You may not share test cases for Part 2. Your test case can test any
functionality of Part 1, as much or as little as you like. It need not be substantively
different 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've
even started implementing the project. This is called Test-driven development
(https://en.wikipedia.org/wiki/Test-driven_development) , which is a popular software
engineering approach.
What to turn in
Put all your code in the code skeleton we have supplied, and upload your solution
using Gradescope. Important: Be sure all of your .java files are at the top level in
your submission. If you submit them inside of a directory, the autograder won't find
your code and compilation will fail. For this and all future projects, you may not
change any public API we specify, including changing the list of exceptions that
may be thrown by a method. Also for this and all future projects, unless otherwise
specified, your code may only use standard Java libraries; it may not use any
libraries that require changing the CLASSPATH or compilation options.