C++ Flight Program You must use a graph to write the program -------------------
ID: 3863229 • Letter: C
Question
C++ Flight Program
You must use a graph to write the program
--------------------------------------------------------------------------------------------------------
For the Graphs, Verticies Weights and Edges are stored in below load.txt file
These vertices, edges and weights are stored in the text file named load.txt file at the bottom. When the program starts, it will use the load.txt file to load the vertices, edges and weights into your program.
--------------------------------------------------------------------------------------------------------
Flight Types (Files at bottom)
Connected Flights:
A direct connection means you can fly from the departure city to the destination city without having to first fly through another city. For this type of connection, you list the departure city, the destination city, and the distance between the two cities.
Through Flights (Listed Below):
A through connection means you can fly from the departure city to the destination city, but you first have to fly to at least one other city. For this type of connection, you list the departure city, the destination city, each city between the departure city and the destination city which is part of the connection, and the total distance between the departure city and the destination city.
--------------------------------------------------------------------------------------------------------
Program Startup
As mentioned above, when the program starts, it will use the load.txt file to load the vertices, edges and weights into the graph. The program then will display a menu, and prompt the user to enter a choice:
1. Choose departure city
2. Exit
You may assume the user enters 1 or 2. No input validation is required.
If the user chooses 2. Exit, then the program ends.
Program lists Departure Cities, and user chooses
If the user choose 1. Choose departure city, then the program lists the cities. The cities don't have to be listed in any particular order. However, an ascending letter or number should be to the left of each city so the user can use that letter or number to choose a city. For example:
1. Los Angeles
2. Beijing
3. San Diego
(and so on)
Choose city:
or
A. Los Angeles
B. Beijing
C. San Diego
(and so on)
Choose city:
You may assume the user enters a valid number or letter; no input validation is required.
--------------------------------------------------------------------------------------------------------
Program lists Destination Cities, and user chooses
Once a user chooses a city, then the program displays "Destination cites" followed by all of the cities except the departure city. Again, the cities don't have to be listed in any particular order, but an ascending letter or number should be to the left of each city so the user can use that letter or number to choose a city.
You again may assume the user enters a valid number or letter; no input validation is required.
--------------------------------------------------------------------------------------------------------
If no connection
Once the user chooses a destination city, if there is no direct or through connection between the departure and destination cities, then the program will output:
No connection between [name of departure city] and [name of destination city]
Press any key to return to menu.
After the user presses the any key (we'll assume the user has an any key on their keyboard :-), then the menu which displayed at the program startup (1. Choose departure city 2. Exit) will re-display and the program will continue as stated above.
--------------------------------------------------------------------------------------------------------
If connection, direct connection?
If there is some connection between the departure and destination cities (See load.txt and connected cities notes below) ... the next issue is whether there is a direct connection between the departure and destination cities.
If there is no direct connection between the departure and destination cities (in other words, only a through connection), then the program will output:
No direction connection between [name of departure city] and [name of destination city]
Then the program will output the information in the next section (If connection is a through connection?).
If there is a direct connection between the departure and destination cities (there presumably only would be one), then the program will output:
Direct connection between [name of departure city] and [name of destination city]
Then the program will output the information in the next section (If connection, through connection?).
--------------------------------------------------------------------------------------------------------
If connection, through connection?
If there is no through connection between the departure and destination cities (in other words, only a direct connection), then the program will output:
No through connection between [name of departure city] and [name of destination city]
Press any key to return to menu [after which the menu displayed at program startup is re-displayed]
If there is at least one through connection between the departure and destination cities, then the program will output all through connections (there may be more than one) in ascending order of distance, listing the intermediate cities, as follows:
Through connection between [name of departure city] and [name of destination city] via [list name or names of cities in between] - [number of miles] miles
After this listing, the program prompts the user to "Press any key to return to menu", after which the menu displayed at program startup is re-displayed.
NEEDED FILES:
//load.txt file
//Direct Connections
Los Angeles, Anchorage, 2340
Anchorage, Beijing,3970
Beijing, Los Angeles, 6260
Los Angeles, Maui, 2490
Maui, San Diego, 2540
San Diego, Las Vegas, 265
Los Angeles, San Diego, 200
//Connecting Cities Notes
//Through Connections
Maui , Los Angeles, Beijing
Maui, Los Angeles, Anchorage
Maui, San Diego, Las Vegas
Las Vegas, San Diego, Las Angeles, Beijing
Explanation / Answer
this program sloves the problem by using FloydWarshall's algorithm, but here im not making use of graphinsted i use the function within the program to initilize the routes.
#include <fstream.h>
#include <stdlib.h>
#include <string.h>
#include "Initialize.h"
#include "Array.h"
#include "Table.h"
#include "Stack.h"
int main(int argc, char * argv[]) {
try {
ifstream in;
// Check arguments
getArgs(argc, argv, in);
// Get number of cities from first line of file
char buf[MAX_LINE_LENGTH];
in.getline(buf,MAX_LINE_LENGTH-1);
int cities = atoi(buf);
if(!cities)
throw MyException("File does not have number of cities as the first line.");
// Construct Distance and Predecessor matrices
Array DistMat(cities,cities);
Array PMatrix(cities,cities);
//Initialize the matrices
InitMatrices(DistMat, PMatrix, cities);
// Construct the String Table
Table st(cities,MAX_STRING_LENGTH);
// Read in the data file
getDAta(in, st, buf, DistMat, PMatrix);
// Check if command line city names are in the data file
bool ArgCheck = TestArgs(argv[1],cities,st);
if(!ArgCheck) {
throw MyException("Start city not found in map file.");
}
char * StartCity = argv[1];
ArgCheck = TestArgs(argv[2],cities,st);
if(!ArgCheck) {
throw MyException("End city not found in map file.");
}
char * EndCity = argv[2];
// Floyd-Warshall Algorithm function
FloydWarshall(DistMat, PMatrix, cities);
// Construct Stack
Stack Reverse(sizeof(int));
// Place route cities on stack
StackCities(StartCity, EndCity, DistMat, PMatrix, st, Reverse);
// Display the route
DispRoute(Reverse, st);
// Display the Intervening cities and the distances between
DispItinerary(st, StartCity, EndCity, DistMat, Reverse);
}catch (MyException e) {
cout<<e.getMessage()<<endl<<endl;
return 1;
}
return 0;
}
// Check arguments and open country file
void getArgs(int argc, char* argv[], ifstream &in) {
if (argc != 4) {
throw MyException("Wrong Number of arguments.");
}else {
in.open(argv[3],ios::in|ios::nocreate);
if (!in) {
throw MyException("Could not open map file.");
}
}
}
// Check if command line city names are in the data file
bool TestArgs (char * Arg,int NumCities,Table &st) {
int TestString;
for(int a=0;a<NumCities;a++) {
TestString = strcmp(Arg,st.getString(a));
if (TestString == 0) return true;
}
return false; // City name not found
}
// Display the route
void DispRoute(Stack &Reverse, Table &st) {
int CityIndex;
cout<<" "<<"The shortest route is as follows: ";
for(int m=Reverse.getNumber(); m>-1; m--) {
CityIndex = *(int *)Reverse.Read(m);
cout<<st.getString(CityIndex)<<" ";
}
//cout<<endl;
}
//Initialize the matrices
void InitMatrices(Array &DistMat,
Array &PMatrix, int cities) {
for(int p=0; p<cities; p++) { // Initialize distance matrix
for (int q=0; q<cities; q++) {
if (p == q) {
DistMat(p, q) = 0;
PMatrix(p, q) = 9999;
}else {
DistMat(p, q) = 9999; // 9999 = infinity
}
}
}
}
// Read in the map data from the data file
void getDAta(ifstream &in, Table &st, char * buf,
Array &DistMat, Array &PMatrix) {
char * C1 = {0};
char * C2 = {0};
char * DistTemp;
char * Trash = {0};
int C1Index;
int C2Index;
int Distance;
while (in.getline(buf,MAX_LINE_LENGTH)) { // Get next line of data
C1Index=NOTFOUND; // NOTFOUND = -1
C2Index=NOTFOUND;
if(C1=strtok(buf,DELIMITER)) { // Skips blank lines in map file
C2=strtok(NULL,DELIMITER);
if (C2 == NULL) // No second city
throw MyException("Data read error in map file. No delimiter?");
DistTemp=strtok(NULL,DELIMITER);
if (DistTemp == NULL) // No distance at end of line
throw MyException("Data read error in map file. No delimiter?");
Trash = strtok(NULL,DELIMITER);
if (Trash != NULL) // Extra data at end of line
throw MyException("Unrecognized data in map file. Too many items on line?");
Distance=atoi(DistTemp);
if(!Distance) // Data at end of line is not an integer
throw MyException("Data read error in map file. No distance?");
C1Index=st.addString(C1); // Add city to string table
C2Index=st.addString(C2);
DistMat(C1Index, C2Index) = Distance; // Seed distance matrix
PMatrix(C1Index, C2Index) = C1Index; // Seed predecessor matrix
}
}
in.close();
}
// Floyd-Warshall Algorithm function
void FloydWarshall(Array &DistMat,
Array &PMatrix, int cities) {
int DistAdder;
for (int k=0; k<cities; k++) {
for (int i=0; i<cities; i++) {
for (int j=0; j<cities; j++) {
DistAdder = DistMat(i, k) + DistMat(k, j);
if( DistAdder < DistMat(i, j)) {
DistMat(i, j) = DistAdder; // Update distance matrix
PMatrix(i, j) = PMatrix(k, j); // Update predecessor matrix
}
}
}
}
}
void StackCities(char * StartCity, char * EndCity,
Array &DistMat,
Array &PMatrix,
Table &st, Stack &Reverse) {
int Previous = st.getIndex(EndCity);
if (!Reverse.Push(&Previous)) {
throw MyException("Stack 'Push' failure");
}
while(PMatrix(st.getIndex(StartCity),Previous) != st.getIndex(StartCity)) {
Previous = PMatrix(st.getIndex(StartCity),Previous);
if (!Reverse.Push(&Previous)) {
throw MyException("Stack 'Push' failure");
}
}
// Stack the start city
Previous = st.getIndex(StartCity);
if (!Reverse.Push(&Previous)) {
throw MyException("Stack 'Push' failure");
}
}
// Display the Intervening cities and the distances between them
void DispItinerary(Table &st, char * StartCity, char * EndCity,
Array &DistMat, Stack &Reverse) {
int RouteDistance;
int Total;
int NameLength1;
int NameLength2;
int Space1;
int Space2;
const char * RouteC1;
const char * RouteC2;
int DisplayDistance = DistMat(st.getIndex(StartCity),st.getIndex(EndCity));
cout<<" The shortest distance from "
<<StartCity<<" to "<<EndCity<<" is "
<<DisplayDistance<<" kilometers."<<endl<<endl;
cout<<" | Distances in kilometers between cities on the shortest route |"<<endl;
cout<<" | | | Distance | Cumulative |"<<endl;
cout<<" | From | To | Between Cities | Distance |"<<endl;
for (int n=Reverse.getNumber(); n>0; n--) {
RouteDistance = DistMat(*(int *)Reverse.Read(n),*(int *)Reverse.Read(n-1));
RouteC1 = st.getString(*(int *)Reverse.Read(n));
NameLength1 = strlen(RouteC1);
Space1 = 15 - NameLength1;
RouteC2 = st.getString(*(int *)Reverse.Read(n-1));
NameLength2 = strlen(RouteC2);
Space2 = 15 - NameLength2;
Total = DistMat(st.getIndex(StartCity),*(int *)Reverse.Read(n-1));
cout<<" | "<<RouteC1;
for (int y=0; y<Space1; y++) cout<<" ";
cout<<" | "<<RouteC2;
for (y=0; y<Space2; y++) cout<<" ";
cout<<" | "<<RouteDistance<<" ";
if (RouteDistance <10 )cout<<" | ";
else if(RouteDistance <100 )cout<<" | ";
else if(RouteDistance <1000) cout<<" | ";
else cout<<" | ";
cout<<Total;
if (Total <10 )cout<<" | ";
else if(Total <100 )cout<<" | ";
else if(Total <1000 )cout<<" | ";
else cout<<" | ";
}
cout<<" +------------------+------------------+----------------+--------------+"<<endl;
}
initilize.h
#ifndef InitilizeHEADER_H
#define InitilizeHEADER_H
#include "Table.h"
#include "Array.h"
#include "Stack.h"
#define MAX_LINE 212
#define MAX_STRING 42
#define DELIMITER ","
#define NOTFOUND -1
bool TestArgs (char * Arg,int NumCities,Table &st);
void PrintChart(int cities, Table &st, Array &PArray);
void DispItinerary(Table &st, char * StartCity, char * EndCity, Array &DistMat, Stack &Reverse);
void DispRoute(Stack &Reverse, Table &st);
void InitMatrices(Array &DistMat, Array &PMatrix, int cities);
void getDAta(ifstream &in, Table &st, char * buf, Array &DistMat, Array &PMatrix);
void FloydWarshall(Array &DistMat, Array &PMatrix, int cities);
void StackCities(char * StartCity, char * EndCity, Array &DistMat, Array &PMatrix, Table &st, Stack &Reverse);
void getArgs(int argc, char* argv[], ifstream &in);
#endif
stack.h
#ifndef STACK_H
#define STACK_H
class Stack {
protected:
enum {INCREMENT=16};
int size;
int Quantity;
int Next;
unsigned char *Storage;
bool Inflate(int Increase);
public:
Stack(int Size);
~Stack();
void *Read(int index);
int getNumber(){return Next-1;}
bool Push(void *Data);
void *Pop();
bool IsEmpty();
};
#endif
Table.h
#ifndef TABLE_H
#define TABLE_H
#ifndef GENERIC1DARRAY_H
#define GENERIC1DARRAY_H
#ifndef MYEXCEPTION_H
#define MYEXCEPTION_H
#include <string.h> // For strncpy()
class MyException {
private:
char message[128];
int errCode;
public:
MyException(char* errorMsg, int errNum = 0) {
strncpy(message, errorMsg,128);
message[127] = 0;
errCode = errNum;
}
const char* getMessage() {return(message);}
int getErrCode() {return errCode;}
};
#endif //myException
class Generic1DArray {
protected:
int elSize; // Size of each space
int quantity; // Number of storage spaces
unsigned char* storage;
public:
Generic1DArray(int nEls, int sz) {
quantity = nEls;
elSize = sz;
int Size = quantity * elSize;
storage = new unsigned char [Size];
}
Generic1DArray::~Generic1DArray() {
if(storage != 0) delete []storage;
}
void add(void* element, int inx) {
if (inx < 0 || inx >= quantity)
throw MyException("Generic1DArray add",inx);
memcpy(&(storage[inx*elSize]), element, elSize);
if(!storage) {
throw MyException("memcpy error - add Generic1DArray");
}
}
void* fetch(int index) const {
if(index >= quantity || index < 0) return 0;
// Return address of desired element:
return &(storage[index * elSize]);
}
};
#endif //Generic
class Table : public Generic1DArray {
protected:
int next;
public:
Table(int numElements, int elSize) : Generic1DArray(numElements, elSize) {
next = 0;
}
enum {NOTFOUND = -1};
const char* getString(int index) {
if(index < 0 || index >= next)
throw MyException("Index out of bounds Table.getString");
return (const char*) fetch(index);
}
int getIndex(const char* s) {
int check;
for (int k=0; k<quantity; k++) {
check = strcmp(s,(const char*)fetch(k));
if (check == 0) return (k);
}
return NOTFOUND;
}
int addString(const char* s) {
int index = getIndex(s);
if(index != NOTFOUND) return (index); // If index is found
add((void*)s, next);
return(next++);
}
};
#endif //TABLE_H
Array.h
#ifndef ARRAY_H
#define ARRAY_H
#ifndef ONEDINTARRAY_H
#define ONEDINTARRAY_H
#include "Generic1DArray.h"
#include "MyException.h"
class OneDIntArray : protected Generic1DArray {
public:
OneDIntArray(int numElements) : Generic1DArray(numElements, sizeof(int)) {}
int& operator[](int index) {
if (index < 0 || index >= quantity) //Indexes are zero based
throw MyException("OneDIntArray operator[]");
int offset = index * sizeof(int);
int *p = (int*) &(storage[offset]);
return (*p); // Dereference p
}
};
#endif //ONEDINTARRAY_H
#ifndef MYEXCEPTION_H
#define MYEXCEPTION_H
#include <string.h> // For strncpy()
class MyException {
private:
char message[128];
int errCode;
public:
MyException(char* errorMsg, int errNum = 0) {
strncpy(message, errorMsg,128);
message[127] = 0;
errCode = errNum;
}
const char* getMessage() {return(message);}
int getErrCode() {return errCode;}
};
#endif //MYEXCEPTION_H
class Array : protected OneDIntArray {
private:
int nRows;
int nCols;
public:
Array(int numRows, int numCols)
: OneDIntArray(numRows * numCols), nRows(numRows), nCols(numCols){}
int& operator() (int row, int col) {
if (row < 0 || row >= nRows) //Indexes are zero based
throw MyException("Array operator() - Row index out of bounds");
if (col < 0 || col >= nCols) //Indexes are zero based
throw MyException("Array operator() - Column index out of bounds");
int index = (row * nCols) + col; // Offsets to one dimentional array
return (this->operator[](index));
}
};
#endif //ARRAY_H
la.txt
Los Angeles, Anchorage, 2340
Anchorage, Beijing,3970
Beijing, Los Angeles, 6260
Los Angeles, Maui, 2490
Maui, San Diego, 2540
San Diego, Las Vegas, 265
Los Angeles, San Diego, 200
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.