Current Posting

This was updated December 4, 2001. This should be the final posting. Read FAQ for any minor updates.

This was posted November 29, 2001. More to be posted soon.

Checklist

A link to a checklist will be provided. You should read the checklist several times, but especially before submitting your project. (To be posted soon)

Project 5 Checklist

Purpose

The purpose of the Project 5

1. To learn use other features of STL.
2. To be able to modify pre-existing code (in this case, written by instructors) for adjacency list and heaps.
3. To implement a graph algorithm, most notably, Dijkstra's shortest path algorithm.

Hardcoding is a Violation of Academic Integrity

If you "hardcode" the output, i.e., attempt to produce the primary output by using print statements or other similar techniques, or use simplified data structures (for example, using an array when you've been asked to use a binary search tree), you may be receive a 0 on the project, and be brought up on charges of academic dishonesty.

Academic Integrity Statement

Any evidence of unauthorized use of computer accounts or cooperation on projects will be submitted to the Student Honor Council, which could result in an XF for the course, suspension, or expulsion from the University. Projects are to be written INDIVIDUALLY. For academic honesty purposes, projects are to be considered comparable to a take-home exam. Any cooperation or exchange of ideas which would be prohibited on an exam is prohibited on a project assignment, and WILL BE REPORTED to the Honor Council.

VIOLATIONS OF ACADEMIC HONESTY INCLUDE:

1. failing to do all or any of the work on a project by yourself, other than assistance from the instructional staff.

2. using any ideas or any part of another student's project, or copying any other individual's work in any way.

3. giving any parts or ideas from your project, including test data, to another student.

4. having programs on an open account or on a PC that other students can access.

5. transferring any part of a project to or from another student or individual by any means, electronic or otherwise.

6. publishing any of your code publicly (e.g., via a webpage) which other students can access, even if the project is already due.

IT IS THE RESPONSIBILITY, UNDER THE UNIVERSITY HONOR POLICY, OF ANY STUDENT WHO LEARNS OF AN INCIDENT OF ACADEMIC DISHONESTY TO REPORT IT TO THEIR INSTRUCTOR.

Style Guide

Here it is

FAQ

We will provide corrections and announcements, as well as "frequently asked questions" on the Project 5 FAQ page.

Project Overview

In this project, you will have to write a parser to read an input file. This input file will give information about several locations, followed by distances to neighbors, followed by one or more commands. Here is a sample input file.

<sitelist>
  <site> Tatooine  </site>
  <site> Alderaan  </site>
  <site> Coruscant  </site>
  <site> Dagobah  </site>
</sitelist>

<adjacencylist>
  <entry>
     <site> Coruscant  </site>
     <neighborlist>
        <neighbor>
          <site> Dagobah  </site>
          <distance> 10 </distance>
        </neighbor>
        <neighbor>
          <site> Alderaan  </site>
          <distance> 20 </distance>
        </neighbor>
     </neighborlist>
   </entry>

  <entry>
     <site> Alderaan  </site>
     <neighborlist>
        <neighbor>
          <site> Coruscant  </site>
          <distance> 20 </distance>
        </neighbor>
     </neighborlist>
   </entry>
</adjacencylist>

<cmmdlist>
 <cmmd> SHORTEST_PATH Dagobah Alderaan </cmmd>
 <cmmd> SHORTEST_ALL Dagobah </cmmd>
</cmmdlist>

Site list

The first part of the input file (which will be read in though input redirection) is the sitelist. This will list all sites. You may assume that each site will be one word. The list is not necessarily sorted. You should short the list, in alphabetical order. These will represent vertices in your adjacency list.

It's important that you sort the list so that everyone numbers their vertices the same. For example, there are four sites listed. In alphabetical order, they are: Alderaan, Coruscant, Dagobah, and Tatooine, and would be numbered 0 thorough 3.

You may assume this list is non-empty, and there are no duplicates.

Adjacency List

The second part of the input file is the adjacency list. This records information about the distances to neighbors. The adjacency list consists of entries. Each entry consists of the name of a site, and the lists of the neighbors of that site, and the corresponding distances.

You may assume that the graph that is produced is undirected. The list of neighbors may therefore not be complete. If Alderaan is listed as a neighbor of Tatooine, then it's not necessary for Tatooine to list Alderaan as a neighbor. If they do list each other, you may assume the distances will be the same. Thus if Alderaan is a neighbor of Coruscant and Coruscant is a neighbor of Alderaan, both should have equal distances.

You should enter edges in both directions into the adjacency list, even if it's only listed in one direction.

The graph does not have to be connected.

Command List

There are only two commands to support: SHORTEST_PATH, which will list out the shortest path between two sites (it lists all intermediate sites, or states that it is unreachable), and the actual shortest distance, and SHORTEST_ALL, which lists out the shortest path distances (not the actual path) to all remaining sites.

Classes Provided

You will be provided two classes: MinHeap and AdjacencyList. The use of MinHeap is optional (5 points extra credit). You can use a PriorityQueue class which you write. A PriorityQueue can simply be an STL vector which contains a Node object (which you write) that contains a weight (tenative cost) and the vertex number.

To remove the minimum value, sort the vector (where the operator< compares the weights of two nodes) and pick the minimum. Remove this from the vector using erase(). Then, update the neighbors costs using linear search in the vector. This is easy to implement, although it runs slowly.

Classes You Write

You will need to write a main.cpp which will serve as your driver. It must be named exactly this. You can write any additional classes you want. Explain which classes you write in the README. You MAY be graded on how many classes you write and your justification for writing such classes. You shouldn't need too many.

You will also need to write a file called "dijkstra.cpp" which will contain all the functions to compute shortest path. You will be provided "dijkstra.h" to work with.

MinHeap class in detail (NEW)

You do NOT have to use the MinHeap class provided. However, if you do not use it as listed (meaning, it must be a template and it must support heapToVertex and vertexToHeap implementations), you don't get 5 points bonus.

First, some corrections. The word "hash" should really be heap. There is no hash table in this implementation.

What are these arrays? You will enter elements into the heap in order starting from vertex 0 up to vertex N - 1, where N is the number of elements in the heap.

The heap will store the "current minimum cost" of each vertex. Initially, the start vertex has weight 0 and the other vertices have infinity (pick a large number, like 100000 for the weight).

In Dijkstra's algorithm, you have a "decrease key" operation which occurs when the cost of a vertex is smaller due to the "relax" operation. When this happens, you, the user of the "heap" will want to specify the vertex whose cost has been decreased (you simply put the new value of the cost as argument to the function call).

However, even though you may specify vertex 5, that may not be the index where it is located in the heap. This is what vertexToHeap is about. You call vertexToHeap[ 5 ] and it should return the index in the heap.

vertexToHeap and heapToVertex are "inverses" of each other (as taught in CMSC 250). Thus, vertexToHeap[ heapToVertex [ i ] ] == i and vice versa.

You must maintain this relation, even as you do the "heapify" or "upheapify" operation.

Heapify/UpHeapify

The "heapify" operation moves a node DOWN the heap (closer to the leaves) by swapping a node with the minimum of the two children and stopping when the heap condition is satisfied. This is used in deletions.

"upheapify" is used in decreaseKey and insert operations. It assumes a node has a small cost/weight and needs to be moved up the heap (closer to the root). Swaps only occur with parents.

Extra Credit

The reason that MinHeap is extra credit is twofold. First, it is a "constraining" class, meaning that you must make it work with templates (whether you like it or not) and you must make it work with these inverse arrays.

Should you choose not to do either one, you should change the name to "PriorityQueue". If you do not implement "MinHeap" with both features, then you will be deducted 5 points for trying to "fool the TA".

Use STL

In this project, we expect you to use STL. You can get rid of all the classes you wrote (BstSortedList, ArrayList) and use STL versions of all them (vector, list, etc).

A posting on STL will be provided to give you enough background to use this. You should be familiar with how to use most of it, since you had to use vectors back in Project 1, and have implemented classes similar to that provided in STL.

Partial Credit

For partial credit, you may wish to implement an Adjacency Matrix class from scratch. This may be easier to use than the AdjacencyList class that will be provided.

After Parsing

Once yuo parse the input, you need to print the list of sites by vertex number. This will require sorting the sites in alphabetical order.

The message will look like:

After parsing sites
----*----*----*----*----*----*
 Vertex 0 : Alderaan
 Vertex 1 : Coruscant
 Vertex 2 : Dagobah
 Vertex 3 : Tatooine

You may assume there is at least one site. The syntax can be deduced from the above. (Add one blank line after the last vertex).

Commands

You will need to support the following commands.

• ADD_EDGE <source> <dest> <cost>

  You may assume the source and destination are valid vertex numbers. The cost is assumed to be positive float. If successful print a message like:

  [ADD_EDGE] Edge from (<source>) to (<dest>) with cost <cost> successfully added
  

  Again, add a blank line afterwards. Recall that this is a undirected graph, so edges are added in both directions.

  If the edge already exists, then print

  [ADD_EDGE] Edge from (<source>) to (<dest>) already exists
  

  and don't add edge.

• UPDATE_EDGE <source> <dest> <cost>

  You may assume the source and destination are valid vertex numbers. The cost is assumed to be positive float. If successful print a message like:

  [UPDATE_EDGE] Edge from (<source>) to (<dest>) with cost <cost> successfully updated
  

  Again, add a blank line afterwards. Recall that this is a undirected graph, so edges are updated in both directions.

  If the edge does not exist, then print

  [UPDATE_EDGE] Edge from (<source>) to (<dest>) does NOT exist
  

  and don't update edge.

• REMOVE_EDGE <source> <dest>

  You may assume the source and destination are valid vertex numbers. If successful print a message like:

  [REMOVE_EDGE] Edge from (<source>) to (<dest>) with cost <cost> successfully removed
  

  Again, add a blank line afterwards. Recall that this is a undirected graph, so edges are removed in both directions.

  If the edge does not exist, then print

  [REMOVE_EDGE] Edge from (<source>) to (<dest>) does NOT exist
  

  and don't remove edge.

• NUM_EDGES

  Print the following for the current graph

  [NUM_EDGES] The graph has <num> undirected edges
  

  where <num> is replaced by the number of undirected edges.

  Again, add a blank line afterwards. Recall that this is a undirected graph, so edges are updated in both directions.

• SHORTEST_PATH <source> <dest>

  You may assume <source> and <dest> are valid vertices (in the graph). However, there may not be a path between the two.

  If there is a path, print:

  [SHORTEST_PATH]   The shortest path from (<source>) and (<dest>)
    Dagobah to Coruscant  (10 parsecs)
    Coruscant to Alderaan  (20 parsecs)
    ----*----*----*----*----*----*
      Total: 30 parsecs
  

  But list intermediates sites. For example, if the path is from site A to site C to site B to site E, then print "A to C" on the first line and the distance, followed by "C to B" on the next line, and the distance between the two, followed by "B to E" on the next line. Then, put the dashes as shown above, and provide the total distance.

  If no path exists, print

  [SHORTEST_PATH] No path exists from (<source>) and (<dest>)
  

• SHORTEST_ALL <source>

  This lists the shortest path to all vertices. The vertices be listed in alphabetical order. You should assume shortest path to the source vertex is itself. Here is an example:

  [SHORTEST_ALL] Shortest distance from (Dagobah) to: 
    Alderaan (30 parsecs)
    Coruscant (10 parsecs)
    Dagobah (0 parsecs)
    Tatooine (UNREACHABLE)
  

  Since there is at least one vertex, you shouldn't worry about the case of no vertices.

• PRINT_GRAPH

  Print the current graph using the print function from the adjacency list.

• DEBUG <source>

  This takes one argument, a source, and prints something like:

  [DEBUG]
  
  Vertex To Heap
  ----*----*----*
   1 --> 2
   2 --> 1
   4 --> 0
  
  Heap To Vertex
  ----*----*----*
   0 --> 4
   1 --> 2
   2 --> 1
  
  Heap Cost
  ----*----*----*
   0 --> 10
   1 --> 25
   2 --> 14
  
  

  This will print the heap after ONE step of Dijkstra's algorithm. This is the step AFTER the source vertex has been selected as the min cost vertex, and its neighbors "relaxed". For example, suppose source vertex A has neighbors B, C, and D with edge weights 3, 7, and 2 respectively. It should print out the information just after A has been selected and B, C, and D have their weights modified to 3, 7, and 2, and the heap has been re "heapified".

  This prints the contents of vertex to heap (there may be "gaps" in the vertex index, so only print the vertices that remain the heap), then heap to vertex, then the cost in each heap. You should be able to write this by modifying the "debug()" function in the MinHeap.

  If you choose not to do MinHeap, just treat this as an illegal command and print the illegal command message as in previous projects.

Designing Sensible Classes

You can use classes from previous projects in this project. You should name them something obvious (i.e., as you named them in previous projects). You may lose points if you decide to do everything in main() or avoid writing classes.

README

Submit a README with your files. Give a list of classes you wrote, and why you wrote them. Again, you may be evaluated on the number of classes written, and their justification. Also, indicate whether you used a MinHeap class or wrote your own PriorityQueue class. MinHeap will gain some extra credit.

How to Submit Your Project

As with Project 1

submit p5.tar 5 SUBMIT

Your executable must be called exactly p5. Any other name will cause your program not to be submitted.

You can name the tar whatever you want. However, you should wait until a primary input and output have been posted. (If you submit before that, then if your project does not pass the primary input/output, you will receive a poor grade on the project, most likely a zero).

Please do not submit until a primary input and output have been posted. If you do, you may receive a 0 for failing to pass the primary.

Web Accessibility