#include #include #include "graph.h" #include "png/png.hpp" #include #include using namespace png; using namespace std;

typedef image Image;

double distance(const rgb_pixel &p1, const rgb_pixel &p2) { // ADD YOUR IMPLEMENTATION HERE return 0; }

void add_edges(Graph &graph, const Image& image, int threshold) { // ADD YOUR IMPLEMENTATION HERE }

// FILL IN THE BLANKS BELOW TO MAKE THE PROGRAM RUNNABLE! int main() { string filename; cout > filename; Image image(filename);

int threshold; cout > threshold;

// 1. DEFINE A Graph OBJECT. WHAT IS THE NUMBER OF VERTICES? // ________________________________

// 2. CALL THE add_edges() FUNCTION // ________________________________

int row, col; cout > row >> col; // 3. GET AND STORE ALL THE VERTICES RECHABLE FROM THE VERTEX // CORRESPONDING TO THE CELL AT THE GIVEN ROW AND COLUMN. // vector reachable = ________________________________

// For every reachable vertex for (int v : reachable) { // 4. COMPUTE AND STORE THE ROW & COLUMN OF v // row = __________________________ // col = __________________________

// change the color of the pixel to white. image[row][col] = rgb_pixel(255, 255, 255); }

cout

return 0; }

// code translated to C++ from https://algs4.cs.princeton.edu/24pq/IndexMinPQ.java.html

#include #include #include using namespace std;

template class MinPQ { public: MinPQ(int maxN); // maxN is the maximum number of elements in the PQ ~MinPQ();

bool isEmpty() const; // checks if no elements are currently in the PQ int size() const; // number of elements currently in the PQ

void insert(int i, T key); // Associates key with index i. int delMin(); // Removes a minimum key and returns its associated index. void remove(int i); // Remove the key associated with index i.

int minIndex() const; // Returns an index associated with a minimum key. T minKey() const; // Returns a minimum key.

bool contains(int i) const; // Is i an index on this priority queue? T keyOf(int i) const; // Returns the key associated with index i.

void changeKey(int i, T key); // Change the key associated with index i // to the specified value. void decreaseKey(int i, T key); // Decrease the key associated with index i // to the specified value. void increaseKey(int i, T key); // Increase the key associated with index i // to the specified value.

private: int maxN; // maximum number of elements on PQ int n; // number of elements on PQ int* pq; // binary heap using 1-based indexing int* qp; // inverse of pq - qp[pq[i]] = pq[qp[i]] = i T* keys; // keys[i] = priority of i

// Helper functions void validateIndex(int i) const; bool greater(int i, int j) const; void exch(int i, int j); void swim(int k); void sink(int k); };

template MinPQ::MinPQ(int maxN) { if (maxN maxN = maxN; n = 0;

keys = new T[maxN + 1]; pq = new int[maxN + 1]; qp = new int[maxN + 1]; for (int i = 0; i

template MinPQ::~MinPQ() { delete [] pq; delete [] qp; delete [] keys; }

template bool MinPQ::isEmpty() const { return n == 0; }

template int MinPQ::size() const { return n; }

// Is i an index on this priority queue? template bool MinPQ::contains(int i) const { validateIndex(i); return qp[i] != -1; }

// Associates key with index i. template void MinPQ::insert(int i, T key) { validateIndex(i); if (contains(i)) throw string("index is already in the priority queue"); n++; qp[i] = n; pq[n] = i; keys[i] = key; swim(n); }

// Returns an index associated with a minimum key. template int MinPQ::minIndex() const { if (n == 0) throw string("Priority queue underflow"); return pq[1]; }

// Returns a minimum key. template T MinPQ::minKey() const { if (n == 0) throw string("Priority queue underflow"); return keys[pq[1]]; }

// Removes a minimum key and returns its associated index. template int MinPQ::delMin() { if (n == 0) throw string("Priority queue underflow"); int min = pq[1]; exch(1, n--); sink(1); assert(min == pq[n+1]); qp[min] = -1; // delete pq[n+1] = -1; // not needed return min; }

// Returns the key associated with index i. template T MinPQ::keyOf(int i) const { validateIndex(i); if (!contains(i)) throw string("index is not in the priority queue"); else return keys[i]; }

// Change the key associated with index i to the specified value. template void MinPQ::changeKey(int i, T key) { validateIndex(i); if (!contains(i)) throw string("index is not in the priority queue"); keys[i] = key; swim(qp[i]); sink(qp[i]); }

// Decrease the key associated with index i to the specified value. template void MinPQ::decreaseKey(int i, T key) { validateIndex(i); if (!contains(i)) throw string("index is not in the priority queue"); if (keys[i] == key) throw string("Calling decreaseKey() with a key equal to the key in the priority queue"); if (keys[i] the key in the priority queue"); keys[i] = key; swim(qp[i]); }

// Increase the key associated with index i to the specified value. template void MinPQ::increaseKey(int i, T key) { validateIndex(i); if (!contains(i)) throw string("index is not in the priority queue"); if (keys[i] == key) throw string("Calling increaseKey() with a key equal to the key in the priority queue"); if (keys[i] > key) throw string("Calling increaseKey() with a key

// Remove the key associated with index i. template void MinPQ::remove(int i) { validateIndex(i); if (!contains(i)) throw string("index is not in the priority queue"); int index = qp[i]; exch(index, n--); swim(index); sink(index); qp[i] = -1; }

// throw an IllegalArgumentException if i is an invalid index template void MinPQ::validateIndex(int i) const { if (i = maxN) throw string("index >= capacity: " + i); }

template bool MinPQ::greater(int i, int j) const { return keys[pq[i]] > keys[pq[j]]; }

template void MinPQ::exch(int i, int j) { int swap = pq[i]; pq[i] = pq[j]; pq[j] = swap; qp[pq[i]] = i; qp[pq[j]] = j; }

template void MinPQ::swim(int k) { while (k > 1 && greater(k/2, k)) { exch(k, k/2); k = k/2; } }

template void MinPQ::sink(int k) { while (2*k Exercise 2: Flood Fill Overview Most image processing applications have a magic wand tool that allows selecting a connected part of the image that has almost the same color. The user can then recolor that part, remove it or perform other transformations. PSUT_Logo_Stacked_RGB copy.png 202.7% GOTOVO In this exercise, you will use your implementation of graph.h to implement an operation similar to the magic wand tool and use it to select parts of an image and recolor it. Images as Graphs An image is a 2D matrix of pixels, where each pixel stores a color. Colors are typically stored as three components: red, green and blue (RGB), where each component has a value between o (nothing) and 255 (full color). For example, (0, 0, 0) means no red, no green and no blue, which is black. White is (255, 255, 255) and (128, 0, 128) is purple. See this link for more examples. We could think of an image as an undirected graph, where each pixel (or cell in the 2D array) is a node and edges are between adjacent pixels (note how the vertices are numbered). 1 2 8 10 The idea in this exercise is to construct the graph such that an edge is added between two adjacent pixels only if their colors are within a certain threshold from each other. For example, the image below can be represented with a graph that has three connected components based on the colors of its pixels. 2 3 Image Library We will use the png++ library in this exercise (and in the following exercises), which allows reading, writing and manipulating PNG files in C++. The following is a very simple example program that shows how to load a PNG image named "test.png", print the RGB components of the first pixel and then change it to black. C++ o 1 #include 2 #include "png/png.hpp" 3 using namespace std; 4 using namespace png; 5 6 typedef image Image; 7 8 int main() { 9 Image image ("test.png"); 10 11 Il print the image dimensions 12 cout 2 #include costream> 3 #include "graph.h" 4 #include "png/png.hpp" 5 #include 6 #include