Java SE 8 API documentation

Last modification: 18/11/16

  1. The FigureDemo class from last week

    Write a FigureDemo class outside of the geometry package.

    1. Define a static method largest() which returns the figure with largest area from a sequence of figures. The largest() accepts a ArrayList and a LinkedList as well, so it takes a List as argument.

      Use the compareTo() method of the interface Figure to select the largest figure, and an Iterator to iterate over the list.

    2. Write a main() method to test your largest() method. Initialize a List variable with a LinkedList object and add some figures to it. Print the largest figure to the output.

  2. The Graph abstract base class

    Create an abstract base class Graph which forms the interface of graphs where each node stores an integer. Add the declarations of the following abstract methods to the class.

    1. A hasEdge() that takes two nodes (two ints) as arguments and returns true if there is an edge from the first node to the second.

    2. An edgesFrom() that takes a node as argument, and returns the set of neighbours of the argument.

    3. An addEdge() that adds an edge from the first node to the second.

  3. The Densegraph subclass

    Create a class DenseGraph which is a subclass of Graph and efficient in representing dense graphs.

    The edges are stored in an adjacency matrix, which is a two-dimensional matrix of boolean values. A true value in the position i,j means an edge from node i to j.

    1. Add a construktor to the class which takes the number of nodes as argument. The nodes are numbers in [0…n − 1]. There is no way to add nodes to the class, but there is for edges.

    2. Implement methods hasEdge(), edgesFrom() and addEdge() of the superclass Graph.

  4. Depth-first traversal

    Add a method depthFirstTraversal() to Graph. The method takes a node as argument and traverses the graph in depth-first order starting from that node. It returns the visited nodes in a list.

    Use a java.util.LinkedList as a stack and an other list for keeping record of the visited nodes.

    1. At the beginning only the start node is in the stack.

    2. In each iteration, take the first element of the stack. If the element has not been visited before (it is not found in the list of visited nodes) then add it to the visited nodes. Take the neighbours of the node and add the unvisited ones to the stack.

    3. Iterate while the stack is not empty.

  5. The SparseGraph subclass

    Create a new subclass SparseGraph of Graph. The subclass is optimal for representing sparse graphs. Store the edges in a java.util.ArrayList, which features fast indexing, where each element is a java.util.Set of neighbours.

    Implement the methods hasEdge(), edgesFrom() and addEdge() accordingly. The constructor should be similar to the above one.

  6. The Main class

    In order to test our classes, create a Main class. The program takes four arguments, the correctness of the arguments is assumed. The arguments are as follows.

    1. Type of graph (dense or sparse)

    2. Number of nodes

    3. List of edges. The edges are given as node1-node2 and separated only with a comma

    4. From which node to start the depth-first traversal

    The program creates the graph, adds the edges, does the traversal, and prints the result of the traversal.

    For instance:

    $ java Main sparse 4 0-1,1-3,0-2,2-3 0
[0, 2, 3, 1]
$ java Main dense 4 0-1,1-3,0-2,2-3 0
[0, 2, 3, 1]