Lab 6: Implementation of a Graph using Linked Lists

Due Date: Monday November 12th, 23:59.

Background:

Lab 6 will allow you to get some familiarity with linked lists. You will re-implement the graph class using an adjacency list format instead of an adjacency matrix. We will be using the data file generated from the Vanguard Airlines route map. The  cities 0-11 are represented by  Atlanta(0),  Buffalo(1), Chicago(2), Denver(3), DFW(4),Kansas City(5), Los Angeles(6), Minneapolis(7), Mrytle Beach(8), New York(9), ,New Orleans(10), Pittsburgh(11)  respectively. The new graph.txt file shows all Vangurad flights between these cities. The first number in the data file is the number of cities(12) and the subsequent lines contain information about flights and the cost of flying between the cities. For example the cost of flying from Pittsburgh(11) to Chicago(2)  is $49. Therefore you will see the entry  11  2   49. Once you're done, you will use the Intro-CS Assignment Dropoff form to hand in your finished program.

What You'll Need

Download the lab6.zip file from the 15-111 course web site. Save the zip file to your temp directory and unzip the files. You should see the following files:

Assignment

You are re-implementing the Graph class with an adjacency list, in essence a vector of pointers to edges emanating from each vertex. Thus, your Edge struct will need a destination field (an int), a cost field (a double) and a pointer to the next edge that exits that vertex. You'll also need to add an Edge struct declaration in this file. Your Edge struct should resemble the following: 
        class Edge
        {
            int dest;
            double cost;
            Edge next;
            Edge(int d, double c, Edge link)

              {dest=d; cost=c; next=link;}
        }
Once you've changed the private data member, you should see what changes this causes in the declarations of the member functions (in particular, the one-parameter constructor). Then it's on to the implementation of all the member functions! You will need to write the implementations of the member functions, AddEdge(int origin, int destination, double value);RemoveEdge(int origin, int destination); bool HasEdge(int origin, int destination)  const;  double EdgeValue(int origin, int destination)  const;.

As in the Adjacency Matrix implementation, you may NOT assume that an edge is not already present between the two vertices in your new implementation of AddEdge and you may NOT assume that an edge is in the graph in your new implementation of RemoveEdge. You must do error checking. Your code should behave analagously to that which was present in the Adjacency Matrix implementation. Your driver program will open a second data file, updates.txt and perform modifications to the original graph. The format of the update.txt is as follows. Each line contains  4 data fields. The first field is the update command. Valid update commands are AddFlight, CancelFlight, ModifyFare. The next 3 data fields are integers given by origination city code (eg: Pittsburgh = 11) and the destination city code(eg:DFW=4) and the cost ($113). Your main program must process the update file and create a log file of changes. The log file is written to log.txt. Your output must be similar to what is produced by lab6.exe.

Handing in your Solution

Your solution should be in the form of a .zip file. When we grade your solution we will unzip the folder and execute the project.

Your Solution zip file must contain (only) the following files

  1. lab6.mcp (the project)
  2. graph.java
  3. edge.java
  4. graph-main-2.java
Do not include a copy of the datafile or updates file.