1 Overview

We have been learning about graphs in class. An important property to test in graphs is whether a given node is part of a cycle — that is, a path that loops back to that same node. For example, in the following graph, nodes A, B, and C are part of a cycle, but nodes D, E, and F are not part of any cycle:

For this homework, you will implement the graph ADT for a directed, unweighted graph, and use your graph implementation to perform a bare-bones graph search and detect whether a given node is part of a cycle.

2 Starter code

• Graph.java
• GraphTest.java
• CycleFinder.java
• DotReader.java
• Stdin.java
• pointy-triangle.dot
• ring-star.dot
• r100.dot
• Makefile

You can get all these files at once by downloading the file hw09.tar.gz and running tar xzvf hw09.tar.gz

What these files give you:

• Graph.java: Java interface for a directed, unweighted graph. You have to write your own MyGraph.java to implement this interface.

• GraphTest.java: Thorough testing of your MyGraph class using JUnit.

• CycleFinder.java: Program to read in a graph file, ask for node names, and say whether each node is in a cycle. The main is written for you; you have to write the hasCycle method.

• DotReader.java: Utility to read in a dot-formatted graph file and use the addVertex and putEdge methods to create a graph using your MyGraph class. You shouldn’t need to change anything here.

• Stdin.java: Simple utility to read standard in line by line. You shouldn’t need to change anything here.

• pointy-triangle.dot, ring-star.dot, r100.dot: Sample graph files

• Makefile: command-line shortcuts to compile, run JUnit tests, and make graph pdfs for visualization

3 Dot format

The graphs you will use are in a file format called DOT. It’s basically a list of edges. For example, the following file pointy-triangle.dot:

digraph {
  A -> B
  B -> C
  C -> A
  D -> A
  B -> E
  F -> C
}

generates the graph shown at the top of the page.

In Java, we have provided the DotReader.java which will read from a dot file into an instance of your class MyGraph.

You can also use any of the free tools from the graphviz package to visualize dot files. This should already be installed on the lab machines; to install on your own VM or WSL instance, do

sudo apt update
sudo apt install graphviz

Then, running a command like

neato pointy-triangle.dot -Tpdf -opointy-triangle.pdf

will convert the dot file into a pdf which you can then open and admire. In fact, the provided Makefile will do this for you if you type, for example, make pointy-triangle.pdf

Try running man neato or man dot for more information if you are interested!

4 First task: Write an implementation of the Graph interface

Graph.java is a Java interface for the Graph ADT that we looked at in class, made a little bit simpler because we are only dealing with unweighted graphs for this homework.

There are 5 methods. You need to create a new class MyGraph.java which implements this interface. Be sure to read the documentation for details on how each method should work, when they should throw exceptions, etc.

In class we discussed two ways to implement a graph: adjacency lists or adjacency matrix. You can use either way for this assignment as long as it is implemented well.

You can also use any class in java.util, such as ArrayList and HashMap. We have implemented lists, sets, maps, and priority queues now, so you are free to use the ones Java has provided for you!

(Hint: if you make good use of Java’s built-in lists and maps, then your implementation of MyGraph.java will be much much easier than past homeworks!)

(Another hint: if you are making an adjacency matrix, I recommend using the BitSet class for each row of the matrix. Bits make sense here because we are only storing unweighted graphs.)

4.1 Testing

A thorough set of JUnit tests is included for you in GraphTest.java. These are the same tests that will run when you submit your code.

If you have downloaded the Makefile, assuming you already installed Junit, you can run these tests by typing

make test

5 Second task: Finding cycles

Once your MyGraph class is working perfectly, the included main in CycleFinder.java should work correctly to read in a graph (in a .dot file) into an instance of your MyGraph class.

Now you just need to complete the CycleFinder program by implementing the hasCycle method.

• Either depth-first or breadth-first search should work here.
• Again, you can use any of the built-in classes in java.util.
• There is basically just one if statement you need to add to a “plain” DFS or BFS in order to detect whether a loop has circled back around to the starting node. Think about it!

5.1 Testing

Use the provided dot files to test your code, or create your own!

For the larger r100.dot file, it will be way too large to make a pdf and visualize it. This graph has 100 nodes and 1000 edges. Instead, we named the nodes conveniently to help you in testing. All the nodes named a1 through a50 are NOT in any cycle, whereas the nodes named c1 through c50 are in cycles.

Be sure to thoroughly test your code before submitting! A few tests on other graph files will also run on the submit system.