programming project involves designing, writing and testing a program that behaves like the Java command line compiler. Whenever we request that the Java compiler recompile a particular class, it not only recompiles that class but every other class that depends upon it, directly or indirectly, and in a particular order. To make the determination about which classes need recompilation, the Java compiler maintains a directed graph of class dependencies. Any relationship in a UML class diagram of a Java program such as inheritance relationships, composition relationships and aggregations relationships indicate a class dependency. The main class P4GUI should create the Swing based GUI shown below:

The GUI must be generated by code that you write. You may not use a drag-and-drop GUI generator. Pressing the Build Directed Graph button should cause the specified input file that contains the class dependency information to be read in and the directed graph represented by those dependencies to be built. The input file should be generated by the students using a simple text editor such as Notepad. The input file associated with the above example is shown below:

ClassA ClassC ClassE

ClassB ClassD ClassG

ClassE ClassB ClassF ClassH

ClassI ClassC

Each line of this file specifies classes that have other classes that depend upon them. The first line, for example, indicates that ClassA has two classes that depend upon it, ClassC and ClassE. In the context of recompilation, it means that when ClassA is recompiled, ClassC and ClassE must be recompiled as well. Using graph terminology, the first name on each line is the name of a vertex and the remaining are its associated adjacency list of dependent classes. Classes that have no dependent classes need not appear at the beginning of a separate line. Notice, for example, that ClassC is not the first name on any line of the file. After pressing the Build Directed Graph button, one of following two messages should be generated depending upon whether the specified file name could be opened:

Once the graph has been built, the name of a class to be recompiled can be specified and the Topological Order button can be pressed. Provided a valid class name has been supplied, a topological order algorithm should be executed that will generate (in the text area at the bottom of the GUI window) the list of classes in the order they are to be recompiled. The correct recompilation order is any topological order of the subgraph that emanates from the specified vertex. An invalid class name should generate an exception and an appropriate error message will be displayed in a JOptionPane. If the graph contains a cycle among the Java classes, an exception will be thrown and a message will be displayed in a JOptionPane indicating that a cycle has been detected. Note. In the real compiling processes, when circular dependencies exist in Java programs, the compiler must make two passes over all the classes in the cycle. For this program, it will be sufficient to display a message indicating that a cycle has been detected. In addition to the main class that defines the GUI, a second class is needed to define the directed graph. It should be a generic class allowing for a generic type of its vertices. In this application the type of the vertices will be String. For better processing purposes, integer values will be used to represent the vertices instead of Strings. The graph should be represented as an array list of vertices (as integer values) that contain a linked list of their associated adjacency lists. The adjacency lists should be lists of integers that represent the index rather than vertex name itself. A hash map should be used to associate vertex names with their index in the list of vertices. For the input file shown above the array list of linked lists of integers would be the following:

0 [1, 2]

1 [] 2 [3, 6, 7]

3 [4, 5]

4 []

5 []

6 []

7 []

8 [1]

Storing the vertex indices rather than the names simplifies the topological order algorithm. The hash map would associate index 0 with ClassA, index 1 with ClassC, index 2 with ClassE and so on. The directed graph class should define methods for initializing the graph each time a new file is read in, for adding a vertex to the graph, for adding an edge to the graph and for generating a topological order given a starting index. Other classes / methods could be also defined to achieve the program requirements and/or to better structuring the code. Finally, custom checked exception classes should be defined for the cases where a cycle occurs and when an invalid class name is specified. Your program should compile without errors.

Show transcribed image textView comments (1)

Expert Answer

Waseem answered this

Was this answer helpful?

0

0

117 answers

P4GUI.java

import javax.swing.*; import javax.swing.border.*; import java.awt.*; import java.awt.event.*; import java.io.*; import java.util.*;

