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.

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

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.

 

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.

 

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of