关于后端:CMPT-135-解题思路

CMPT 135 202101 Final Project
Due Date and Time: Tuesday 20 April 2021 at 7:00AM PST
Vision of Project
In this project we are going to build a software solution for the computation of the shortest path from one
place to another place in a two dimensional space similar to a global positioning system (GPS) without making
use of any C++ library; instead building everything from scratch.
The vision of the project is that given the map of a region and its road connectivity, we would like to compute
the shortest path to go from one place to another place. See the diagram below for illustration purposes.
Fig 1: Region map and its road connectivity
As we can see in the illustration above, places in the region are connected by roads. There may or may not be
a direct road from a place to another. In the illustration above for example, there is a direct road from
Vancouver to North Vancouver but there is no a direct road from Vancouver to Port Coquitlam. However, we
can go from Vancouver to Port Coquitlam in several ways among which are the following paths (or routes)
Vancouver  Burnaby  Port Coquitlam
Vancouver  Coquitlam  Port Coquitlam
Vancouver BurnabyNew Westminster  Port Coquitlam
CMPT 135 – FIC 202101 – Final Exam Project – Dr. Yonas T. Weldeselassie (Ph.D.) Page 2
Moreover, we assume that the roads are two ways and that whenever there is a road from A to B then we
automatically assume that there is a road from B to A. That is, we assume that roads are symmetric by nature.
Thus we may go from Vancouver to Port Coquitlam using the following routes as well
Vancouver DeltaSurrey Port Coquitlam
Vancouver  Coquitlam  Burnaby  Port Coquitlam
Or if we want to waste our time going in an unnecessary loop, then we may go in the following route too
Vancouver Burnaby RichmondNew WestminsterBurnaby  Port Coquitlam
We can still find many more possible routes.
The aim of our project is therefore to find the shortest path. Of course in order to compute the shortest path,
we need to be given the distances between pairs of cities along the roads as shown on the illustration above.
In computing science, we generally speak in terms of the cost of a path. The cost can be any measurable
quantity as you go from one place to another place. Typical costs include distances between places (like the
illustration shown above), the amount of petrol you will burn as you drive from one place to another, or some
other measurements. Thus the shortest path problem is generally referred to as the minimum cost path.
For example if the cost under consideration is the amount of petrol you burn as you go from one place to
another, then it should also be noted that you may burn more petrol on a given shorter distance road than a
longer one. For example if the longer road is a freeway (highway) but the shorter one is a congested road in a
city. This is how a typical GPS device (application) works.
Therefore, we need to always define what measurement to use to compute costs of paths so that we can
select the minimum cost path based on the measure under consideration.
In the illustration above for example, assuming the cost is the distances shown in the illustration; then the
costs of the six paths we have listed above will respectively be: 11.2, 9.8, 14.3, 16.7, 15.9, and 25.0. Since the
minimum cost among the costs computed is 9.8, we therefore conclude that the minimum cost path among
the paths shown above is therefore to go through the path
Vancouver  Coquitlam  Port Coquitlam [cost = 9.8]
Of course it should also be noted from the paths listed above that the last one, that is
Vancouver Burnaby RichmondNew WestminsterBurnaby  Port Coquitlam
is a useless computation because the path contains a loop (that is to say the path passes through a place but
then loops back to the same place before it reaches the destination place). A path with a loop should
obviously be avoided.
Terminologies
 Graph: The region map with its road connectivity shown in the diagram above is called a graph.
 Vertex: A vertex (plural vertices) is a unit in a graph (such as a city in the diagram above).
 Edge: A unit in a graph that connects pairs of vertices of the graph.
 Path: A route to go from one vertex of a graph to another following the edges in the graph.
 Origin Vertex of an edge: A vertex from where an edge emanates (comes out from).
 Destination Vertex of an edge: A vertex where an edge ends (comes into).
CMPT 135 – FIC 202101 – Final Exam Project – Dr. Yonas T. Weldeselassie (Ph.D.) Page 3
Scope of Project
The scope of the project will encompass
 Data Structures: The design of classes to represent vertices, edges, graph, and paths in a graph.
 Algorithms: The design of clearly defined steps to solve the shortest path problem.
Restrictions of Libraries
We would like to build the project from scratch. Thus we will limit ourselves to using only a few libraries of C++
language; namely

include <iostream>

include <fstream>,

include <cassert>

include <ctime>

include <iomanip>

Using namespace std;
No other library is permitted in the project.
Starting Our Project
At this stage, it should be fairly obvious that our vertices have city names that need to be stored in our
application. For this reason, it makes sense to start by defining a class to store a string of characters. The
following class declaration therefore suffices to achieve our objective.

include <iostream>

include <fstream>

include <cassert>

include <ctime>

include <iomanip>

