For this assignment, you will implement the shortest path algorithm demonstrated
ID: 3766398 • Letter: F
Question
For this assignment, you will implement the shortest path algorithm demonstrated in class (Dijkstra's algorithm). You will take the Graph class I showed you and fill in the shortestPath method. The method should return a vector of node pointers, where each pointer is a stop in the path. For example, if you are finding a path from node A to node E, and the path goes through nodes B, C, and D, in that order, the return value should be a vector whose values are:
[A, B, C, D, E]
Things you should understand very well going into this assignment:
Dijkstra's algorithm for finding the shortest path.
Using ADTs - specifically deque, unordered_set, vector, and unordered_map.
Using iterators to go through an ADT one element at a time.
Throwing exceptions.
Templates.
Pointers.
NOTE: You'll have to use std:: in front of every ADT you use - std::vector, std::deque, etc.
If you are feeling fuzzy on any of the above, please come to office hours so the TAs or I can help you!
Starter files:
graph.h - The Graph class, with nothing in the shortestPath method. This is the part you fill in!
main.cpp - A simple file that makes use of the Graph class, including the shortestPath method. This is not a thorough test! Write your own code to test finding paths in more complicated graphs. Make sure you test edge cases (e.g. when a node doesn't exist, when there is no path between the two nodes, etc.).
main.cpp contents:
#include "graph.h"
using namespace std;
int main()
{
Graph<string> g;
Node<string>* a = g.insert("a");
Node<string>* b = g.insert("b");
Node<string>* c = g.insert("c");
Node<string>* d = g.insert("d");
Node<string>* e = g.insert("e");
g.connect(a, b);
g.connect(c, d);
g.connect(b, e);
g.connect(c, e);
cout << "Graph 1" << endl;
g.print();
cout << "-----" << endl;
vector<Node<string>*> path = g.shortestPath("a", "e");
cout << "Graph 1: path from a to e: ";
for (int i = 0; i < path.size(); i++) {
cout << path[i]->value << " ";
}
cout << endl;
cout << "----" << endl;
Graph<string> g2(g);
g2.connect("a", "e");
cout << "Graph 1 again" << endl;
g.print();
cout << "-----" << endl;
cout << "Graph 2" << endl;
g2.print();
cout << "-----" << endl;
path = g.shortestPath("a", "e");
cout << "Graph 1: path from a to e: ";
for (int i = 0; i < path.size(); i++) {
cout << path[i]->value << " ";
}
cout << endl;
cout << "----" << endl;
path = g2.shortestPath("a", "e");
cout << "Graph 2: path from a to e: ";
for (int i = 0; i < path.size(); i++) {
cout << path[i]->value << " ";
}
cout << endl;
cout << "----" << endl;
Graph<string> g3;
g3.insert("z"); // this should get overwritten
g3.insert("y"); // and this
g3.connect("y", "z"); // also this
g3 = g;
g3.connect("a", "e");
cout << "Graph 1 a third time" << endl;
g.print();
cout << "-----" << endl;
cout << "Graph 3" << endl;
g3.print();
cout << "-----" << endl;
path = g.shortestPath("a", "e");
cout << "Graph 1: path from a to e: ";
for (int i = 0; i < path.size(); i++) {
cout << path[i]->value << " ";
}
cout << endl;
cout << "----" << endl;
path = g3.shortestPath("a", "e");
cout << "Graph 3: path from a to e: ";
for (int i = 0; i < path.size(); i++) {
cout << path[i]->value << " ";
}
cout << endl;
cout << "----" << endl;
return 0;
}
And here is graph.h contents:
#ifndef _GRAPH_H
#define _GRAPH_H
#include <cstdlib>
#include <iostream>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <stdexcept>
/*
* Exception for trying to find
* a path between two nodes if
* at least one of the nodes
* doesn't exist.
*/
class NonExistentNodeException : public std::exception
{
public:
virtual const char* what() const throw() {
return "At least one of those nodes doesn't exist!";
}
};
/*
* Exception for trying to find
* a path between two nodes when
* no path exists.
*/
class NoPathException : public std::exception
{
public:
virtual const char* what() const throw() {
return "No path exists between those two nodes!";
}
};
/*
* Node
* -----
* Represents a node in a graph. T is
* the type of value held in the node.
*/
template <typename T>
class Node
{
public:
Node(const T& value) : value(value) {}
/*
* Why wouldn't this do what we want?
*
* Hint: what is the new node connected to?
*/
/*
Node<T>* copy(const Node& other) {
return new Node<T>(value);
}
*/
/*
* Why not a vector for the list of adjacent
* nodes?
*/
std::unordered_set<Node<T>*> adjacents;
T value;
bool marked;
};
/*
* Graph
* -----
* Represents a bi-directional (undirected)
* graph. Nodes can have any value. The
* graph does not have to be connected. Values
* must be unique.
*/
template <typename T>
class Graph
{
public:
Graph() {}
/*
* Since we dynamically allocate each node,
* we need the big 3!
*
* - destructor
* - copy constructor
* - assignment operator
*/
~Graph() {
clear();
}
Graph(const Graph<T>& other) {
copyOther(other);
}
Graph<T>& operator=(const Graph<T>& other) {
if (this != &other) {
clear();
copyOther(other);
}
return *this;
}
/*
* Common graph operations.
*/
Node<T>* insert(const T& value) {
if (nodes.find(value) != nodes.end()) {
return NULL;
}
Node<T>* newNode = new Node<T>(value);
nodes[value] = newNode;
return newNode;
}
// Two versions of connect! One that takes
// node pointers, another that takes node
// values.
void connect(Node<T>* first, Node<T>* second) {
first->adjacents.insert(second);
second->adjacents.insert(first);
}
void connect(const T& first, const T& second) {
if (nodes.find(first) == nodes.end() ||
nodes.find(second) == nodes.end()) {
throw NonExistentNodeException();
}
connect(nodes[first], nodes[second]);
}
void unmarkAll() {
for (auto iter = nodes.begin();
iter != nodes.end();
iter++) {
iter->second->marked = false;
}
}
void print() {
for (auto iter = nodes.begin();
iter != nodes.end();
iter++) {
std::cout << iter->first << ": ";
for (auto neighborsIter = iter->second->adjacents.begin();
neighborsIter != iter->second->adjacents.end();
neighborsIter++) {
std::cout << (*neighborsIter)->value << " ";
}
std::cout << std::endl;
}
}
std::vector<Node<T>*> shortestPath(const T& start, const T& end) {
// Make sure both nodes exist! If one doesn't, throw
// the appropriate exception.
// Ok, both nodes exist. Get the node pointers from
// your unordered_map!
// You will need some way to store partial paths.
// I highly recommend representing a partial
// path as a vector of node pointers, since this
// is what you will ultimately be returning.
//
// I would ALSO recommend using a deque to store
// all your partial paths. (A deque is
// shorthand for double-ended queue. It's part
// of the STL.
//
// If you choose to use a deque (which you should),
// you'll have a deque of vectors, where each vector
// in turn contains node pointers. Kind of
// complicated! But effective!
// Don't forget to unmark your nodes!
// Your first partial path will just contain one
// node - the start node. Not much of a path, but
// you have to start somewhere!
// Now, repeatedly do the following:
// 1. Get the topmost partial path.
// 2. Look at every node you can get to from
// the end of that partial path (ignoring
// nodes you've already seen).
// 3. Create a partial path that has the same
// nodes as the current partial path, PLUS
// one more node (the node that you're
// looking at).
// 4. Store those partial paths at the end.
//
// You stop when:
// - You see the end node in step 2. Put the
// end node at the end of the current partial
// path, and then return the partial (now
// complete) path!
// - You run out of partial paths to look at.
// If this ever happens, that means there is
// no path to the end node. Throw the
// appropriate exception.
// This method returns an empty vector for now.
// Get rid of this line!
return std::vector<Node<T>*>();
}
private:
std::unordered_map<T, Node<T>*> nodes; // for uniqueness and lookup
void copyOther(const Graph<T>& other) {
for (auto iter = other.nodes.begin();
iter != other.nodes.end();
iter++) {
insert(iter->first);
}
for (auto iter = other.nodes.begin();
iter != other.nodes.end();
iter++) {
auto adjacents = iter->second->adjacents;
for (auto neighborsIter = adjacents.begin();
neighborsIter != adjacents.end();
++neighborsIter) {
// Need to connect the values here!
// Connecting iter->second and *neighborsIter
// would re-connect the nodes in the old graph
// (so this would do nothing)
connect(iter->first, (*neighborsIter)->value);
}
}
}
void clear() {
for (auto iter = nodes.begin();
iter != nodes.end();
iter++) {
delete iter->second;
}
nodes.clear();
}
};
#endif
Explanation / Answer
Given below is the completed graph.h file and modified main.cpp. The output of main is shown below. Please do rate the answer if it helped. Thank you.
graph.h
#ifndef _GRAPH_H
#define _GRAPH_H
#include <cstdlib>
#include <iostream>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <stdexcept>
/*
* Exception for trying to find
* a path between two nodes if
* at least one of the nodes
* doesn't exist.
*/
class NonExistentNodeException : public std::exception
{
public:
virtual const char* what() const throw() {
return "At least one of those nodes doesn't exist!";
}
};
/*
* Exception for trying to find
* a path between two nodes when
* no path exists.
*/
class NoPathException : public std::exception
{
public:
virtual const char* what() const throw() {
return "No path exists between those two nodes!";
}
};
/*
* Node
* -----
* Represents a node in a graph. T is
* the type of value held in the node.
*/
template <typename T>
class Node
{
public:
Node(const T& value) : value(value) {}
/*
* Why wouldn't this do what we want?
*
* Hint: what is the new node connected to?
*/
/*
Node<T>* copy(const Node& other) {
return new Node<T>(value);
}
*/
/*
* Why not a vector for the list of adjacent
* nodes?
*/
std::unordered_set<Node<T>*> adjacents;
T value;
bool marked;
};
/*
* Graph
* -----
* Represents a bi-directional (undirected)
* graph. Nodes can have any value. The
* graph does not have to be connected. Values
* must be unique.
*/
template <typename T>
class Graph
{
private:
std::unordered_map<T, Node<T>*> nodes; // for uniqueness and lookup
void copyOther(const Graph<T>& other) {
for (auto iter = other.nodes.begin();
iter != other.nodes.end();
iter++) {
insert(iter->first);
}
for (auto iter = other.nodes.begin();
iter != other.nodes.end();
iter++) {
auto adjacents = iter->second->adjacents;
for (auto neighborsIter = adjacents.begin();
neighborsIter != adjacents.end();
++neighborsIter) {
// Need to connect the values here!
// Connecting iter->second and *neighborsIter
// would re-connect the nodes in the old graph
// (so this would do nothing)
connect(iter->first, (*neighborsIter)->value);
}
}
}
void clear() {
for (auto iter = nodes.begin();
iter != nodes.end();
iter++) {
delete iter->second;
}
nodes.clear();
}
public:
Graph() {}
/*
* Since we dynamically allocate each node,
* we need the big 3!
*
* - destructor
* - copy constructor
* - assignment operator
*/
~Graph() {
clear();
}
Graph(const Graph<T>& other) {
copyOther(other);
}
Graph<T>& operator=(const Graph<T>& other) {
if (this != &other) {
clear();
copyOther(other);
}
return *this;
}
/*
* Common graph operations.
*/
Node<T>* insert(const T& value) {
if (nodes.find(value) != nodes.end()) {
return NULL;
}
Node<T>* newNode = new Node<T>(value);
nodes[value] = newNode;
return newNode;
}
// Two versions of connect! One that takes
// node pointers, another that takes node
// values.
void connect(Node<T>* first, Node<T>* second) {
first->adjacents.insert(second);
second->adjacents.insert(first);
}
void connect(const T& first, const T& second) {
if (nodes.find(first) == nodes.end() ||
nodes.find(second) == nodes.end()) {
throw NonExistentNodeException();
}
connect(nodes[first], nodes[second]);
}
void unmarkAll() {
for (auto iter = nodes.begin();
iter != nodes.end();
iter++) {
iter->second->marked = false;
}
}
void print() {
for (auto iter = nodes.begin();
iter != nodes.end();
iter++) {
std::cout << iter->first << ": ";
for (auto neighborsIter = iter->second->adjacents.begin();
neighborsIter != iter->second->adjacents.end();
neighborsIter++) {
std::cout << (*neighborsIter)->value << " ";
}
std::cout << std::endl;
}
}
std::vector<Node<T>*> shortestPath(const T& start, const T& end) {
// Make sure both nodes exist! If one doesn't, throw
// the appropriate exception.
if (nodes.find(start) == nodes.end() ||
nodes.find(end) == nodes.end()) {
throw NonExistentNodeException();
}
// Ok, both nodes exist. Get the node pointers from
// your unordered_map!
Node<T>* sn = nodes[start];
Node<T>* en = nodes[end];
// You will need some way to store partial paths.
// I highly recommend representing a partial
// path as a vector of node pointers, since this
// is what you will ultimately be returning.
//
// I would ALSO recommend using a deque to store
// all your partial paths. (A deque is
// shorthand for double-ended queue. It's part
// of the STL.
//
// If you choose to use a deque (which you should),
// you'll have a deque of vectors, where each vector
// in turn contains node pointers. Kind of
// complicated! But effective!
//std::deque<std::vector<Node<T>*> nodedq;
std::vector<Node<T>*> partialpath;
// Don't forget to unmark your nodes!
unmarkAll();
// Your first partial path will just contain one
// node - the start node. Not much of a path, but
// you have to start somewhere!
partialpath.push_back(sn);
std::deque<std::vector<Node<T>*>> dq;
dq.push_back(partialpath);
// Now, repeatedly do the following:
// 1. Get the topmost partial path.
while(!dq.empty())
{
// 2. Look at every node you can get to from
// the end of that partial path (ignoring
// nodes you've already seen).
std::vector<Node<T>*> pp = dq.front();
dq.pop_front();
Node<T>* last = pp.back();
for (auto neighborsIter = last->adjacents.begin();
neighborsIter != last->adjacents.end();
neighborsIter++) {
// 3. Create a partial path that has the same
// nodes as the current partial path, PLUS
// one more node (the node that you're
// looking at).
if(!(*neighborsIter)->marked)
{
// 4. Store those partial paths at the end.
//
std::vector<Node<T>*> newpp(pp);
newpp.push_back(*neighborsIter);
dq.push_back(newpp);
(*neighborsIter)->marked = true;
if(newpp.back() == en)
return newpp;
}
}
}
// You stop when:
// - You see the end node in step 2. Put the
// end node at the end of the current partial
// path, and then return the partial (now
// complete) path!
// - You run out of partial paths to look at.
// If this ever happens, that means there is
// no path to the end node. Throw the
// appropriate exception.
// This method returns an empty vector for now.
// Get rid of this line!
throw NoPathException();
}
};
#endif
main.cpp
#include "graph.h"
using namespace std;
int main()
{
Graph<string> g;
Node<string>* a = g.insert("a");
Node<string>* b = g.insert("b");
Node<string>* c = g.insert("c");
Node<string>* d = g.insert("d");
Node<string>* e = g.insert("e");
g.connect(a, b);
g.connect(c, d);
g.connect(b, e);
g.connect(c, e);
cout << "Graph 1" << endl;
g.print();
cout << "-----" << endl;
vector<Node<string>*> path = g.shortestPath("a", "e");
cout << "Graph 1: path from a to e: ";
for (int i = 0; i < path.size(); i++) {
cout << path[i]->value << " ";
}
cout << endl;
cout << "----" << endl;
Graph<string> g2(g);
g2.connect("a", "e");
cout << "Graph 1 again" << endl;
g.print();
cout << "-----" << endl;
cout << "Graph 2" << endl;
g2.print();
cout << "-----" << endl;
path = g.shortestPath("a", "e");
cout << "Graph 1: path from a to e: ";
for (int i = 0; i < path.size(); i++) {
cout << path[i]->value << " ";
}
cout << endl;
cout << "----" << endl;
path = g2.shortestPath("a", "e");
cout << "Graph 2: path from a to e: ";
for (int i = 0; i < path.size(); i++) {
cout << path[i]->value << " ";
}
cout << endl;
cout << "----" << endl;
Graph<string> g3;
g3.insert("z"); // this should get overwritten
g3.insert("y"); // and this
g3.connect("y", "z"); // also this
g3 = g;
g3.connect("a", "e");
cout << "Graph 1 a third time" << endl;
g.print();
cout << "-----" << endl;
cout << "Graph 3" << endl;
g3.print();
cout << "-----" << endl;
path = g.shortestPath("a", "e");
cout << "Graph 1: path from a to e: ";
for (int i = 0; i < path.size(); i++) {
cout << path[i]->value << " ";
}
cout << endl;
cout << "----" << endl;
path = g3.shortestPath("a", "e");
cout << "Graph 3: path from a to e: ";
for (int i = 0; i < path.size(); i++) {
cout << path[i]->value << " ";
}
cout << endl;
cout << "----" << endl;
try {
cout << endl;
cout << "----" << endl;
path = g3.shortestPath("a", "f");
cout << "Graph 3: path from a to f: ";
for (int i = 0; i < path.size(); i++) {
cout << path[i]->value << " ";
}
cout << endl;
cout << "----" << endl;
} catch (NonExistentNodeException e) {
cout << e.what() << endl;
}
return 0;
}
output
Graph 1
e: c b
d: c
b: e a
c: e d
a: b
-----
Graph 1: path from a to e: a b e
----
Graph 1 again
e: c b
d: c
b: e a
c: e d
a: b
-----
Graph 2
a: e b
c: d e
b: a e
d: c
e: a c b
-----
Graph 1: path from a to e: a b e
----
Graph 2: path from a to e: a e
----
Graph 1 a third time
e: c b
d: c
b: e a
c: e d
a: b
-----
Graph 3
a: e b
c: d e
b: a e
d: c
e: c a b
-----
Graph 1: path from a to e: a b e
----
Graph 3: path from a to e: a e
----
----
At least one of those nodes doesn't exist!
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.