C++ Data Structures and Algorithms Here is the general project instructions: htt
ID: 3818512 • Letter: C
Question
C++ Data Structures and Algorithms
Here is the general project instructions: https://ece.uwaterloo.ca/~dwharder/aads/Projects/5/
Here are the source files: https://ece.uwaterloo.ca/~dwharder/aads/Projects/5/Kruskal/src/
Please take your time to answer the question in full!!
Answer this question after reading the project instructions in the link
In this sub-project, you will implement one class:
A weighted graph: Weighted_graph
This is a graph that has positive real weights for edges (double). Note that there are no templates used in this project.
I appreciate your help.
Explanation / Answer
There are 3 new files to be included.
CODE:
Set.h
#ifndef SET_CLASS
#define SET_CLASS
class set{
private:
int * s;
int size;
public:
set(){
};
void setsize(int n){
size = n;
s = new int[size];
}
int find(int x) const{
if(s[x] < 0 )
return x;
else
return s[x] = find(s[x]);
};
void unite(int x1, int x2){
if(s[x1] < s[x2])
s[x1] = x2;
else{
if(s[x1] == s[x2])
--s[x1];
s[x2] = x1;
}
};
~set(){
delete [] s;
};
};
#endif
-------------------------------------------------
Heap.h
#ifndef heap_class
#define heap_class
#include <iostream>
using namespace std;
template <class t>
class Heap{
t * array;
int size;
int arrsize;
public:
Heap(){
};
void setsize(int n){
size = 0;
arrsize = n;
array = new t [arrsize];
};
void insert(t value){
if(size == arrsize){
t * oldarray = array;
array = new t[arrsize * 2];
for(int i = 0; i < size + 1;i++){
arrsize = arrsize * 2;
array[i] = oldarray[i];
//cout << array[i];
}
}
int hole = ++ size;
t copy = value;
array[0] = std::move(copy);
for(; value < array[hole / 2]; hole /= 2)
array[hole] = std::move(array[hole / 2]);
array[hole] = std::move(array[0]);
};
t deletemin(){
t returnvalue;
//if(size == 0)
//throw exception();
returnvalue = array[1];
array[1] = std::move(array[size --]);
goDown(1);
return returnvalue;
};
t & find(t value){
// linear search for now
for(int i = 1; i < size; i ++){
if(array[i] == value)
return array[i];
}
};
bool contains(t value){
// linear search for now
for(int i = 1; i < size; i ++){
if(array[i] == value)
return true;
}
return false;
};
void goDown(int hole){
int child;
t tmp = std::move(array[hole]);
for(;hole * 2 <= size; hole = child){
child = hole * 2;
if(child != size && array[child + 1] < array[child])
++child;
if(array[child] < tmp)
array[hole] = std::move(array[child]);
else
break;
}
array[hole] = std::move(tmp);
};
~Heap(){
delete [] array;
};
};
#endif
------------------------------------------------------
Edge.h
#ifndef edge_class
#define edge_class
struct edge{
int v1;
int v2;
double weight;
bool operator < (edge & rhs){
if(weight < rhs.weight)
return true;
else
return false;
};
bool operator > (edge & rhs){
if(weight > rhs.weight)
return true;
else
return false;
};
bool operator == (edge & rhs){
if(v1 == rhs.v1 && v2 == rhs.v2)
return true;
else if(v1 == rhs.v2 && v2 == rhs.v1)
return true;
else
return false;
};
edge & operator = (edge & rhs){
v1 = rhs.v1;
v2 = rhs.v2;
weight = rhs.weight;
return *this;
};
};
#endif
--------------------------------------------------------------
weightedgraph.h
#ifndef WEIGHTED_GRAPH_H
#define WEIGHTED_GRAPH_H
#ifndef nullptr
#define nullptr 0
#endif
#include <iostream>
#include <limits>
#include "Set.h"
#include "Heap.h"
#include "Edge.h"
//#include "Exception.h"
class Weighted_graph {
private:
static const double INF;
int size;
set s;
Heap<edge> h;
// Do not implement these functions!
// By making these private and not implementing them, any attempt
// to make copies or assignments will result in errors
Weighted_graph( Weighted_graph const & );
Weighted_graph &operator=( Weighted_graph );
// your choice
public:
Weighted_graph( int = 10 );
~Weighted_graph();
int degree( int ) const;
int edge_count() const;
std::pair<double, int> minimum_spanning_tree();
bool insert_edge( int, int, double );
bool erase_edge( int, int );
void clear_edges();
// Friends
friend std::ostream &operator<<( std::ostream &, Weighted_graph const & );
};
const double Weighted_graph::INF = std::numeric_limits<double>::infinity();
Weighted_graph::Weighted_graph( int n ) {
size = n;
h.setsize(n*n);
s.setsize(n);
}
Weighted_graph::~Weighted_graph() {
}
int Weighted_graph::degree( int n ) const{
return 0;
}
int Weighted_graph::edge_count() const{
return 0;
}
bool Weighted_graph::insert_edge( int i, int j, double d ) {
edge temp = {i,j,d};
if(i == j)
return false;
if(h.contains(temp))
h.find(temp) = temp;
else
h.insert(temp);
return true;
}
std::pair<double, int> Weighted_graph::minimum_spanning_tree(){
int weight = 0;
int edges = 0;
while(edges < size - 1){
edge e = h.deletemin();
if(s.find(e.v1) != s.find(e.v2)){
s.unite(e.v1, e.v2);
weight += e.weight;
edges++;
}
}
cout << weight;
cout << endl << edges;
return std::pair<double, int>( weight, edges );
};
std::ostream &operator<<( std::ostream &out, Weighted_graph const &graph ) {
// Your implementation
return out;
}
#endif
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.