using namespace std;
class CMPT135_String
{
private:
char *buffer; //The dynamic array to store the printable characters and a null terminating character
public:
CMPT135_String(); //The buffer is initialized to nullptr value
CMPT135_String(const char *); //A non-default constructor with a null terminated char array argument
CMPT135_String(const CMPT135_String &); //Deep copy constructor
~CMPT135_String(); //Delete any heap memory and assign buffer nullptr value
CMPT135_String& operator = (const CMPT135_String &); //Memory cleanup and deep copy assignment
int length() const; //Return the number of printable characters. Return zero if buffer is nullptr
bool empty() const; //Return true if length is 0. Otherwise return false
char& operator [] (const int &) const; //Assert index and then return the char at the index
CMPT135_String operator + (const char &) const; //Return a new CMPT135_String object made from the
// characters of *this and the character argument
CMPT135_String& operator += (const char &); //Append the character argument to the *this object and
//then return the *this object
bool operator == (const CMPT135_String &) const; //Case sensitive equality comparison
bool operator != (const CMPT135_String &) const; //Case sensitive not equality comparison
friend istream& operator >> (istream &, CMPT135_String &); //Implemented for you
friend ostream& operator << (ostream &, const CMPT135_String &); //Implemented for you
};
istream& operator >> (istream &in, CMPT135_String &s)
CMPT 135 – FIC 202101 – Final Exam Project – Dr. Yonas T. Weldeselassie (Ph.D.) Page 4
{
//This function reads characters input from a keyboard or a file until either a TAB, EOL, or EOF is
//reached. The function ignores any leading spaces, TAB, or EOL characters. It is designed
//to be able to read a string of characters that may or may not contain spaces without any problem.
//It is also designed to ignore any trailing spaces.
//Define some useful constant values

define SPACE ‘ ‘

define TAB ‘\t’

define EOL ‘\n’

//Delete the old value of s
s.~CMPT135_String();
//Skip leading spaces, tabs, and empty lines
char ch;
while (!in.eof())
{
in.get(ch);
if (ch == SPACE || ch == TAB || ch == EOL)
continue;
break;
}
if (in.eof())
return in;
//Append ch to s
if (ch != SPACE && ch != TAB && ch != EOL)
s += ch;
//Read characters into s until a TAB or EOL or EOF is reached
while (!in.eof())
{
in.get(ch);
if (ch == TAB || ch == EOL || in.eof())
break;
else
s += ch;
}
//Remove trailing spaces if any
int trailingSpacesCount = 0;
for (int i = s.length()-1; i >= 0; i–)
{
if (s[i] != SPACE)
break;
trailingSpacesCount++;
}
if (trailingSpacesCount > 0)
{
CMPT135_String temp;
for (int i = 0; i < s.length()-trailingSpacesCount; i++)
temp += s[i];
s = temp;
}
return in;
}
ostream& operator << (ostream &out, const CMPT135_String &s)
{
for (int i = 0; i < s.length(); i++)
out << s[i];
return out;
}
CMPT 135 – FIC 202101 – Final Exam Project – Dr. Yonas T. Weldeselassie (Ph.D.) Page 5
Use the test program given below to test your CMPT135_String class before proceeding to the next section.
The ConnectivityMap1.txt input text file is uploaded together with the project in order to help you test
your code. The text file contains information about a small region map for testing purposes. You will notice in
the text file that the road connectivity between the cities of Vancouver and North Vancouver is listed twice
with different costs. Don’t worry about it for now because we don’t need to understand the input file
information contents at this point. We will discuss it in more detail later. For now, let’s just use it as it is given
in order to test our class. Also please note that there are some empty lines in the file and at the end of the file
as well as there are different number of tabs or spaces between city names and costs. But these will not cause
any problem because the overloaded input stream operator friend function in the CMPT135_String class will
take care of all the details of the reading for us. All we need is to remember any leading spaces, tabs, and EOL
characters will be ignored and reading will stop only when it encounters tab, EOL, or EOF character. This
means there must be at least one tab or EOL character between the city names and the costs. In addition any
trailing spaces after a city name will be removed after the reading of a city name is completed.
Please note that this test program is not part of the project and should not be included in your submission.
int main()
{
CMPT135_String departure, destination;
double cost;
ifstream fin(“ConnectivityMap1.txt”);
assert(!fin.fail());
const int CITY_NAME_WIDTH = 25; //For output formatting purposes
while (!fin.eof())
{
fin >> departure;
fin >> destination;
if (departure.empty() || destination.empty())
break;
fin >> cost;
cout << departure << setw(CITY_NAME_WIDTH – departure.length()) << ” “;
cout << destination << setw(CITY_NAME_WIDTH – destination.length()) << ” “;
cout << cost << endl;
}
fin.close();
system(“Pause”);
return 0;
}
Output
Vancouver Burnaby 1.5
Vancouver North Vancouver 1.2
Burnaby North Vancouver 4.7
Burnaby Port Moody 3.6
North Vancouver Port Moody 5.8
North Vancouver Vancouver 2.9
Press any key to continue . . .
Next, we will need to store several items (such as vertices, edges, CMPT135_Strings) in different containers. It
therefore makes sense to define a generic container using a class template so that we may also use the same
container to store different objects. The following class declaration based on Assignment 3 therefore suffices
to achieve our objective.
template <class T>
class SmarterArray
{
private:
CMPT 135 – FIC 202101 – Final Exam Project – Dr. Yonas T. Weldeselassie (Ph.D.) Page 6
T *A; //The dynamic array to store the elements
int size; //The number of elements in the array
public:
//Constructors
SmarterArray(); //Implemented for you
SmarterArray(const SmarterArray<T>&); //Copy constructor. Deep copy of the argument
//Assignment operator
SmarterArray<T>& operator = (const SmarterArray<T>&); //Memory cleanup and deep copy of the argument
//Destructor
~SmarterArray(); //Implemented for you
//Getters, Setters, operators and other functions
int getSize() const; //Return the number of elements in the container
T& operator[](const int&) const; //Assert index and then return the element at the given index
int find(const T&) const; //Return the index of the first element that is == to the argument.
//Return -1 if not found.
void insert(const int &index, const T&); //Assert index >= 0 && index <= size and then insert the T
//type argument into the calling object at the index. If index is
//equal to size, then insert as a last element
void append(const T&); //Insert T as a last element
bool remove(const int&); //If the index is valid, then remove the element at the index argument
//from the calling object and return true. Otherwise do nothing and return
//false. Do not assert the index argument.
bool operator == (const SmarterArray<T>&) const; //Return true if sizes are equal and elements at the
//same indexes are equal. Otherwise return false
template <class T1> //Those of you working with xCode, don’t use the same template name T. T1 is ok.
friend ostream& operator << (ostream&, const SmarterArray<T1>&); //Implemented for you
};
template <class T>
SmarterArray<T>::SmarterArray()
{
this->A = nullptr;
this->size = 0;
}
template <class T>
SmarterArray<T>::~SmarterArray()
{
if (this->getSize() > 0)
{
delete[] this->A;
A = nullptr;
this->size= 0;
}
}
template <class T>
ostream& operator << (ostream& out, const SmarterArray<T>& L)
{
if (L.getSize() == 0)
out << “[Empty List]”;
else
{
cout << endl;
for (int i = 0; i < L.getSize()-1; i++)
out << L[i] << endl;
out << L[L.getSize()-1] << endl;
}
return out;
}
CMPT 135 – FIC 202101 – Final Exam Project – Dr. Yonas T. Weldeselassie (Ph.D.) Page 7
Task 1
Implement the CMPT135_String class and the SmarterArray class template that we will be using in our
subsequent sections.
Representing vertices, edges, and a graph
Each Vertex object will store the name of the city (CMPT135_String data type) at the vertex and a set of
edges emanating from the vertex together with their costs. A graph will then simply be a set of vertices (that is
a SmarterArray<Vertex> data type). This means each Vertex object will have an associated index in the
graph container. Therefore an Edge object can easily be represented as a struct that will store the index of its
destination vertex in the underlying graph and the cost of the edge. Thus we are given the following C++ struct
declaration to represent Edge objects.
struct Edge
{
int desVertexIndex; //the index (in the underlying graph) of the destination vertex of this edge
double cost;//cost of an edge
};
We note that an Edge object does not need to store its origin vertex because the origin vertex will store the
edge instead.
The following class declaration therefore suffices in order to represent vertex objects in a graph.
class Vertex
{
private:
CMPT135_String name; //Name of the city at the vertex
SmarterArray<Edge> E; //A container to store the edges emanating from this vertex. All the elements of
//E have the same origin vertex which is the *this object. But they have different destination
//vertices which are given by the desVertexIndex member variable of each element of the E container
public:
Vertex(); //Assign name = “N/A” and initialize E to an empty container (default object E)
Vertex(const CMPT135_String &); //Assign name = the argument and initialize E to an empty container
CMPT135_String getName() const; //Return the name
SmarterArray<Edge> getEdgeSet() const; //Return E
int getEdgeSetSize() const; //Return the size of E
Edge getEdge(const int & desVertexIndex) const; //Assert an edge whose destination vertex index is
//equal to the argument is found in E. Then return the edge
double getEdgeCost(const int &desVertexIndex) const; //Assert an edge whose destination vertex index
//is equal to the argument is found in E. Then return its cost
void setEdgeCost(const int &desVertexIndex, const double &cost); //Assert an edge whose destination vertex index
//is equal to the argument is found in E. Then assign its cost the argument
void appendEdge(const int &desVertexIndex, const double &cost); //Assert there is no element of E
//whose destination vertex index and cost are equal to the argument values. Then append
//a new element whose destination vertex index and cost are initialized with the
//argument values to E
friend ostream& operator << (ostream &, const Vertex &); //Implemented for you
};
ostream& operator << (ostream &out, const Vertex &vertex)
{
out << “Name = ” << vertex.name << endl;
out << “Edge Set” << endl;
for (int i = 0; i < vertex.E.getSize(); i++)
out << “\t to —> ” << vertex.E[i].desVertexIndex << “, cost = ” << vertex.E[i].cost << endl;
return out;
}
With our Vertex class design, we can see that the vertex belonging to the city of Surrey in the diagram above is
represented with a Vertex object whose name member variable is assigned “Surrey” and whose E member
CMPT 135 – FIC 202101 – Final Exam Project – Dr. Yonas T. Weldeselassie (Ph.D.) Page 8
variable will store 3 Edge data type elements (an edge to the Delta vertex with a cost of 3.9, an edge to the
New Westminster vertex with a cost of 3.1, and an edge to the Port Coquitlam vertex with a cost of 4.5).
Assuming the Delta, New Westminster, and Port Coquitlam Vertex objects are stored at indices 5, 2, and 9
respectively of the underlying graph, then E[0] = [desVertexIndex = 5, cost = 3.9], E[1] = [desVertexIndex = 2,
cost = 3.1], and E[2] = [desVertexIndex = 9, cost = 4.5].
Now, we give the class declaration of the Graph class that represents graph objects.
class Graph
{
private:
SmarterArray<Vertex> V; //A graph is simply a container that contains many vertex objects where each vertex
//will have all its connectivity information in it.
public:
Graph();//Construct empty graph (default object V)
Graph(const char *); //Construct a graph from a text file whose path is given by the argument cstring.
//The input text file will consist pairs of cities and the cost to go from one to the other as in the
//following examples
// Vancouver Port Coquitlam 4.5
// Burnaby Surrey 2.5
// UBC Delta 6.8
//The pairs of cities and their costs will be separated by one or more SPACE, TAB or EOL characters.
//It doesn’t matter how many spaces, tabs or EOL characters are present. All leading spaces, tabs and
//EOL characters will be ignored. Moreover any trailing spaces will be removed.
//The reading of characters will start at the first non space, tab, or EOL character and it will stop
//when either a tab, EOL, or EOF character is read. This means THERE MUST BE AT LEAST ONE TAB OR EOL
//character between pairs of city names and cost. Last but not least, there can be as many spaces, TABs,
//or EOL characters at the end of the file and these do not affect the reading of the input file.
//This means a city name can have a space in it as in “Port Coquitlam” and it will be read correctly.
//Please note that we do not need to worry about all these input format details because our CMPT135_String
//class is designed to do all the reading details for us as shown in the test program given above.
//Thus this function should perform the following tasks
//1.Construct a non-default file input streaming object fin using the cstring argument file name
//2.Assert the file is opened successfully
//3.While EOF is not reached do
// a. Read city name. This is the departure city.
// b. Read city name. This is the destination city.
// b. If either the departure city or the destination city is empty CMPT135_String object, then break.
// d. Read the cost.
// e. Append a vertex whose name is the departure city and whose edge set is empty to the graph.
// You must use the appendVertex member function of this class (see below) to append appropriately.
// f. Append a vertex whose name is the destination city and whose edge set is empty to the graph.
// You must use the appendVertex member function of this class to append appropriately.
// g. Append an edge from the departure city to the destination city with a cost read in part (d) above
// to the graph. You must use the appendEdge member function of this class (see below) to append
// appropriately.
// h. Append an edge from the destination city to the departure city with a cost read in part (d) above
// to the graph. You must use the appendEdge member function of this class (see below) to append
// appropriately.
//4.Close the input file stream object and you are done.
SmarterArray<Vertex> getVertexSet() const; //Return V
int getVertexSetSize() const; //Return the number of elements of V
Vertex& operator[](const int &index) const; //Assert the index argument and then return the element at index
int getVertexIndex(const CMPT135_String &) const; //Return the index of an element whose name matches
//the argument. If no such element is found, return -1.
//Assertion should not be performed.
int getVertexIndex(const Vertex &) const; //Return the index of the element whose name matches the
//name of the vertex argument. If no such element is found,
//return -1. Assertion should not be performed.
CMPT135_String getRandomVertexName() const; //Pick a vertex at random and return its name
void appendVertex(const CMPT135_String &); //Append a vertex with the given name and empty E only
//if no vertex with the same name already exists in the graph. If same name
CMPT 135 – FIC 202101 – Final Exam Project – Dr. Yonas T. Weldeselassie (Ph.D.) Page 9
//vertex already exists then do nothing and return. Assertion should not be performed.
void appendVertex(const Vertex &); //Append the argument only if no vertex with the same name already exists
//in the graph. If same name vertex already exists then do nothing
//and return. Assertion should not be performed.
void appendEdge(const CMPT135_String &departure, const CMPT135_String &destination, const double &cost);
//Assert two vertices whose names match the departure and destination arguments exist in the graph.
//If there is already an edge from the departure argument to the destination argument, then
//Update (modify) its cost to the cost argument.
//Otherwise
//Append an edge to the vertex whose name matches the departure argument. The destination vertex index of the
//edge must be set to the index of the vertex whose name matches destination argument and its cost must be set to
// the cost argument.
friend ostream& operator << (ostream &, const Graph &); //Implemented for you
};
ostream& operator << (ostream &out, const Graph &g)
{
const int CITY_NAME_WIDTH = 25;
out << endl;
out << “The graph has ” << g.getVertexSetSize() << ” vertices.” << endl;
out << “These vertices are” << endl;
for (int i = 0; i < g.getVertexSetSize(); i++)
{
Vertex v = g.V[i];
out << “Vertex at index ” << i << ” = ” << v.getName() << endl;
}
out << endl;
out << “Each vertex together with its edge set looks like as follows” << endl;
for (int i = 0; i < g.getVertexSetSize(); i++)
{
Vertex v = g.V[i];
out << v << endl;
}
out << endl;
out << “The graph connectivities are as follows…” << endl;
out.setf(ios::fixed | ios::left); //Left aligned fixed decimal places formatting
for (int i = 0; i < g.getVertexSetSize(); i++)
{
Vertex depVertex = g[i];
SmarterArray<Edge> E = depVertex.getEdgeSet();
for (int j = 0; j < E.getSize(); j++)
{
int desVertexIndex = E[j].desVertexIndex;
Vertex desVertex = g[desVertexIndex];
out << depVertex.getName() << setw(CITY_NAME_WIDTH – depVertex.getName().length()) << ” “;
out << desVertex.getName() << setw(CITY_NAME_WIDTH – desVertex.getName().length()) << ” “;
out << setprecision(2) << E[j].cost << endl;
}
}
out.unsetf(ios::fixed | ios::left); //Removing formatting
cout.precision(0); //Resetting the decimal places to default
return out;
}
Observation
 Considering our graph constructor is designed to insert edges not only from the departure city to the
