CS 242 Fall 2011 : Assignment 2.1

This page last changed on Sep 26, 2011 by cemeyer2.

Assignment 2.1 – Launching an Airline

Reading

The reading due next Monday, September 26th is chapters 6 and 7 from Code Complete.

Tutorial

For Monday, September 26th you will do a tutorial on VIM. Please login to an EWS machine (either in the lab or remotely) and run the command vimtutor. Please walk through this tutorial.

Reading and tutorial assignments are all fair game for lecture quizzes.

Coding Assignment

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
  • Learn a basic design pattern

Language: Your choice of Ruby, Python, Perl, or JavaScript. The caveat though is that you must choose a language that you have never done a project with before. If you are experienced in all three of these languages, please email the course staff

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 course piazza space since there may be other people in the course that can help with your problem.

Update:
Due Date and Submission: This assignment is due in Subversion at 10:00 AM on Wednesday, September 28th. 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/fa11-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 CEOs Woodley and Kamin 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. Some languages even have JSON built into the core API. 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 the source of all lies.

Graphs

A graph, at least to computer scientists, is a set of vertices and a set of edges which 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. Trust us, it will be easier to follow this approach for future extensions to this assignment.

If you were using Java, the idiomatic way to implement the graph would be to have an Airport class and an object for each airport; the object would contain references to the other airports to which there are direct flights; you would presumably also have a hash table mapping airport names to Airport objects. If you are using Python or Ruby, it would be more idiomatic to represent the entire graph as a dictionary mapping airport names to lists, with the list containing all the information about that airport. In particular, it would contain the names of the airports to which there is a direct flight. Note that the standard JSON libraries for these languages parse the JSON file and return a dictionary; this is not the dictionary you want to use to answer queries, so you’ll need to construct the latter after reading the JSON file. (If you are using JavaScript, either method would be idiomatic, but the object-based method is probably somewhat easier.)

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.
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. It is up to you to determine what makes a city a “hub city”.

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 Command Pattern

To implement this part of the assignment, you must use the command pattern. To accomplish this, you will need to think in a very object-oriented manner. You should be able to make a command object for each of commands we are asking you to implement. The source of all lies has a good overview of how to use the command properly, although the example is in Java. You should be able to adopt it to the language you choose.

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, CEOs Woodley and Kamin have 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.

Challenge:

Have your code automatically download the route map image and display it in a simple GUI.

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 could use Java with jUnit this week (which you cannot), 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. Think about covering all the main as well as corner cases.

Grading

Criteria Weight Comment
Basic Preparation 1  
Cleverness 1  
Code Reading 2  
Code Submission 4 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 6 Proper statistics generation and use of command pattern
Requirements – Image Generation 2  
Testing 3  

graph.jpg (image/jpeg)

map.jpg (image/jpeg)

map_data.json (application/json)

csair_graph.jpg (image/jpeg)
Document generated by Confluence on Feb 22, 2012 18:09

  1. No comments yet.

  1. No trackbacks yet.