[SOLVED] Ece 650 section 001 assignment 3

For this assignment, you are to:
• Modify the output format of your Python script from Assignment 1 to match the input format
of your C++ program from Assignment 2.
• Modify your C++ program from Assignment 2 to output the input graph on standard output.
• Write a program in C++ to generate random input for your Python script.
• Write a driver program in C++ that uses Inter-Process Communication (IPC) to link the
output of the random input generator to the input of the Python script, and the output of the
Python script to the input of the C++ program from Assignment 2.
Resources
The online book, “Operating Systems: Three Easy Pieces”, will be useful for this assignment and
beyond. For this assignment, you might find Chapter 4 on Processes and Chapter 5 on Process API
the most useful. The book is available online at http://pages.cs.wisc.edu/∼remzi/OSTEP/.
You might also want to consult “Advanced Linux Programming”, especially Chapter 3 on Processes and Chapter 5.4 on Pipes. The book is available from https://github.com/MentorEmbedded/
advancedlinuxprogramming/blob/gh-pages/alp-folder/advanced-linux-programming.pdf
Sample Run
You should name the driver’s executable ece650-a3. In the following, we assume that “$” is the
shell command-prompt.
$ cd build
$ cmake ../
$ make install
$ cd ./run/bin
$ ./ece650-a3 -s 5 -n 4 -l 5
V 8
E {<1,3>,<1,4>,<1,5>,<2,4>,<5,8>,<6,3>,<6,7>}
s 3 5
3-1-5
In the above, the first three lines make your executable, and run the driver program with some
command-line arguments. Then, the lines “V = …”, “E = …”, and “3-1-5” are output. The
input the user provided to your program via stdin is “s 3 5”.
1
Input, Output, and Error
Your program should take input from stdin, and output to stdout. Errors should be output to stderr.
Errors should always start with “Error:” followed by a brief description. All your processes should
terminate gracefully (and quietly) once you see EOF at stdin. Your program should not generate
any extraneous output; for example, do not print out prompt strings such as “please enter input”
and things like that.
As the example above indicates, there are two kinds of input the user provides. One is via the
command-line arguments, with switches such as -s and -n . This is done only once, when your
program is first started. The other type of input is the ’s’ command on stdin, which may be issued
repeatedly, just as in Assignment 2. For the ’s’ command, your program should output a shortest
path.
We will not test your program for format errors in the input. That is, the command-line
arguments, whenever specified, will be formatted correctly, and the s input will also be formatted
correctly. Of course, we may omit command-line arguments (see below for what to do in such cases),
and specify vertex IDs with s that do not exist, or between whom a path does not exist. The latter
two cases should cause your program to report an error.
Marking
• Does not compile/make/crashes: automatic 0
• Your program runs, awaits input and does not crash on input: + 20
• Run in default mode: + 15
• Error check arguments: + 5
• Test functionality: + 20
• Test rgen: + 20
• Replace rgen: + 20
CMake
As discussed below under “Submission Instructions”, you should use a CMakeLists.txt file to build
your project. We will build your project using the following sequence:
cd a3 && mkdir build && cd build && cmake ../ && make install
If your code is not compiled from scratch (i.e., from the C++ sources), you get an automatic 0.
Note that we are using make install instead of make. The install target instructs make to
copy all of the binaries (both Python and C++) into directory ./run/bin. This ensures that all
the executable files (including the Python program) are in the same directory.
Submission Instructions
You should place all your files in the a3 directory in your GitLab repository. The directory should
contain:
• All your C++ and Python source-code files. IMPORTANT NOTE: the executable for your
random generator must be named rgen. The reason is that part of our testing will replace your
generator with ours.
• A CMakeLists.txt, that builds all of the C++ executables: rgen, ece650-a2, and ece650-a3.
• A file user.yml that includes your name, WatIAM, and student number.
See README.md for any additional information.
The submitted files should be in the a3 directory of the master branch of your repository.
2
File names
There are two file names that are important. One is your main executable. This must be named
ece650-a3. Our marking script will simply try and run this after building your project. The other
executable file whose name is important is your random input generator. The executable for this
must be named rgen. The reason is that for some of our tests, we will replace your rgen with ours.
Things to be done
Python script
You should edit your Python script from Assignment 1 so that its output which is the specification
of the graph is formatted to match the input format of your C++ program from Assignment 2.
Think of it as though your Python script provides command-line input to the C++ program. The
way to do this is to simply map each vertex to an index in [1, n] (where n is the number of vertices),
and rename your edges accordingly.
Also, the only output that your Python script should produce to stdout is in response to “gg”,
for which it outputs the specification of the graph (i.e., V and E). Error output should go to stderr.
Cpp program from Assignment 2
You should edit it to print the graph that it has read before accepting an s command. This is
necessary so that you know what graph has been produced and which vertices are available.
Random input generator
Your random input generator rgen should generate random street specifications as input for your
Python script. It takes four command-line arguments. All are optional.
• -s k — where k is an integer ≥ 2. The number of streets should be a random integer in [2, k].
If this option is not specified, you should use a default of k = 10; that is, the number of streets
should be a random integer in [2, 10].
• -n k — where k is an integer ≥ 1. The number of line-segments in each street should be a
random integer in [1, k]. Default: k = 5.
• -l k — where k is an integer ≥ 5. Your process should wait a random number w seconds,
where w is in [5, k] before generating the next (random) input. Default: k = 5.
• -c k — where k is an integer ≥ 1. Your process should generate (x, y) coordinates such that
every x and y value is in the range [−k, k]. For example, if k = 15, all of your coordinate values
should be integers between −15 and 15. Default: k = 20.
Your program should generate a specification of streets in the format that your Python script
expects (see Assignment 1). You can name the streets whatever you want. You should ensure
that your input does not have errors. For example, if you generate a line-segment that overlaps
with a line-segment (across all streets) generated earlier, you should regenerate that line-segment.
Similarly, you should not have any zero-length line segments.
Also, note that your random generator could go into an infinite loop looking for a valid specification. You should disallow this from happening by limiting the number of tries. That is, if your
random generator fails to generate a valid specification for a continuous A number of attempts,
it should exit() with an error message reported on stderr. A reasonable A to adopt may be 25.
Whatever A you adopt, your error message should mention it. That is, your error message should
be something like, “Error: failed to generate valid input for 25 simultaneous attempts”.
Before adding a new street graph specification to your Python script, your generator should
issue “rm” commands to your Python script to remove all previous streets and replace them with
the new street specification.
3
After generating the input, the generator must issue the “gg” command.
Thus, a typical interaction of the random generator is as follows:
1. issue enough rm commands to clear any existing street database;
2. issue add commands to add new streets satisfying the specification;
3. issue a gg command;
4. wait for specified number of seconds and repeat.
You must use /dev/urandom as the source of your random data. Also, see under “Submission
Instructions” how your executable for the random generator must be named.
Driver
Your driver program has the overall control. You have at least three programs that run concurrently:
(1) the random generator, (2) your Python script from Assignment 1, and, (3) your program from
Assignment 2 that takes a graph-specification as input and computes shortest paths. Your driver
program should fork() two processes and exec() two of those programs, and then exec() the
third (so it turns into a process that corresponds to the third program). It should set up all IPC
appropriately beforehand.
It should send normal output to stdout, error output to stderr, and take input from stdin. As
we mention above, the only input it takes are “s” commands, that ask for a shortest path between
vertices.
Gotcha warning: note that I say “you have at least three programs that run concurrently.” You
may need more than three that run concurrently. (Why?)
Sample code
The skeleton repository for the assignment contains some sample code. You should replace all
sample code with your own code. Including replacing the Python code with your solution from
Assignment 1, and C++ code from your solution to Assignment 2.
4