World Airline Route Search

CSCE 3110 Data Structures Project

 

Total: 200 points

 

Due date: Pre-finals week

Presentation: 04/30/2007-02/05/2007

Program: 04/29/2007, 11:59pm

Report: 04/29/2007, 11:59pm

 

 

 

Introduction

In this project, you will be designing and implementing algorithms to store and search graphs. World Airline (WA) flies to many destinations worldwide including: Moscow, Seoul, Tokyo, Hong Kong, and London. Complete detailed information regarding airline flight routes can be found from the link flight.txt. The flight.txt contains a “from  city” and its destination cities that WA flights to. Note that the flight.txt is a synthetically generated datasets by a graph data generator available from the link graphGen. You may want to download the graph generator and generate a few more graphs with different number of cities to test your algorithms.

 

Your task

Your task is to design and implement algorithms to answer the following questions:

  1. I am in city “A”, can I fly to city  “B”  with less than x connections? Give me the route with the smallest number of connections or tell me there is no such a route.
  2. Give me the route with the smallest number of connections from city “A” to city “D” through city “B” and “C”. (the order of  “B” and “C” is not important). Or tell me there is no such a route
  3. I want to start from city “A”, visit all the cities that can be reached and then come back to “A” using as less connections as possible. Give me a route or tell me there is no such a route. (note: once you come back to “A”, you do not go out anymore).
  4. I am in city “A”, my friend John is in a different city “B”, and my other friend Ann is in yet another different city “C”. We want to find a city different from the three cities we are in to meet so that the total number of connections among three of us is minimized. Tell me the city we should fly to and the routes for us or tell me there is no such a city.

 

You will need to process the documents and store their content in the data structures that you selected. Next, for every question, you will search your data structure using an algorithm of your choice. You have the freedom to select the data structures and algorithms that you consider to be more efficient for the tasks. Of course, you will have to justify your decisions. No fancy user interface is expected (fancy interface may be counted towards extra credits though).  You program should take a few parameters with the first as the number of the question (1-4). The rest of the parameters and output of the four questions (1-4) are described as follows assuming your program is called routeSearch:

1.      usage: routeSearch 1 <city_A> <city_B> <num_connection>

sample output:

         city_A to city_x to city_y … to city_B

         total connection: 4

2.      usage: routeSearch 2 <city_A>  through <city_B> and <city_C> to <city_D>

sample output:

         city_A to city_x to city_C to city_y  … to city_B to city_D

         smallest number of connection: 4

3.      usage: routeSearch 3 <city_A> 

sample output:

         city_A to city_x  to city_y  … to city_z to city_A

         smallest number of connection: 4

 

Note: this query has been into an extra credit problem. 50 extra credits will be given if you do this query (algorithm design, analysis, implementation, optimization etc). The total 200 points does not include the 50 extra credits for this problem.

 

4.      usage: routeSearch 4 <city_A>  <city_B>  <city_C>

sample output:

         You three should meet at city_D

          Route for first person: city_A to city_x  … to city_D (3 connections)

          Route for second person: city_B to city_y  … to city_D (1 connections)

          Route for second person: city_C to city_y  … to city_D (0 connections)

          Total  number of connection: 4

 

You can choose to work alone or work with another student as a team of two. If you choose to work in a team, both of you will receive the same score for the project. However, you will need to explicitly specify each person’s portion of work in the appendix of your written report. This information is used only when a student’s final letter grade is on the boundary.

 

Note: if it takes too long for your program to finish the tasks, try to generate smaller graphs using the provided graphGen.cpp.

 

What to turn in

 

There are three main parts in this project, all of them contributing to the final project grade.

 

1. You will have to write a project report (about 3-5 typed pages – single space – 12pt font) that includes:

-          design issues, what are the problems and how you solve them

-          data structures you use, the decision behind selecting them

-          algorithms you employ, again with a justification of your decision

-          particular emphasis should be placed on the running time of your algorithm, please show the asymptotic costs for each of your algorithm

-          optimization issues: what could you do to further optimize your algorithm

-          you need to specifically address the problem of scalability: would you implementation be efficient in the case of very large species collections for larger scale geographic area?

-          any other remarks about your design and implementation

 

The due date for your final written report is 04/29/2007 before midnight through project command on the CSP machines.

 

2. You will have to send in a fully working program, written in C/C++. We will test your algorithms extensively by generating graphs with different characteristics. It is mandatory that you include a README file, as detailed as possible, including compilation and running instructions.  Is it also mandatory that your programs are fully documented, that is they should include detailed comments on what is included in each file and what each method does. Submit your programs using the project command on the CSP machines – project name is PROJECT. As with the previous assignments, make sure that your programs compile and run on the CSP Linux machines. Make sure you submit your programs and report by 04/29/2007 before midnight. The 3-days delay policy does not apply to the project.

 

3. In class presentation. You will have to prepare a short presentation, to last about 10-12 minutes (questions included), where you will present the design and implementation decisions you made in this project. Make use of examples, compare with other possible approaches, and use any other means you wish to make your point (that your design is the best). You should prepare PowerPoint slides and put them to a web accessible place.  Project presentations will take place in class on 04/30/2007 and 05/02/2007.

 

Grading

Design issues, data structures efficiency, algorithms,

other issues addressed in the written report                                       - 110 points

Program (should compile and run correctly, have an

associated README file, should be fully documented)                   -   60 points

In class presentation (presentation materials, communication

skills, presentation polish, audience contact,

presentation time, questions/answers)                                     -   30 points

Extra                                                                                                   -   up to 100 points

 

Notes

*  No late submissions are accepted!

 

* Up to 100 points extra credit may be given if you implement a fancy interface (question menu, query 3, TCL/TK, graph drawing Web based, other)