/** * Purpose: Creates a GUI for testing the CompilerGraph and related classes. */ public class P4GUI extends JFrame { private static final int TEXT_FIELD_WIDTH = 7; CompilerGraph graph; boolean initialized = false; public P4GUI() { super("Class Dependency Graph"); setLocationRelativeTo(null); setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); setLayout(new BorderLayout(5, 10)); //Initialize JPanels JPanel inputFrame = new JPanel(new BorderLayout(25,0)); inputFrame.setBorder(new EmptyBorder(10, 20, 0, 20)); JPanel outputFrame = new JPanel(new BorderLayout()); JPanel inputLabels = new JPanel(new BorderLayout()); JPanel inputFields = new JPanel(new BorderLayout()); JPanel inputButtons = new JPanel(new BorderLayout(10,5)); //Initialize components //Labels JLabel fileLabel = new JLabel("Input file name: "); JLabel classLabel = new JLabel("Class to recompile: "); //Fields final JTextField fileField = new JTextField(TEXT_FIELD_WIDTH); final JTextField classField = new JTextField(TEXT_FIELD_WIDTH); //Buttons JButton buildButton = new JButton("Build Directed Graph"); JButton topoButton = new JButton("Topological Order"); //Output area JLabel recompileLabel = new JLabel("Recompilation Order: "); final JTextArea outputArea = new JTextArea(11, 50); JScrollPane scrollPane = new JScrollPane(outputArea); outputArea.setEditable(false); //Listeners buildButton.addActionListener(new ActionListener() { public void actionPerformed(ActionEvent event) { Scanner fileIn = null; String fileName = fileField.getText();

try { fileIn = new Scanner(new BufferedReader( new FileReader(fileName))); graph = new CompilerGraph(); graph.initializeGraph(fileIn); initialized = true; JOptionPane.showMessageDialog(null, "Graph built succesfully!", "Success", JOptionPane.INFORMATION_MESSAGE); } catch (IOException e) { JOptionPane.showMessageDialog(null, "\"" + fileName + "\"" + " is not a valid input. Please enter a valid filename.", "Invalid Input", JOptionPane.ERROR_MESSAGE); } catch (CycleDetectedException e) { JOptionPane.showMessageDialog(null, "A cycle has been" + "detected. Please try a different input.", "Cycle Detected", JOptionPane.ERROR_MESSAGE); }

finally { if (fileIn != null) { fileIn.close(); } } } }); topoButton.addActionListener(new ActionListener() { public void actionPerformed(ActionEvent event) { if (!initialized) { JOptionPane.showMessageDialog(null, "No graph has been " + "initialized. Please initialize a graph.", "Invalid Graph", JOptionPane.ERROR_MESSAGE); } else { try { outputArea.setText(graph.topologicalOrder( classField.getText())); } catch(InvalidClassNameException exc) { JOptionPane.showMessageDialog(null, exc.getClassName() + " is not a valid class name. Please enter a valid" + " class name.", "Invalid Class Name", JOptionPane.ERROR_MESSAGE); } } } }); //Add components to panels inputLabels.add(fileLabel, BorderLayout.NORTH); inputLabels.add(classLabel, BorderLayout.SOUTH); inputFields.add(fileField, BorderLayout.NORTH); inputFields.add(classField, BorderLayout.SOUTH); inputButtons.add(buildButton, BorderLayout.NORTH); inputButtons.add(topoButton, BorderLayout.SOUTH); inputFrame.add(inputLabels, BorderLayout.WEST); inputFrame.add(inputFields, BorderLayout.CENTER); inputFrame.add(inputButtons, BorderLayout.EAST); outputFrame.add(recompileLabel, BorderLayout.NORTH); outputFrame.add(outputArea, BorderLayout.SOUTH); add(inputFrame, BorderLayout.NORTH); add(outputFrame, BorderLayout.SOUTH); }

public static void main(String[] args) { P4GUI gui = new P4GUI(); gui.pack(); gui.setVisible(true); } }

CompilerGraph.java

import java.util.ArrayList; import java.util.HashMap; import java.util.LinkedList; import java.util.Map.Entry; import java.util.Scanner; import java.util.Stack;

