COMP202 -  Data Structures and Algorithms - Assignment 6 - Solved

This assignment requires you to implement:

•    A given graph ADT

•    Graph search algorithms

•    Graph traversal on an implicit graph (an image)

The files provided to you have comments that will help you with implementation. In addition, keep the slides handy as they include the pseudo-codes for the algorithms. The file descriptions are below. Bold ones are the ones you need to modify and they are placed under the code folder, with the rest under given. The homework consists of three parts:

Graph Implementation
This part of the homework requires you to implement a given graph ADT for four different types of graphs. There is no explicit Edge class or an explicit Vertex class. This is done to give you total freedom. If you need extra classes such as these, feel free to put them as nested classes but do not provide extra files.

•    iGraph.java: The interface that defines the graph ADT. Make sure you pay attention to all the comments!

•    BaseGraph.java: The abstract base class for the graphs that you should implement. You can put the common functions here or ignore this file all together.

•    UndirectedUnweightedGraph.java: Implement an undirected-unweighted graph in this file.

•    DirectedUnweightedGraph.java: Implement a directed-unweighted graph in this file.

•    UndirectedWeightedGraph.java: Implement an undirected-weighted graph in this file.

•    DirectedWeightedGraph.java: Implement an directed-weighted graph in this file.

•    GraphTesting.java: The file that includes the autograder implementation this part. Can be run by itself.

Graph Algorithms
This part of the homework requires you to implement depth first search (DFS), breadth first search (BFS), Dijkstra’s single-source all-destinations shortest path (or actually smallest cost) algorithm and cycle finding algorithms (for both directed and undirected graphs).

•    GraphAlgorithms.java: Implement the algorithms. You can (and probably should) add more methods and fields.

•    AlgTesting.java: The file that includes the autograder implementation this part. Can be run by itself.

Implicit Graphs: Image Segmentation
This part of the homework requires you to work on an implicit graph formed by the pixels of an image. Think of an image as a 2D array of floating point numbers (doubles in this case). These individual floating point numbers are called pixels. Pixels are indexed by their rows and columns. Pixels values range from 0.0 to 1.0. See Fig. 1

 

Figure 1: A grayscale image is very similar to a 2D array.

The task is to segment a given image by applying graph algorithms. The goal of image segmentation is to cluster pixels into image regions. In our segmentation approach, we want to group together pixels that have similar values. We can pose this as a problem of finding connected components in a graph where each pixel is a vertex and pixel value similarity decides whether there is an edge between neighboring vertices Each pixel has 4 possible neighbors as shown in Fig.2:

 

Figure 2: The pixel in the middle(red color) has 4 possible neighbors labeled 0, 1, 2, 3.

Look at the images under the images/input and images/reference folders to get an idea.

•    ImageSegmenter.java: The file where you need to implement the segmentation approach. There is a dummyIteration method to help you get around the image.

•    Image.java: This files defines a wrapper for an image class. You need to go over it to be able to handle this part of the assignment