代做CMPT 135编程设计、代写C++、C++程序语言调试

日期：2021-04-21 11:17

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!!!