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 ", 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 ", 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 AEB 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.