Your assignment is to create a program that allows the reservation agents to quo
ID: 3824727 • Letter: Y
Question
Your assignment is to create a program that allows the reservation agents to quote mileage and airfare from the source airport to all destinations from that source including multiple (connecting) flight information. There is no information about departures or arrival times so you do not need to worry about them (to simplify the problem).
Your program reads the direct flight information and builds the directed graph. Allow the user to enter the file name to read.
Once your directed graph is built, print to the screen the Direct Flights report that shows the direct flights from each city (in alphabetical order by source airport abbreviation) with the mileage and airfare for each to confirm that you have read in the file correctly and built the graph correctly. Format the cost using a dollar sign, no cents (or decimals) will be given for the cost. The report is formatted as follows (this is an example and does not reflect the actual data you will be given):
Direct Flights
Source Dest Mileage Cost
------ ---- ------- ----
DEN SFA 1026 $119
DEN LAX 844 $45
LAX LV 231 $29
LAX SLC 581 $39
LV SLC 362 $19
LV PHX 256 $29
PHX DEN 586 $36
SLC DEN 379 $39
SLC SJC 585 $29
SJC SFO 51 $11
Allow the user to enter an airport abbreviation for a source airport and print the following Best Price Report (item 4 below) using airfare from that source to all reachable destinations from that source. Instruct and allow the user to press enter when they are finished viewing the report, continue in a loop so the user can continue to enter airport source abbreviations and view the report until they want to quit. Allow the user to enter the word “quit” as the airport abbreviation to end the program. Print appropriate instructions telling the user what they can do and what they must do to quit.
Write and use a shortest path algorithm to determine the shortest path by cost (airfare) to every reachable destination from the airport source abbreviation entered by the user. Maintain the path of connecting flights (list of airport abbreviations in the order they are visited, including the cost of each path, and mileage for each in determining the shortest path based on cost). As you determine the shortest path add the cost of the path to the cost to the final destination and add the mileage to the mileage for the final destination. Print the Best Price Report (example below) to the screen showing the source airport abbreviation (Source), final destination abbreviation (Dest), shortest path airfare (Cost), the mileage of that path (Mileage), and the connecting flight (intermediate path) information. The connecting flight information includes the source airport abbreviation for the connecting flight (Src), the destination airport abbreviation for the connecting flight (Dest), the airfare to the destination in the connecting flight (Cost), and the mileage for the connecting flight (Mileage). Here is an example (this is an example and does not reflect the actual data you will be using):
Best Price Report
Connecting Flight Information
Source Dest Cost Mileage Src Dest Cost Mileage
------ ---- ----- ------- --------------------------------------
SLC DEN $39 379 SLC->DEN $39 379
------ ---- ----- ------- --------------------------------------
SLC SJC $29 585 SLC->SJC $29 585
------ ---- ----- ------- --------------------------------------
SLC SFO $68 636 SLC->SJC $29 585
SJC->SFO $39 51
------ ---- ----- ------- --------------------------------------
Explanation / Answer
main.cpp
#include "ShortestPath.h"
#include "Graph.h"
#include "AirportDictionary.h"
using namespace std;
void main() {
Graph graph(15U);
/*
1. Your program reads the direct flight information and builds the directed graph. Allow the user to enter the file name to read. */
string airportName = "";
cout << "Enter the name of the file containing the graph >";
string fileName = "p7data.txt";
graph.load(fileName);
// graph.printAdjacencyMatrixByCost();
graph.printDirectFlightReport();
cout << "Select starting airport [x to quit] >";
cin >> airportName;
while (airportName != "x")
{
graph.getBestPriceReport(airportName);
cout << "Select another starting airport [x to quit] >";
cin >> airportName;
}
}
Airport.h
#pragma once
#include "ShortestPath.h"
#define NO_AIRPORT_NAME "None"
#define NO_AIRPORT_ID -1
typedef size_t airportId;
using namespace std;
struct Airport
{
string Name;
airportId Id;
Airport() :Name(NO_AIRPORT_NAME), Id(NO_AIRPORT_ID)
{}
Airport(const string& name, airportId id)
:Name(name), Id(id)
{}
};
AirportDictionary.cpp
#include "AirportDictionary.h"
AirportDictionary::AirportDictionary(size_t max) : _MAX(max), size(0)
{
for (size_t i = 0; i < _MAX; i++)
{
Airport a(NO_AIRPORT_NAME, NO_AIRPORT_ID);
_dictionary.push_back(a);
}
}
AirportDictionary::~AirportDictionary()
{
_dictionary.clear();
}
Airport AirportDictionary::getAirportById(const airportId& id) const
{
if (id < this->size)
{
for (size_t i = 0; i < this->size; i++)
{
if (_dictionary[i].Id == id)
return _dictionary[i];
}
}
string msg = "Airport with id '" + to_string(id) + "' not found";
throw notFoundException(msg);
}
size_t AirportDictionary::count() const
{
size_t count = 0;
count = this->size;
return count;
}
Airport AirportDictionary::getAirportByName(const string& name) const
{
for (size_t i = 0; i < _MAX; i++)
{
if (_dictionary[i].Name == name)
return _dictionary[i];
}
throw notFoundException("Airport named '" + name + "' not found");
}
Airport AirportDictionary::addAirportByName(const string& name)
{
for (size_t newIx = 0; newIx < _MAX; newIx++)
{
if (_dictionary[newIx].Name == name)
return _dictionary[newIx];
else if (_dictionary[newIx].Name == NO_AIRPORT_NAME)
{
this->size++;
Airport a(name, newIx);
_dictionary[newIx] = a;
return a;
}
}
throw dictionaryFullException();
}
AirportDictionary.h
#pragma once
#include "ShortestPath.h"
#include "Airport.h"
#define NAME_COLUMN 0
#define ID_COLUMN 1
using namespace std;
class AirportDictionary
{
private:
size_t _MAX;
vector<Airport> _dictionary;
size_t size;
public:
Airport getAirportById(const airportId&) const;
Airport getAirportByName(const string& name) const;
Airport addAirportByName(const string& name);
AirportDictionary()
:AirportDictionary(DEFAULT_MAX)
{}
size_t count() const;
AirportDictionary(size_t max);
~AirportDictionary();
};
Flight.cpp
#include "Flight.h"
void Flight::addConnection(Flight& connection, bool addToFront)
{
//Flight* newConn = new Flight(connection);
TotalCost += connection.RouteCost;
TotalMileage += connection.RouteMileage;
connection.TotalCost = TotalCost;
connection.TotalMileage = TotalMileage;
Flight conn(connection);
/*if (addToFront)
this->Connections.push_front(connection);
else*/
this->Connections.push_back(connection);
this->Destination = connection.Destination;
}
Flight.h
#pragma once
#include "ShortestPath.h"
#include "AirportDictionary.h"
#include <deque>
#include <stack>
using namespace std;
class Flight
{
public:
Airport Source;
Airport Destination;
vector<Flight>Connections;
int RouteCost;
int RouteMileage;
int weight;
int TotalCost;
int TotalMileage;
Flight()
:RouteCost(Infinity), TotalCost(Infinity),
RouteMileage(Infinity), TotalMileage(Infinity),
Source(NO_AIRPORT_NAME, NO_AIRPORT_ID),
Destination(NO_AIRPORT_NAME, NO_AIRPORT_ID)
, Connections()
{}
Flight(Airport& source, Airport& dest, int cost, int mileage)
:
Source(source), Destination(dest),
RouteCost(cost), TotalCost(cost),
RouteMileage(mileage), TotalMileage(mileage)
, Connections()
{ }
Flight(const Flight& right) :
Source(right.Source), Destination(right.Destination),
RouteCost(right.RouteCost), TotalCost(right.TotalCost),
RouteMileage(right.RouteMileage), TotalMileage(right.TotalMileage)
, Connections(right.Connections)
{
}
void addConnection(Flight& connection, bool addToFront = false);
};
Graph.cpp
#include "Graph.h"
#include <stack>
using namespace std;
Graph::Graph(size_t max)
: MAX_SIZE(max),
airports(max)
{
// Initialize graph
Flight f;
vector<Flight> row(MAX_SIZE, f);
_graph = vector<vector<Flight>>(MAX_SIZE, row);
}
void Graph::throwIfOutOfRange(int i) const
{
if (!isInRange(i))
throw outOfRangeException();
}
bool Graph::hasDirectEdge(vertex& i, vertex& j) const
{
try
{
throwIfOutOfRange(i);
throwIfOutOfRange(j);
return (_graph[i][j].RouteCost < Infinity);
}
catch (const outOfRangeException&)
{
return false;
}
}
bool Graph::vertexIsAllowed(vector<vertex>& vect, vertex& val) const
{
size_t maxSize = getMaxSize();
for (size_t i = 0; i < vect.size() && i < maxSize; i++)
{
if (vect[i] == val)
return true;
}
return false;
}
void Graph::load(const string& fileName)
{
string sourceName, destName, costFormatted;
int mileage, cost;
Airport source, dest;
ifstream file;
file.open(fileName);
if (!file.bad())
{
for (size_t i = 0; i < MAX_SIZE && !file.eof(); i++)
{
file >> sourceName;
throwIfFileBad(file);
file >> destName;
throwIfFileBad(file);
file >> mileage;
throwIfFileBad(file);
file >> cost;
throwIfFileBad(file);
source = airports.addAirportByName(sourceName);
dest = airports.addAirportByName(destName);
costFormatted = "$" + cost;
Flight f(source, dest, cost, mileage);
_graph[source.Id][dest.Id] = f;
}
}
else
{
throw fileOpenException("Error Opening file");
}
}
vertex Graph::getIndexOfSmallestVertexValue(const vector<int>& weights, const vertex& startIndex) const
{
int smallest = Infinity;
size_t maxSize = getMaxSize();
vertex v = startIndex;
for (size_t i = v; i < maxSize; i++)
{
int candidate = weights[i];
if (candidate < Infinity && candidate < smallest)
{
smallest = candidate;
v = i;
}
}
return v;
}
FlightReport Graph::getBestPath(const airportId& start) const
{
size_t maxSize = getMaxSize();
vector<int> distance;
//vector<int> costs;
vector<Flight> row = _graph[start];
vector<Flight> reachedSet;
vector<int> predecessor;
vector<Flight> route;
vector<vertex> allowed_vertices;
Flight f;
Airport starting = airports.getAirportById(start);
vector<FlightReport> reports;
// permitted path: path where each vertex except the final vertex must be in the path
// initialize the distance array
for (size_t i = 0; i < maxSize; i++)
{
if (i == start)
{
distance.push_back(0);
}
else
distance.push_back(row[i].RouteCost);
predecessor.push_back(Infinity);
}
// find allowed vertices
for (vertex allowed_size = 1; allowed_size <= maxSize; ++allowed_size)
{
vertex next = getIndexOfSmallestVertexValue(distance, allowed_size);
if (next < Infinity && !vertexIsAllowed(allowed_vertices, next))
{
allowed_vertices.push_back(next);
int sum = 0;
vertex finalId = 0;
Airport finalDestination;
for (vertex v = 0; v < maxSize; ++v)
{
if (!vertexIsAllowed(allowed_vertices, v) && hasDirectEdge(next, v))
{
sum = distance[next] + _graph[next][v].RouteCost;
if (sum < distance[v])
{
distance[v] = sum;
Flight f = _graph[next][v];
reachedSet.push_back(f);
predecessor[v] = next;
finalId = v;
}
}
}
vector<Flight>flightRoute;
vertex vertex_on_path = finalId;
vertex last = start;
//flightRoute.push_back()
while (vertex_on_path != start)
{
if (distance[vertex_on_path] != Infinity)
{
vertex_on_path = predecessor[vertex_on_path];
}
}
}
}
Airport end;
FlightReport report(starting, end, route, distance, allowed_vertices, reachedSet);
return report;
}
void Graph::getBestPriceReport(const string& airportName) const
{
Airport startingAirport = airports.getAirportByName(airportName);
dijkstra(startingAirport.Id);
return;
//Airport startingAirport = airports.getAirportByName(airportName);
string lineBreak = "------ ---- ----- ------- --------------------------------------";
FlightReport report = getBestPath(startingAirport.Id);
size_t maxSize = getMaxSize();
for (size_t i = 0; i < maxSize; i++)
{
if (report.Route.size() > 0)
{
cout << "Best Price Report" << endl
<< " Connecting Flight Information" << endl
<< "Source Dest Cost Mileage Src Dest Cost Mileage" << endl
<< lineBreak;
}
}
}
void Graph::printDirectFlightReport() const
{
size_t maxSize = getMaxSize();
cout
<< "Direct Flights" << endl
<< "Source Dest Mileage Cost" << endl
<< "---- ---- ------ -----" << endl;
for (size_t srcId = 0; srcId < maxSize; srcId++)
{
for (size_t destId = 0; destId < maxSize; destId++)
{
Flight f = getFlight(srcId, destId);
if (f.RouteCost != Infinity)
{
cout << f.Source.Name << " " << f.Destination.Name << " " << f.RouteMileage << " $" << f.RouteCost << endl;
}
}
}
}
void Graph::printAdjacencyMatrixByCost(bool writeToFile) const
{
stringstream stream;
size_t numAirports = getMaxSize();
stream << " ";
for (size_t srcId = 0; srcId < numAirports; srcId++)
stream << srcId << " " << airports.getAirportById(srcId).Name << " ";
stream << endl;
for (size_t srcId = 0; srcId < numAirports; srcId++)
{
Airport source = airports.getAirportById(srcId);
stream << srcId << " " << source.Name << " ";
for (size_t destId = 0; destId < numAirports; destId++)
{
Flight f = getFlight(srcId, destId);
if (f.RouteCost != Infinity)
stream << f.RouteCost;
else
stream << "-";
stream << " ";
}
stream << endl;
}
cout << stream.str();
if (writeToFile)
{
ofstream outF;
outF.open("adjacencyMatrix.txt");
outF << stream.str();
outF.close();
}
}
int Graph::minDistance(const vector<int>& dist, const vector<bool>& reachedSet) const
{
// Initialize min value
int min = Infinity, min_index = 0;
int maxSize = getMaxSize();
for (int v = 0; v < maxSize; v++)
if (!reachedSet[v] && dist[v] <= min) {
min = dist[v];
min_index = v;
}
return min_index;
}
void Graph::dijkstra(int src) const
{
size_t maxSize = getMaxSize();
vector<int> distance(maxSize, Infinity); // The output array. dist[i] will hold the shortest
// distance from src to i
vector<int> predecessor(maxSize, Infinity);
vector<bool> reachedSet(maxSize, false); // sptSet[i] will true if vertex i is included in shortest
// path tree or shortest distance from src to i is finalized
Flight f;
vector<Flight> routes(maxSize, f);
vector<FlightReport> report;
for (size_t i = 0; i < maxSize; i++)
distance[i] = getFlight(src, i).RouteCost;
// Distance of source vertex from itself is always 0
distance[src] = 0;
Airport startingAirport = airports.getAirportById(src);
// Find shortest path for all vertices
for (vertex count = 0; count < maxSize - 1; count++)
{
// Pick the minimum distance vertex from the set of vertices not
// yet processed. u is always equal to src in first iteration.
int next = minDistance(distance, reachedSet);
f = getFlight(src, next);
try
{
f.Source = startingAirport;
f.Destination = airports.getAirportById(next);
}
catch (const notFoundException&)
{
reachedSet[next] = true;
continue;
}
reachedSet[next] = true;
if (next == src)
continue;
// Update dist value of the adjacent vertices of the picked vertex.
for (vertex v = 0; v < maxSize; v++)
{
Flight connection = getFlight(next, v);
int sum = (distance[next] + connection.RouteCost);
if (!reachedSet[v] && connection.RouteCost != Infinity && distance[next] != Infinity && sum < distance[v])
{
distance[v] = sum,
predecessor[v] = next;
}
}
if (f.RouteCost != Infinity)
routes.push_back(f);
}
vector<Flight> finalRoutes;
for (size_t v = 0; v < maxSize; v++)
{
vertex vertex_on_path = v;
stack<Flight> flights;
if (distance[v] != Infinity)
{
if (predecessor[vertex_on_path] != Infinity)
{
while (vertex_on_path != src && predecessor[vertex_on_path] != Infinity)
{
Flight fl = getFlight(predecessor[vertex_on_path], vertex_on_path);
vertex_on_path = predecessor[vertex_on_path];
if (fl.RouteCost != Infinity)
flights.push(fl);
}
if (!flights.empty())
{
Flight finalFl = getFlight(src, flights.top().Source.Id);
flights.push(finalFl);
finalFl.weight = distance[v];
while (!flights.empty())
{
Flight connection = flights.top();
finalFl.addConnection(connection);
flights.pop();
}
if (finalFl.Source.Name != NO_AIRPORT_NAME)
finalRoutes.push_back(finalFl);
}
}
else
{
Flight f = getFlight(src, v);
if (f.Source.Name != NO_AIRPORT_NAME)
finalRoutes.push_back(f);
}
}
}
printRoutes(finalRoutes);
}
Flight Graph::getFlight(const vertex& srcId, const vertex& destId) const
{
throwIfOutOfRange(srcId);
throwIfOutOfRange(destId);
return _graph[srcId][destId];
}
Flight Graph::getFlight(const string& src, const string& dest) const
{
Airport source = airports.getAirportByName(src),
destination = airports.getAirportByName(dest);
return getFlight(source.Id, destination.Id);
}
void Graph::printRoutes(const vector<Flight>& routes) const
{
string lineBreak = "------ ---- ----- ------- --------------------------------------";
if (routes.size() > 0)
{
cout << endl << "Best Price Report from " << routes[0].Source.Name << endl
<< " Connecting Flight Information" << endl
<< "Source Dest Cost Mileage Src Dest Cost Mileage" << endl
<< lineBreak << endl;
}
for (size_t i = 0; i < routes.size(); i++)
{
Flight f = routes[i];
if (f.Source.Name != NO_AIRPORT_NAME)
{
cout << f.Source.Name << " " << f.Destination.Name << " $" << f.TotalCost << " " << f.TotalMileage << " ";
if (f.Connections.size() == 0)
cout << "Direct" << endl;
else
for (size_t i = 0; i < f.Connections.size(); i++)
{
Flight connection = f.Connections[i];
cout << connection.Source.Name << " -> " << connection.Destination.Name << " $" << connection.RouteCost << " " << connection.RouteMileage << endl;
if (i + 1 != f.Connections.size())
cout << " ";
}
cout << lineBreak << endl;
}
}
cout << endl;
}
Graph.h
#pragma once
#include "ShortestPath.h"
#include "AirportDictionary.h"
#include "Flight.h"
using namespace std;
struct FlightReport {
vector<Flight> Route;
vector<int> Weights;
vector<vertex> AllowedVertices;
vector<Flight> ReachedSet;
int TotalCost;
Airport Source;
Airport Destination;
FlightReport(Airport& source, Airport& destination, const vector<Flight>& route, const vector<int>& weights, const vector<vertex>& allowed_vertices, const vector<Flight>&reachedSet)
:Source(source), Destination(destination),
Route(route), Weights(weights), AllowedVertices(allowed_vertices), ReachedSet(reachedSet)
{ }
};
class Graph
{
private:
size_t MAX_SIZE;
vector<vector<Flight>> _graph;
AirportDictionary airports;
bool isInRange(size_t i) const
{
return (i >= 0 && i < MAX_SIZE);
}
void throwIfOutOfRange(int i) const;
bool hasDirectEdge(vertex& i, vertex& j) const;
bool vertexIsAllowed(vector<vertex>& vect, vertex& val) const;
vertex getIndexOfSmallestVertexValue(const vector<int>& weights, const vertex& startIndex) const;
FlightReport getBestPath(const airportId& srcRow) const;
void dijkstra(int src) const;
int minDistance(const vector<int>& dist, const vector<bool>& sptSet) const;
void printRoutes(const vector<Flight>& routes) const;
size_t getMaxSize() const { return airports.count(); }
public:
Graph(size_t max = DEFAULT_MAX);
~Graph() { _graph.clear(); }
Flight getFlight(const vertex& srcId, const vertex& destId) const;
Flight getFlight(const string& srcId, const string& destId) const;
void printDirectFlightReport() const;
void printAdjacencyMatrixByCost(bool writeToFile = false)const;
void load(const string& fileName);
void getBestPriceReport(const string& airportName) const;
};
ShortestPath.cpp
#include "ShortestPath.h"
int min(int a, int b) { return a > b ? b : a; }
int max(int a, int b) { return a > b ? a : b; }
void throwIfFileBad(const ifstream& file) {
bool good = file.good(),
bad = file.bad(),
eof = file.eof(),
fail = file.eof();
if (file.bad())
throw fileReadException("Error opening file");
}
ShortestPath.h
#pragma once
#include <string>
#include <iostream>
#include <fstream>
#include <vector>
#include <sstream>
using namespace std;
#define DEFAULT_MAX 10U
#define Infinity (INT_MAX - 10000)
class outOfRangeException :public exception
{
public:
outOfRangeException(string msg = "Index out of range") :exception(msg.c_str())
{ }
};
class dictionaryFullException :public exception
{
public:
dictionaryFullException(string msg = "Dictionary is full") :exception(msg.c_str())
{ }
};
class fileOpenException :public exception
{
public:
fileOpenException(string msg = "Error opening file") :exception(msg.c_str())
{ }
};
class fileReadException :public exception
{
public:
fileReadException(string msg = "Error reading file") :exception(msg.c_str())
{ }
};
class notFoundException : public exception
{
public:
notFoundException(string msg = "Item not found") :exception(msg.c_str())
{ }
};
typedef size_t vertex;
int min(int a, int b);
int max(int a, int b);
void throwIfFileBad(const ifstream& file);
p7data.txt
SFA SLC 700 59
SFO LV 420 39
LAX LV 231 23
LV SLC 362 29
LAX SFO 344 39
LAX SLC 581 57
SFA SFO 679 67
SFO SLC 605 19
PHX DEN 586 65
LV PHX 256 21
DEN SFA 1026 72
DEN LAX 844 69
SLC DEN 379 49
SLC SJC 585 29
SJC SFO 51 19
adjacencyMatrix.txt
SFA SLC SFO LV LAX PHX DEN SJC
SFA - 59 67 - - - - -
SLC - - - - - - 49 29
SFO - 19 - 39 - - - -
LV - 29 - - - 21 - -
LAX - 57 39 23 - - - -
PHX - - - - - - 65 -
DEN 72 - - - 69 - - -
SJC - - 19 - - - - -
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.