Lab 2 - Concurrency

Due - Tuesday 9/6/2011 - 11:59pm

In this lab, you will implement a multi-threaded Twitter crawler. Your program will take as input two Twitter user ids and find the degrees of separation between the two users, based on who the users follow. If, for example, the program input is a as the source and id b as the target, you might discover that a follows c, c follows d, and d follows b, hence there are 3 degrees of separation between the two users.

Requirements

1. Your program will retrieve the friends list of up to 5 users concurrently. In the example above, suppose a follows c, w, x, y, and z. Once you retrieve the list of a's friends, you will use multiple threads to retrieve the friends lists of c, w, x, y, and z in parallel.
2. You may design a data structure to store information about the friends graph as information is retrieved from Twitter. Keep in mind that you will have multiple threads accessing this graph concurrently, so you must ensure that updates to the data structure do not conflict.
3. Use a work queue to reduce the overhead of thread creation.
4. Once a path is found between the source and target, gracefully shutdown your WorkQueue before printing the result (e.g., Degrees of separation between a and b: X) and terminating the program.
5. You are required to submit your .java files and your .class files in a jar file named lab2.jar. This jar file must be available in your SVN repository <username>/cs682/lab2/lab2.jar. Failure to follow these instructions will result in a 0.
6. The input of your program will be provided at the command line using the source and target flags:

java -cp lab2.jar Crawler -source a -target b