Read and familiarize yourself with the JCF classes. You may use these classes if you wish...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Read and familiarize yourself with the JCF classes. You may use these classes if you wish (or you are welcome to reuse your previous project code, or "roll your own" versions of these classes). Below is an overview of the most likely classes to be helpful in this assignment: 1. ArrayList and LinkedList - Java's list classes supported by a dynamic array or a linked structure respectively 2. ArrayDeque - Java's double ended queue supported by an array, LinkedList is Java's double ended queue supported by a linked list 3. PriorityQueue - Java's priority queue (supported by a heap) 4. HashMap and HashSet - Java's map and set supported by a hash table 5. TreeMap and TreeSet - Java's map and set supported by a red-black tree 6. Collection - All JCF classes implement this generic interface. Where should you start? The Java Tutorials of course! (If you didn't know, Oracle's official Java documentation includes a set of tutorials.) The Trail: Collections tutorial w provide you with more than enough information on how to use these classes. Task 2: Read the Provided Code Base (0%) Read and familiarize yourself with the code. This will save you a lot of time later. An overview of the provided code in is given below, but you need to read the code base yourself. //This class represents a node in a graph. //It is provided, but you may edit it in some specific ways if you want. class ThreeTenNode {...} //This class represents an edge in a graph. //It is provided, but you may edit it in some specific ways if you want. class ThreeTenEdge {...} //This class represents a directed graph. //You will write 99% of this class, but a template is provided. class ThreeTenGraph<V, E> implements Graph<V, E>, DirectedGraph<V, E> {...} //This interface defines an algorithm that can be simulated with the GUI interface ThreeTenAlg {...} //You will be writing this algorithm (Dijkstra's shortest path) class ThreeTenDijkstra implements ThreeTenAlg {...} //This is the simulator and handles all the graphical stuff, it is provided. class simGUI {...} Task 3: Implement a Directed Graph Class to Support the Simulator (50%) In order for the simulator to work, you need an internal representation of a graph. The JUNG library provides an interfaces for this: Graph<V, E>. You need to implement the directed graph ThreeTenGraph<V, E> (in Three TenGraph.java) which implements the Graph<V, E> interface. Below is a quick overview of the methods you need to support. Note that in the template, actual JavaDoc comments are provided. That said, the JavaDocs are those from the Graph<> interface and the HyperGraph<> interface in JUNG. They have been copied from that library for your reference, but are otherwise unaltered. Part of this assignment is to practice reading "real" documentation and understanding what to implement based on the library's requirements. //*** // Graph Editing (20%) ******// ********* boolean addEdge (E e, V v1, V v2) {...} boolean addVertex (V vertex) {...} boolean removeEdge (E edge) {...} boolean removeVertex (V vertex) {...} ********************************// // Graph Information (30%) //***** ********* //For a given graph... Collection<E> getEdges () {...} Collection<V> getVertices () {...} boolean containsVertex (V vertex) {...} boolean contains Edge (E edge) {...} int getEdgeCount() {...} int getVertexCount() {...} //For a given vertex in a graph... int degree (V vertex) {...} int getNeighborCount (V vertex) {...} Collection<E> getInEdges (V vertex) {...} Collection<E> getOut Edges (V vertex) {...} Collection<E> getIncident Edges (V vertex) Collection<V> getPredecessors (V vertex) {...} Collection<V> getSuccessors (V vertex) {...} Collection<V> getNeighbors (V vertex) {...} //Given two verticies in a graph... boolean isPredecessor (V V1, V v2) {...} boolean isSuccessor (V v1, V v2) {...} boolean isNeighbor (V v1, V v2) {...} E find Edge (V v1, V v2) {...} //Given an edge in a graph... V getSource (E directed_edge) {...} V getDest (E directed_edge) {...} Pair<V> getEndpoints (E edge) {...} Collection<V> getIncidentVertices (E edge) {...} //Given a vertex and an edge in a graph... boolean isIncident (V vertex, E edge) {...} When you are done with this step, you can generate and play with some graphs in the simulator (see the Examples Page). Hints and Notes • Read ALL the methods before you decide how to represent your graph, you may need track a lot more things than the simple graphs we covered in class. . Note that the graph has Objects for verticies and edges... this is not the same as an index! If only there was some way to map one object to a number... . Note that we cannot test editing a graph or getting information about a graph independently of each other. So you cannot get points for completing only the graph editing or only the graph information parts of this interface, you need everything... Task 4: Implement Dijkstra's Shortest Path Algorithm in the Simulator (45%) Now for the fun part! The simulator need to know what one "step" of Dijkstra's shortest path algorithm looks like. ThreeTenDijkstra (in ThreeTenDijkstra.java) Will provide the steps for the algorithm, but there are two related classes as well: 1. ThreeTenEdge (in Three TenEdge.java) provides a representation of an edge which is used by the simulator. It tracks things like the weight and color of an edge. 2. ThreeTenNode (in ThreeTenNode.java) provides a representation of a node which is used by the simulator. It tracks things like the text and color of a node. You may add additional private instance variables to both Three TenEdge and ThreeTenNode and associated public accessors and mutators if you want/need, but you may not break the code that exists and you may not add any public non-accessors/non-mutators methods. An overview of some key parts of ThreeTenDijkstra class is given below to get you started: //this is the actual "step" method, which calls other methods you will be writing... boolean step() { if(!started) { } } start(); return true; cleanUpLastStep(); if(!setupNextMin()) { finish(); return false; } doUpdates (); return true; //this code is partially provided for you, but you can add more setup here if you want/need void start() {...} //performs any "clean up" in preparation for performing another step of the algorithm //detailed instructions are provided in the template void cleanUpLastStep() {...} //pick the next minimum node to look at for the algorithm and updates the graph accordingly //detailed instructions are provided in the template boolean setupNextMin() {...} //does the neighbor updates from Dijkstra's algorithm //detailed instructions are provided in the template void doUpdates () {...} //this code is partially provided for you, but you can add more tear down here if you want/need //you also need to complete a helper method for the provided code to work void finish() {...} When you are done with this step, you can play the algorithm in the simulator (see the Examples Page). Hints and Notes • You must complete the JavaDocs for all three of these classes, so you may want to start by doing this to familiarize yourself with the code. • You are not responsible for making the algorithm work if the user edits the graph while Dijkstra's is running. Just assume all editing will take place before hitting "step" or "play" and that, if they want to do the algorithm again, they will hit "reset" and generate a new graph. Task 5: Runtime Write-up (5%) At the end of your readme.txt file, write a three sentence paragraph: Sentence 1 Describe how you chose to represent your graph internally. . Sentence 2-3 - Describe why you made your implementation the way you did. Specifically, you must indicate how your decisions were influenced by the Big-O runtime of your implementation. You must: 1. Have a style (indentation, good variable names, etc.) 2. Comment your code well in JavaDoc style (no need to overdo it, just do it well) 3. Have code that compiles with the command: javac -cp .;310libs.jar *.java (Windows) or javac -cp .:310libs.jar *.java (Linux/MacOS) in your user directory You may: 1. Add any additional private helper methods or instance variables to existing classes. 2. Add any additional classes you have written entirely yourself (such as simple data structures from previous projects). 3. [In Three TenNode and Three TenEdge ONLY] you add any additional public accessors and mutators for any private instance variables (but no other types of public methods can be added, and the existing ones still need to work). 4. Use any of the Java Collections Framework classes in java.util (already imported for you in the existing classes, you may add this to any additional classes you write). You may not: 1. Make your program part of a package. 2. Import any additional libraries/packages. 3. Alter any method signatures defined in the template code. Note: "throws" is part of the method signature in Java, don't add/remove these. 4. Add @SuppressWarnings to any methods unless they are private helper methods for use with a method we provided which already has an @SuppressWarnings on it. 5. Alter any fully provided classes (specifically simGUI) or methods that are complete and marked in a "DO NOT EDIT" section. 6. Use any code from the internet (including the JUNG libary) which was not provided to you in 310libs.jar. Example 1 Displaying a Graph Once you have the ThreeTenGraph<V, E> class working, you can run the main program to test and debug. The main program is SimGUI, which can be compiled and run with the following commands if you are on Windows: javac -cp .i318libs.jar xijava java -cp.:31elibs.jar SinGUI or the following commands if you are on Linux/MacOS: javac -cp .:318libs, jar w.java java -cp.:31elibs.jar sinGUI Why is there extra stuff? The -cp is short for classpath (meaning "where the class files can be found). The 310libs.jar or .:310libs.jar has the following components: the current directory, or the separator for Windows or Linux/MacOS respectively, 310libs.jar the provided jar file which contains the library code for JUNG. If you run the simulator with the above command, you will get a six node graph with some random edges. Each time you hit "reset" you get another graph, but the same sequence of graphs is always generated (for your testing). However, the simulator can also be run with some additional optional parameters to get some more interesting results: The number of nodes, the likelihood that two nodes have an edge between them, the random seed for the graph generator. For example: Image 14 Command java -cp. .:31@libs.jar SimGUI Explanation Generate a six node graph, with connection probability of 0.4, and seed 0. java -cp .:310libs.jar SimGUI 10 1 java -cp .:310libs.jar SimGUI 12 0.5 Generate a ten node graph where all nodes are connected. Generate a twelve node graph where nodes have a 50% chance of being connected. java -cp .:318libs.jar SimGUI 6 8.4 1123 Generate a difference sequence of graphs using seed 1123. Example 2 Adding nodes and edges to a graph You'll want to test out adding multiple nodes and edges from your graphs to make sure you've gotten out all the bugs. Algorithm Simulation Simulation Mode TRANSFORMING PICKING EDITING Image stop | ketliy 010-X Explanation Select "Mode", then "Editing". Algorithm Simulation Semulation Mode Step Reset Play OD Click Anywhere on the graph surface to add a node. Algorithm Simulation Simulation Mode 4 1000 Drag to another node to add an edge with at random weight. Example 3 Removing a nodes and edges from a graph You'll want to test out removing multiple nodes and edges from your graphs to make sure you've gotten out all the bugs. Algorithm Simulation Simulation Mode Image Delete Vertex PV Step Reset Play Explanation In any mode, right click a node and select "delete vertex". D Algorithm Simulation Simulation I Step Reset Play In any mode, right click an edge and select "delete edge". Example 4 Running Dijkstra's in the simulator You can try out Dijkstra's algorithm one step at a time to help debugging your code. Tmulam Image Explanation Setup your graph (you can zoom with mouse scroll) Hit "Step" (nodes should now show distances) Hit "Step" (smallest node is picked, edges are highlighted, and neighbors show their updates) Hit "Step" (previous node is finished, next smallest node is picked...) Hit "Play" (will complete the algorithm, used edges are in green and others are grey) Example 5 What happens for unreachable paths? The simulator should still step through all nodes (because this is what Dijkstra's algorithm does). However, the parent pointer for nodes that are "infinitely far away" is never set, so there are no green edges. Algorithm Simulation Simulation Mode Image TO 10 Step Reset Play Explanation Completed run for a graph with unreachable nodes. Read and familiarize yourself with the JCF classes. You may use these classes if you wish (or you are welcome to reuse your previous project code, or "roll your own" versions of these classes). Below is an overview of the most likely classes to be helpful in this assignment: 1. ArrayList and LinkedList - Java's list classes supported by a dynamic array or a linked structure respectively 2. ArrayDeque - Java's double ended queue supported by an array, LinkedList is Java's double ended queue supported by a linked list 3. PriorityQueue - Java's priority queue (supported by a heap) 4. HashMap and HashSet - Java's map and set supported by a hash table 5. TreeMap and TreeSet - Java's map and set supported by a red-black tree 6. Collection - All JCF classes implement this generic interface. Where should you start? The Java Tutorials of course! (If you didn't know, Oracle's official Java documentation includes a set of tutorials.) The Trail: Collections tutorial w provide you with more than enough information on how to use these classes. Task 2: Read the Provided Code Base (0%) Read and familiarize yourself with the code. This will save you a lot of time later. An overview of the provided code in is given below, but you need to read the code base yourself. //This class represents a node in a graph. //It is provided, but you may edit it in some specific ways if you want. class ThreeTenNode {...} //This class represents an edge in a graph. //It is provided, but you may edit it in some specific ways if you want. class ThreeTenEdge {...} //This class represents a directed graph. //You will write 99% of this class, but a template is provided. class ThreeTenGraph<V, E> implements Graph<V, E>, DirectedGraph<V, E> {...} //This interface defines an algorithm that can be simulated with the GUI interface ThreeTenAlg {...} //You will be writing this algorithm (Dijkstra's shortest path) class ThreeTenDijkstra implements ThreeTenAlg {...} //This is the simulator and handles all the graphical stuff, it is provided. class simGUI {...} Task 3: Implement a Directed Graph Class to Support the Simulator (50%) In order for the simulator to work, you need an internal representation of a graph. The JUNG library provides an interfaces for this: Graph<V, E>. You need to implement the directed graph ThreeTenGraph<V, E> (in Three TenGraph.java) which implements the Graph<V, E> interface. Below is a quick overview of the methods you need to support. Note that in the template, actual JavaDoc comments are provided. That said, the JavaDocs are those from the Graph<> interface and the HyperGraph<> interface in JUNG. They have been copied from that library for your reference, but are otherwise unaltered. Part of this assignment is to practice reading "real" documentation and understanding what to implement based on the library's requirements. //*** // Graph Editing (20%) ******// ********* boolean addEdge (E e, V v1, V v2) {...} boolean addVertex (V vertex) {...} boolean removeEdge (E edge) {...} boolean removeVertex (V vertex) {...} ********************************// // Graph Information (30%) //***** ********* //For a given graph... Collection<E> getEdges () {...} Collection<V> getVertices () {...} boolean containsVertex (V vertex) {...} boolean contains Edge (E edge) {...} int getEdgeCount() {...} int getVertexCount() {...} //For a given vertex in a graph... int degree (V vertex) {...} int getNeighborCount (V vertex) {...} Collection<E> getInEdges (V vertex) {...} Collection<E> getOut Edges (V vertex) {...} Collection<E> getIncident Edges (V vertex) Collection<V> getPredecessors (V vertex) {...} Collection<V> getSuccessors (V vertex) {...} Collection<V> getNeighbors (V vertex) {...} //Given two verticies in a graph... boolean isPredecessor (V V1, V v2) {...} boolean isSuccessor (V v1, V v2) {...} boolean isNeighbor (V v1, V v2) {...} E find Edge (V v1, V v2) {...} //Given an edge in a graph... V getSource (E directed_edge) {...} V getDest (E directed_edge) {...} Pair<V> getEndpoints (E edge) {...} Collection<V> getIncidentVertices (E edge) {...} //Given a vertex and an edge in a graph... boolean isIncident (V vertex, E edge) {...} When you are done with this step, you can generate and play with some graphs in the simulator (see the Examples Page). Hints and Notes • Read ALL the methods before you decide how to represent your graph, you may need track a lot more things than the simple graphs we covered in class. . Note that the graph has Objects for verticies and edges... this is not the same as an index! If only there was some way to map one object to a number... . Note that we cannot test editing a graph or getting information about a graph independently of each other. So you cannot get points for completing only the graph editing or only the graph information parts of this interface, you need everything... Task 4: Implement Dijkstra's Shortest Path Algorithm in the Simulator (45%) Now for the fun part! The simulator need to know what one "step" of Dijkstra's shortest path algorithm looks like. ThreeTenDijkstra (in ThreeTenDijkstra.java) Will provide the steps for the algorithm, but there are two related classes as well: 1. ThreeTenEdge (in Three TenEdge.java) provides a representation of an edge which is used by the simulator. It tracks things like the weight and color of an edge. 2. ThreeTenNode (in ThreeTenNode.java) provides a representation of a node which is used by the simulator. It tracks things like the text and color of a node. You may add additional private instance variables to both Three TenEdge and ThreeTenNode and associated public accessors and mutators if you want/need, but you may not break the code that exists and you may not add any public non-accessors/non-mutators methods. An overview of some key parts of ThreeTenDijkstra class is given below to get you started: //this is the actual "step" method, which calls other methods you will be writing... boolean step() { if(!started) { } } start(); return true; cleanUpLastStep(); if(!setupNextMin()) { finish(); return false; } doUpdates (); return true; //this code is partially provided for you, but you can add more setup here if you want/need void start() {...} //performs any "clean up" in preparation for performing another step of the algorithm //detailed instructions are provided in the template void cleanUpLastStep() {...} //pick the next minimum node to look at for the algorithm and updates the graph accordingly //detailed instructions are provided in the template boolean setupNextMin() {...} //does the neighbor updates from Dijkstra's algorithm //detailed instructions are provided in the template void doUpdates () {...} //this code is partially provided for you, but you can add more tear down here if you want/need //you also need to complete a helper method for the provided code to work void finish() {...} When you are done with this step, you can play the algorithm in the simulator (see the Examples Page). Hints and Notes • You must complete the JavaDocs for all three of these classes, so you may want to start by doing this to familiarize yourself with the code. • You are not responsible for making the algorithm work if the user edits the graph while Dijkstra's is running. Just assume all editing will take place before hitting "step" or "play" and that, if they want to do the algorithm again, they will hit "reset" and generate a new graph. Task 5: Runtime Write-up (5%) At the end of your readme.txt file, write a three sentence paragraph: Sentence 1 Describe how you chose to represent your graph internally. . Sentence 2-3 - Describe why you made your implementation the way you did. Specifically, you must indicate how your decisions were influenced by the Big-O runtime of your implementation. You must: 1. Have a style (indentation, good variable names, etc.) 2. Comment your code well in JavaDoc style (no need to overdo it, just do it well) 3. Have code that compiles with the command: javac -cp .;310libs.jar *.java (Windows) or javac -cp .:310libs.jar *.java (Linux/MacOS) in your user directory You may: 1. Add any additional private helper methods or instance variables to existing classes. 2. Add any additional classes you have written entirely yourself (such as simple data structures from previous projects). 3. [In Three TenNode and Three TenEdge ONLY] you add any additional public accessors and mutators for any private instance variables (but no other types of public methods can be added, and the existing ones still need to work). 4. Use any of the Java Collections Framework classes in java.util (already imported for you in the existing classes, you may add this to any additional classes you write). You may not: 1. Make your program part of a package. 2. Import any additional libraries/packages. 3. Alter any method signatures defined in the template code. Note: "throws" is part of the method signature in Java, don't add/remove these. 4. Add @SuppressWarnings to any methods unless they are private helper methods for use with a method we provided which already has an @SuppressWarnings on it. 5. Alter any fully provided classes (specifically simGUI) or methods that are complete and marked in a "DO NOT EDIT" section. 6. Use any code from the internet (including the JUNG libary) which was not provided to you in 310libs.jar. Example 1 Displaying a Graph Once you have the ThreeTenGraph<V, E> class working, you can run the main program to test and debug. The main program is SimGUI, which can be compiled and run with the following commands if you are on Windows: javac -cp .i318libs.jar xijava java -cp.:31elibs.jar SinGUI or the following commands if you are on Linux/MacOS: javac -cp .:318libs, jar w.java java -cp.:31elibs.jar sinGUI Why is there extra stuff? The -cp is short for classpath (meaning "where the class files can be found). The 310libs.jar or .:310libs.jar has the following components: the current directory, or the separator for Windows or Linux/MacOS respectively, 310libs.jar the provided jar file which contains the library code for JUNG. If you run the simulator with the above command, you will get a six node graph with some random edges. Each time you hit "reset" you get another graph, but the same sequence of graphs is always generated (for your testing). However, the simulator can also be run with some additional optional parameters to get some more interesting results: The number of nodes, the likelihood that two nodes have an edge between them, the random seed for the graph generator. For example: Image 14 Command java -cp. .:31@libs.jar SimGUI Explanation Generate a six node graph, with connection probability of 0.4, and seed 0. java -cp .:310libs.jar SimGUI 10 1 java -cp .:310libs.jar SimGUI 12 0.5 Generate a ten node graph where all nodes are connected. Generate a twelve node graph where nodes have a 50% chance of being connected. java -cp .:318libs.jar SimGUI 6 8.4 1123 Generate a difference sequence of graphs using seed 1123. Example 2 Adding nodes and edges to a graph You'll want to test out adding multiple nodes and edges from your graphs to make sure you've gotten out all the bugs. Algorithm Simulation Simulation Mode TRANSFORMING PICKING EDITING Image stop | ketliy 010-X Explanation Select "Mode", then "Editing". Algorithm Simulation Semulation Mode Step Reset Play OD Click Anywhere on the graph surface to add a node. Algorithm Simulation Simulation Mode 4 1000 Drag to another node to add an edge with at random weight. Example 3 Removing a nodes and edges from a graph You'll want to test out removing multiple nodes and edges from your graphs to make sure you've gotten out all the bugs. Algorithm Simulation Simulation Mode Image Delete Vertex PV Step Reset Play Explanation In any mode, right click a node and select "delete vertex". D Algorithm Simulation Simulation I Step Reset Play In any mode, right click an edge and select "delete edge". Example 4 Running Dijkstra's in the simulator You can try out Dijkstra's algorithm one step at a time to help debugging your code. Tmulam Image Explanation Setup your graph (you can zoom with mouse scroll) Hit "Step" (nodes should now show distances) Hit "Step" (smallest node is picked, edges are highlighted, and neighbors show their updates) Hit "Step" (previous node is finished, next smallest node is picked...) Hit "Play" (will complete the algorithm, used edges are in green and others are grey) Example 5 What happens for unreachable paths? The simulator should still step through all nodes (because this is what Dijkstra's algorithm does). However, the parent pointer for nodes that are "infinitely far away" is never set, so there are no green edges. Algorithm Simulation Simulation Mode Image TO 10 Step Reset Play Explanation Completed run for a graph with unreachable nodes.
Expert Answer:
Related Book For
Posted Date:
Students also viewed these organizational behavior questions
-
Familiarize yourself with the following industry. PAYX Answer the following questions for this industry analysis. Using any annual reports found online very easily. All 12 questions need to be...
-
In order to familiarize yourself with the measures of variation, compute the range, standard deviation, and variance for each set of scores. a. .6, .5, .8, .6, .2, .3, .9, .9, .7 b. 9.62, 9.31, 9.15,...
-
Visit behaviouralfinance.net and familiarize yourself with the list of behavioural finance terms that are not covered in this chapter.
-
A record company needs to produce 100 gold records at one or more of its three studios. the cost of producing x records at studio 1 is 10 x; the cost of producing y records at studio 2 is 2y 2 ; the...
-
Sammi Company needs to determine the amount of inventory in its warehouse at the time that an earthquake destroyed it. Sammis gross profit percentage averaged 28% over the last three years. Sammi...
-
How do loan sales and securitization help an FI manage its interest rate and liquidity risk exposures?
-
9. ROLE REVERSAL Draft an essay or short-answer question that involves a dispute brought to the WTO on one of these issues: dumping, nontariff barriers, or intellectual property.
-
The following is an excerpt from a note to the nancial statements of the city of Dallas (dates changed): The city prepares its annual appropriated general fund, debt service fund, and proprietary...
-
Problem 1 A company made the following merchandise purchases and sales during the month of July: July 1 purchased 380 units at $15 each July 5 purchased 270 units at $20 each July 9 sold 500 units at...
-
Amanda Autry and Carley Wilson are partners in A & W Gift Shop, which employs the individuals listed below. Paychecks are distributed every Friday to all employees. Based on the information given,...
-
Edge Soccer Program (Edge) began the year with a cash balance of $10,500. The budget forecasts that collections from customers owed to the company will be $11,000 in January and $15,200 in February....
-
Why has Congress criticized nonattest services?
-
What services are generally provided to clients by public accounting firms?
-
Discuss economic explanations for why audits arose before any government or governmental agency required them.
-
How are financial statement audits and other attestation services (e.g., environmental and cost audits) similar and different?
-
How are auditing and accounting related?
-
The gross value of Diamond Wholesaler Inc.'s accounts receivable as of December 31, Year 1 and Year 2 was $860,000 and $1,500,000, respectively. The balance in the allowance for uncollectible...
-
Given that all the choices are true, which one concludes the paragraph with a precise and detailed description that relates to the main topic of the essay? A. NO CHANGE B. Decades, X-ray C. Decades...
-
What are the disadvantages of using z distributions?
-
Distinguish between a theory and a hypothesis.
-
The Humane Society has to set up a budget for the coming year. The concern is whether they need to buy more dog food or more cat food. Over the past year, they have housed 637 cats and 725 dogs. If...
-
To determine whether your firm should change its dividend policy, based on an analysis of its investment opportunities and comparable firms. Key Questions How much could this firm have returned to...
-
What are the current trends in software platforms?
-
One early morning in the fall of 2007, Dennis Jonsson was reading the latest reports on global warming and thought that someone ought to do something about it. Then he realized that he and his fellow...
Study smarter with the SolutionInn App