ASSIGNMENT 10
In this assignment, you will gain experience coding in C++, using arrays, and reading from files.
You will also implement a greedy algorithmic solution to the traveling salesman problem that you did with a linked list in python.
Remember, to compile a C++ program on lumen use:
g++ MyProgram.cpp
Or, to create an executable file with a meaningful name, use:
g++ -o MyProgram MyProgram.cpp
To get command line arguments into your program, you will need to modify the definition of the main function that we used often in class.
Instead, use:
int main(int argc, char *argv[])
The integer argument argc will be the count of the arguments read from the command line and argv will be (just like Python!) an array of strings, one for each argument.
GreedyPath
Given a file containing a list of two-dimensional points, you need to develop a program that does the following:
-
Computes the bounding box of the set of points.
That is, find the lower-left coordinate (x1, y1) and upper-right coordinate (x2, y2) of a rectangle that contains all points in the file.
-
Construct a path visiting each point exactly once.
The path always starts from the first point in the file.
You construct the path in a greedy fashion, always going next to the closest unvisited point.
-
Compute the total distance of the greedy path you found through the points.
The file GreedyPath.zip contains some example input files.
Here is one of the provided input files, points7.txt:
7
0.0 1.0
1.0 1.0
-1.0 1.0
2.0 0.0
-2.0 -2.0
1.0 -2.0
2.0 -2.0
Your first task will be to read the point data from the file and put it into appropriate array variables.
For this program, use "parallel" arrays - that is one array for the x values, one for the y values, and one that indicates whether that point has been visited or not.
You can assume the input file will be well-formed and contain at least one point.
The first two lines of output of your program will be the lower-left and upper-right coordinates of the bounding box containing the points.
After this should come a blank line and then a line containing the integer number of points you read in.
You may want to get this working before working on the harder part of computing the path.
Here are sample runs of just this part of the program:
% GreedyPath points7.txt
-2 -2
2 1
7
% GreedyPath points5.txt
0 0
1.9 1.65
5
% GreedyPath points3.txt
-1 0
1 1
3
We assume paths always start at the first point in the file.
From there, the path always goes to the next closest point that has not already been visited.
So for example in points7.txt, starting at (0.0, 1.0), the next closest point is (1.0, 1.0).
From (1.0, 1.0), the next closest point would be (0.0, 1.0), but since we already visited this one, the next best one is (2.0, 0.0), and so on.
You will need to use your arrays of the x- and y-coordinates to figure out which point is closest given your current location.
In the event of a tie, you should use the point that occurs first in the file.
You will also need to keep track of whether each point has been visited or not.
Hint: keeping track of something that has a yes or no answer is a perfect time for the boolean (bool) data type.
Everytime you decide on the next point (including the very first one), output the point's coordinate on a single line with the x- and y-coordinate separated by a space.
Also as you go, you should keep track of the total distance accrued by your path (i.e. compute the Euclidean distance between the last point and the point being added to the path, adding this to a sum variable).
After outputting all the points on the path, output a blank line followed by this distance.
Here is the complete output for some of the provided files:
% GreedyPath points7.txt
-2 -2
2 1
7
0 1
1 1
2 0
2 -2
1 -2
-2 -2
-1 1
11.5765
% GreedyPath points5.txt
0 0
1.9 1.65
5
0 0
0.5 0
0.5 0.5
1 1.65
1.9 0.5
3.7143
% GreedyPath points3.txt
-1 0
1 1
3
0 0
1 1
-1 1
3.41421
% GreedyPath points3b.txt
-1 0
1 1
3
0 0
-1 1
1 1
3.41421
How do I check if a command line argument was given?
You can use the argc variable to see how many arguments were given on the command line.
Just like in python, the program name is the first argument, and others follow.
These are all stored in char * argv[] - an array of strings.
Unlike python you do not need sys.argv, just argv[1] for example:
myFile.open(argv[1])
How do I read from a file in C++?
First of all, at the top of your program include the file stream library:
#include <fstream>
To define a file, create an input file variable of type ifstream:
ifstream myFile;
You will need to open the file, giving it the name of the file:
myFile.open(argv[1]);
When you want to read a whitespace separated item from the file, it is much like getting user input, but you get it from the file instead:
myFile >> myVar;
Of course, myVar needs to be a variable that you have defined previously.
How do I compute the Euclidean distance between two points?
You need to use the formula: 
In this formula p1 and p2 are the coordinates of one point and q1 and q2 are the coordinates of another.
How do I calculate square root in C++?
First of all, at the top of your program:
#include <math.h>
Then you can use sqrt(x) or whatever you need to take the square root of.
Grading Your program will be graded on how it runs on lumen.
You are welcome to develop your code and run it on a local machine if you prefer, but make sure you test it on lumen before submitting it.
You will be graded according to the following criteria:
| Grade Item | Points Possible | Points Earned |
|---|
| Program Compiles (on lumen) | 4 | |
| Program Runs (on lumen) | 4 | |
| Header Comment |
4 | |
| Bounding Rectangle | 4 | |
| Number of Points Output | 2 | |
| (Correct) List of Points | 8 | |
| (Correct) Distance | 4 | |
Submission.
Submit your program GreedyPath.cpp via Moodle.
Be sure each submitted source file has the required header with your name and a description of the program.
Page last updated: January 06, 2022
