C++

Forum

 
Flight finder C++

bigJoe561 (9)
Note: This program works as intended to. Thanks for the help

I am having trouble finding adding a second vector on a flight.
For example when i reach sfo lax 89 in the data file lax 89 doesn't get added to sfo in the unordered_map.

Test data:
stl jfk 99
ord jfk 199
cle jfk 179
sfo jfk 388
sfo lax 89
stl cle 77
lax cle 30
sfo stl 200
ord stl 99

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
 
#include <iostream>
#include <fstream>
#include <unordered_map>
#include <map>
#include <vector>
#include <limits>
#include <algorithm>
#include <string>

using namespace std;

class Flight {
public:
	// double unordered_map data structure to store data
	//		(Depature city as string), (Arrival Dest as a string,int pair)
	unordered_map<string, unordered_map<string, int>> vertices;
	int cost = 0;			// Total cost

	void add_vertex(string name, unordered_map<string, int>& edges){
		// Insert the connected nodes in unordered map
		vertices.insert(unordered_map<string, unordered_map<string, int>>::value_type(name, edges));
	}

	// Deletes vertices or data
	void clearVertices() { vertices.clear(); }

	// Returns the total cost
	int getCost() { return cost; }

	// Rests the cost to 0
	void restCost() { cost = 0; }

	// Calculates the cost of a flight plan
	void calcCost(string start, vector<string> path) {
		path.insert(path.end(), start);
		std::reverse(path.begin(), path.end());
		int plength = path.size();
		plength--;
		string acode;
		// For every path
		for (std::vector<string>::const_iterator i = path.begin(); i != path.end(); ++i) {
			// Run trough airports
			for (auto& airport : vertices) {
				// Compare if airports equals the actual path
				if (airport.first == *i) {
					// Storing airport code
					acode = airport.first;
					// Condition statement to fix out of bounds error
					if(plength > 0){
						// Running trough that airport's flights
						for (auto& flight : vertices[acode]) {
							// Comparing if the flight matches the next path
							if (flight.first == *(i + 1)) {
								// If so adds to the total cost
								cost += flight.second;
							}
						}
						plength--;
					}
				}
			}
		}
	}

	// Dijkstra algorithm
	vector<string> cheapest_path(string start, string finish) {
		// Second arguments -> flights
		// Find the cheapest flight in the closed list and push it in -> previous
		unordered_map<string, int> flights;
		unordered_map<string, string> previous;
		vector<string> nodes; // Open list
		vector<string> path; // Closed list

		// Comparator function
		auto comparator = [&](string left, string right) { return flights[left] > flights[right]; };

		// The implamentation of dijkstra algorithm
		for (auto& vertex : vertices) {
			if (vertex.first == start) {
				flights[vertex.first] = 0;
			}
			else {
				flights[vertex.first] = numeric_limits<int>::max();
			}
			nodes.push_back(vertex.first);
			push_heap(begin(nodes), end(nodes), comparator);
		}

		// Building path from destination to departure
		while (!nodes.empty()){
			pop_heap(begin(nodes), end(nodes), comparator);
			string smallest = nodes.back();
			nodes.pop_back();
			if (smallest == finish){
				while (previous.find(smallest) != end(previous)) {
					path.push_back(smallest);
					smallest = previous[smallest];
				}
				break;
			}

			if (flights[smallest] == numeric_limits<int>::max()) {
				break;
			}

			for (auto& neighbor : vertices[smallest]) {
				int alt = flights[smallest] + neighbor.second;
				if (alt < flights[neighbor.first]) {
					flights[neighbor.first] = alt;
					previous[neighbor.first] = smallest;
					make_heap(begin(nodes), end(nodes), comparator);
				}
			}
		}
		return path;
	}
};

