I am very picky on answers, THIS IS MY 6TH TIME ASKING THE SAME QUESTION! GIVE A
ID: 667193 • Letter: I
Question
I am very picky on answers, THIS IS MY 6TH TIME ASKING THE SAME QUESTION! GIVE A UNIQUE ANSWER AND PLEASE BE THOROUGH IN YOUR ANSWERS! The Project is to implement a Union-Find Data Structure and Kruskal's algorithm on a minimum spanning tree. You must finish implementing the methods already given. NO NEW METHODS ARE TO BE IMPLEMENTED! Please include comments so that I can follow the code and thought process.
PLEASE DON'T FORGET TO EDIT THE KRUSKAL METHOD IN MAIN.CPP.
Gina is an astronomer and only has a limited amount of time using the Hubble telescope to take the pictures she needs. She needs to point the telescope at n different points in the sky, before returning it to the starting position. To solve this problem, she wants to plot the points she wants to take a picture of and she needs your help to find the best order to photograph these points in. Unfortunately, you have to explain to here that there is no known polynomial time algorithm for solving this problem. Instead you recommend approximatting the answer using a depth first traversal of a minimum spanning tree. Gina was able to write the depth first search and some code to display the tour, but she needs you to write the code to compute a minimum spanning tree of the points.
To find a minimum spanning tree, we will be using Kruskal's algorithm. The first step of Kruskal's algorithm is to sort the edges by their cost. For this project instead of writing our own sorting function we are going to use C++'s built in sort. A fact you might find useful is that by default pairs in C++ are sorted lexicographically e.g. if you create a pair where the first entry is an edge weight and the second entry is the edge, then the sort will sort the edges by their edge weight. So if you have a vector of std::pair<int,std::pair<int,int>>, std::sort will sort them by the first int. You will also need to write a union find data structure. You are required to do unioning by rank and to do path compression.
Gina has provided the graph of the n points in the form of an unordered_map<int,unordered_map<int,int>>. Each vertex has a label from 0 to n-1 and maps to a map of its neighbors where the key is the neighboring vertex and the value is the cost of that edge. So for example, if graph.at(i).at(j) = k (see the notes for why we use .at()), then there is an edge from vertex i to vertex j of cost k. Because she is only doing a depth first search of the tree you return and does not care about the edge weights, she expects you to return an unordered_map<int,unordered_set> where if vertex i has vertex j as a neighbor than j is in tree[i].
The starter code for this project consists of several files: main.cpp, union_find.hpp, graph_view.hpp, and graph_view.cpp. The two graph_view files contain code to handle the rendering of our TSP tour and minimum spanning tree. You should not need to edit them. The main.cpp file contains the code that will compute the tour and spanning tree. Everything in main.cpp is implemented except for Kruskal's algorithm. The union_find.hpp file contains the method stubs for the union find data structure we discussed in class.
Notes:
Because the graph is provided as a const reference, you cannot use the [] operator which would return a reference the corresponding value. Instead use .at() which returns a const reference.
When adding edges to your tree, remember that the tree is undirected, so you need to add edges in both directions.
Make sure you use union by rank and path compression in your union find implementation.
Don't forget to run the update.sh script. You can try running the code when you first download it to check. The window should look the same just with no edges drawn and an error message should be outputted in the console.
You are allowed to use any of the STL data structures you find helpful.
Code:
union_find.hpp
// This file contains the method stubs for a union find
// data structure. You are responsible for implementing
// these stubs.
//
#ifndef __UNION_FIND_HPP__
#define __UNION_FIND_HPP__
#include <unordered_map>
template <typename T>
class UnionFind
{
public:
UnionFind<T>();
void add_set(T x);
T find(T x);
void union_sets(T x, T y);
private:
// You should only need these two maps for
// your implementation. However you are
// free to add new private members.
std::unordered_map<T,T> parent;
std::unordered_map<T,int> rank;
};
template <typename T>
UnionFind<T>::UnionFind() : parent() , rank()
{}
// Adds a new set containing the element x
template <typename T>
void UnionFind<T>::add_set(T x)
{
//TODO: implement this method
}
// Finds a representative element from x's set
template <typename T>
T UnionFind<T>::find(T x)
{
//TODO: implement this method
}
// Unions the two sets that contain x and y
template <typename T>
void UnionFind<T>::union_sets(T x, T y)
{
}
#endif //__UNION_FIND_HPP__
main.cpp
// This file contains code for computing an approximation of the
// optimal travelling salesperson tour. You are responsible for
// implementing Kruskal's algorithm in this file.
//
#include "graph_view.hpp"
#include "union_find.hpp"
#include <iostream>
#include <random>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
//Computes a minimum spanning tree of graph using Kruskal's algorithm
std::unordered_map<int,std::unordered_set<int>> kruskal(std::unordered_map<int,std::unordered_map<int,int>> graph, int n)
{
//TODO: implement this method
// This small piece of code is so things will still run, if you haven't implemented this method
std::unordered_map<int,std::unordered_set<int>> tree;
return tree;
}
//A recursive depth first search that adds the vertices
//to the vector order in the order they are encountered
void dfs(const std::unordered_map<int,std::unordered_set<int>>& graph,
std::vector<int>& order, std::unordered_set<int>& visited, int v) {
visited.insert(v);
order.push_back(v);
for(int neighbor : graph.at(v)) {
if (visited.find(neighbor) == visited.end())
dfs(graph, order, visited, neighbor);
}
}
//Fills the vector tour with the vertices in graph in the order
//they are traversed by a depth first search
void build_tour(const std::unordered_map<int,std::unordered_set<int>>& graph, std::vector<int>& tour) {
if (graph.size() == 0)
return;
std::unordered_set<int> visited;
dfs(graph,tour,visited,0);
}
//Computes a tour of the vertices of graph using the
//Christofides algorithm as we discussed it in class
//(The actual Christfides algorithm is a little fancier)
void christofides(const std::unordered_map<int,std::unordered_map<int,int>>& graph, std::vector<int>& tour, std::unordered_map<int,std::unordered_set<int>>& mst, int n)
{
mst = kruskal(graph, n);
build_tour(mst,tour);
}
int main(int argc, char* args[])
{
std::string number_points;
std::cout<<"Please enter the number of points to tour: ";
std::cin >> number_points;
int n = std::stoi(number_points);
//Generate n random points to find a tour of
std::random_device rd;
std::default_random_engine eng(rd());
std::uniform_real_distribution<> dis(0,1);
std::vector<std::pair<int,int>> points;
for (int i = 0; i < n; i++) {
points.push_back(std::make_pair((int)WINDOW_WIDTH*dis(eng),(int)WINDOW_HEIGHT*dis(eng)));
}
//Build the graph on these points
std::unordered_map<int,std::unordered_map<int,int>> graph;
for (int i = 0; i < n; i++)
graph[i] = std::unordered_map<int,int>();
for (int i = 0; i < n; i++) {
int x1 = points[i].first;
int y1 = points[i].second;
for (int j = i+1; j < n; j++) {
int x2 = points[j].first;
int y2 = points[j].second;
//Compute the distance between the two points
double distance = hypot(x1-x2,y1-y2);
graph[i][j] = distance;
graph[j][i] = distance;
}
}
//Compute the minimum spanning tree and approximate tour
std::vector<int> tour;
std::unordered_map<int,std::unordered_set<int>> mst;
christofides(graph,tour,mst,n);
//The processing is now done and we can start the rendering
GraphView v(points,tour,mst,n);
std::cout<<"Press the spacebar to toggle between the mst or the tsp"<<std::endl;
bool quit = false;
v.render();
while (!quit) {
DrawEvent de = v.get_event();
switch (de) {
case DrawEvent::Quit: quit = true; break;
case DrawEvent::Switch:
v.switch_draw();
v.render();
break;
default: break;
}
}
return 0;
}
GRAPH_VIEW.HPP & GRAPH_VIEW.CPP DO NOT NEED TO BE EDITTED
graph_view.cpp
// This file implements the graph view. It handles the rendering
// of the tree, tour, and vertices. You do not need to edit this file.
//
#include "graph_view.hpp"
#include "SDL2/SDL2_gfxPrimitives.h"
#include <iostream>
GraphView::GraphView(std::vector<std::pair<int,int>> p, std::vector<int> tsp, std::unordered_map<int,std::unordered_set<int>> mst, int num_verts)
{
points = p;
tour = tsp;
tree = mst;
n = num_verts;
d = Draw::Tour;
//Open a window with SDL
std::cout<<"----------Ignore these warnings----------"<<std::endl;
SDL_Init(SDL_INIT_EVERYTHING);
std::cout<<"----------Ignore these warnings----------"<<std::endl;
screen = SDL_CreateWindow("Project 5", SDL_WINDOWPOS_CENTERED,
SDL_WINDOWPOS_CENTERED, WINDOW_WIDTH, WINDOW_HEIGHT, SDL_WINDOW_RESIZABLE);
renderer = SDL_CreateRenderer(screen, -1, SDL_RENDERER_ACCELERATED);
}
GraphView::~GraphView()
{
SDL_DestroyRenderer(renderer);
SDL_DestroyWindow(screen);
SDL_Quit();
}
DrawEvent GraphView::get_event()
{
SDL_Event e;
DrawEvent de = DrawEvent::Nothing;
while (SDL_PollEvent(&e) != 0) {
switch (e.type) {
case SDL_QUIT:
de = DrawEvent::Quit; break;
case SDL_KEYDOWN:
if (e.key.keysym.sym == SDLK_SPACE) {
de = DrawEvent::Switch;
}
break;
default:
break;
}
}
return de;
}
void GraphView::switch_draw()
{
if (d == Draw::Tour)
d = Draw::Tree;
else
d = Draw::Tour;
}
void GraphView::render() {
//Clear the window to a white screen
SDL_SetRenderDrawColor(renderer,255,255,255,255);
SDL_RenderClear(renderer);
if (d == Draw::Tour)
draw_tour();
else
draw_tree();
//Draw the vertices on top of the edges
draw_verts();
//Tell the screen to display our tour
SDL_RenderPresent(renderer);
}
void GraphView::draw_edge(int v1, int v2, unsigned int color)
{
int x1 = points[v1].first;
int y1 = points[v1].second;
int x2 = points[v2].first;
int y2 = points[v2].second;
lineColor(renderer, x1, y1, x2, y2, color);
}
void GraphView::draw_tour() {
if(tour.size() != n)
{
std::cout<<"Drawing error: the tour does not visit n vertices"<<std::endl;
return;
}
//Draw the edges of the tour
for (int i = 0; i < n-1; i++) {
draw_edge(tour[i],tour[i+1],TSP_COLOR);
}
//Don't forget the final edge
draw_edge(tour[0],tour[n-1],TSP_COLOR);
}
void GraphView::draw_tree() {
if(tree.size() != n)
{
std::cout<<"Drawing error: the tree does not have n vertices"<<std::endl;
return;
}
//Draw the edges of the tree
for (int i = 0; i < n; i++) {
for (int neighbor : tree.at(i)) {
draw_edge(i,neighbor,MST_COLOR);
}
}
}
void GraphView::draw_verts() {
SDL_SetRenderDrawColor(renderer,0,0,0,255);
for (int i = 0; i < n; i++)
filledCircleColor(renderer, points[i].first, points[i].second, 3, VERTEX_COLOR);
}
graph_view.hpp
// This file contains the headers for the graph view. The
// graph view handles all of the rendering. You do not need
// to edit this file.
//
#ifndef __GRAPH_VIEW_HPP__
#define __GRAPH_VIEW_HPP__
#include "SDL2/SDL.h"
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define WINDOW_WIDTH 600
#define WINDOW_HEIGHT 600
#define TSP_COLOR 0xff0000ff
#define MST_COLOR 0xffff0000
#define VERTEX_COLOR 0xff000000
enum class Draw { Tree, Tour };
enum class DrawEvent { Nothing, Switch, Quit };
class GraphView
{
public:
GraphView(std::vector<std::pair<int,int>> points, std::vector<int> tour, std::unordered_map<int,std::unordered_set<int>> mst, int num_verts);
~GraphView();
// Overwrites the copy constructor and assignment operator
// Using these would cause errors
GraphView(const GraphView&) = delete;
GraphView& operator=(const GraphView&) = delete;
DrawEvent get_event();
// Switches from rendering the tree and the tour
void switch_draw();
// Renders the current scene
void render();
private:
int n;
std::vector<std::pair<int,int>> points;
std::vector<int> tour;
std::unordered_map<int,std::unordered_set<int>> tree;
//Keeps track of whether to draw the tree or the tour
Draw d;
//SDL objects for rendering
SDL_Renderer* renderer;
SDL_Window* screen;
// Private methods for rendering
void draw_edge(int v1, int v2, unsigned int color);
void draw_tree();
void draw_tour();
void draw_verts();
};
#endif //__GRAPH_VIEW_HPP__
I am very picky on answers, PLEASE BE THOROUGH IN YOUR ANSWERS! The Project is to implement a Union-Find Data Structure and Kruskal's algorithm. You must finish implementing the methods already given. NO NEW METHODS ARE TO BE IMPLEMENTED! Please include comments so that I can follow the code and thought process.
Explanation / Answer
#ifndef __UNION_FIND_HPP__
#define __UNION_FIND_HPP__
#include <unordered_map>
template <typename T>
class UnionFind
{
public:
UnionFind<T>();
void add_set(T x);
T find(T x);
void union_sets(T x, T y);
private:
// You should only need these two maps for
// your implementation. However you are
// free to add new private members.
std::unordered_map<T,T> parent;
std::unordered_map<T,int> rank;
};
template <typename T>
UnionFind<T>::UnionFind() : parent() , rank()
{}
// Adds a new set containing the element x
template <typename T>
void UnionFind<T>::add_set(T x)
{
T.parent = x;
}
// Finds a representative element from x's set
template <typename T>
T UnionFind<T>::find(T x)
{
boolean result = false;
for(int i=0;i<T.length;i++){
if(T.parent == x){
result = true;
break;
}
}
return result;
}
// Unions the two sets that contain x and y
template <typename T>
void UnionFind<T>::union_sets(T x, T y)
{
template <typename T> new ;
new.parent = x; //it will save as parent
new.parent = y; //it will add y as parent
}
---------------------------------------------------------
main.cpp
#include "graph_view.hpp"
#include "union_find.hpp"
#include <iostream>
#include <random>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
//Computes a minimum spanning tree of graph using Kruskal's algorithm
std::unordered_map<int,std::unordered_set<int>> kruskal(std::unordered_map<int,std::unordered_map<int,int>> graph, int n)
{
std::pair<int,std::pair<int,int>> vector;
// This small piece of code is so things will still run, if you haven't implemented this method
std::unordered_map<int,std::unordered_set<int>> tree;
return tree;
}
//A recursive depth first search that adds the vertices
//to the vector order in the order they are encountered
void dfs(const std::unordered_map<int,std::unordered_set<int>>& graph,
std::vector<int>& order, std::unordered_set<int>& visited, int v) {
visited.insert(v);
order.push_back(v);
for(int neighbor : graph.at(v)) {
if (visited.find(neighbor) == visited.end())
dfs(graph, order, visited, neighbor);
}
}
//Fills the vector tour with the vertices in graph in the order
//they are traversed by a depth first search
void build_tour(const std::unordered_map<int,std::unordered_set<int>>& graph, std::vector<int>& tour) {
if (graph.size() == 0)
return;
std::unordered_set<int> visited;
dfs(graph,tour,visited,0);
}
void christofides(const std::unordered_map<int,std::unordered_map<int,int>>& graph, std::vector<int>& tour, std::unordered_map<int,std::unordered_set<int>>& mst, int n)
{
mst = kruskal(graph, n);
build_tour(mst,tour);
}
int main(int argc, char* args[])
{
std::string number_points;
std::cout<<"Please enter the number of points to tour: ";
std::cin >> number_points;
int n = std::stoi(number_points);
//Generate n random points to find a tour of
std::random_device rd;
std::default_random_engine eng(rd());
std::uniform_real_distribution<> dis(0,1);
std::vector<std::pair<int,int>> points;
for (int i = 0; i < n; i++) {
points.push_back(std::make_pair((int)WINDOW_WIDTH*dis(eng),(int)WINDOW_HEIGHT*dis(eng)));
}
//Build the graph on these points
std::unordered_map<int,std::unordered_map<int,int>> graph;
for (int i = 0; i < n; i++)
graph[i] = std::unordered_map<int,int>();
for (int i = 0; i < n; i++) {
int x1 = points[i].first;
int y1 = points[i].second;
for (int j = i+1; j < n; j++) {
int x2 = points[j].first;
int y2 = points[j].second;
//Compute the distance between the two points
double distance = hypot(x1-x2,y1-y2);
graph[i][j] = distance;
graph[j][i] = distance;
}
}
//Compute the minimum spanning tree and approximate tour
std::vector<int> tour;
std::unordered_map<int,std::unordered_set<int>> mst;
christofides(graph,tour,mst,n);
//The processing is now done and we can start the rendering
GraphView v(points,tour,mst,n);
std::cout<<"Press the spacebar to toggle between the mst or the tsp"<<std::endl;
bool quit = false;
v.render();
while (!quit) {
DrawEvent de = v.get_event();
switch (de) {
case DrawEvent::Quit: quit = true; break;
case DrawEvent::Switch:
v.switch_draw();
v.render();
break;
default: break;
}
}
return 0;
}
GRAPH_VIEW.HPP & GRAPH_VIEW.CPP DO NOT NEED TO BE EDITTED
graph_view.cpp
// This file implements the graph view. It handles the rendering
// of the tree, tour, and vertices. You do not need to edit this file.
#include "graph_view.hpp"
#include "SDL2/SDL2_gfxPrimitives.h"
#include <iostream>
GraphView::GraphView(std::vector<std::pair<int,int>> p, std::vector<int> tsp, std::unordered_map<int,std::unordered_set<int>> mst, int num_verts)
{
points = p;
tour = tsp;
tree = mst;
n = num_verts;
d = Draw::Tour;
//Open a window with SDL
std::cout<<"----------Ignore these warnings----------"<<std::endl;
SDL_Init(SDL_INIT_EVERYTHING);
std::cout<<"----------Ignore these warnings----------"<<std::endl;
screen = SDL_CreateWindow("Project 5", SDL_WINDOWPOS_CENTERED,
SDL_WINDOWPOS_CENTERED, WINDOW_WIDTH, WINDOW_HEIGHT, SDL_WINDOW_RESIZABLE);
renderer = SDL_CreateRenderer(screen, -1, SDL_RENDERER_ACCELERATED);
}
GraphView::~GraphView()
{
SDL_DestroyRenderer(renderer);
SDL_DestroyWindow(screen);
SDL_Quit();
}
DrawEvent GraphView::get_event()
{
SDL_Event e;
DrawEvent de = DrawEvent::Nothing;
while (SDL_PollEvent(&e) != 0) {
switch (e.type) {
case SDL_QUIT:
de = DrawEvent::Quit; break;
case SDL_KEYDOWN:
if (e.key.keysym.sym == SDLK_SPACE) {
de = DrawEvent::Switch;
}
break;
default:
break;
}
}
return de;
}
void GraphView::switch_draw()
{
if (d == Draw::Tour)
d = Draw::Tree;
else
d = Draw::Tour;
}
void GraphView::render() {
//Clear the window to a white screen
SDL_SetRenderDrawColor(renderer,255,255,255,255);
SDL_RenderClear(renderer);
if (d == Draw::Tour)
draw_tour();
else
draw_tree();
//Draw the vertices on top of the edges
draw_verts();
//Tell the screen to display our tour
SDL_RenderPresent(renderer);
}
void GraphView::draw_edge(int v1, int v2, unsigned int color)
{
int x1 = points[v1].first;
int y1 = points[v1].second;
int x2 = points[v2].first;
int y2 = points[v2].second;
lineColor(renderer, x1, y1, x2, y2, color);
}
void GraphView::draw_tour() {
if(tour.size() != n)
{
std::cout<<"Drawing error: the tour does not visit n vertices"<<std::endl;
return;
}
//Draw the edges of the tour
for (int i = 0; i < n-1; i++) {
draw_edge(tour[i],tour[i+1],TSP_COLOR);
}
//Don't forget the final edge
draw_edge(tour[0],tour[n-1],TSP_COLOR);
}
void GraphView::draw_tree() {
if(tree.size() != n)
{
std::cout<<"Drawing error: the tree does not have n vertices"<<std::endl;
return;
}
//Draw the edges of the tree
for (int i = 0; i < n; i++) {
for (int neighbor : tree.at(i)) {
draw_edge(i,neighbor,MST_COLOR);
}
}
}
void GraphView::draw_verts() {
SDL_SetRenderDrawColor(renderer,0,0,0,255);
for (int i = 0; i < n; i++)
filledCircleColor(renderer, points[i].first, points[i].second, 3, VERTEX_COLOR);
}
graph_view.hpp
// This file contains the headers for the graph view. The
// graph view handles all of the rendering. You do not need
// to edit this file.
//
#ifndef __GRAPH_VIEW_HPP__
#define __GRAPH_VIEW_HPP__
#include "SDL2/SDL.h"
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define WINDOW_WIDTH 600
#define WINDOW_HEIGHT 600
#define TSP_COLOR 0xff0000ff
#define MST_COLOR 0xffff0000
#define VERTEX_COLOR 0xff000000
enum class Draw { Tree, Tour };
enum class DrawEvent { Nothing, Switch, Quit };
class GraphView
{
public:
GraphView(std::vector<std::pair<int,int>> points, std::vector<int> tour, std::unordered_map<int,std::unordered_set<int>> mst, int num_verts);
~GraphView();
// Overwrites the copy constructor and assignment operator
// Using these would cause errors
GraphView(const GraphView&) = delete;
GraphView& operator=(const GraphView&) = delete;
DrawEvent get_event();
// Switches from rendering the tree and the tour
void switch_draw();
// Renders the current scene
void render();
private:
int n;
std::vector<std::pair<int,int>> points;
std::vector<int> tour;
std::unordered_map<int,std::unordered_set<int>> tree;
//Keeps track of whether to draw the tree or the tour
Draw d;
//SDL objects for rendering
SDL_Renderer* renderer;
SDL_Window* screen;
// Private methods for rendering
void draw_edge(int v1, int v2, unsigned int color);
void draw_tree();
void draw_tour();
void draw_verts();
};
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.