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