/** * Purpose: Implements the fields and methods necessary to build a directed * * * graph of vertices. */ public class CompilerGraph { private HashMap vertices; private ArrayList> adjacencies; private int curIdx = 0; private HashMap vertexMap = new HashMap(); private ArrayList headList; private Stack vertStack = new Stack(); public CompilerGraph() { vertices = new HashMap(); vertexMap = new HashMap(); adjacencies = new ArrayList(); headList = new ArrayList(); } // Initializes the graph and builds the agacency list. public void initializeGraph(Scanner input) { Scanner curLine; String curName; Vertex curVertex; while (input.hasNextLine()) { curLine = new Scanner(input.nextLine()); curName = curLine.next(); headList.add(curName); if (vertexMap.containsKey(curName)) { curVertex = vertexMap.get(curName); if (curVertex.isDiscovered()) { throw new CycleDetectedException(curVertex.getValue()); } else { curVertex.setDiscovered(); } } else { vertexMap.put(curName, new Vertex(curName)); } while(curLine.hasNext()) { String newName = curLine.next(); if (vertexMap.containsKey(newName)) { Vertex newVertex = vertexMap.get(newName); vertexMap.get(curName).addChild(newVertex); if (newVertex.isDiscovered()) { throw new CycleDetectedException(newVertex.getValue()); } else { newVertex.setDiscovered(); } } else { vertexMap.put(newName, new Vertex(newName)); vertexMap.get(curName).addChild(vertexMap.get(newName)); } } } int vertIdx = 0; String newName = ""; for (String head : headList) { curVertex = vertexMap.get(head); buildAdjacencyList(curVertex); } } // Takes a single vertex and adds to the adjacency list that // vertex and all of its children, utilizing the addEdge() method public void buildAdjacencyList(Vertex vertex) { String curName = ""; int vertIdx = 0; String newName = ""; curName = vertex.getValue(); if (vertices.containsValue(curName)) { vertIdx = getKey(curName); } else { vertIdx = curIdx; vertices.put(curIdx, curName); curIdx++; adjacencies.add(new LinkedList()); } if (vertex.hasChildren()){ for (Vertex child : vertex.getChildren()) { addEdge(vertex, child); buildAdjacencyList(child); } } } // Adds an edge to the corresponding adjacency list public void addEdge(Vertex source, Vertex destination) { int sourceIdx = getKey(source.getValue()); int destIdx; if (vertices.containsValue(destination.getValue())) { destIdx = getKey(destination.getValue()); } else { destIdx = curIdx; curIdx++; vertices.put(destIdx, destination.getValue()); adjacencies.add(new LinkedList()); } adjacencies.get(sourceIdx).add(destIdx); } // Helper method to simplify getting the corresponding key for a given value // in the vertices HashMap public Integer getKey(String value) { for(Entry entry : vertices.entrySet()) { if (entry.getValue().equals(value)) { return entry.getKey(); } } return -1; } // Returns as a String the topological order emmanating from the given class // name. Throws an Exception if the class name does not exist in the graph. // Initializes the depthFirstSearch() method. public String topologicalOrder(String vertName) { // Resets the discovered and finished flags for each vertex for (Entry entry : vertexMap.entrySet()) { entry.getValue().reset(); } String result = ""; if (vertices.containsValue(vertName)){ depthFirstSearch(vertexMap.get(vertName));

while (!vertStack.isEmpty()) { result += vertStack.pop().getValue() + " "; }

return result; } else { throw new InvalidClassNameException(vertName); } } // Utilizes a depth first search algorithm to generate the topological order // from a given vertex. public void depthFirstSearch(Vertex vertex) { if (vertex.isDiscovered()) { throw new CycleDetectedException(vertex.getValue()); } if (vertex.isFinished()) { return; } vertex.setDiscovered(); if (vertex.hasChildren()) { for (Vertex child : vertex.getChildren()) { depthFirstSearch(child); } } vertex.setFinished(); vertStack.push(vertex); }

}

CycleDetectedException.java

public class CycleDetectedException extends RuntimeException { private String cycleVert = "";

/** * Creates a new instance of CycleDetectedException without * detail message. */ public CycleDetectedException() { }

/** * Constructs an instance of CycleDetectedException with the * specified detail message. * * @param msg the detail message. */ public CycleDetectedException(String vertName) { cycleVert = vertName; } public String getCycleVertex() { return cycleVert; } }

InvalidClassNameException .java

/* * Purpose: Implements an Exception for when the user inputs the name of a class * * * not found in the graph. The illegalCLass field allows the GUI to pull the * * * offending class name. */ public class InvalidClassNameException extends RuntimeException { private String illegalClass = "";

/** * Creates a new instance of CycleDetectedException without * detail message. */ public InvalidClassNameException() { }

/** * Constructs an instance of CycleDetectedException with the * specified detail message. * * @param msg the detail message. */ public InvalidClassNameException(String className) { illegalClass = className; } public String getClassName() { return illegalClass; } }

Vertex.java

import java.util.*; /** * Purpose: Implements the methods and fields necessary to create a class for * * * a vertex in a directed graph/ */ public class Vertex { private ArrayList> children; private T value; private boolean discovered = false; private boolean finished = false; public Vertex(T value) { this.value = value; children = new ArrayList(); } public Vertex(T value, ArrayList> children) { this.value = value; this.children = children; } public void addChild(Vertex child) { children.add(child); } public ArrayList> getChildren() { return children; } public T getValue() { return value; } public boolean hasChildren() { return (children.size() > 0); } public boolean isDiscovered() { return discovered; } public boolean isFinished() { return finished; } public void setDiscovered() { discovered = true; } public void setFinished() { finished = true; } // Resets the discovered and finished flags public void reset() { discovered = false; finished = false; }

}

Class Dependency Graph Input file name:graph.tt Build Directed Graph Class to recompile: ClassA Topological Order Recompilation Order ClassA ClassE ClassH ClassF ClassB ClassG ClassD ClassC Class Dependency Graph Input file name:graph.tt Build Directed Graph Class to recompile: ClassA Topological Order Recompilation Order ClassA ClassE ClassH ClassF ClassB ClassG ClassD ClassC