CODE IN C++ 1. Implement a directed and weighted labeled graph. With std::vector> edges. The graph s

[answerhappygod]

CODE IN C++
1. Implement a directed and weighted labeled graph. With
std::vector<std::vector<double>> edges. The graph
should have all the functionalities similar to those of the
unweighted labeled graph. Additionally, the graph class should have
a function to print the entire edges table. (This is different from
the print() with depth-first and with breadth-first.)
2. Add two functions to the class in part 1 to implement
Dijkstra's shortest-distance and shortest-path algorithms.
CODE PROVIDED IN CLASS
template <typename T> class graph {
public:
graph();
void addVertex(const T& label);
void removeVertex(const T& label);
void addEdge(const T& source, const T& target, bool
directed = false);
void removeEdge(const T& source, const T& target, bool
directed = false);
private:
std::vector<T> labels;
std::vector<std::set<unsigned int>> edges;
unsigned int iVertex(const T& label);
};
template <typename T>
graph<T>::graph() {
labels = std::vector<T>();
edges = std::vector<std::set<unsigned int>>();
}
template <typename T>
unsigned int graph<T>::iVertex(const T& label) {
for (unsigned int i = 0; i < labels.size(); i++) {
if (labels == label)
return i;
}
return UINT32_MAX;
}
template <typename T>
void graph<T>::addVertex(const T& label) {
if (std::find(labels.begin(), labels.end(), label) == labels.end())
{
labels.push_back(label);
edges.push_back(std::set<unsigned int>());
}
}
template <typename T>
void graph<T>::addEdge(const T& source, const T&
target, bool directed) {
unsigned int iSource = iVertex(source), iTarget =
iVertex(target);
assert(iSource != UINT32_MAX && iTarget !=
UINT32_MAX);
std::set<unsigned int>& sSet = edges[iSource];
if (sSet.find(iTarget) == sSet.end()) sSet.insert(iTarget);
if (directed) return;
std::set<unsigned int>& tSet = edges[iTarget];
if (tSet.find(iSource) == tSet.end()) tSet.insert(iSource);
}
template <typename T>
void graph<T>::removeEdge(const T& source, const T&
target, bool directed) {
unsigned int iSource = iVertex(source), iTarget =
iVertex(target);
assert(iSource != UINT32_MAX && iTarget !=
UINT32_MAX);
edges[iSource].erase(iTarget);
if (directed) return;
edges[iTarget].erase(iSource);
}
template <typename T>
unsigned int graph<T>::nVertex() {
return labels.size();
}
template <typename T>
unsigned int graph<T>::nEdge(bool directed) {
unsigned int eCount = 0, lCount = 0;
for (unsigned int i = 0; i < edges.size(); i++)
for (auto e : edges) {
if (e == i) lCount++;
else eCount++;
}
return lCount + (eCount / (directed ? 1 : 2));
}
template <typename T>
std::set<unsigned int>& graph<T>::vAdjacent(const
T& source) {
unsigned int iSource = iVertex(source);
assert(iSource != UINT32_MAX);
return edges[iSource];
}
template <typename T>
bool graph<T>::isEdge(const T& source, const T&
target) {
unsigned int iSource = iVertex(source), iTarget =
iVertex(target);
assert(iSource != UINT32_MAX && iTarget !=
UINT32_MAX);
std::set<unsigned int>& sSet = edges[iSource];
return sSet.find(iTarget) != sSet.end();
std::queue<unsigned int> q; // vertices to be
visited
std::vector<bool> visited(nVertex(), false); // marker for
visited vertices
q.push(sVertex); visited[sVertex] = true; // add starting vertex to
queue
while (!q.empty()) {
unsigned int v = q.front(); q.pop(); // about to be visited
vertex
// visiting the vertex
for (auto aV : edges[v]) // neighboring vertices
if (!visited[aV]) { // vertex hasn’t been visited yet
q.push(aV); visited[aV] = true; // add vertex to queue
}
}
template <typename T> void graph<T>::print(unsigned
int sVertex) {
std::queue<unsigned int> q; // vertices to be visited
std::vector<bool> visited(nVertex(), false); // marker for
visited vertices
q.push(sVertex); visited[sVertex] = true; // add starting vertex to
queue
while (!q.empty()) {
unsigned int v = q.front(); q.pop(); // about to be visited
vertex
printVertex(v); // visiting the vertex
for (auto aV : edges[v]) // neighboring vertices
if (!visited[aV]) { // vertex hasn’t been visited yet
q.push(aV); visited[aV] = true; // add vertex to queue
}
}
}
q.push(i); visited = true;
while (!q.empty()) {
unsigned int v = q.front(); q.pop();
for (auto aV : edges[v])
if (!visited[aV]) {
q.push(aV); visited[aV] = true;
}
}
template <typename T> unsigned int
graph<T>::nConnectedComponent() {
std::queue<unsigned int> q;
std::vector<bool> visited(nVertex(), false);
unsigned int count = 0;
for (unsigned int i = 0; i < nVertex(); i++)
if (!visited) { // found a component
count++;
// visit i and all vertices connected to i
}
return count;
}
template <typename T> bool graph<T>::isConnected()
{
return nConnectedComponent() == 1;
}
std::stack<unsigned int> s; // vertices to be
visited
std::vector<bool> visited(nVertex(), false); // marker for
visited vertices
s.push(sVertex); visited[sVertex] = true; // add starting vertex to
stack
while (!s.empty()) {
unsigned int v = s.top(); s.pop(); // about to be visited
vertex
// visiting the vertex
std::set<unsigned int>::reverse_iterator iA;// neighboring
vertices
for (iA = edges[v].rbegin(); iA != edges[v].rend(); iA++)
if (!visited[*iA]) { // vertex hasn’t been visited yet
q.push(*iA); visited[*iA] = true; // add vertex to stack
}
}
template <typename T> void graph<T>::print(unsigned
int sVertex) {
std::stack<unsigned int> s; // vertices to be visited
std::vector<bool> visited(nVertex(), false); // marker for
visited vertices
s.push(sVertex); visited[sVertex] = true; // add starting vertex to
stack
while (!s.empty()) {
unsigned int v = s.top(); s.pop(); // about to be visited
vertex
printVertex(v); // visiting the vertex
std::set<unsigned int>::reverse_iterator iA;// neighboring
vertices
for (iA = edges[v].rbegin(); iA != edges[v].rend(); iA++)
if (!visited[*iA]) { // vertex hasn’t been visited yet
q.push(*iA); visited[*iA] = true; // add vertex to stack
}
}
std::vector<int> predecessor(nVertex(), -1); // initialize
all elements to -1
while (!s.empty()) {
...
for (iA = edges[v].rbegin(); iA != edges[v].rend(); iA++)
if (!visited[*iA]) {
...
predecessor[*iA] = v; // set predecessor of the neighboring
vertex
}
}
template <typename T>
void graph<T>::printPath(unsigned int source, unsigned int
destination) {
...
std::vector<int> predecessor(nVertex(), -1); // initialize
all elements to -1
...
while (destination != -1) {
printVertex(destination);
destination = predecessor[destination];
}
Please give answer in code
}