CS 242 Fall 2010 : Assignment 2.1
CS 242 Fall 2010 : Assignment 2.1
This page last changed on Oct 06, 2010 by m3rabb.
This week, you will be reading in raw data in JSON format and representing it as a graph in memory. You will then provide an interface to query data about the graph and provide a hook to visualize the data.
Language: Your choice, but it must be a language that other people in your discussion section can actively comment about even if they do not understand all the semantics. If you are in doubt about your choice, email the TAs for clarification.
Due Date and Submission: This assignment is due in Subversion at 8:00 AM on Wednesday, October 6th. This change is intentional, since we will be doing code reading for assignment 2.x. Please commit to a folder in SVN named Assignment2.1.
You are a senior software engineer for a new international airline, CSAir. Before CSAir launches passenger service across the globe, they first need to start selling tickets to passengers. But before that can happen, some software needs to be written to manage the extensive route map. You have been tasked by CEO Woodley to begin work on this software.Specifically, the initial requirements for this new software are:
JSON is most commonly used in web applications, as a lightweight format to transfer data asynchronously between a client and server. For instance, Facebook transmits status updates to your newsfeed using JSON so that new posts appear without having to reload the page. But, JSON is not limited for web applications. Parsers for JSON are available for just about every language out there. See http://www.json.org for parsers for some of the most common programming languages. It would be wise for you to pick a language for this assignment that already has a well developed parser.
You can read more about JSON on Wikipedia.
A graph, at least to computer scientists, is a set of vertices and a set of edges that connect them. Each vertex in a (directed) graph has a set of outgoing edges and a set of incoming edges. There are many ways to represent a graph in memory, it is up to you to determine which representation you would like to use. For your assignment, you will represent each city in CSAir’s route map as a vertex in a graph and each route that CSAir flies as an edge between the two vertices that represent the linked destinations of that route. See the image below for a graphical representation of what a graph might look like:
Also, your graph will need to be augmented to hold extra data about each city and the routes that link them together. You will have to adapt your implementation to handle this extra data. In our case, the graph will be actually be directed. That is, the edges in the graph will have a source and a destination. But, for each route in CSAir’s route network, you will need to add two edges in your graph. One going from city A to city B and another going from city B to city A. The data that these two edges contain with be identical. This is because CSAir flies in both directions on all routes in its network. Imagine if the routes were one way only, eventually it could be possible that no aircraft would be able to get to a city to carry passengers.
This week’s assignment is split into three main components.
You will need to write code that parses the given JSON file and loads it into graph representation in memory.
You need to write a simple user interface that allows the user to:
All of this information should be calculated at query time from your graph and not be hard coded into your source. Your program should be console driven, that is it should start up, prompt the user for input, and be able to perform any combination of valid operations without exiting. Also, be careful to check for invalid input. For instance, what happens when a user queries data about a city that CSAir does not fly to?
The third and final phase of this week’s assignment is for you to visualize CSAir’s route map. To aid you in this task, CEO Woodley has told you about a website, the Great Circle Mapper. To accomplish this task, you do not need to write any code that actually draws the graph, but rather use the Great Circle Mapper to do it for you. This website uses the code associated with each city in CSAir’s route network. To view a sample of a generated route map, do the following:
Notice how when you do this, the Great Circle Mapper automatically generates a route map for you. Try playing around with some of the options to edit/enhance the generated image.
To generate a route map from your graph, you will need to:
You can minimally print this URL out to the console for the user to copy and paste into their web browser, but it would be better if you are able to automatically launch the web browser on the system to that URL.
As usual, we require that you write extensive unit tests for each part of this assignment. We realize that testing a console interface is difficult, so it is acceptable to write unit tests for each of the functions that your library has. When you choose your language for this assignment, make sure you look into what unit testing frameworks are available for that language and use one of them. If your language does not have a testing framework (unlikely), you will need to implement your own test runner and utilities to accomplish this part of the assignment.
For example, if you decide to use Java with jUnit this week, some asserts you might have:
This is by no means a a comprehensive list of tests that you will need to write, but it should become clear what you need to test as you work on the assignment.
|Document generated by Confluence on Feb 22, 2012 18:13|