Read and familiarize yourself with the JCF classes. You may use these classes if you wish...

           
       

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.