Assignment 9 Graph Flood Fill

Assignment 9
CS329e - Elements of Software Design
Graph Flood Fill
(100 points)
Due Date on Canvas and Gradescope
1 Description
In this assignment you will build a graph, print its adjacency matrix and implement Breadth-First Search
and Depth-First Search to flood fill pixels in images.
You may also know this feature as ”bucket fill” from graphics applications. It allows you to select a pixel
in an image and it will fill the selected pixel and all connected pixels of the same color with a new color,
thereby allowing you to change the color of a large area of an image.
You will implement this feature using the Breadth-First Search and Depth-First Search algorithms. We
treat each pixel of an input image as a node in a graph. We start at a given node/pixel and explore the graph
from there, changing the color of each pixel as we visit it.
You will read in a file containing nodes, consisting of an x-&y-coordinate and a color, and edges between
the nodes to build a graph. The skeleton code provides the function ImageGraph.print image() to display the
graph of ColorNodes as an image in the console.
In this assignment your task is to complete a python program with the name GraphFill.py.
1
2 Tasks
You are given the following tasks:
1. Read in the input file.
2. Create the nodes. Add them to the list ImageGraph.nodes in the order they appear in the input file.
3. Connect the nodes with the edges described in the input file.
4. Print the adjacency matrix of the graph.
5. Complete the Breadth-First Search function of the Graph class.
6. Complete the Depth-First Search function of the Graph class.
Rules for the search algorithms:
• Only visit nodes that have the same color as the starting node.
• Color visited nodes in the new color.
• Call the ImageGraph.print image() function after coloring a pixel.
• If there is ambiguity about which node to visit first, use the order in which they appear in ColorNode.
edges (sorted by index in the ImageGraph.nodes list) to follow the same path as the grader.
Apart from the ImageGraph and ColorNode classes, you will also find a Stack and a Queue class. You might
find these helpful in your search algorithm implementations.
2
Input:
You will read your input data from the provided *.in files. The file small.in contains the smallest amount
of nodes and might be a good starting point to test your implementation. The format of the files will be as
follows:
1 5
2 5
3 1 , 1 , r e d
4 2 , 1 , r e d
5 3 , 1 , r e d
6 2 , 2 , r e d
7 3 , 2 , r e d
8 5
9 0 ,1
10 1 ,2
11 1 ,3
12 2 ,4
13 3 ,4
14 2 , g r e e n
15 2 , r e d
The first line will be the dimension of the image (width and height). Use this number to initialize the
ImageGraph. The second line is the number of lines following afterwards describing the nodes. Each node
description has the format
x,y,color.
After the nodes, there’s another line with a single number telling you how many edge descriptions follow.
Each edge description has the format
from node index,to node index.
You should connect from node to to node and to node to from node.
Finally, there’s two lines telling you which node index to start the BFS and DFS algorithms on and which
color to use for the flood fill. The first line gives you the values for the Breadth-First Search and the second
one gives you the values for the Depth-First Search.
3
Output:
There’s three parts to the output:
1. The adjacency matrix
2. The intermediate images produced by the BFS algorithm
3. The intermediate images produced by the DFS algorithm
The adjacency matrix has a one at position x,y if there is an edge connecting the node at position x in
the ImageGraph.nodes list and the node at position y in the list; otherwise it is zero in this position. There are
no spaces or other delimiters between the numbers.
Make sure to call ImageGraph.print image() after each pixel that you color and don’t remove the empty print ()
statements that add new lines from the function/add more new lines to the output.
Here’s what the output for small.in should look like:
You can find additional desired outputs for the example *.in files we provided in the out files directory.
Use cat out files/horns.out on Mac/Linux or type out files/horns.out on Windows to
print the desired outputs for the input file in files/horns.in in the terminal.
The file that you will be turning in will be called GraphFill.py. You will follow the standard coding
conventions in Python.
You may not change the names of the functions listed. They must have the functionality as given in the
specifications. You can always add more functions than those listed.
4
For this assignment you may work with a partner. Both of you must read the paper on Pair Programming1
and abide by the ground rules as stated in that paper. If you are working with a partner then only one of you
will be submitting the code. But make sure that your partner’s name and UT EID is in the header. If you are
working alone then remove the partner’s name and eid from the header.
2.1 Turnin
Turn in your assignment on time on Gradescope system on Canvas. For the due date of the assignments,
please see the Gradescope and Canvas systems.
2.2 Academic Misconduct Regarding Programming
In a programming class like our class, there is sometimes a very fine line between ”cheating” and acceptable
and beneficial interaction between students (In different assignment groups). Thus, it is very important that
you fully understand what is and what is not allowed in terms of collaboration with your classmates. We
want to be 100% precise, so that there can be no confusion.
The rule on collaboration and communication with your classmates is very simple: you cannot transmit
or receive code from or to anyone in the class in any way – visually (by showing someone your code),
electronically (by emailing, posting, or otherwise sending someone your code), verbally (by reading code to
someone) or in any other way we have not yet imagined. Any other collaboration is acceptable.
The rule on collaboration and communication with people who are not your classmates (or your TAs or
instructor) is also very simple: it is not allowed in any way, period. This disallows (for example) posting
any questions of any nature to programming forums such as StackOverflow. As far as going to the web and
using Google, we will apply the ”two line rule”. Go to any web page you like and do any search that you
like. But you cannot take more than two lines of code from an external resource and actually include it in
your assignment in any form. Note that changing variable names or otherwise transforming or obfuscating
code you found on the web does not render the ”two line rule” inapplicable. It is still a violation to obtain
more than two lines of code from an external resource and turn it in, whatever you do to those two lines after
you first obtain them.
Furthermore, you should cite your sources. Add a comment to your code that includes the URL(s) that
you consulted when constructing your solution. This turns out to be very helpful when you’re looking at
something you wrote a while ago and you need to remind yourself what you were thinking.
We will use the following Code plagiarism Detection Software to automatically detect plagiarism.
• Staford MOSS
https://theory.stanford.edu/˜aiken/moss/
• Jplag - Detecting Software Plagiarism
https://github.com/jplag/jplag and https://jplag.ipd.kit.edu/
1Read this paper about Pair Programming https://collaboration.csc.ncsu.edu/laurie/Papers/
Kindergarten.PDF
5