PHASE III: Team members of the visual-traverse group(algorithms group): Edward Wong (edwong@ccs.neu.edu) Patrick Tibbetts (tibbs@ccs.neu.edu) Jackson Fong (jackson@ccs.neu.edu) ---------------------------------------------------------------------------- Your host: Kedar Patankar We also talked to Doug Orleans and Binoy Samuel. ---------------------------------------------------------------------------- Account Name: edwong@ccs.neu.edu ---------------------------------------------------------------------------- URL of our project home page is at : http://www.ccs.neu.edu/home/tibbs/com1205.html ---------------------------------------------------------------------------- Project: Our project is to implement the algorithm to calculate the subgraph of the traversal specification and print out the list of UIDs that are in the subgraph so that the GUI team of the visual-traverse group could highlight those elements with the corresponding UIDs. In our third phase of our project, we took a subset of evolve.cd(excluding the Decorator class since we don't use it in our code) to use as our underlying class dictionary, implementing construction, alternation, and terminal classes as well as construction and alternation edges. We also implemented multiple targets and a choice of to or to-stop in the the traversal specification. We read in the prefix for both the .input and .trav files(.input is the class dictionary as the input and .trav is the traversal specfication file). We now print to the .output file just a list of UIDs that are in the subgraph. Previously in Phase II, we print out the subgraph in class dictionary form, but Dave Mann(our GUI counterpart) wanted just a list of UIDs instead. The project requirements for our group are: o Printing out the list of UIDs that are in the subgraph o Testing and correcting any bugs in the existing subgraph algorithm o Documenting all of the code in a local copy of demjava.beh that deals with the subgraph algorithm created by Doug Orleans o Improving the speed of the existing subgraph algorithm(through a hashtable) o Try to add the "through" property in the existing subgraph algorithm if time permits ---------------------------------------------------------------------------- Directory: This is a directory in: /proj/demsys/com1205/w97/edwong/project/phase3 This file is called README-project ---------------------------------------------------------------------------- Credits: Some of the ideas used in our project came from the algorithm for calculating the subgraph of the traversal in demjava.beh, created by Doug Orleans. Doug also helped to explain many of the subtleties of the subgraph algorithm and some of the issues we need to deal with. Binoy Samuel also gave us the underlying class dictionary file to use, evolve.cd, and some pointers in creating hashtables and dealing with multiple targets. Kedar Patankar also gave us pointers on how to start our project and in developing our algorithm. Files that we reused some of the ideas came from: o demjava.beh - in directory /proj/demsys/demjava/cur/src (especially the subgraph algorithm part in the behavior file starting from the boolean markSubgraph...; also the part where the program reads in multiple input files and writing to an output file in the beginning of the .beh file) ---------------------------------------------------------------------------- The command to run our program is: o java Main [prefix] // where prefix is the beginning part of the // filename(what comes before the extension); for // example if the input files are prog.input and // prog.trav, the user should type "java Main prog" How to run the application: 1. Execute the command: make clean 2. Execute the command: make test (the compilation will occur and automatically runs the command "java Main program") 3. The algorithm will write the output to the output file, [prefix].output in this case, prefix is "program" 4. Execute the command: more [prefix].output to view the list of UIDs that are in the subgraph To run the program using other inputs, execute the command: "java Main [prefix]" where prefix could be any prefix preceding the .input and .trav files. The [prefix].output is the output file generated that stores the list of UIDs in the subgraph. We did not use the new version of Demeter/Java, because it was a bit flaky and unstable, so we reverted back to the 0.4.2 version. ----------------------------------------------------------------------------- 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. ----------------------------------------------------------------------------- Class Dictionary and behavior file which we used: o program.cd - a subset of the class dictionary, evolve.cd; this class dictionary now accepts construction, alternation and terminal classes as well as construction and alternation edges o program.beh - the behavior file that implements the algorithm that calculates the subgraph of the traversal and prints the list of UIDs that are in the subgraph to an output file In phase III, the .output file has a list of UIDs that are in the subgraph rather than the subgraph in class dictionary form. ----------------------------------------------------------------------------- Growth phases which we used: Phase I: o Establish a general USE CASE o Document the code for Doug Orlean's existing subgraph algorithm in demjava.beh (a local copy in our phase1 directory) o Implement a basic version of the subgraph algorithm based on evolve.cd(created by Binoy Samuel). This basic algorithm deals with only simple FROM ... TO traversals and consturction classes and edges o Use a printing visitor to print the subgraph in a class dictionary form o Make our algorithm efficient by using a hashtable o Continue updating our project web page Phase II: o Change main program to read in two input files([prefix].input and [prefix].trav) and write to an output file([prefix].output) o Add alternation classes and edges into our class dictionary and modify our behavior file o Modify the algorithm to accept a list of BYPASSING elements o Add the Coordinates class to the class dictionary and modified the .input files to have coordinates o Collaborate with GUI group of the visual-traverse team to decide how to transfer the input and output class dictionaries o Continue updating our project web page Phase III: o Modify algorithm to accept multiple targets(Professor Lieberherr and Johan mentioned that multiple sources was not necessary to implement so we took that off our list) o Implement the "to-stop" property in our algorithm and modified the IndependentTraversal object to choose between To and To-Stop traversals o Add terminal classes in the class dictionary and check if the source, list of targets and list of bypassing elements have terminal classes o Add the Cardinality class and its related classes in the class dictionary and modify the PrintingVisitor to print it out o Continue collaborating with the GUI group in deciding how to transfer the input and output files o Fix any existing bugs in our subgraph algorithm o Eliminated parts of our PrintingVisitor so that it now only prints a list of UIDs in the subpath o Try to implement the "through" property in our algorithm, if time permits o Continue updating our project web page In Phase III, we had six stages: o Stage 1: works1.beh and works1.cd o At this stage, we added the Cardinality, Lower, and Upper classes to our class dictionary. We also modified the PrintingVisitor so that it could print out the necessary syntax for cardinality for construction edges. o Stage 2: works2.beh and works2.cd o At this stage, we added the UTerm class to our class dictionary. We also check to see if the single source or single target is a terminal vertex. If it is, we print out an error saying that it is an invalid traversal specification. Otherwise, it will calculate the subgraph of the specified traversal. o Stage 3: works3.beh and works3.cd o At this stage, we split up the IndependentTraversal object into three classes: From, Target, and Bypass. Target is then split up into To and ToStop. We implemented the "to-stop" property in our algorithm. If the traversal has a to-stop clause, the algorithm will not traverse further if it reaches a to-stop target (in other words, it will not mark the outgoing edges of a to-stop target). o Stage 4: works4.beh and works4.cd o At this stage, we implemented multiple targets(a list of UIDs). We have to do a backward depth-first search for every one of the target vertices in the specified traversal. We also check to see if a target is a terminal vertex before storing it into a vector. The vector will store only the valid UIDs(only targets that are not terminal classes). NOTE: This stage is before we changed our code to reflect the collaboration with the code of the GUI team of the visual- traverse group(Dave Mann). o Stage 5: works5.beh and works5.cd o At this stage, we deleted major parts of our PrintingVisitor and completely eliminated the PrintingListVisitor, because we now only need to print out a list of UIDs that are contained in the subgraph (the GUI team of the visual-traverse group preferred it that way). o Stage 6: works6.beh and works6.cd o At this stage, we check to see if any of the bypassing elements are terminal classes. If a bypassing element is a terminal class, it is not stored in the vector. The vector will only store valid bypassing UIDs(none of them could be a terminal class). If a bypassing element is a terminal class, it will print out an error. o Stage 7: program.beh and program.cd o At this stage, we cleaned up our code and added documentation to our .cd and .beh files. We also removed all of our debugging statements(excluding error messages). NOTE: works0.beh and works0.cd are the program.beh and program.cd from phase II(before making any changes in Phase III) ----------------------------------------------------------------------------- Parts of our project that we could have developed further if we had more time: We could have modified our algorithm to handle multiple sources(although it wasn't required by Professor Lieberherr, Johan, or Kedar). We could also have implemented the "through" property if we had the time. We could have also checked our code to see if we could make it even more efficient than as of now. If we had the time, we could have made the collaboration of our code with the code from the GUI team of the visual- traverse group much more smoother(instead of reading input files and passing back output files to each other). However, we do point out that our code does work on an individual basis. If we also had time, we could have fixed any other bugs that Doug might know of. List of known bugs: o Does not accept an IndependentTraversal object with multiple sources o Does not accept a list of UIDs to be in a "through" list o Only accepts a flattened class dictionary as an input ----------------------------------------------------------------------------- Files where test inputs are found: .input - file that holds the class dictionary of the class graph drawn in CD-Draw .trav - file that holds the traversal specification(parsed to an IndependentTraversal object) o program.input & program.trav - input files read in when executing "make" o pA.input & pA.trav - input files (#1) o pB.input & pB.trav - input files (#2) o pC.input & pC.trav - input files (#3) o pD.input & pD.trav - input files (#4) //invalid traversal specification o pE.input & pE.trav - input files (#5) //invalid traversal specification o pF.input & pF.trav - input files (#6) o pG.input & pG.trav - input files (#7) o pH.input & pH.trav - input files (#8) o pI.input & pI.trav - input files (#9) //invalid traversal specification o pK.input & pK.trav - input files (#10) o pL.input & pL.trav - input files (#11) o pM.input & pM.trav - input files (#12) o pN.input & pN.trav - input files (#13) o pO.input & pO.trav - input files (#14) o pP.input & pP.trav - input files (#15) o pQ.input & pQ.trav - input files (#16) o pR.input & pR.trav - input files (#17) ----------------------------------------------------------------------------- Files where test outputs are found: .output - file that stores the list of UIDs that are contained in the subgraph o program.output - output file from program.output and program.trav o pA.output - output file from input files #1 o pB.output - output file from input files #2 o pC.output - output file from input files #3 o pD.output - output file from input files #4 //empty output file o pE.output - output file from input files #5 //empty output file o pF.output - output file from input files #6 o pG.output - output file from input files #7 o pH.output - output file from input files #8 o pI.output - output file from input files #9 //empty output file o pK.output - output file from input files #10 o pL.output - output file from input files #11 o pM.output - output file from input files #12 o pN.output - output file from input files #13 o pO.output - output file from input files #14 o pP.output - output file from input files #15 o pQ.output - output file from input files #16 o pR.output - output file from input files #17 NOTE: pD.output, pE.output, and pF.output are empty output files because the traversal specification is invalid(either source or all targets are terminal classes). ----------------------------------------------------------------------------- An interesting input/output pair is: pG.input: #Class #Dictionary #Graph #Vertex #List #ConstVertex 1 A { 62 409 } #Incoming #Outgoing 3 7 11 #ConstVertex 2 B { 384 50 } #Incoming 3 5 #Outgoing 13 #ConstVertex 4 C { 172 426 } #Incoming 7 9 #Outgoing 17 #ConstVertex 6 D { 86 119 } #Incoming 11 #Outgoing 23 #ConstVertex 8 E { 62 49 } #Incoming 13 #Outgoing 15 #ConstVertex 14 F { 38 56 } #Incoming 15 #Outgoing 5 #ConstVertex 10 G { 12 426 } #Incoming 17 19 #Outgoing 21 #ConstVertex 16 H { 86 19 } #Incoming 21 #Outgoing 19 #ConstVertex 12 I { 62 499 } #Incoming 23 #Outgoing 9 25 #ConstVertex 18 J { 384 156 } #Incoming 25 #Outgoing #Edge #List #ConstEdge b1 1 3 1 2 #ConstEdge b2 1 5 14 2 #ConstEdge c1 1 7 1 4 #ConstEdge c2 1 9 12 4 #ConstEdge d 1 11 1 6 #ConstEdge e 1 13 2 8 #ConstEdge f 1 15 8 14 #ConstEdge g1 1 17 4 10 #ConstEdge g2 1 19 16 10 #ConstEdge h 1 21 10 16 #ConstEdge i 1 23 6 12 #ConstEdge j 1 25 12 18 pG.trav: from 1 to-stop 8 10 bypassing 7 pG.output: 1 2 4 6 8 10 12 3 9 11 13 17 23 //the list of UIDs that are contained in the // subgraph NOTE: An empty outfile will be produced if the source is a terminal class, all targets specified in the traversal are terminal classes, or there is no subpath from the source to all targets(In the latter case, no error is produced since no terminal classes were detected). ----------------------------------------------------------------------------- We did not change the generated Java code wich "make" generates from the \ program.cd and program.beh files that we wrote. It was not necessary, because we make all changes to the .cd and .beh files. **NOTE** We did change the generated Makefile which j-gen-make produced. Although we used the default name, program, for our .cd and .beh files, we changed the command for our execution of the program. The 2 lines we changed were: o TEST_ARGS = $(PROG) o TEST_DEPS = $(PROG).input $(PROG).trav This lets the user to run the command, "java Main [prefix]", so the user does not have to type in the names of both input files. Rather, the user could type in the prefix of the two input files(as explained above). The original makefile for phase I is the file: GNUmakefile.old