CS 242 Fall 2010 : Assignment 2.1

This page last changed on Oct 06, 2010 by m3rabb.

Assignment 2.1 – Launching an Airline

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.

Objectives:

  • Learn about graphs and how to implement them
  • Learn to work with data in JSON format
  • Learn how to effectively decompose your code into reusable modules
  • Visualize the given 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.

Language Selection
Be aware that the TAs are not familiar with every programming language out there, so we may or may not be able to provide in-depth help with the language you choose. If we cannot help you, post your question to the newsgroup since there may be other people in the course that can help with your problem.

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.

Different Due Date Than Normal
Code is due on Wednesday for assignment 2.x, not Thursday. This is to facilitate code reading. Code reading will be posted each Wednesday morning at https://subversion.ews.illinois.edu/svn/fa10-cs242/_public/code_reading. Your moderator will assign whose code you will read each week, and that week in discussion, you will lead the discussion on that person’s code. To ensure a lively discussion, it is important that you read the assigned code and come prepared to section.

Background

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:

  1. Parse the raw data that represents CSAir’s route map into a data structure in memory
  2. Allow users of the software to query data about each of the destinations that CSAir flies to, including its code, name, country, continent, timezone, longitude and latitude, population, region, and each of the cities that are accessible via a single non-stop flight from that destination
  3. Provide a graphical representation of CSAir’s route map

The Data

CSAir has provided you with a text file containing a representation of its route map in JSON format. You can get the given data here.

What is JSON?

“JSON (JavaScript Object Notation) is a lightweight data-interchange format. It is easy for humans to read and write. It is easy for machines to parse and generate.” -json.org

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.

Graphs

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.

Your Task

This week’s assignment is split into three main components.

Parsing the input data

You will need to write code that parses the given JSON file and loads it into graph representation in memory.

Caveats:

  • You can use any JSON parser you wish to parse the input data
  • You can not use any existing graph library to handle the representation of your graph in memory. That is, you need to write your own graph implementation for this assignment.
If you plan on using Java again this week, the staff recommends using the org.json parser. It is simple, but is only able to be downloaded as individual source files. To aid you, we have compiled them together into a jar file including source and documentation for you to use with your project. You can download it here.
Querying the data

You need to write a simple user interface that allows the user to:

  1. Get a list of all the cities that CSAir flies to
  2. Get specific information about a specific city in the CSAir route network. This information should include:
    1. Its code
    2. Its name
    3. Its country
    4. Its continent
    5. Its timezone
    6. Its latitude and longitude
    7. Its population
    8. Its region
    9. A list of all of the other cities that are accessible via a single non-stop flight from that source city. This list should include the distance of each of those flights.
  3. Statistical information about CSAir’s route network, such as:
    1. the longest single flight in the network
    2. the shortest single flight in the network
    3. the average distance of all the flights in the network
    4. the biggest city (by population) served by CSAir
    5. the smallest city (by population) served by CSAir
    6. the average size (by population) of all the cities served by CSAir
    7. a list of the continents served by CSAir and which cities are in them
    8. identifying CSAir’s hub cities – the cities that have the most direct connections.

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?

Visualizing CSAir’s route map

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:

  1. Open a web browser to http://www.gcmap.com
  2. In the text box at the top, type a comma separated list of routes. For example, you might enter LIM-MEX, LIM-BOG, MEX-LAX
  3. Click on the map button

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:

  1. Analyze the structure of the URLs that the Great Circle Mapper generates based on the input you supply to it
  2. Traverse through your graph and craft a URL matching that pattern that will generate a route map for CSAir’s route network

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.

Testing

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.

Grading

Criteria Weight Comment
Basic Preparation 1  
Cleverness 1  
Code Reading 2  
Code Submission 1 submitted on time for code reading and to the correct location, so that the code reading script could grab it
Decomposition 3  
Documentation 1  
Effort 1  
Naming 2  
Overall design 4  
Participation 2 How you critique others code.
Performance 1  
Presentation 2 How you critique your code.
Requirements – Parsing 4  
Requirements – Statistics Generation 4  
Requirements – Image Generation 2  
Testing 3  

graph.jpg (image/jpeg)

map.jpg (image/jpeg)

map_data.json (application/json)

map_data.json (application/octet-stream)

org.json.jar (application/x-jar)

map_data.json (application/octet-stream)

map_data.json (application/octet-stream)

map_data.json (application/octet-stream)
Document generated by Confluence on Feb 22, 2012 18:13

  1. No comments yet.

  1. No trackbacks yet.