Please finish the codes in Graph.h class. #################### Vertex.h : #ifnde
ID: 3779344 • Letter: P
Question
Please finish the codes in Graph.h class.
#################### Vertex.h :
#ifndef VERTEX_H
#define VERTEX_H
#include <string>
#include <queue>
#include <unordered_map>
using namespace std;
class Vertex
{
private:
int _id;
static int _id_counter;
unordered_map<Vertex *, int> _edges;
//cheater method for tracking path weight
int _path_weight = 0;
public:
Vertex()
{
_id_counter++;
_id = _id_counter;
}
Vertex(int id)
{
if (id >= _id_counter)
{
_id_counter = id + 1;
}
_id = id;
}
int getPathWeight() const
{
return _path_weight;
}
void setPathWeight(int weight)
{
_path_weight = weight;
}
int getId() const
{
return _id;
}
void addEdge(Vertex *vertex, int weight)
{
_edges[vertex] = weight;
}
int getEdgeWeight(Vertex *edge)
{
return _edges[edge];
}
unordered_map<Vertex *, int> &getEdges()
{
return _edges;
}
void removeEdge(Vertex *vertex)
{
_edges.erase(vertex);
}
};
int operator==(const Vertex &lhs, const Vertex &rhs)
{
return lhs.getId() == rhs.getId();
}
bool operator<(const Vertex &lhs, const Vertex &rhs)
{
return lhs < rhs;
}
bool operator>(const Vertex &lhs, const Vertex &rhs)
{
return lhs > rhs;
}
class PathWeightComparer
{
public:
bool operator()(const Vertex lhs, const Vertex rhs)
{
return (lhs.getPathWeight() > rhs.getPathWeight());
}
};
//hashing algorithm must exist in STD namespace
namespace std {
template <>
struct hash<Vertex>
{
//provide a hash (convert grocery item into integer)
std::size_t operator()(const Vertex& item) const
{
size_t hash_val = 0;
//to hash INTs using the STL
hash<int> int_hash{};
//define hashing algorithm. Ours is pretty easy...
hash_val = int_hash(item.getId());
//add others as necessary
return hash_val;
}
};
}
int Vertex::_id_counter = 0;
#endif
#################### Graph.h :
#ifndef GRAPH_H
#define GRAPH_H
#include <unordered_map>
#include <queue>
#include <functional>
#include "Vertex.h"
using namespace std;
class Graph
{
unordered_map<int, Vertex> _vertices;
public:
void addVertex(Vertex vertex)
{
_vertices[vertex.getId()] = vertex;
}
//MA #12 TODO: IMPLEMENT!
unordered_map<Vertex, int> computeShortestPath(Vertex *start)
{
//holds known distances
unordered_map<Vertex, int> distances;
//underlying heap
priority_queue<Vertex, vector<Vertex>, PathWeightComparer> dijkstra_queue{};
//reset start's path weight
start->setPathWeight(0);
//make sure that the starting vertex is in the graph
//push on starting vertex
//while queue not empty
//Top of heap not known (in distances)?
//make known
//push on outgoing edges
return distances;
}
};
#endif
######################### main.cpp
#include <cstdlib>
#include <iostream>
#include <unordered_map>
#include <vector>
#include "Graph.h"
#include "Vertex.h"
using namespace std;
void graphTest()
{
//populate graph
Graph graph{};
vector<Vertex> vertices{};
//generate vertices
for (int i = 0; i < 4; i++)
{
vertices.push_back(Vertex{});
}
/*
Graph: 0 -> 1 (weight 4)
0 -> 3 (weight 10)
1 -> 2 (weight 4)
1 -> 3 (weight 8)
2 -> 3 (weight 15)
*/
vertices[0].addEdge(&vertices[1], 4);
vertices[0].addEdge(&vertices[3], 20);
vertices[1].addEdge(&vertices[2], 4);
vertices[1].addEdge(&vertices[3], 8);
vertices[2].addEdge(&vertices[3], 15);
//add vertices to graph
for (auto vertex : vertices)
{
graph.addVertex(vertex);
}
unordered_map<Vertex, int> distances = graph.computeShortestPath(&vertices[0]);
cout << "Distance from 0 to 0: " << distances[vertices[0]] << " (expected: 0)" << endl;
cout << "Distance from 0 to 1: " << distances[vertices[1]] << " (expected: 4)" << endl;
cout << "Distance from 0 to 2: " << distances[vertices[2]] << " (expected: 8)" << endl;
cout << "Distance from 0 to 3: " << distances[vertices[3]] << " (expected: 12)" << endl;
}
int main(int argc, char* argv[])
{
graphTest();
}
Explanation / Answer
Graph.h
// Includes
#include "Graph.h"
// Overloaders
int operator==(const vertex &lhs, const vertex &rhs)
{
return lhs.get_id() == rhs.get_id();
}
bool operator<(const vertex &lhs, const vertex &rhs)
{
return lhs.get_id() < rhs.get_id();
}
bool operator>(const vertex &lhs, const vertex &rhs)
{
return lhs.get_id() > rhs.get_id();
}
// Constructors
graph::graph()
{
//_vertices = empty!
}
graph::graph(unordered_map<int, vertex*> new_vertices)
{
_vertices = new_vertices;
}
// Copy Consturctor
// Destructor
// Getters
unordered_map<int, vertex*> graph::get_vertices() const
{
return _vertices;
}
// Setters
void graph::set_vertices(unordered_map<int, vertex*> new_vertices)
{
_vertices = new_vertices;
}
// Methods
unordered_map<vertex*, path> graph::computeShortestPath(vertex* start , int starting_vertex, int ending_vertex)
{
//holds known distances
unordered_map<vertex*, path> paths;
//underlying heap
priority_queue<path, vector<path>, PathWeightComparer> dijkstra_queue{};
path temp;
//reset start's path weight
start->set_path_weight(0);
temp.push_vertex(start);
//make sure that the starting vertex is in the graph
if (_vertices.find(start->get_id()) != _vertices.end())
{
//push on starting vertex
dijkstra_queue.push(temp);
//while queue not empty
while (dijkstra_queue.empty() == false)
{
//push on outgoing edges that haven't been discovered
path top = dijkstra_queue.top();
dijkstra_queue.pop();
//Top of heap not known (in distances)?
if (paths.find(top.get_vertices().top()) == paths.end())
{
paths[top.get_vertices().top()] = top;
//push on outgoing edges
for (auto item : top.get_vertices().top()->get_edges())
{
vertex *next = item.first;
//not known? add to heap
if (paths.find(next) == paths.end())
{
path next_path = top;
int current_path_weight = item.second * next->get_load_factor();
next_path.push_vertex(next);
next_path.set_distance_traveled(top.get_distance_traveled() + current_path_weight);
dijkstra_queue.push(next_path);
}
}
}
}
}
return paths;
}
Vertex.h
#ifndef VERTEX_H
#define VERTEX_H
#include <string>
#include <queue>
#include <unordered_map>
using namespace std;
class Vertex
{
private:
int _id;
static int _id_counter;
unordered_map<Vertex *, int> _edges;
//unordered_map<int, int> weight;
//cheater method for tracking path weight
int _path_weight = 0;
int loadfactor = 1;
public:
Vertex()
{
_id_counter++;
_id = _id_counter;
}
Vertex(int id)
{
if (id >= _id_counter)
{
_id_counter = id + 1;
}
_id = id;
}
int getPathWeight() const
{
return _path_weight;
}
void setPathWeight(int weight)
{
_path_weight = weight;
}
int getload() const
{
return loadfactor;
}
void setload(int weight)
{
loadfactor = weight;
}
void plusload()
{
loadfactor++;
}
void minusload()
{
loadfactor--;
}
int getId() const
{
return _id;
}
void setid(int id)
{
_id = id;
}
void addEdge(Vertex *vertex, int weight)
{
_edges[vertex] = weight;
}
int getEdgeWeight(Vertex *edge)
{
return _edges[edge];
}
unordered_map<Vertex *, int> &getEdges()
{
return _edges;
}
void removeEdge(Vertex *vertex)
{
_edges.erase(vertex);
}
};
int operator==(const Vertex &lhs, const Vertex &rhs)
{
return lhs.getId() == rhs.getId();
}
bool operator<(const Vertex &lhs, const Vertex &rhs)
{
return lhs.getId() < rhs.getId();
}
bool operator>(const Vertex &lhs, const Vertex &rhs)
{
return lhs.getId() > rhs.getId();
}
class PathWeightComparer
{
public:
bool operator()(const Vertex lhs, const Vertex rhs)
{
return (lhs.getPathWeight() > rhs.getPathWeight());
}
};
//hashing algorithm must exist in STD namespace
namespace std {
template <>
struct hash<Vertex>
{
//provide a hash (convert grocery item into integer)
std::size_t operator()(const Vertex& item) const
{
size_t hash_val = 0;
//to hash INTs using the STL
hash<int> int_hash{};
//define hashing algorithm. Ours is pretty easy...
hash_val = int_hash(item.getId());
//add others as necessary
return hash_val;
}
};
}
int Vertex::_id_counter = 0;
#endif
main.cpp
#include <cstdlib>
#include <iostream>
#include <unordered_map>
#include <vector>
#include "Graph.h"
#include "Vertex.h"
using namespace std;
void graphTest()
{
//populate graph
Graph graph{};
vector<Vertex> vertices{};
//generate vertices
for (int i = 0; i < 4; i++)
{
vertices.push_back(Vertex{});
}
/*
Graph: 0 -> 1 (weight 4)
0 -> 3 (weight 10)
1 -> 2 (weight 4)
1 -> 3 (weight 8)
2 -> 3 (weight 15)
*/
vertices[0].addEdge(&vertices[1], 4);
vertices[0].addEdge(&vertices[3], 20);
vertices[1].addEdge(&vertices[2], 4);
vertices[1].addEdge(&vertices[3], 8);
vertices[2].addEdge(&vertices[3], 15);
//add vertices to graph
for (auto vertex : vertices)
{
graph.addVertex(vertex);
}
unordered_map<Vertex, int> distances = graph.computeShortestPath(&vertices[0]);
cout << "Distance from 0 to 0: " << distances[vertices[0]] << " (expected: 0)" << endl;
cout << "Distance from 0 to 1: " << distances[vertices[1]] << " (expected: 4)" << endl;
cout << "Distance from 0 to 2: " << distances[vertices[2]] << " (expected: 8)" << endl;
cout << "Distance from 0 to 3: " << distances[vertices[3]] << " (expected: 12)" << endl;
}
int main(int argc, char* argv[])
{
graphTest();
}