Driver

In HW8, you have implemented the Graph ADT. Our Graph abstraction was generic and comprehensive with many operations. For this (take-home) exam, we will use a much simpler graph representation where the graph data can be read from the standard input. Concisely, graphs are given as follows.

4 5
2 1 
4 3 
1 4 
2 4 
3 2
  • The first line contains non-negative integers $n$ and $m$ — the number of vertices and the number of edges, respectively.
  • The vertices are always numbered from $1$ to $n$. A graph must have at least one vertex.
  • The number of edges is always a value $\geq 0$.
  • Each of the following $m$ lines defines an edge in the format $(u, v)$ where $1 \leq u, v \leq n$ are endpoints of the edge. For the questions in this take-home exam, all graphs are simple, directed, and unweighted.
  • This format of providing graph data is referred to as the "standard from" in this exam.

You are provided with Graph.java, which facilitates reading and printing graph data from/to standard input/output. The Graph.read() method reads graph data and returns an array of List<Edge> which encapsulates an adjacency (incidence) list representation of a graph. Notice the Graph.Edge inner class, which represents a directed edge. You can use Graph.print to print graph data to standard output. The output can be used to "create" visualization of your graph using the GraphViz tool: https://edotor.net/.

Run the Driver program and try the following input:

4 5
2 1 
4 3 
1 4 
2 4 
3 2

The input above results in the following output:

digraph {
   rankdir=LR;
   node [shape=circle];
   1
   2
   3
   4
   1 -> 4
   2 -> 1
   2 -> 4
   3 -> 2
   4 -> 3
}

The output corresponds to the following directed graph:

Note the Graph.read method ignores white spaces. That is, you can provide the above input data in the following formats as well:

4 
5
2 
1 
4 
3 
1 
4 
2 
4 
3 
2

4 5 2 1 4 3 1 4 2 4 3 2

If you look at GraphTest.java file, you will find two more examples. Notice the use of @StdIo annotation. This is an extension to the JUnit library that allows you to test programs (such as Graph.read) that read data from standard input. All the tests for the tasks in this exam use this utility for unit testing.