Description

This programming assignment will test your knowledge and your implementation abilities of what you have learned in the Graph parts of the class.
Description
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 for 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 a gray-scale image as a 2D array of numbers, e.g., as in Fig. 1. These individual numbers are called pixels. Pixels are indexed by their rows and columns. Pixel values are between a range. In this homework, the pixel values are double-precision floating point numbers between 0.0 and 1.0.

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.
• GradeImagePart.java: This file includes the autograder for the image segmentation part. Can be run by itself.
Grading
Your assignment will be graded through an autograder. Make sure to implement the code as instructed, use the same variable and method names. A version of the autograder is released to you. Our version will more or less be similar, potentially including more tests.
Run the main program in the Grade.java to get the autograder output and your grade.
Submission
You are going to submit a compressed archive through the blackboard site. The file should extract to a folder with your student ID without the leading zeros. This folder should only contain files that were in boldface in the previous section. Other files, which you should not have modified anyways, will be deleted and replaced with default versions.
We download all the submissions from blackboard together and put them in a folder. We then run multiple scripts to extract, cleanup and grade your codes. Your codes are compiled from the command line, no IDE is used. If you do not follow the instructions given below, then scripts might fail. This will lead you to get a lower grade than what the autograder suggests. More importantly, your code might not compie, which will result in a grade of 0. Make sure to follow these instructions:
Important: Make sure to download your submission to make sure it is not corrupted and it has your latest code. You are only going to be graded by your blackboard submission.
• You are going to submit a compressed archive through the blackboard site. The file can have zip, tar, rar, tar.gz or 7z format.
• The compressed file should have all the files that you need to modify. If anything is missing, we automaticlly copy over the default versions.
• The compressed file should not contain another compressed file.
• After creating the compressed file, move it to your desktop and extract it. Then check if all the above criteria is met.
• Once you are sure about your assignment and the compressed file, submit it through Blackboard.
• After you submit your code, download it and check if it is the one you intended to submit.
• Do not submit code that does not terminate or that blows up the memory.