Basic Graph Data Structure Assignment
4 Pages1092 Words99 Views
Added on 2019-10-09
Basic Graph Data Structure Assignment
Added on 2019-10-09
ShareRelated Documents
Assignment 5 – Due Thursday, November 17Objective: The objective of this assignment is for you to gain experience working with the basic graphdata structure, including iterating through vertices and adjacencies. This assignment is not as long orintricate as other full-credit assignments, so take the time to experiment with the graph data structureand 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 torepresent prerequisites as a graph (like on the prerequisite chart we publish on our department webpage). It is easy to create a graph of courses linked to prerequisites by scraping data from theUniversity Bulletin, and you can use that as input to construct a graph with an edge from a course toeach 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 theoriginal graph, or the graph with the same vertices and connections, but with the direction of eachedge reversed. Your goal for this assignment is to write methods that will allow you to take a graph ofComputer Science courses and prerequisites, and print the transpose graph. Samples of the output forboth the original graph and the transposed graph are given on the following pages.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 thenuse 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 on thefollowing pages. Note that the output is “nice” in the sense that each vertex is followed by anappropriate, grammatically correct phrase on the same line, depending on whether there arezero, one, or more adjacent vertices. Note also that the vertices are given in sorted order — youactually get that “for free” if you change one data structure that is used in the Weiss graphimplementation. These small touches matter!•getTransposedGraph() operates on a graph and returns a new graph that is the transposeof the original graph (which is not changed).Submission Instructions: Using NetBeans, commit all changes to your project and do a “push toupstream” to put the most up-to-date files on the Bitbucket server. Remember: Do not create a pullrequest — I will clone your repository (if it exists and you granted me access) at 12:30 on the duedate, and will assume that is your submission. If you intend to keep working on your project andsubmit late, please let me know by email, and I will ignore your repository until the late submissiondeadline.2Handout10:Assignment5–DueThursday,November17
Original Graph Output: This shows the output of the printGraph() method when called on theoriginal graph (courses with edges to their prerequisites). Youroutputwillnotbetwocolumns,ofcourse—it’sjustprintedthatwayheretosavespace.CSC130 -- no edges out CSC230 --edge out to:CSC130CSC250 -- edge out to: CSC130CSC261 -- edges out to:CSC230CSC250CSC312 -- edges out to:CSC230CSC250CSC330 -- edges out to:CSC230CSC250CSC339 -- edge out to:CSC330CSC340 -- edge out to:CSC330CSC350 -- edge out to: CSC250CSC463 -- edges out to:CSC562CSC567CSC464 -- edge out to:CSC463CSC465 -- edge out to:CSC464CSC471 -- edge out to: CSC330CSC510 -- edges out to:CSC330CSC567CSC521 -- edges out to:CSC340CSC350CSC522 -- edges out to:CSC330CSC350CSC523 -- edges out to:CSC130CSC350CSC524 -- edge out to: CSC523CSC529 -- edges out to:CSC330CSC350CSC539 -- edges out to:CSC261CSC330CSC540 -- edge out to:CSC340CSC553 -- edge out to:CSC350CSC555 -- edge out to: CSC330CSC561 -- edges out to:CSC261CSC330CSC350CSC562 -- edges out to:CSC261CSC340CSC567 -- edges out to:CSC261CSC330CSC568 -- edges out to:CSC330CSC567CSC580 -- edges out to:CSC330CSC350
End of preview
Want to access all the pages? Upload your documents or become a member.
Related Documents
Graph Coloring: A Breakthrough in Sciencelg...
|6
|1529
|407
Physics 201 Lab 1 - Working with Numberslg...
|3
|907
|51