Project 1: Java ADTs and the Adapter Pattern

COMP 150-SEN, Spring 2019

Test case (part 3) due: Mon, Feb 4 @ 11:59pm

Main project due: Tue, Feb 12 @ 11:59pm

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 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);
    List succ(String n);
    List pred(String n);
    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:

Here is the code skeleton for the project.

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 in which the nodes and edges of the graph are represented using the following field:

   private HashMap<String, LinkedList<String>> 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), and the lists are LinkedLists, 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<String>());  // add node "a" to the graph
nodes.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 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.

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:

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 hasPath(List l);
with the following methods:

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 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'll notice that for some methods of EdgeGraph, you can call corresponding methods of g with no change. With other 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!

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

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.

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 can test any functionality of the project, 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, which is a popular software engineering approach.

Put all your code in the code skeleton we have supplied, and upload your solution using Gradescope.