destination city but also vice versa, we conclude that it is assumed in our application that whenever
there is a connectivity from a city to another city then there is the same connectivity in the opposite
direction as well. That is to say connectivities are assumed to be symmetric by nature.
 When we prepare the input text file therefore we don’t need to list symmetric connectivities in the
input file. It is enough to list only a path from “A” to “B” (but not from “B” to “A”) with some cost
because our graph constructor member function will add both the edges from “A” to “B” and from “B”
to “A” with the same cost.
 How about if an edge information is listed more than once or in both directions? The appendEdge
member function will take care of this seamlessly because whenever it finds an edge already exists in
CMPT 135 – FIC 202101 – Final Exam Project – Dr. Yonas T. Weldeselassie (Ph.D.) Page 10
the graph, then it will only update the cost without appending any new edge. This means only the last
edge information in the input file will ultimately be stored in the graph.
 Therefore given a text file as shown below
ConnectivityMap1.txt
Vancouver Burnaby 1.5
Vancouver North Vancouver 1.2
Burnaby North Vancouver 4.7
Burnaby Port Moody 3.6
North Vancouver Port Moody 5.8
North Vancouver Vancouver 2.9
The following test program should produce the outputs shown below.
int main()
{
Graph g(“ConnectivityMap1.txt”);
cout<<“Graph constructed successfully.”<<endl;
cout<< g <<endl;
system(“Pause”);
return 0;
}
The outputs will be as follows.
Graph constructed successfully.
The graph has 4 vertices.
These vertices are
Vertex at index 0 = Vancouver
Vertex at index 1 = Burnaby
Vertex at index 2 = North Vancouver
Vertex at index 3 = Port Moody
Each vertex together with its edge set looks like as follows
Name = Vancouver
Edge Set
to —> 1, cost = 1.5
to —> 2, cost = 2.9
Name = Burnaby
Edge Set
to —> 0, cost = 1.5
to —> 2, cost = 4.7
to —> 3, cost = 3.6
Name = North Vancouver
Edge Set
to —> 0, cost = 2.9
to —> 1, cost = 4.7
to —> 3, cost = 5.8
Name = Port Moody
Edge Set
to —> 1, cost = 3.6
CMPT 135 – FIC 202101 – Final Exam Project – Dr. Yonas T. Weldeselassie (Ph.D.) Page 11
to —> 2, cost = 5.8
The graph connectivities are as follows…
Vancouver Burnaby 1.50
Vancouver North Vancouver 2.90
Burnaby Vancouver 1.50
Burnaby North Vancouver 4.70
Burnaby Port Moody 3.60
North Vancouver Vancouver 2.90
North Vancouver Burnaby 4.70
North Vancouver Port Moody 5.80
Port Moody Burnaby 3.60
Port Moody North Vancouver 5.80
Press any key to continue . . .
Observe very carefully that although the edge from Vancouver to North Vancouver is listed twice in the input
file (first with a cost of 1.2 and then with a cost of 2.9), our graph object however stores only the information
provided on the last one (cost 2.9) thanks to the design of the appendEdge member function of the Graph
class. This means it doesn’t matter how many times we may list edge connectivities between pairs of cities
because the graph will ultimately store only the information provided on the last one among all same edge
information provided in the input file.
Task 2
Implement the Vertex and the Graph classes that we will be using in our subsequent sections. Use the test
program given above to test your classes before proceeding to the next section. However please note that the
test program given above is not part of the project and should not be included in your submission.
Representing a path in a graph
A path in a graph will be represented as a list of vertices. In order to conserve memory however, we will not
store the actual Vertex objects along the path. Instead we will store only the indices of the Vertex objects in
the underlying graph. An example of a path in the illustration graph shown above might be a Path object
whose P member variable stores the elements: [5, 6, 2, 4]. Assuming that the vertex at index 5 of the
graph is Vancouver, the vertex at 6 of the graph is Burnaby, the vertex at index 2 of the graph is New
Westminster, and the vertex at index 4 of the graph is Port Coquitlam, then we see that the specified path
corresponds to [Vancouver  Burnaby  New Westminster  Port Coquitlam].
We will then use the underlying Graph object in order to find the costs of the edges along a path (that is edges
connecting successive elements of P) so that to be able to compute the total cost of the path (which is the sum
of the costs of the edges along the path). Moreover the underlying Graph object will, if we wish, help us to
validate a given path is a valid path in the graph.
Thus the following class declaration suffices to represent Path objects.
class Path
{
private:
SmarterArray<int> P; //The indices (singular index) the vertices along the path
public:
Path(); //Construct an empty path. Default object P.
int length() const; //Return the number of vertices along the path (the number of elements of P)
int find(const int &vertexIndex) const; //Return the index of an element of P such that P[index] == vertexIndex.
//If no element satisfies the condition, then return -1
//Do not perform assertion operation.
double computePathCost(const Graph &) const; //Compute the sum of the costs of edges along this path
CMPT 135 – FIC 202101 – Final Exam Project – Dr. Yonas T. Weldeselassie (Ph.D.) Page 12
//given the underlying Graph argument. Remember that the path object stores only vertex indices. Thus
//you need the underlying graph argument to determine the vertex objects in the graph that correspond to
//the indices. Then you will be able to find the edges that connect the vertices which will enable you to
//get the costs of the edges. The sum of the costs of these edges is returned from this function. If
//during the computation of the path cost, you find that there is no any edge in the underlying graph
//that connects successive elements in P, then it means your path is an invalid path and you
//need to abort your application.
//For example, if the Path object contains P = [3, 8, 6, 4, 9] then this function will return the
//cost(from vertex whose index in G is 3 to the vertex whose index in G is 8) +
//cost(from vertex whose index in G is 8 to the vertex whose index in G is 6) +
//cost(from vertex whose index in G is 6 to the vertex whose index in G is 4) +
//cost(from vertex whose index in G is 4 to the vertex whose index in G is 9)
int& operator [](const int &index) const; //Assert index is valid in P and then return P[index]
void insert(const int &index, const int &vertexIndex); //Assert the condition index >= 0 &&
//index <= the length and then insert the vertexIndex argument
//at the specified index. If index is equal to the length, then
//perform append.
void append(const int &vertexIndex); //Insert the argument as a last element.
void remove(const int &index); //Assert the index argument and then remove the element P[index]
SmarterArray<CMPT135_String> getPathNamesList(const Graph &) const; //Implemented for you
friend ostream& operator << (ostream &, const Path &); //Implemented for you.
};
SmarterArray<CMPT135_String> Path::getPathNamesList(const Graph &g) const
{
SmarterArray<CMPT135_String> path;
for (int i = 0; i < this->length(); i++)
{
int vertexIndex = (*this)[i];
path.append(g[vertexIndex].getName());
}
return path;
}
ostream& operator << (ostream &out, const Path &path)
{
out << “[“;
if (path.length() > 0)
{
for (int i = 0; i < path.length()-1; i++)
out << path[i] << ” -> “;
out << path[path.length()-1];
}
out << “]”;
return out;
}
Computing All Possible Paths: Pseudo-Code
In order to compute all the possible paths, all we need is to utilize our understanding of recursion as described
below. Suppose we would like to go from a given city named departure to another city named
destination in an underlying graph named g. Then the following algorithm implemented as a non-member
function will do the job.
Path computeMinCostPath(const Graph &g, const CMPT135_String &departure, const CMPT135_String
&destination, int &pathCount, Path &currentPath = Path())
The function will compute and print all the possible paths and then return the one with the minimum cost.
Because, we will need the information of the current partial path as we walk through the edges in the
underlying graph, this current partial path needs to pass as an argument to the function. Moreover, when we
first call this function from the main program, we need to start from an empty partial path which is why it is
initialized to a default empty Path object argument value. This way, we don’t need to pass this argument when
we call the function from within our main program. We would also like to count how many valid paths were
found while computing the minimum cost path which is why we have the pathCount parameter as well. Since
CMPT 135 – FIC 202101 – Final Exam Project – Dr. Yonas T. Weldeselassie (Ph.D.) Page 13
counting of valid paths needs to start from zero, the argument passed to this parameter needs to be initialized
to zero in the main program.
Detailed specification of the minimum cost path algorithm:

