Description
The purpose of this assignment is to do more involved work with pointers, linked lists, and memory allocation, to do a little work with command line arguments and reading from a file, and to learn to free all allocated memory.
General Requirements
1. Your C code should adhere to the coding standards for this class as listed in the Documents section on the Resources tab for Piazza. This includes protecting against buffer overflows whenever you read strings. 2. Your programs should indicate if they executed without any problems via their exit status, i.e., the value returned by the program when it terminates:
Execution Exit Status Normal, no problems 0 Error or problem encountered 1 3. Under bash you can check the exit status of a command or program cmd by typing the command “echo $?” immediately after the execution of cmd. A program can exit with status n by executing “exit(n)” anywhere in the program, or by having main() execute the statement “return(n)”. 4. Remember your code will be graded on lectura using a grading script. You should test your code on lectura using the diff command to compare your output to that of the example executable. 5. To get full points your code should compile without warnings or errors when the -Wall flag is set in gcc 6. Anytime you input a string you must protect against a buffer overflow. Review slides 82 – 87 of the basic_C deck. 7. You must check the return values to system calls that might fail due to not being able to allocate memory. (e.g. Check that malloc/calloc don’t return NULL) getline() is an exception to this rule. 8. Your code must run without errors using valgrind. 9. NEW REQUIREMENT, your program must free all allocated memory before exiting.
Testing
Example executables of the programs will be made available. You should copy and run these programs on lectura to test your program’s output and to answer questions you might have about how the program is supposed to operate. Our class has a home directory on lectura which is:
/home/cs352/fall18
You all have access to this directory. The example programs will always be in the appropriate assignments/assg#/prob# subdirectory of this directory. They will have the same name as the assigned program with “ex” added to the start and the capitalization changed to maintain camelback. So, for example, if the assigned program is theBigProgram, then the example executable will be named exTheBigProgram. You should use the appropriate UNIX commands to copy these executables to your own directory.
Your programs will be graded by a script. This will include a timeout for all test cases. There must be a timeout or programs that don’t terminate will cause the grading script to never finish. This time out will never be less than 10 times the time it takes the example executable to complete with that test input and will usually be much longer than that. If your program takes an exceedingly long time to complete compared to the example code, you may want to think about how to clean up your implementation.
Makefiles
You will be required to include a Makefile with each program. Running the command:
make progName
should create the executable file progName, where progName is the program name listed for the problem. The gcc command in your Makefile must include the -Wall flag. Other than that, the command may have any flags you desire.
Submission Instructions
Your solutions are to be turned in on the host lectura.cs.arizona.edu. Since the assignment will be graded by a script, it is important you have the directory structure and the names of the files exact. Remember that UNIX is case sensitive, so make sure the capitalization is also correct. For all our assignments the directory structure should be as follows: The root directory will be named assg#, where # is the number of the current assignment. Inside that directory should be a subdirectory for each problem. These directories will be named prob# where # is the number of the problem within the assignment. Inside these directories should be any files required by the problem descriptions. For this assignment the directory structure should look like:
assg8 prob1 calls.c Makefile To submit your solutions, go to the directory containing your assg8 directory and use the following command:
turnin cs352f18-assg8 assg8
Problems prob1: calls
It’s time for some data mining! For this assignment you will write a C program in a file called calls.c and a Makefile which creates the executable calls that will open up a set of files (usually more than one), each of which has lines that are pairs of phone numbers (representing phone calls). You will record how many times each phone number has talked to each other phone number. After reading the files and creating a data structure, you will read queries from stdin. Each query will be a pair of phone numbers. If the two numbers have talked to each other, you will print how many times they talked (as indicated below). If they have not talked together, you will see if the numbers are connected through conversations. If they have, you will print the shortest path that connects the numbers. Details for this are below.
Invocation:
Your program will be invoked with one or more file names specified as command line arguments:
calls inFile1 [ inFilei ] . . .
at least one inFile must be specified. It is followed by an optional number of additional files.
Input:
All input for this program will consist of lines of two different phone numbers, where the phone numbers are specified by whitespace. The phone numbers should have the format, ddd-ddd-dddd where each d is a digit (0-9). So all input lines should look like:
ddd-ddd-dddd ddd-ddd-dddd
where the phone numbers are not identical and are separated by one or more spaces or tabs. Blank lines (lines containing only whitespace) are also allowed and should be ignored. A line in any other format should cause and error message to be printed to stderr and the line should be ignored.
Program behavior:
Your program should open each of the specified input files for reading. If any of the files cannot be opened, you should print and error message to stderr and continue to the next given file. You will read the lines of phone numbers and use them to create a graph, much like you did in the last assignment. Here the phone numbers will be the vertices and the edges will represent a call between those numbers.
After all the files have been read, your program will read input from stdin. As with reading the files, it will read in lines, each of which should be a pair of phone numbers. These are queries. If the two numbers have talked your program will print out:
Talked n times
where n is the number of times the two numbers talked. Print this statement using:
printf(“Talked %d times\n”, num);
where num is an int variable containing the number of times the numbers talked.
If there was no direct call between the two numbers, then the program should check to see if they are connected indirectly. Two numbers are connected indirectly if there is a path of phone calls between them. For example suppose A did not talk to B, but A talked to C and C talked to B. In this case A is indirectly connected to B. If this is the case your program should print out the message:
Connected through n numbers
where n is the smallest number of phone numbers connecting the two numbers. Print this statement using the command:
printf(“Connected through %d numbers\n”, num);
where num is an int variable containing the smallest number of connecting numbers. The smallest number of connecting numbers is the number of phone numbers between the target phone numbers on the SHORTEST path connecting them. For example, if A talked to C and C talked to D, and D talked to B, then there are two connecting numbers on this path from A to B. However if A also talked to E and E talked to B, then there is only one connecting number on this path. In this case, the shorter path is A→E→B so the number 1 should be printed.
If there is no connecting path between the two numbers, you should print out the message:
Not connected
Note, please be careful of the format of these outputs. Check your output against the example executable using diff. I will use the –Z option on diff to grade these (meaning whitespace at the end of the line will be ignored), but I would hate for someone’s program to calculate the values correctly but lose all the points because of extra punctuation or misspelling.
If during the input of queries a phone number is entered that is not in the graph this should also be treated as a nonfatal error. (an error message printed to stderr and the input line ignored) It is also a nonfatal error if the two phone numbers are the same.
Error Conditions:
Non-fatal errors: These should all be listed above. They include specifying an input file that can’t be opened for reading or a nonblank line that contains something other than two different phone numbers in correct format. It is also an error if a phone number that is not in the graph is queried. Remember to exit with a status of 1 if any error is encountered.
Fatal errors: If no input files are given as command line arguments. (Failure to get allocated memory is also a fatal error but not one that will be tested. Just make sure you check the return values of malloc, calloc, and strdup.)
Restrictions:
The usual restrictions apply to this program. You may not allocate space for a large array to save the data structure. Instead you must implement the graph using linked lists.
Data structure:
As in the last assignment, the data structure you should use for this program is an adjacency list to represent a graph. Note that in the last assignment the graph you created was directed, but in this assignment it should be undirected. If A talked to B, then B also talked to A. The easiest way to represent this is to add two edges, one from A and one from B, for every line you process.
Also note that vertices are added implicitly in this program. By this I mean that we don’t have a specific command to add phone numbers. Instead, if a line indicates that there was a call between A and B and A is not in the list of phone numbers it should be added. A last difference between this graph and the one you did for the last assignment is that you need to keep track of the number of calls made. To do this you will need to add a field to the struct you use to represent the graph’s edges to keep track of how many calls were made.
Algorithm:
You need to find the shortest path connecting two nodes. For this a depth first search will not work. A depth first search finds if there is a path between two vertices, but not the shortest path. To find the shortest path, we will use a breadth first search. A depth first search recursively searches all the children of each vertex. A breadth first search puts all the children on a queue. This way all the children are searched before the grandchildren, etc. Here is the algorithm for a breadth first search:
//BFS does a breadth first search to find the shortest path //from Start to Target. It returns the size of that path if there //is a path from Start to Target and returns -1 otherwise int BFS(Start, Target) mark Start as queued set level of Start to 0 add Start to the queue
while queue is not empty do Take A from top of queue If A = Target, return A.level For all children C of A do if C not queued mark C as queued set level of C to A.level + 1 add C to queue
return -1 //If you get through loop without finding Target, //there is no path from Start to Target
Note that in C you will have to implement this queue with a linked list. Don’t forget to free it again after you’re done using it if applicable.
Please note: the level this algorithm gives you is the distance between two vertices. The program asks for the number of vertices between the two vertices, so the number you will output is the value returned – 1.
Makefile:
In addition to your source file, you should submit a make file named Makefile that supports at least the following functionality:
make calls Compiles the C source code to create an executable named linked. The compiler options used should include -Wall.
Don’t forget that for this assignment you must free all your memory before exiting. Use valgrind to make sure all the memory is freed and that you have no memory errors.