Overview

• This lab requires that you install or set up some infrastructure for using the course software. Follow the "setup" portion of this lab right by class on Thursday.
  If there is a problem, we can resolve it quickly and get you underway

Setup

1. Some have had difficulties with eclipse's latest (Europa) version. You might try an archived version, such as 3.2.x.
2. Rob's description of the patterns used in this software can be found here
3. Documentation for the software can be found here.
4. Download this hw1.jar file, which needs to stay around for the duration of this assignment.

   Make sure the jar files are saved as .jar files! Internet Explorer tried to save them as zip files in CEC

5. Download this hw1.zip file and put it in a temporary but handy spot (like your Desktop).
6. Installation instructions:
   • Eclipse:
     1. File → New → Project … and choose Java Project. Give it a meaningful name, say CSE531hw1.
     2. From eclipse, click File → Import … and choose Archive File. Browse to find the hw1.zip file and import it into the CSE531hw1 project you created by clicking Finish
     3. In the Package Explorer, open the CSE531hw1 project.

        Eclipse, in its eagerness, has probably already tried to compile your project, but there are some things it won't find yet.

        Silly eclipse.

        So don't worry about problems just yet.
     4. In some of the files for this lab, there are references to classes that are in the jar file you downloaded. We must make eclipse aware of this:
        1. Click on the CSE531hw1 in the Package Explorer
        2. Click File→Properties
        3. Click Java Build Path
        4. Select the Libraries tab
        5. Click Add External JARs…
        6. Add the hw1.jar file to the list by browsing for the location at which you stored the file.
     5. At this point, or shortly thereafter, all the red flags should go away, as eclipse recompiles the code with the jar file now present.
     6. Open the demos/HydraDom.java file from the Package Explorer.
     7. There seems to be some problem with running in the Europa version of eclipse. Try each of the following, and one should work.
        • Right-click the HydraDom.java entry in the Package Explorer, and go down to Run as → Java Application and let it go. You should see output in the Console window.
        • Right-click the Project name, go down to Run as → Run… and make sure the main program is demos.HydraDom. Click Run.
   • Linux:
     1. Unzip the hw1.zip file
     2. Set the CLASSPATH environment variable to include the hw1.jar file and the classes directory (you may not see it yet, but it will be created by ant; it's OK to set the environment variable now to include it).
     3. Run ant to compile the software.
     4. To run the application: java demos.HydraDom
   • Older versions of Java: Follow the instructions for Linux, above, and grab the same hw1.zip file, but using the following jar file:
     • hw1.jar
7. What you should see in the output:
   • For each of two examples, the application builds the DFST, runs my solution to the dominators problem, and then runs yours. Yours doesn't do anything yet, so the idom fields are null in the last graph listing.
   • The first example provided is the one from class, so you should be able to debug with it. The second example is a 3-node example where node 1 should dominate nodes 2 and 3. You are asked to make that example more interesting before turning in your solution.

   ---

   Assignment

   You are free to work on this project in teams, so that you can help each other understand the code and the problem at hand. However, you must create and turn in your own solution as your own work. You are not allowed to copy code!
   • You are to implement the Tarjan-Lengauer Dominators algorithm in the PCESGraph/CSE531DomTree.java file, and that is the only file you will submit. You are to complete the computeIdom method, but you will probably want to write some private helper methods.
   • You are to fill in the PCESGraph.CSE531DomTree.genMyGraph method with a more interesting and unique graph -- at least 10 nodes, at least 15 edges, and verify that your solution works on that graph as well.
   Turn in your solution by email to Rob LeGrand.

   Notes:

   • Given a Vertex v, you can get the DirectedVertex corresponding to v by:

       DirectedVertex dirV = DirectedGraph.getDirectedVertex(v);
     

   • Given a Vertex v, you can get its DomVertex by
     • The private method DomTree.getLocalDom(v)
     • Do not use the static method getDomVertex -- it does not seem to work and I'm looking into that.
     and you can put the DomVertex's fields to good use in your algorithm, as there are fields there to hold the semidominator, etc.