Use cases we used: o High-Level Use Case: Use Case: Receiving Class Dictionary and Traversal Specification from GUI team Actors: GUI team, Algorithms team Description: The GUI team sends the algorithms team two inputs: the class dictionary of the class graph drawn in CD-Draw(in the format of evolve.cd) and the traversal specification Basic Course of Events: 1. This use case begins when the GUI group sends us two input files: a .input file (class dictionary of the class graph) and a .trav file (the traversal specification) 2. In the main program, the .input file is parsed into an UGraph object. 3. The .trav file is parsed into an IndependentTraversal object. 4. The method markSubgraph of the UGraph object is called to calculate the subgraph. Alternative Course of Events: * At step 4, if the .input and .trav files are not readable or are not in the current directory, the program will print out an error message. The subgraph algorithm will, in turn, not run. Use Case: Sending Output File with List of UIDs back to GUI team Actors: Algorithms team, GUI team Description: The algorithms team will print to a file all the UIDs that are contained in the subgraph; (Previously, in phase II, the algorithms team will print to a file all the vertices and edges that are found in the subgraph of the traversal. This file will be in a class dictionary form that is accepted by evolve.cd(created by Binoy Samuel)). Basic Course of Events: 1. Using a printing visitor, the algorithm traverses to all vertex and edge objects. 2. At a UConstVertex, UAltVertex, UConstEdge, or UAltEdge object, the algorithm checks to see if it is marked twice(marked during both the forward and backward depth-first search; in other words, the vertex or edge is in the subgraph). In turn, it will print its associated UID to an output file. o Expanded Use Case: Use Case: Calculating the Subgraph of the Traversal Actors: Program Description: The algorithm will first store all the UVertex and UEdge objects in a hashtable using its corresponding UID as a key. It will then do a forward depth-first search from the source vertex and then a backward depth-first search from all the target vertices. Then, a printing visitor is called to traverse through the UGraph object and prints out all the UIDs that are contained in the subgraph. Basic Course of Events: 1. A hashtable is created to store all the UVertex and UEdge objects found in the UGraph object, using their corresponding UID as the key. 2. Taking the UID of the source vertex of the traversal, it gets the corresponding UVertex object from the hashtable(starting the forward depth-first search). 3. It marks the vertex as visited in the forward direction. 4. It calls a traversal to the list of UIDs in the outgoing edge list to continue the forward depth-first search 5. Take each UID object in the outgoing edge list and get its corresponding UEdge object from the hashtable. 6. It marks the edge as visited in the forward direction. 7. Repeat the process by going back to step #2 using the UID object of to-Vertex. This cycle continues until all subpaths from the source vertex of the traversal have been visited. 8. When the forward depth-first traversal finishes, the backward depth-first traversal starts for each target vertex specified in the traversal. 9. It marks the vertex as visited in the backward direction. 10. It calls a traversal to the list of UIDs in the incoming edge list to continue the backward depth-first search. 11. Take each UID object in the incoming edge list and get its corresponding UEdge object from the hashtable. 12. It marks the edge as visited in the backward direction. 13. Repeat the process by going back to step #8 using the UID object stored in the edge's fromVertex part. This cycle continues until all subpaths from the target vertex of the traversal have been visited. 14. A printing visitor is called and traverses to all the appropriate objects and prints the UIDs that are contained in the subgraph to an output file. Alternative Course of Events: * At step 2, if the source vertex is a terminal class or none of the targets are valid(all targets are terminal classes), an error is printed saying that it was an invalid traversal specification and an empty output file is produced. * At step 3, if the vertex has been visited, it will not traverse any deeper because its subpaths have already been visited in the forward direction. If the vertex is in the bypass list, it will not mark the vertex and will not traverse any deeper in the forward direction. * At step 3, after the vertex is marked and if the current vertex is a target in the traversal specification AND that it is a to-stop traversal, it will not traverse any further since no outgoing edges from a to-stop target should be marked. * At step 6, if the edge is in the bypass list, it will not mark the edge and will not traverse any deeper in the forward direction. * At step 9, if the vertex has been visited, it will not traverse any deeper because its subpaths have already been visited in the backwards direction. If the vertex is in the bypass list, it will not mark the vertex and will not traverse any deeper in the backward direction. * At step 12, if the edge is in the bypass list, it will not mark the edge and will not traverse any deeper in the backward direction. * At step 14, it will print out an empty output file if either the source is a terminal class, all targets are terminal classes, or there is no subgraph from the source to all of the targets.