Graph Algorithm Simulator

CS 310 Programming Assignment 4 Due: November 18th (Thursday) 11:59pm, 2021

Quick Links

Assignment Objectives

Create and use a graph data structure.
Update a priority queue (heap) data structure for new features.
Understand Prim's minimum spanning tree algorithm on a graph, integrating key components with existing visualization code.
Apply basic knowledge of Big-O.

Assignment Overview

Professional code often uses existing libraries to quickly prototype interesting programs. You are going to use 2-3 established libraries to quickly develop the internal representation of an advanced data structure (a graph) and simulate a simple graph algorithm (Prim's Minimum Spanning Tree Algorithm). This GUI can be easily extended to other types of algorithms you might encounter in the future (such as in CS483), and you may find it useful to simulate later algorithms you learn using this same framework.

The four libraries you are going to use are:

The PriorityQueue portion of the Weiss data structures library from your textbook (this is provided to you with your textbook for free on the author’s website, if you’ve never looked).
Your previous project code - You will need a hash table for part of this project, and you have written one in Project 3. You're encouraged to reuse your implementation!
The Java Collections Framework - This is a collection of existing simple data structures (lists, queues, sets, maps, etc.) which can form the basis for more advanced data structures.
A subset of JUNG (Java Universal Network/Graph Framework) - This library provides a lot of cool visualization tools for graphs: automatic layouts for graphs, an easy interface for creating/editing graphs, and much more.

Tasks Overview

There are 5 tasks in this assignment. It is suggested that you implement these tasks in the given order:

Task 1: Examine the JCF Classes (0%)
Task 2: Read the Provided Code Base (0%)
Task 3: Implement an Undirected Graph Class to Support the Simulator (60%)
Task 4: Implement an Efficient Update Mechanism for a Heap Class (30%)
Task 5: Implement Prim's Minimum Spanning Tree Algorithm in the Simulator (10%)

See the Examples Page for what the simulator should be able to do when you are done, and then see the Task Details Page for a walk-through of each specific task.

Need a schedule?

You've got 2.5 weeks.
You have other classes with final exams/projects.
Assume you want to spend the last half week doing the EC and getting additional help.
Keeping those things in mind, fill in the following:
- 11/01-11/04: _______________________________ (first week)
  - Suggestions: Task 1 and Task 2
- 11/05-11/07: _______________________________ (first weekend)
  - Suggestions: JavaDocs for All Classes, Start Task 3
- 11/08-11/11: _______________________________ (second week)
  - Suggestions: Finish Task 3
- 11/12-11/14: _______________________________ (second weekend)
  - Suggestions: Task 4 and Task 5
- 11/15-11/18: _______________________________ (third week)
  - Suggestions: Turn in early for extra credit

Rules and Grading