1. Assert there is at least one vertex in the graph g.
2. Compute depVertexIndex = index of the vertex in g whose name matches departure city
3. Compute desVertexIndex = index of the vertex in g whose name matches destination city
4. Assert both depVertexIndex and desVertexIndex are valid
5. Construct an empty Path object named minCostPath
6. If departure city == destination city, then
   o Nice! A valid path is found.
   o Assign minCostPath the currentPath
   o Append the desVertexIndex to the minCostPath object
   o Print the minCostPath and its cost as follows:
   cout << “Path found: ” << minCostPath << ” with cost ” <<
   minCostPath.computePathCost(g) << endl;
   o Increment the pathCount
   o Return the minCostPath
7. Else if the departure city already exists in the currentPath, then
   o Too bad! This is becoming a loop that we need to avoid
   o Assign minCostPath the currentPath
   o Return the minCostPath
8. Else
   o Compute depVertex = the vertex object in g whose name matches departure city
   o Compute E = the edge set of depVertex object
   o Append departure city to the currentPath
   o for (int i = 0; i < E.getSize(); i++) do the following steps
    Compute nextVertexName = the name of the destination vertex of the edge
   E[i] in g
    If nextVertexName is found in currentPath then we don’t need to walk along
   E[i] because it will create a loop. So we skip this iteration and go to
   the next iteration of the for loop.
    Compute a path starting from nextVertexName to destination. We can do this
   by calling the same function that we are implementing (recursion). The
   function call code is given for you
   Path candidatePath = computeMinCostPath(g, nextVertexName, destination, pathCount,
   currentPath);
    If candidatePath is empty then it is useless, so we skip this iteration
   and we go to the next iteration of the for loop.
    Else if the last element of the candidatePath is not equal to the
   destination, then it means the candidatePath did not reach the destination
   city. It means it got stuck somewhere and returned with a partial path.
   Thus it is useless and we discard it and therefore we skip this iteration
   CMPT 135 – FIC 202101 – Final Exam Project – Dr. Yonas T. Weldeselassie (Ph.D.) Page 14
   and we go to the next iteration of the for loop.
    Else if minCostPath is empty, then it means the candidatePath is our first
   successful path and hence we should assign it to the minCostPath. So
   assign minCostPath = candidatePath and go to the next iteration of the for
   loop.
    Else if the candidatePath has a lower cost than the minCostPath, then the
   candidatePath is better than the minCostPath. So assign minCostPath =
   candidatePath and go to the next iteration of the for loop.
   o Remove the last element of the currentPath object. (N.B: This statement is
   outside of the for loop but inside the Else block.)
   o Return minCostPath
