Last modification: 18/11/16
The FigureDemo
class from last week
Write a FigureDemo
class outside of the geometry
package.
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.
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.
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.
A hasEdge()
that takes two nodes (two int
s) as arguments and returns true if there is an edge from the first node to the second.
An edgesFrom()
that takes a node as argument, and returns the set of neighbours of the argument.
An addEdge()
that adds an edge from the first node to the second.
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
.
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.
Implement methods hasEdge()
, edgesFrom()
and addEdge()
of the superclass Graph
.
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.
At the beginning only the start node is in the stack.
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.
Iterate while the stack is not empty.
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.
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.
Type of graph (dense or sparse)
Number of nodes
List of edges. The edges are given as node1-node2
and separated only with a comma
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]