CSC 330: Advanced Data Structures
Navigation
Class Home
Syllabus
Textbook Code
Handouts
Assignments
Java API Docs
More Information

A printable PDF is available.

Assignment 5 - Due Thursday, November 17

Objective: The objective of this assignment is for you to gain experience working with the basic graph data structure, including iterating through vertices and adjacencies. This assignment is not as long or intricate as other full-credit assignments, so take the time to experiment with the graph data structure and get comfortable working with it. The time you invest in this will pay off on the final assignment!

Background: Courses in Computer Science depend heavily on prerequisites, and it is common to represent prerequisites as a graph (like on the prerequisite chart we publish on our department web page). It is easy to create a graph of courses linked to prerequisites by scraping data from the UNCG Bulletin, and you can use that as input to construct a graph with an edge from a course to each of its prerequisites. However, sometimes we might want to look at this graph in the other way: For each course that acts as a prerequisite, what courses depend on it? This is the transpose of the original graph, or the graph with the same vertices and connections, but with the direction of each edge reversed. Your goal for this assignment is to write methods that will allow you to take a graph of Computer Science courses and prerequisites, and print the transpose graph. Samples of the output for both the original graph and the transposed graph are given below.

What To Do: Start with the code in Bitbucket, as in previous assignments: fork the "Assign5" repository, rename it to include your username, grant read access to the class administrators, and then use NetBeans on your computer to clone it so you can work with it.

You are to write two methods (stubs are given in the provided code):

  • printGraph() prints the graph in a readable form, as shown in the samples below. Note that the output is "nice" in the sense that each vertex is followed by an appropriate, grammatically correct phrase on the same line, depending on whether there are zero, one, or more adjacent vertices. Note also that the vertices are given in sorted order -- you actually get that "for free" if you change one data structure that is used in the Weiss graph implementation. These small touches matter!

  • getTransposedGraph() operates on a graph and returns a new graph that is the transpose of the original graph (which is not changed).

Submission Instructions: Using NetBeans, commit all changes to your project and do a "push to upstream" to put the most up-to-date files on the Bitbucket server. Remember: Do not create a pull request -- I will clone your repository (if it exists and you granted me access) at 12:30 on the due date, and will assume that is your submission. If you intend to keep working on your project and submit late, please let me know by email, and I will ignore your repository until the late submission deadline.

Original Graph Output: This shows the output of the printGraph() method when called on the original graph (courses with edges to their prerequisites). 

CSC130 -- no edges out
CSC230 -- edge out to:
    CSC130
CSC250 -- edge out to:
    CSC130
CSC261 -- edges out to:
    CSC230
    CSC250
CSC312 -- edges out to:
    CSC230
    CSC250
CSC330 -- edges out to:
    CSC230
    CSC250
CSC339 -- edge out to:
    CSC330
CSC340 -- edge out to:
    CSC330
CSC350 -- edge out to:
    CSC250
CSC463 -- edges out to:
    CSC562
    CSC567
CSC464 -- edge out to:
    CSC463
CSC465 -- edge out to:
    CSC464
CSC471 -- edge out to:
    CSC330
CSC510 -- edges out to:
    CSC330
    CSC567
CSC521 -- edges out to:
    CSC340
    CSC350
CSC522 -- edges out to:
    CSC330
    CSC350
CSC523 -- edges out to:
    CSC130
    CSC350
CSC524 -- edge out to:
    CSC523
CSC529 -- edges out to:
    CSC330
    CSC350
CSC539 -- edges out to:
    CSC261
    CSC330
CSC540 -- edge out to:
    CSC340
CSC553 -- edge out to:
    CSC350
CSC555 -- edge out to:
    CSC330
CSC561 -- edges out to:
    CSC261
    CSC330
    CSC350
CSC562 -- edges out to:
    CSC261
    CSC340
CSC567 -- edges out to:
    CSC261
    CSC330
CSC568 -- edges out to:
    CSC330
    CSC567
CSC580 -- edges out to:
    CSC330
    CSC350
CSC583 -- edges out to:
    CSC567
    CSC580

Transposed Graph Output: This shows the output of the transposed graph (the graph with all edge directions reversed). From this output, we can easily check a course to see what later courses depend on it. Note how important this class (CSC 330) is! 

CSC130 -- edges out to:
    CSC230
    CSC250
    CSC523
CSC230 -- edges out to:
    CSC261
    CSC312
    CSC330
CSC250 -- edges out to:
    CSC261
    CSC312
    CSC330
    CSC350
CSC261 -- edges out to:
    CSC539
    CSC561
    CSC562
    CSC567
CSC312 -- no edges out
CSC330 -- edges out to:
    CSC339
    CSC340
    CSC471
    CSC510
    CSC522
    CSC529
    CSC539
    CSC555
    CSC561
    CSC567
    CSC568
    CSC580
CSC339 -- no edges out
CSC340 -- edges out to:
    CSC521
    CSC540
    CSC562
CSC350 -- edges out to:
    CSC521
    CSC522
    CSC523
    CSC529
    CSC553
    CSC561
    CSC580
CSC463 -- edge out to:
    CSC464
CSC464 -- edge out to:
    CSC465
CSC465 -- no edges out
CSC471 -- no edges out
CSC510 -- no edges out
CSC521 -- no edges out
CSC522 -- no edges out
CSC523 -- edge out to:
    CSC524
CSC524 -- no edges out
CSC529 -- no edges out
CSC539 -- no edges out
CSC540 -- no edges out
CSC553 -- no edges out
CSC555 -- no edges out
CSC561 -- no edges out
CSC562 -- edge out to:
    CSC463
CSC567 -- edges out to:
    CSC463
    CSC510
    CSC568
    CSC583
CSC568 -- no edges out
CSC580 -- edge out to:
    CSC583
CSC583 -- no edges out