9. Algorithm (function implementation) complete!!!
   Task 3
   Implement the Path class and the computeMinCostPath non-member function. This completes the project.
   Testing Your Work
   You may use the following test program to test your work.
   int main()
   {
   srand(time(0));
   Graph g(“ConnectivityMap1.txt”);
   cout << “Graph constructed successfully.” << endl;
   cout << g << endl;
   CMPT135_String departure, destination;
   int pathCount;
   for (int i = 0; i < 10; i++)
   {
   cout << endl << “Test #” << i+1 << endl;
   departure = g.getRandomVertexName();
   destination = g.getRandomVertexName();
   cout << “Computing shortest path from ” << departure << ” to ” << destination << endl;
   pathCount = 0;
   Path minCostPath = computeMinCostPath(g, departure, destination, pathCount);
   cout << “There were ” << pathCount << ” possible paths found.” << endl;
   cout << “The minimum cost path is: ” << minCostPath << ” Cost = ” << minCostPath.computePathCost(g) << endl;
   cout << “The cities along the minimum cost path are ” << endl;
   cout << “[“;
   if (minCostPath.length() > 0)
   {
   SmarterArray<CMPT135_String> p = minCostPath.getPathNamesList(g);
   for (int i = 0; i < p.getSize()-1; i++)
   cout << p[i] << ” -> “;
   cout << p[p.getSize()-1];
   }
   cout << “]” << endl << endl;
   }
   system(“Pause”);
   return 0;
   }
   Sample Run Output
   Graph constructed successfully.
   CMPT 135 – FIC 202101 – Final Exam Project – Dr. Yonas T. Weldeselassie (Ph.D.) Page 15
   The graph has 4 vertices.
   These vertices are
   Vertex at index 0 = Vancouver
   Vertex at index 1 = Burnaby
   Vertex at index 2 = North Vancouver
   Vertex at index 3 = Port Moody
   Each vertex together with its edge set looks like as follows
   Name = Vancouver
   Edge Set
   to —> 1, cost = 1.5
   to —> 2, cost = 2.9
   Name = Burnaby
   Edge Set
   to —> 0, cost = 1.5
   to —> 2, cost = 4.7
   to —> 3, cost = 3.6
   Name = North Vancouver
   Edge Set
   to —> 0, cost = 2.9
   to —> 1, cost = 4.7
   to —> 3, cost = 5.8
   Name = Port Moody
   Edge Set
   to —> 1, cost = 3.6
   to —> 2, cost = 5.8
   The graph connectivities are as follows…
   Vancouver Burnaby 1.50
   Vancouver North Vancouver 2.90
   Burnaby Vancouver 1.50
   Burnaby North Vancouver 4.70
   Burnaby Port Moody 3.60
   North Vancouver Vancouver 2.90
   North Vancouver Burnaby 4.70
   North Vancouver Port Moody 5.80
   Port Moody Burnaby 3.60
   Port Moody North Vancouver 5.80
   Test #1
   Computing shortest path from Port Moody to Burnaby
   Path found: [3 -> 1] with cost 3.6
   Path found: [3 -> 2 -> 0 -> 1] with cost 10.2
   Path found: [3 -> 2 -> 1] with cost 10.5
   There were 3 possible paths found.
   The minimum cost path is: [3 -> 1] Cost = 3.6
   The cities along the minimum cost path are
   [Port Moody -> Burnaby]
   Test #2
   Computing shortest path from Port Moody to Vancouver
   Path found: [3 -> 1 -> 0] with cost 5.1
   Path found: [3 -> 1 -> 2 -> 0] with cost 11.2
   Path found: [3 -> 2 -> 0] with cost 8.7
   Path found: [3 -> 2 -> 1 -> 0] with cost 12
   There were 4 possible paths found.
   The minimum cost path is: [3 -> 1 -> 0] Cost = 5.1
   The cities along the minimum cost path are
   [Port Moody -> Burnaby -> Vancouver]
   CMPT 135 – FIC 202101 – Final Exam Project – Dr. Yonas T. Weldeselassie (Ph.D.) Page 16
   Test #3
   Computing shortest path from North Vancouver to North Vancouver
   Path found: [2] with cost 0
   There were 1 possible paths found.
   The minimum cost path is: [2] Cost = 0
   The cities along the minimum cost path are
   [North Vancouver]
   Test #4
   Computing shortest path from Port Moody to Burnaby
   Path found: [3 -> 1] with cost 3.6
   Path found: [3 -> 2 -> 0 -> 1] with cost 10.2
   Path found: [3 -> 2 -> 1] with cost 10.5
   There were 3 possible paths found.
   The minimum cost path is: [3 -> 1] Cost = 3.6
   The cities along the minimum cost path are
   [Port Moody -> Burnaby]
   Test #5
   Computing shortest path from North Vancouver to Burnaby
   Path found: [2 -> 0 -> 1] with cost 4.4
   Path found: [2 -> 1] with cost 4.7
   Path found: [2 -> 3 -> 1] with cost 9.4
   There were 3 possible paths found.
   The minimum cost path is: [2 -> 0 -> 1] Cost = 4.4
   The cities along the minimum cost path are
   [North Vancouver -> Vancouver -> Burnaby]
   Test #6
   Computing shortest path from North Vancouver to North Vancouver
   Path found: [2] with cost 0
   There were 1 possible paths found.
   The minimum cost path is: [2] Cost = 0
   The cities along the minimum cost path are
   [North Vancouver]
   Test #7
   Computing shortest path from North Vancouver to Port Moody
   Path found: [2 -> 0 -> 1 -> 3] with cost 8
   Path found: [2 -> 1 -> 3] with cost 8.3
   Path found: [2 -> 3] with cost 5.8
   There were 3 possible paths found.
   The minimum cost path is: [2 -> 3] Cost = 5.8
   The cities along the minimum cost path are
   [North Vancouver -> Port Moody]
   Test #8
   Computing shortest path from North Vancouver to Burnaby
   Path found: [2 -> 0 -> 1] with cost 4.4
   Path found: [2 -> 1] with cost 4.7
   Path found: [2 -> 3 -> 1] with cost 9.4
   There were 3 possible paths found.
   The minimum cost path is: [2 -> 0 -> 1] Cost = 4.4
   The cities along the minimum cost path are
   [North Vancouver -> Vancouver -> Burnaby]
   Test #9
   CMPT 135 – FIC 202101 – Final Exam Project – Dr. Yonas T. Weldeselassie (Ph.D.) Page 17
   Computing shortest path from North Vancouver to Port Moody
   Path found: [2 -> 0 -> 1 -> 3] with cost 8
   Path found: [2 -> 1 -> 3] with cost 8.3
   Path found: [2 -> 3] with cost 5.8
   There were 3 possible paths found.
   The minimum cost path is: [2 -> 3] Cost = 5.8
   The cities along the minimum cost path are
   [North Vancouver -> Port Moody]
   Test #10
   Computing shortest path from North Vancouver to Burnaby
   Path found: [2 -> 0 -> 1] with cost 4.4
   Path found: [2 -> 1] with cost 4.7
   Path found: [2 -> 3 -> 1] with cost 9.4
   There were 3 possible paths found.
   The minimum cost path is: [2 -> 0 -> 1] Cost = 4.4
   The cities along the minimum cost path are
   [North Vancouver -> Vancouver -> Burnaby]
   Press any key to continue . . .
   Of course this is a very small input file designed to help test your work minimally. An input file
   (ConnectivityMap2.txt) that contains a bigger graph is posted together with this assignment in order to
   test your work more rigorously and a text file (TestProgram_and_Output.txt) containing a test program
   and its sample run output on the bigger graph is also posted together with the assignment.
   Starter Code
   You are given a text file (StarterCode.txt) that contains all the code segments given in the discussions
   above. You are required to copy the given code and provide all the missing parts and get the test program to
   work without any syntax, linking, runtime, or semantic errors. Please note that
    You are NOT allowed to add or remove any include directive or namespace.
    You are NOT allowed to change or modify any function signature.
    You are NOT allowed to add or remove any member, friend, or non-member function.
   Submission
   You are required to submit one source code file (that is.cpp file) that contains all the class declarations and
   definitions including the ones already implemented for you and any non-member function(s) that you are
   required to implement. You don’t need to submit any test program.
   Backtracking Algorithms
   The most important tasks in the computeMinCostPath algorithm above are the appending of the
   departure city to the current path (Step 8 just before the for loop) and the removal of the
   last element of the current path (Step 8 just after the for loop). That is, in order to go say from a
   departure place named A to a destination place named D and assuming A has edges only to places named B
   and C, then you first walk from A to B and try to reach D along that route. Although you will then walk from B
   to other possible places through valid edges in order to reach D, the fact that you will perform the walking in a
   recursive way means that when you finish the route through B; you will still remember you came to B from A.
   At that point, you walk back (i.e. you backtrack) to A and then restart searching for another route along the C.
   CMPT 135 – FIC 202101 – Final Exam Project – Dr. Yonas T. Weldeselassie (Ph.D.) Page 18
   This is the fundamental idea behind what are known as backtracking algorithms that allow us to solve
   complicated problems by doing something and then backtracking in order to try to do something else with the
   aim of finding all possible solutions to a problem and then pick the best solution.
   Backtracking algorithms are used in solving variety of problems such as
    Finding all the permutations of characters in a string,
    Finding all the subsets of a set,
    Finding all the solutions of Sudoku game board,
    Finding all possible moves in a chess game,
    Finding the best scheduling times (least conflicts) of exams or class times in a school,
    Finding the least number of colors needed to color objects stacked together in some form so that no
   adjacent objects are colored with the same color, and so on so forth.
   Afterwards…
   Once you are done with your project and submitted it, then go ahead and create a nice graph based on the
   cities in your own country and use your app to have a virtual tour and navigate your country. Moreover you
   may design your own projects to solve the problems stated above with carefully designed data structures and
   backtracking algorithms.
   That, at CMPT 135 level, will be cool, don’t you think?
   Have fun and enjoy your last touch of CMPT 135 202101 course at FIC!!!