void readData(ifstream &data2 , Flight &f, Flight &c) {
	// Read until end of file
	while (true) {
		string
			departure,  // Departure loc
			arrival;    // Arrival loc
		int cost;       // Cost

		// Temparary map for airports w/o flights
		unordered_map<string, int> temp;

		// Reading in data
		data2 >> departure;
		if (data2.eof()) {
			return;
		}
		data2 >> arrival;
		data2 >> cost;

		// Adding blank airport to flights if needed
		f.add_vertex(arrival, temp);
		c.add_vertex(arrival, temp);
		
		// Inserting data into the vertices
		f.vertices[departure][arrival] = cost;
		c.vertices[departure][arrival] = cost;
	}
}

int main() {

	ifstream data2;		// Data file

	char fileName[25];	// A string for filenames

	string
		departure,  // Departure loc
		arrival;    // Arrival loc

	data2.clear();
	// Prompt user
	cout << "Please enter the name of the input file: ";
	cin >> fileName;	// Read data

	// Open file
	data2.open(fileName, ios::in);

	// Checks file
	if (!data2) {
		cerr << "Can't open input file " << fileName << endl;
		exit(1);
	}

	// Data structure 
	Flight f, c;

	// Read data
	readData(data2, f, c);
	// Close data file
	data2.close();

	// Prompt user
	cout << endl << "Please enter a source and a destination (q to quit): ";
	// Read data until user enters "q"
	cin >> departure;
	do
	{
		// If user enters "q" in the beginnig for some reason
		if (departure == "q") {
			break;
		}
		cin >> arrival;

		// Creating and reseting values
		f.restCost();
		c.restCost();
		vector<string> path;

		// Calculate cheapest flight path
		path = f.cheapest_path(departure, arrival);
		// Calculate total cost of path
		c.calcCost(departure, path);
		// Adding starting airport to path
		path.insert(path.end(), departure);
		// Reversing path bc cheapest_path returns the path backwards
		std::reverse(path.begin(), path.end());
		// Get's path size
		int vec_size = path.size();
		// Output
		if (c.getCost() == 0) {
			cout << "There is not a trip from " << departure << " -> " << arrival << endl;
		}
		else {
			cout << "Cheapest trip from: " << departure << " -> " << arrival << ": $" << c.getCost() << " [ ";
			// More output
			for (int i = 0; i < vec_size; i++) {
				cout << path.at(i) << " ";
			}
			cout << "]" << endl;
		}

		// Prompt user
		cout << endl << "Please enter a source and a destination (q to quit): ";
		// Read data from user
		cin >> departure;
		// Repeat if departure dosen't equal "q"
	} while (departure != "q");
}
Last edited on
Repeater (3046)
Your unordered map key is the first value of each line of the input file.
You cannot have duplicate keys in the map.

1
2
 
sfo jfk 388
sfo lax 89
bigJoe561 (9)
that didn't solve the problem. i really need help i don't know what to do!
Last edited on
Repeater (3046)
What didn't solve the problem? I told you what the problem was. Presumably you just tried something to fix it, and that attempted solution didn't work.

Given that you didn't tell us what you tried, simply telling us that it didn't work isn't really much information for us to go on.
bigJoe561 (9)
I tried to read through the input file finding all of the pairs the associated with a key and that didn't work either. I know this will work properly if i can get all my data into the unordered map. But i am really unsure on how to do that.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
 
class Flight {

public:

	unordered_map<string, unordered_map<string, int>> vertices;
	int cost;

	void add_vertex(string name, unordered_map<string, int>& edges){
		// Insert the connected nodes in unordered map
		vertices.insert(unordered_map<string, unordered_map<string, int>>::value_type(name, edges));
	}

};

void readData(ifstream &data2 , Flight &f, Flight &c) {
	while (true) {
		string
			departure,  // departure loc
			departureK,
			arrival,    // arrival loc
			arrivalk;
		string arrivals[200];
		int costs[200];
		int cost, costK;       // cost
		int size = 0;
		int pos;

		data2 >> departureK;
		if (data2.eof()) {
			return;
		}
		data2 >> arrivalk;
		data2 >> costK;

		pos = data2.tellg();
		unordered_map<string, int> temp;
		temp.insert(unordered_map<string, int>::value_type(arrivalk, costK));
		while (true) {
			data2 >> departure;
			if (data2.eof()) {
				return;
			}
			data2 >> arrival;
			data2 >> cost;
			if (departureK == departure) {
				arrivals[size] = arrival;
				costs[size] = cost;
				size++;
			}
		}
		for (int i = 0; i < size; i++) {
			temp.insert(unordered_map<string, int>::value_type(arrivals[i], costs[i]));
		}
		f.add_vertex(departureK, temp);
		c.add_vertex(departureK, temp);
		temp.clear();
		size = 0;
		data2.seekg(pos);
		
		/*data2 >> departure;
		if (data2.eof()) {
			return;
		}
		data2 >> arrival;
		data2 >> cost;
		unordered_map<string, int> temp;
		temp.insert(unordered_map<string, int>::value_type(arrival, cost));
		f.add_vertex(departure, temp);
		c.add_vertex(departure, temp);
		temp.clear();*/
	}
}

int main() {

	ifstream data2;

	char fileName[25];	// a string for filenames

	string
		departure,  // departure loc
		arrival;    // arrival loc

	int cost;       // cost

	data2.clear();
	cout << "Please enter the name of the input file: ";
	cin >> fileName;

	data2.open(fileName, ios::in);

	if (!data2) {
		cerr << "Can't open input file " << fileName << endl;
		exit(1);
	}

	// checks file

	Flight f, c;

	readData(data2, f, c);

	cout << endl << "Please enter a source and a destination (q to quit): ";
	do
	{
		cin >> departure;
		if (departure == "q") {
			break;
		}
		cin >> arrival;

		f.restCost();
		c.restCost();
		vector<string> path;

		path = f.cheapest_path(departure, arrival);
		c.calcCost(path);
		std::reverse(path.begin(), path.end());
		int vec_size = path.size();
		cout << "Cheapest trip from: " << departure << " -> " << arrival << ":" << c.getCost() << " [";
		for (int i = 0; i < vec_size; i++) {
			cout << path.at(i) << " ";
		}
		cout << "]" << endl;
		f.restCost();
		c.restCost();
		f.clearVertices();
		readData(data2, f, c);
		cout << endl << "Please enter a source and a destination (q to quit): ";
	} while (departure != "q");
	// close file
	data2.close();
}
Last edited on
Repeater (3046)
temp.insert(unordered_map<string, int>::value_type(arrival, cost));

This code suggests that you're now trying to use the arrival location as your UNIQUE key. The key that you can only have ONE of in an unordered_map. Let's check to see if there are any duplicate arrival locations:

stl jfk 99
ord jfk 199
cle jfk 179
sfo jfk 388
sfo lax 89
stl cle 77
lax cle 30
sfo stl 200
ord stl 99

Lots of duplicates.

This is the exact same problem as before. You're trying to use an unordered_map, in which you cannot have duplicate keys. unordered_map seems like entirely the wrong kind of data structure to use, given that you cannot have duplicate keys in an unordered_map.
bigJoe561 (9)
I am trying to get my stored data to look like this.

unordered_map<string, unordered_map<string, int>> vertices;

stl {jfk 99, cle 179}
ord {jfk 199, stl 99}
cle {jfk 179}
sfo {jfk 388, lax 89, stl 200}
lax {cle 30}

I was trying to use temp to store the second unordered_map in vertices by using temp.insert to store the flights leaving from a given airport with the cost.

temp.insert(unordered_map<string, int>::value_type(arrivalk, costK));

Then using add_vertex() function i created.

f.add_vertex(departureK, temp);

Do you see what i mean? I know the rest of the code works but i need to hard code the data in first to check it. But i need to be able to read that data from a file.
Last edited on
bigJoe561 (9)
This fixed the data structure:
1
2
 
		f.vertices[departure][arrival] = cost;
		c.vertices[departure][arrival] = cost;


Not my best work but i re-uploaded the code.
Topic archived. No new replies allowed.